1//===- Local.cpp - Functions to perform local transformations -------------===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// This family of functions perform various local transformations to the 12//===----------------------------------------------------------------------===// 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
106cl::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."));
116"max-phi-entries-increase-after-removing-empty-block",
cl::init(1000),
118cl::desc(
"Stop removing an empty block if removing it will introduce more " 119"than this number of phi entries in its successor"));
121// Max recursion depth for collectBitParts used when detecting bswap and 125//===----------------------------------------------------------------------===// 126// Local constant propagation. 129/// ConstantFoldTerminator - If a terminator instruction is predicated on a 130/// constant value, convert it into an unconditional branch to the constant 131/// destination. This is a nontrivial operation because the successors of this 132/// basic block must have their PHI nodes updated. 133/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch 134/// conditions and indirectbr addresses this might make dead if 135/// DeleteDeadConditions is true. 142// Branch - See if we are conditional jumping on constant 143if (
auto *BI = dyn_cast<BranchInst>(
T)) {
144if (BI->isUnconditional())
returnfalse;
// Can't optimize uncond branch 149if (Dest2 == Dest1) {
// Conditional branch to same location? 150// This branch matches something like this: 151// br bool %cond, label %Dest, label %Dest 152// and changes it into: br label %Dest 154// Let the basic block know that we are letting go of one copy of it. 155assert(BI->getParent() &&
"Terminator not inserted in block!");
158// Replace the conditional branch with an unconditional one. 161// Transfer the metadata to the new branch instruction. 162 NewBI->
copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
163 LLVMContext::MD_annotation});
166 BI->eraseFromParent();
167if (DeleteDeadConditions)
172if (
auto *
Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
173// Are we branching on constant? 174// YES. Change to unconditional branch... 178// Let the basic block know that we are letting go of it. Based on this, 179// it will adjust it's PHI nodes. 182// Replace the conditional branch with an unconditional one. 185// Transfer the metadata to the new branch instruction. 186 NewBI->
copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
187 LLVMContext::MD_annotation});
189 BI->eraseFromParent();
191 DTU->
applyUpdates({{DominatorTree::Delete, BB, OldDest}});
198if (
auto *SI = dyn_cast<SwitchInst>(
T)) {
199// If we are switching on a constant, we can convert the switch to an 200// unconditional branch. 201auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
202BasicBlock *DefaultDest = SI->getDefaultDest();
205// If the default is unreachable, ignore it when searching for TheOnlyDest. 207 SI->getNumCases() > 0) {
208 TheOnlyDest = SI->case_begin()->getCaseSuccessor();
213// Figure out which case it goes to. 214for (
auto It = SI->case_begin(),
End = SI->case_end(); It !=
End;) {
215// Found case matching a constant operand? 216if (It->getCaseValue() == CI) {
217 TheOnlyDest = It->getCaseSuccessor();
221// Check to see if this branch is going to the same place as the default 222// dest. If so, eliminate it as an explicit compare. 223if (It->getCaseSuccessor() == DefaultDest) {
225unsigned NCases = SI->getNumCases();
226// Fold the case metadata into the default if there will be any branches 227// left, unless the metadata doesn't match the switch. 228if (NCases > 1 && MD) {
229// Collect branch weights into a vector. 233// Merge weight of this case to the default weight. 234unsignedIdx = It->getCaseIndex();
235// TODO: Add overflow check. 236 Weights[0] += Weights[
Idx + 1];
237// Remove weight for this case. 245 It = SI->removeCase(It);
248// Removing this case may have made the condition constant. In that 249// case, update CI and restart iteration through the cases. 250if (
auto *NewCI = dyn_cast<ConstantInt>(SI->getCondition())) {
252 It = SI->case_begin();
259// Otherwise, check to see if the switch only branches to one destination. 260// We do this by reseting "TheOnlyDest" to null when we find two non-equal 262if (It->getCaseSuccessor() != TheOnlyDest)
263 TheOnlyDest =
nullptr;
265// Increment this iterator as we haven't removed the case. 269if (CI && !TheOnlyDest) {
270// Branching on a constant, but not any of the cases, go to the default 272 TheOnlyDest = SI->getDefaultDest();
275// If we found a single destination that we can fold the switch into, do so 278// Insert the new branch. 284// Remove entries from PHI nodes which we no longer branch to... 287if (DTU && Succ != TheOnlyDest)
288 RemovedSuccessors.
insert(Succ);
289// Found case matching a constant operand? 290if (Succ == SuccToKeep) {
291 SuccToKeep =
nullptr;
// Don't modify the first branch to TheOnlyDest 297// Delete the old switch. 299 SI->eraseFromParent();
300if (DeleteDeadConditions)
303 std::vector<DominatorTree::UpdateType> Updates;
304 Updates.reserve(RemovedSuccessors.
size());
305for (
auto *RemovedSuccessor : RemovedSuccessors)
306 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
312if (SI->getNumCases() == 1) {
313// Otherwise, we can fold this switch into a conditional branch 314// instruction if it has only one non-default destination. 315auto FirstCase = *SI->case_begin();
317 FirstCase.getCaseValue(),
"cond");
319// Insert the new branch. 321 FirstCase.getCaseSuccessor(),
322 SI->getDefaultDest());
327// The TrueWeight should be the weight for the single case of SI. 333// Update make.implicit metadata to the newly-created conditional branch. 334MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
336 NewBr->
setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
338// Delete the old switch. 339 SI->eraseFromParent();
345if (
auto *IBI = dyn_cast<IndirectBrInst>(
T)) {
346// indirectbr blockaddress(@F, @BB) -> br label @BB 348 dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
352// Insert the new branch. 356for (
unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
358if (DTU && DestBB != TheOnlyDest)
359 RemovedSuccessors.
insert(DestBB);
360if (IBI->getDestination(i) == SuccToKeep) {
367 IBI->eraseFromParent();
368if (DeleteDeadConditions)
369// Delete pointer cast instructions. 372// Also zap the blockaddress constant if there are no users remaining, 373// otherwise the destination is still marked as having its address taken. 375 BA->destroyConstant();
377// If we didn't find our destination in the IBI successor list, then we 378// have undefined behavior. Replace the unconditional branch with an 379// 'unreachable' instruction. 386 std::vector<DominatorTree::UpdateType> Updates;
387 Updates.reserve(RemovedSuccessors.
size());
388for (
auto *RemovedSuccessor : RemovedSuccessors)
389 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
399//===----------------------------------------------------------------------===// 400// Local dead code elimination. 403/// isInstructionTriviallyDead - Return true if the result produced by the 404/// instruction is not used, and the instruction has no side effects. 415// Instructions that are "markers" and have implied meaning on code around 416// them (without explicit uses), are not dead on unused paths. 418if (
II->getIntrinsicID() == Intrinsic::stacksave ||
419II->getIntrinsicID() == Intrinsic::launder_invariant_group ||
420II->isLifetimeStartOrEnd())
427if (
I->isTerminator())
430// We don't want the landingpad-like instructions removed by anything this 435// We don't want debug info removed by anything this general. 436if (isa<DbgVariableIntrinsic>(
I))
445if (
auto *CB = dyn_cast<CallBase>(
I))
449if (!
I->willReturn()) {
450auto *
II = dyn_cast<IntrinsicInst>(
I);
454switch (
II->getIntrinsicID()) {
455case Intrinsic::experimental_guard: {
456// Guards on true are operationally no-ops. In the future we can 457// consider more sophisticated tradeoffs for guards considering potential 458// for check widening, but for now we keep things simple. 459auto *
Cond = dyn_cast<ConstantInt>(
II->getArgOperand(0));
462// TODO: These intrinsics are not safe to remove, because this may remove 463// a well-defined trap. 464case Intrinsic::wasm_trunc_signed:
465case Intrinsic::wasm_trunc_unsigned:
466case Intrinsic::ptrauth_auth:
467case Intrinsic::ptrauth_resign:
474if (!
I->mayHaveSideEffects())
477// Special case intrinsics that "may have side effects" but can be deleted 480// Safe to delete llvm.stacksave and launder.invariant.group if dead. 481if (
II->getIntrinsicID() == Intrinsic::stacksave ||
482II->getIntrinsicID() == Intrinsic::launder_invariant_group)
485// Intrinsics declare sideeffects to prevent them from moving, but they are 486// nops without users. 487if (
II->getIntrinsicID() == Intrinsic::allow_runtime_check ||
488II->getIntrinsicID() == Intrinsic::allow_ubsan_check)
491if (
II->isLifetimeStartOrEnd()) {
492auto *Arg =
II->getArgOperand(1);
493// Lifetime intrinsics are dead when their right-hand is undef. 494if (isa<UndefValue>(Arg))
496// If the right-hand is an alloc, global, or argument and the only uses 497// are lifetime intrinsics then the intrinsics are dead. 498if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg))
500 if (IntrinsicInst *IntrinsicUse =
501 dyn_cast<IntrinsicInst>(Use.getUser()))
502 return IntrinsicUse->isLifetimeStartOrEnd();
508// Assumptions are dead if their condition is trivially true. 509if (
II->getIntrinsicID() == Intrinsic::assume &&
512return !
Cond->isZero();
517if (
auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(
I)) {
518 std::optional<fp::ExceptionBehavior> ExBehavior =
519 FPI->getExceptionBehavior();
524if (
auto *Call = dyn_cast<CallBase>(
I)) {
526if (
Constant *
C = dyn_cast<Constant>(FreedOp))
527returnC->isNullValue() || isa<UndefValue>(
C);
532// Non-volatile atomic loads from constants can be removed. 533if (
auto *LI = dyn_cast<LoadInst>(
I))
534if (
auto *GV = dyn_cast<GlobalVariable>(
535 LI->getPointerOperand()->stripPointerCasts()))
536if (!LI->isVolatile() && GV->isConstant())
542/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a 543/// trivially dead instruction, delete it. If that makes any of its operands 544/// trivially dead, delete them too, recursively. Return true if any 545/// instructions were deleted. 548 std::function<
void(
Value *)> AboutToDeleteCallback) {
556 AboutToDeleteCallback);
564 std::function<
void(
Value *)> AboutToDeleteCallback) {
565unsigned S = 0, E = DeadInsts.
size(), Alive = 0;
567auto *
I = dyn_cast_or_null<Instruction>(DeadInsts[S]);
569 DeadInsts[S] =
nullptr;
576 AboutToDeleteCallback);
583 std::function<
void(
Value *)> AboutToDeleteCallback) {
584// Process the dead instruction list until empty. 585while (!DeadInsts.
empty()) {
591"Live instruction found in dead worklist!");
592assert(
I->use_empty() &&
"Instructions with uses are not dead.");
594// Don't lose the debug info while deleting the instructions. 597if (AboutToDeleteCallback)
598 AboutToDeleteCallback(
I);
600// Null out all of the instruction's operands to see if any operand becomes 602for (
Use &OpU :
I->operands()) {
603Value *OpV = OpU.get();
609// If the operand is an instruction that became dead as we nulled out the 610// operand, and if it is 'trivially' dead, delete it in a future loop 627for (
auto *DII : DbgUsers)
628 DII->setKillLocation();
629for (
auto *DVR : DPUsers)
630 DVR->setKillLocation();
634/// areAllUsesEqual - Check whether the uses of a value are all the same. 635/// This is similar to Instruction::hasOneUse() except this will also return 636/// true when there are no uses or multiple uses that all refer to the same 645for (++UI; UI != UE; ++UI) {
652/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively 653/// dead PHI node, due to being a def-use chain of single-use nodes that 654/// either forms a cycle or is terminated by a trivially dead instruction, 655/// delete it. If that makes any of its operands trivially dead, delete them 656/// too, recursively. Return true if a change was made. 662I = cast<Instruction>(*
I->user_begin())) {
666// If we find an instruction more than once, we're on a cycle that 667// won't prove fruitful. 668if (!Visited.
insert(
I).second) {
669// Break the cycle and delete the instruction and its operands. 686// Null out all of the instruction's operands to see if any operand becomes 688for (
unsigned i = 0, e =
I->getNumOperands(); i != e; ++i) {
689Value *OpV =
I->getOperand(i);
690I->setOperand(i,
nullptr);
695// If the operand is an instruction that became dead as we nulled out the 696// operand, and if it is 'trivially' dead, delete it in a future loop 709// Add the users to the worklist. CAREFUL: an instruction can use itself, 710// in the case of a phi node. 711for (
User *U :
I->users()) {
713 WorkList.
insert(cast<Instruction>(U));
717// Replace the instruction with its simplified value. 719if (!
I->use_empty()) {
720I->replaceAllUsesWith(SimpleV);
732/// SimplifyInstructionsInBlock - Scan the specified basic block and try to 733/// simplify any instructions in it and recursively delete dead instructions. 735/// This returns true if it changed the code, note that it can delete 736/// instructions in other blocks as well in this block. 739bool MadeChange =
false;
743// In debug builds, ensure that the terminator of the block is never replaced 744// or deleted by these simplifications. The idea of simplification is that it 745// cannot introduce new instructions, and there is no way to replace the 746// terminator of a block without introducing a new instruction. 751// Iterate over the original function, only adding insts to the worklist 752// if they actually need to be revisited. This avoids having to pre-init 753// the worklist with the entire function's worth of instructions. 756assert(!BI->isTerminator());
760// We're visiting this instruction now, so make sure it's not in the 761// worklist from an earlier visit. 766while (!WorkList.
empty()) {
773//===----------------------------------------------------------------------===// 774// Control Flow Graph Restructuring. 780// If BB has single-entry PHI nodes, fold them. 781while (
PHINode *PN = dyn_cast<PHINode>(DestBB->
begin())) {
782Value *NewVal = PN->getIncomingValue(0);
783// Replace self referencing PHI with poison, it must be dead. 785 PN->replaceAllUsesWith(NewVal);
786 PN->eraseFromParent();
790assert(PredBB &&
"Block doesn't have a single predecessor!");
794// DTU updates: Collect all the edges that enter 795// PredBB. These dominator edges will be redirected to DestBB. 799// To avoid processing the same predecessor more than once. 803// This predecessor of PredBB may already have DestBB as a successor. 804if (PredOfPredBB != PredBB)
805if (SeenPreds.
insert(PredOfPredBB).second)
806 Updates.
push_back({DominatorTree::Insert, PredOfPredBB, DestBB});
809if (SeenPreds.
insert(PredOfPredBB).second)
810 Updates.
push_back({DominatorTree::Delete, PredOfPredBB, PredBB});
811 Updates.
push_back({DominatorTree::Delete, PredBB, DestBB});
814// Zap anything that took the address of DestBB. Not doing this will give the 815// address an invalid value. 825// Anything that branched to PredBB now branches to DestBB. 828// Splice all the instructions from PredBB to DestBB. 833// If the PredBB is the entry block of the function, move DestBB up to 834// become the entry block after we erase PredBB. 841"The successor list of PredBB isn't empty before " 842"applying corresponding DTU updates.");
845// Recalculation of DomTree is needed when updating a forward DomTree and 846// the Entry BB is replaced. 848// The entry block was removed and there is no external interface for 849// the dominator tree to be notified of this change. In this corner-case 850// we recalculate the entire tree. 860/// Return true if we can choose one of these values to use in place of the 861/// other. Note that we will always choose the non-undef value to keep. 863returnFirst == Second || isa<UndefValue>(
First) || isa<UndefValue>(Second);
866/// Return true if we can fold BB, an almost-empty BB ending in an unconditional 867/// branch to Succ, into Succ. 869/// Assumption: Succ is the single successor for BB. 877// Shortcut, if there is only a single predecessor it must be BB and merging 882// Look at all the phi nodes in Succ, to see if they present a conflict when 883// merging these blocks 887// If the incoming value from BB is again a PHINode in 888// BB which has the same incoming value for *PI as PN does, we can 889// merge the phi nodes and then the blocks can still be merged 894if (BBPreds.
count(IBB) &&
898 <<
"Can't fold, phi node " << PN->
getName() <<
" in " 899 << Succ->
getName() <<
" is conflicting with " 900 << BBPN->
getName() <<
" with regard to common predecessor " 908// See if the incoming value for the common predecessor is equal to the 909// one for BB, in which case this phi node will not prevent the merging 912if (BBPreds.
count(IBB) &&
916 <<
" is conflicting with regard to common " 917 <<
"predecessor " << IBB->
getName() <<
"\n");
930/// Determines the value to use as the phi node input for a block. 932/// Select between \p OldVal any value that we know flows from \p BB 933/// to a particular phi on the basis of which one (if either) is not 934/// undef. Update IncomingValues based on the selected value. 936/// \param OldVal The value we are considering selecting. 937/// \param BB The block that the value flows in from. 938/// \param IncomingValues A map from block-to-value for other phi inputs 939/// that we have examined. 941/// \returns the selected value. 944if (!isa<UndefValue>(OldVal)) {
946 IncomingValues.
find(BB)->second == OldVal) &&
947"Expected OldVal to match incoming value from BB!");
949 IncomingValues.
insert(std::make_pair(BB, OldVal));
954if (It != IncomingValues.
end())
return It->second;
959/// Create a map from block to value for the operands of a 962/// Create a map from block to value for each non-undef value flowing 965/// \param PN The phi we are collecting the map for. 966/// \param IncomingValues [out] The map from block to value for this phi. 973if (!isa<UndefValue>(V))
974 IncomingValues.
insert(std::make_pair(BB, V));
978/// Replace the incoming undef values to a phi with the values 979/// from a block-to-value map. 981/// \param PN The phi we are replacing the undefs in. 982/// \param IncomingValues A map from block to value. 989if (!isa<UndefValue>(V))
continue;
994// Keep track of undef/poison incoming values. Those must match, so we fix 995// them up below if needed. 996// Note: this is conservatively correct, but we could try harder and group 997// the undef values per incoming basic block. 998if (It == IncomingValues.
end()) {
1003// There is a defined value for this incoming block, so map this undef 1004// incoming value to the defined value. 1008// If there are both undef and poison values incoming, then convert those 1009// values to undef. It is invalid to have different values for the same 1011unsigned PoisonCount =
count_if(TrueUndefOps, [&](
unsigned i) {
1014if (PoisonCount != 0 && PoisonCount != TrueUndefOps.
size()) {
1015for (
unsigned i : TrueUndefOps)
1020// Only when they shares a single common predecessor, return true. 1021// Only handles cases when BB can't be merged while its predecessors can be 1028// There must be phis in BB, otherwise BB will be merged into Succ directly 1029if (BB->
phis().empty() || Succ->
phis().empty())
1032// BB must have predecessors not shared that can be redirected to Succ 1041// Get the single common predecessor of both BB and Succ. Return false 1042// when there are more than one common predecessors. 1044if (BBPreds.
count(SuccPred)) {
1047 CommonPred = SuccPred;
1054/// Check whether removing \p BB will make the phis in its \p Succ have too 1055/// many incoming entries. This function does not check whether \p BB is 1058// If BB only has one predecessor, then removing it will not introduce more 1059// incoming edges for phis. 1063unsigned NumChangedPhi = 0;
1064for (
auto &Phi : Succ->
phis()) {
1065// If the incoming value is a phi and the phi is defined in BB, 1066// then removing BB will not increase the total phi entries of the ir. 1067if (
auto *IncomingPhi = dyn_cast<PHINode>(Phi.getIncomingValueForBlock(BB)))
1068if (IncomingPhi->getParent() == BB)
1070// Otherwise, we need to add entries to the phi 1073// For every phi that needs to be changed, (NumPreds - 1) new entries will be 1074// added. If the total increase in phi entries exceeds 1075// MaxPhiEntriesIncreaseAfterRemovingEmptyBlock, it will be considered as 1076// introducing too many new phi entries. 1077return (NumPreds - 1) * NumChangedPhi >
1081/// Replace a value flowing from a block to a phi with 1082/// potentially multiple instances of that value flowing from the 1083/// block's predecessors to the phi. 1085/// \param BB The block with the value flowing into the phi. 1086/// \param BBPreds The predecessors of BB. 1087/// \param PN The phi that we are updating. 1088/// \param CommonPred The common predecessor of BB and PN's BasicBlock 1094assert(OldVal &&
"No entry in PHI for Pred BB!");
1098// We are merging two blocks - BB, and the block containing PN - and 1099// as a result we need to redirect edges from the predecessors of BB 1100// to go to the block containing PN, and update PN 1101// accordingly. Since we allow merging blocks in the case where the 1102// predecessor and successor blocks both share some predecessors, 1103// and where some of those common predecessors might have undef 1104// values flowing into PN, we want to rewrite those values to be 1105// consistent with the non-undef values. 1109// If this incoming value is one of the PHI nodes in BB, the new entries 1110// in the PHI node are the entries from the old PHI. 1111if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->
getParent() == BB) {
1112PHINode *OldValPN = cast<PHINode>(OldVal);
1114// Note that, since we are merging phi nodes and BB and Succ might 1115// have common predecessors, we could end up with a phi node with 1116// identical incoming branches. This will be cleaned up later (and 1117// will trigger asserts if we try to clean it up now, without also 1118// simplifying the corresponding conditional branch). 1121if (PredBB == CommonPred)
1128// And add a new incoming value for this predecessor for the 1129// newly retargeted branch. 1137// Update existing incoming values in PN for this 1138// predecessor of BB. 1139if (PredBB == CommonPred)
1145// And add a new incoming value for this predecessor for the 1146// newly retargeted branch. 1159"TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
1161// We can't simplify infinite loops. 1168// The single common predecessor of BB and Succ when BB cannot be killed 1173// Even if we can not fold BB into Succ, we may be able to redirect the 1174// predecessors of BB to Succ. 1176 BB, Succ, BBPreds, CommonPred);
1181// Check to see if merging these blocks/phis would cause conflicts for any of 1182// the phi nodes in BB or Succ. If not, we can safely merge. 1184// Check for cases where Succ has multiple predecessors and a PHI node in BB 1185// has uses which will not disappear when the PHI nodes are merged. It is 1186// possible to handle such cases, but difficult: it requires checking whether 1187// BB dominates Succ, which is non-trivial to calculate in the case where 1188// Succ has multiple predecessors. Also, it requires checking whether 1189// constructing the necessary self-referential PHI node doesn't introduce any 1190// conflicts; this isn't too difficult, but the previous code for doing this 1193// Note that if this check finds a live use, BB dominates Succ, so BB is 1194// something like a loop pre-header (or rarely, a part of an irreducible CFG); 1195// folding the branch isn't profitable in that case anyway. 1198while (isa<PHINode>(*BBI)) {
1199for (
Use &U : BBI->uses()) {
1200if (
PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
1201if (PN->getIncomingBlock(U) != BB)
1211if (BBPhisMergeable && CommonPred)
1213 <<
" and " << Succ->
getName() <<
" : " 1214 << CommonPred->
getName() <<
"\n");
1216// 'BB' and 'BB->Pred' are loop latches, bail out to presrve inner loop 1219// FIXME: This is a stop-gap solution to preserve inner-loop metadata given 1220// current status (that loop metadata is implemented as metadata attached to 1221// the branch instruction in the loop latch block). To quote from review 1222// comments, "the current representation of loop metadata (using a loop latch 1223// terminator attachment) is known to be fundamentally broken. Loop latches 1224// are not uniquely associated with loops (both in that a latch can be part of 1225// multiple loops and a loop may have multiple latches). Loop headers are. The 1226// solution to this problem is also known: Add support for basic block 1227// metadata, and attach loop metadata to the loop header." 1230// In this case, we expect 'BB' is the latch for outer-loop and 'BB->Pred' is 1231// the latch for inner-loop (see reason below), so bail out to prerserve 1232// inner-loop metadata rather than eliminating 'BB' and attaching its metadata 1233// to this inner-loop. 1234// - The reason we believe 'BB' and 'BB->Pred' have different inner-most 1235// loops: assuming 'BB' and 'BB->Pred' are from the same inner-most loop L, 1236// then 'BB' is the header and latch of 'L' and thereby 'L' must consist of 1237// one self-looping basic block, which is contradictory with the assumption. 1239// To illustrate how inner-loop metadata is dropped: 1243// BB is while.cond.exit, attached with loop metdata md2. 1244// BB->Pred is for.body, attached with loop metadata md1. 1249// ---> while.cond -------------> while.end 1255// | for.body <---- (md1) 1258// | while.cond.exit (md2) 1264// while.cond1 is the merge of while.cond.exit and while.cond above. 1265// for.body is attached with md2, and md1 is dropped. 1266// If LoopSimplify runs later (as a part of loop pass), it could create 1267// dedicated exits for inner-loop (essentially adding `while.cond.exit` 1268// back), but won't it won't see 'md1' nor restore it for the inner-loop. 1273// ---> while.cond1 -------------> while.end 1279// | for.body <---- (md2) 1280// |_______| |______| 1282if (TI->hasNonDebugLocLoopMetadata())
1285if (PredTI->hasNonDebugLocLoopMetadata())
1290elseif (BBPhisMergeable)
1296// To avoid processing the same predecessor more than once. 1298// All predecessors of BB (except the common predecessor) will be moved to 1303// Do not modify those common predecessors of BB and Succ 1305if (SeenPreds.
insert(PredOfBB).second)
1306 Updates.
push_back({DominatorTree::Insert, PredOfBB, Succ});
1312// When BB cannot be killed, do not remove the edge between BB and 1314if (SeenPreds.
insert(PredOfBB).second && PredOfBB != CommonPred)
1315 Updates.
push_back({DominatorTree::Delete, PredOfBB, BB});
1318 Updates.
push_back({DominatorTree::Delete, BB, Succ});
1321if (isa<PHINode>(Succ->
begin())) {
1322// If there is more than one pred of succ, and there are PHI nodes in 1323// the successor, then we need to add incoming edges for the PHI nodes 1327// Loop over all of the PHI nodes in the successor of BB. 1335// BB is the only predecessor of Succ, so Succ will end up with exactly 1336// the same predecessors BB had. 1337// Copy over any phi, debug or lifetime instruction. 1342// We explicitly check for such uses for merging phis. 1343assert(PN->use_empty() &&
"There shouldn't be any uses here!");
1344 PN->eraseFromParent();
1348// If the unconditional branch we replaced contains non-debug llvm.loop 1349// metadata, we add the metadata to the branch instructions in the 1352if (TI->hasNonDebugLocLoopMetadata()) {
1353MDNode *LoopMD = TI->getMetadata(LLVMContext::MD_loop);
1355 Pred->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopMD);
1359// Everything that jumped to BB now goes to Succ. 1365// Clear the successor list of BB to match updates applying to DTU later. 1371"applying corresponding DTU updates.");
1372 }
elseif (BBPhisMergeable) {
1373// Everything except CommonPred that jumped to BB now goes to Succ. 1375if (
Instruction *UseInst = dyn_cast<Instruction>(U.getUser()))
1376return UseInst->
getParent() != CommonPred &&
1377 BBPreds.
contains(UseInst->getParent());
1394// This implementation doesn't currently consider undef operands 1395// specially. Theoretically, two phis which are identical except for 1396// one having an undef where the other doesn't could be collapsed. 1401// Note that increment of I must *NOT* be in the iteration_expression, since 1402// we don't want to immediately advance when we restart from the beginning. 1405// Is there an identical PHI node in this basic block? 1406// Note that we only look in the upper square's triangle, 1407// we already checked that the lower triangle PHI's aren't identical. 1408for (
auto J =
I;
PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
1413// A duplicate. Replace this PHI with the base PHI. 1419// The RAUW can change PHIs that we already visited. 1421break;
// Start over from the beginning. 1430// This implementation doesn't currently consider undef operands 1431// specially. Theoretically, two phis which are identical except for 1432// one having an undef where the other doesn't could be collapsed. 1434structPHIDenseMapInfo {
1439staticPHINode *getTombstoneKey() {
1444return PN == getEmptyKey() || PN == getTombstoneKey();
1447// WARNING: this logic must be kept in sync with 1448// Instruction::isIdenticalToWhenDefined()! 1450// Compute a hash value on the operands. Instcombine will likely have 1451// sorted them, which helps expose duplicates, but we have to check all 1452// the operands to be safe in case instcombine hasn't run. 1458staticunsigned getHashValue(
PHINode *PN) {
1460// If -phicse-debug-hash was specified, return a constant -- this 1461// will force all hashing to collide, so we'll exhaustively search 1462// the table for a match, and the assertion in isEqual will fire if 1463// there's a bug causing equal keys to hash differently. 1473returnLHS->isIdenticalTo(
RHS);
1477// These comparisons are nontrivial, so assert that equality implies 1478// hash equality (DenseMap demands this as an invariant). 1486// Set of unique PHINodes. 1495auto Inserted = PHISet.
insert(PN);
1496if (!Inserted.second) {
1497// A duplicate. Replace this PHI with its duplicate. 1499 PN->replaceAllUsesWith(*Inserted.first);
1503// The RAUW can change PHIs that we already visited. Start over from the 1528 PN->eraseFromParent();
1534 V = V->stripPointerCasts();
1536if (
AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1537// TODO: Ideally, this function would not be called if PrefAlign is smaller 1538// than the current alignment, as the known bits calculation should have 1539// already taken it into account. However, this is not always the case, 1540// as computeKnownBits() has a depth limit, while stripPointerCasts() 1542Align CurrentAlign = AI->getAlign();
1543if (PrefAlign <= CurrentAlign)
1546// If the preferred alignment is greater than the natural stack alignment 1547// then don't round up. This avoids dynamic stack realignment. 1549if (StackAlign && PrefAlign > *StackAlign)
1551 AI->setAlignment(PrefAlign);
1555if (
auto *GO = dyn_cast<GlobalObject>(V)) {
1556// TODO: as above, this shouldn't be necessary. 1557Align CurrentAlign = GO->getPointerAlignment(
DL);
1558if (PrefAlign <= CurrentAlign)
1561// If there is a large requested alignment and we can, bump up the alignment 1562// of the global. If the memory we set aside for the global may not be the 1563// memory used by the final program then it is impossible for us to reliably 1564// enforce the preferred alignment. 1565if (!GO->canIncreaseAlignment())
1568if (GO->isThreadLocal()) {
1569unsigned MaxTLSAlign = GO->getParent()->getMaxTLSAlignment() / CHAR_BIT;
1570if (MaxTLSAlign && PrefAlign >
Align(MaxTLSAlign))
1571 PrefAlign =
Align(MaxTLSAlign);
1574 GO->setAlignment(PrefAlign);
1586assert(V->getType()->isPointerTy() &&
1587"getOrEnforceKnownAlignment expects a pointer!");
1592// Avoid trouble with ridiculously large TrailZ values, such as 1593// those computed from a null pointer. 1594// LLVM doesn't support alignments larger than (1 << MaxAlignmentExponent). 1599if (PrefAlign && *PrefAlign > Alignment)
1602// We don't need to make any adjustment. 1606///===---------------------------------------------------------------------===// 1607/// Dbg Intrinsic utilities 1610/// See if there is a dbg.value intrinsic for DIVar for the PHI node. 1614// Since we can't guarantee that the original dbg.declare intrinsic 1615// is removed by LowerDbgDeclare(), we need to make sure that we are 1616// not inserting the same dbg.value intrinsic over and over. 1620for (
auto *DVI : DbgValues) {
1622if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1625for (
auto *DVR : DbgVariableRecords) {
1627if ((DVR->getVariable() == DIVar) && (DVR->getExpression() == DIExpr))
1633/// Check if the alloc size of \p ValTy is large enough to cover the variable 1634/// (or fragment of the variable) described by \p DII. 1636/// This is primarily intended as a helper for the different 1637/// ConvertDebugDeclareToDebugValue functions. The dbg.declare that is converted 1638/// describes an alloca'd variable, so we need to use the alloc size of the 1639/// value when doing the comparison. E.g. an i1 value will be identified as 1640/// covering an n-bit fragment, if the store size of i1 is at least n bits. 1643TypeSize ValueSize =
DL.getTypeAllocSizeInBits(ValTy);
1644if (std::optional<uint64_t> FragmentSize =
1648// We can't always calculate the size of the DI variable (e.g. if it is a 1649// VLA). Try to use the size of the alloca that the dbg intrinsic describes 1652// DII should have exactly 1 location when it is an address. 1654"address of variable must have exactly 1 location operand.");
1657if (std::optional<TypeSize> FragmentSize =
1658 AI->getAllocationSizeInBits(
DL)) {
1659return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1663// Could not determine size of variable. Conservatively return false. 1666// RemoveDIs: duplicate implementation of the above, using DbgVariableRecords, 1667// the replacement for dbg.values. 1670TypeSize ValueSize =
DL.getTypeAllocSizeInBits(ValTy);
1671if (std::optional<uint64_t> FragmentSize =
1675// We can't always calculate the size of the DI variable (e.g. if it is a 1676// VLA). Try to use the size of the alloca that the dbg intrinsic describes 1679// DVR should have exactly 1 location when it is an address. 1681"address of variable must have exactly 1 location operand.");
1684if (std::optional<TypeSize> FragmentSize = AI->getAllocationSizeInBits(
DL)) {
1685return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1689// Could not determine size of variable. Conservatively return false. 1699auto DbgVal = Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc,
1701 cast<Instruction *>(DbgVal)->insertBefore(Instr);
1703// RemoveDIs: if we're using the new debug-info format, allocate a 1704// DbgVariableRecord directly instead of a dbg.value intrinsic. 1708 Instr->getParent()->insertDbgRecordBefore(DV, Instr);
1716auto DbgVal = Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc,
1718 cast<Instruction *>(DbgVal)->insertAfter(Instr);
1720// RemoveDIs: if we're using the new debug-info format, allocate a 1721// DbgVariableRecord directly instead of a dbg.value intrinsic. 1725 Instr->getParent()->insertDbgRecordAfter(DV, &*Instr);
1729/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value 1730/// that has an associated llvm.dbg.declare intrinsic. 1735assert(DIVar &&
"Missing variable");
1737Value *DV = SI->getValueOperand();
1741// If the alloca describes the variable itself, i.e. the expression in the 1742// dbg.declare doesn't start with a dereference, we can perform the 1743// conversion if the value covers the entire fragment of DII. 1744// If the alloca describes the *address* of DIVar, i.e. DIExpr is 1745// *just* a DW_OP_deref, we use DV as is for the dbg.value. 1746// We conservatively ignore other dereferences, because the following two are 1748// dbg.declare(alloca, ..., !Expr(deref, plus_uconstant, 2)) 1749// dbg.value(DV, ..., !Expr(deref, plus_uconstant, 2)) 1750// The former is adding 2 to the address of the variable, whereas the latter 1751// is adding 2 to the value of the variable. As such, we insist on just a 1754 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1762// FIXME: If storing to a part of the variable described by the dbg.declare, 1763// then we want to insert a dbg.value for the corresponding fragment. 1764LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " << *DII
1766// For now, when there is a store to parts of the variable (but we do not 1767// know which part) we insert an dbg.value intrinsic to indicate that we 1768// know nothing about the variable's content. 1776return DIExpression::get(DIExpr->
getContext(),
1783assert(DIVar &&
"Missing variable");
1786Value *DV = SI->getValueOperand();
1794/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value 1795/// that has an associated llvm.dbg.declare intrinsic. 1800assert(DIVar &&
"Missing variable");
1803// FIXME: If only referring to a part of the variable described by the 1804// dbg.declare, then we want to insert a dbg.value for the corresponding 1806LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " 1813// We are now tracking the loaded value instead of the address. In the 1814// future if multi-location support is added to the IR, it might be 1815// preferable to keep tracking both the loaded value and the original 1816// address in case the alloca can not be elided. 1825assert(DIVar &&
"Missing variable");
1827Value *DV = SI->getValueOperand();
1831// If the alloca describes the variable itself, i.e. the expression in the 1832// dbg.declare doesn't start with a dereference, we can perform the 1833// conversion if the value covers the entire fragment of DII. 1834// If the alloca describes the *address* of DIVar, i.e. DIExpr is 1835// *just* a DW_OP_deref, we use DV as is for the dbg.value. 1836// We conservatively ignore other dereferences, because the following two are 1838// dbg.declare(alloca, ..., !Expr(deref, plus_uconstant, 2)) 1839// dbg.value(DV, ..., !Expr(deref, plus_uconstant, 2)) 1840// The former is adding 2 to the address of the variable, whereas the latter 1841// is adding 2 to the value of the variable. As such, we insist on just a 1844 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1852// FIXME: If storing to a part of the variable described by the dbg.declare, 1853// then we want to insert a dbg.value for the corresponding fragment. 1854LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " << *DVR
1858// For now, when there is a store to parts of the variable (but we do not 1859// know which part) we insert an dbg.value intrinsic to indicate that we 1860// know nothing about the variable's content. 1865 SI->getParent()->insertDbgRecordBefore(NewDVR, SI->getIterator());
1871assert(DIVar &&
"Missing variable");
1874Value *DV = SI->getValueOperand();
1882/// Inserts a llvm.dbg.value intrinsic after a phi that has an associated 1883/// llvm.dbg.declare intrinsic. 1888assert(DIVar &&
"Missing variable");
1894// FIXME: If only referring to a part of the variable described by the 1895// dbg.declare, then we want to insert a dbg.value for the corresponding 1897LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to dbg.value: " 1907// The block may be a catchswitch block, which does not have a valid 1909// FIXME: Insert dbg.value markers in the successors when appropriate. 1910if (InsertionPt != BB->
end()) {
1920assert(DIVar &&
"Missing variable");
1923// FIXME: If only referring to a part of the variable described by the 1924// dbg.declare, then we want to insert a DbgVariableRecord for the 1925// corresponding fragment. 1926LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to DbgVariableRecord: " 1933// We are now tracking the loaded value instead of the address. In the 1934// future if multi-location support is added to the IR, it might be 1935// preferable to keep tracking both the loaded value and the original 1936// address in case the alloca can not be elided. 1939// Create a DbgVariableRecord directly and insert. 1943 LI->
getParent()->insertDbgRecordAfter(DV, LI);
1946/// Determine whether this alloca is either a VLA or an array. 1952/// Determine whether this alloca is a structure. 1960assert(DIVar &&
"Missing variable");
1966// FIXME: If only referring to a part of the variable described by the 1967// dbg.declare, then we want to insert a DbgVariableRecord for the 1968// corresponding fragment. 1969LLVM_DEBUG(
dbgs() <<
"Failed to convert dbg.declare to DbgVariableRecord: " 1979// The block may be a catchswitch block, which does not have a valid 1981// FIXME: Insert DbgVariableRecord markers in the successors when appropriate. 1982if (InsertionPt != BB->
end()) {
1988/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set 1989/// of llvm.dbg.value intrinsics. 1992DIBuilder DIB(*
F.getParent(),
/*AllowUnresolved*/false);
1997if (
auto *DDI = dyn_cast<DbgDeclareInst>(&BI))
2000if (DVR.getType() == DbgVariableRecord::LocationType::Declare)
2009auto LowerOne = [&](
auto *DDI) {
2011 dyn_cast_or_null<AllocaInst>(DDI->getVariableLocationOp(0));
2012// If this is an alloca for a scalar variable, insert a dbg.value 2013// at each load and store to the alloca and erase the dbg.declare. 2014// The dbg.values allow tracking a variable even if it is not 2015// stored on the stack, while the dbg.declare can only describe 2016// the stack slot (and at a lexical-scope granularity). Later 2017// passes will attempt to elide the stack slot. 2021// A volatile load/store means that the alloca can't be elided anyway. 2023 if (LoadInst *LI = dyn_cast<LoadInst>(U))
2024 return LI->isVolatile();
2025 if (StoreInst *SI = dyn_cast<StoreInst>(U))
2026 return SI->isVolatile();
2033while (!WorkList.
empty()) {
2035for (
constauto &AIUse : V->uses()) {
2036User *U = AIUse.getUser();
2037if (
StoreInst *SI = dyn_cast<StoreInst>(U)) {
2038if (AIUse.getOperandNo() == 1)
2040 }
elseif (
LoadInst *LI = dyn_cast<LoadInst>(U)) {
2042 }
elseif (
CallInst *CI = dyn_cast<CallInst>(U)) {
2043// This is a call by-value or some other instruction that takes a 2044// pointer to the variable. Insert a *value* intrinsic that describes 2045// the variable by dereferencing the alloca. 2046if (!CI->isLifetimeStartOrEnd()) {
2054 }
elseif (
BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
2055if (BI->getType()->isPointerTy())
2060 DDI->eraseFromParent();
2074// RemoveDIs: re-implementation of insertDebugValuesForPHIs, but which pulls the 2075// debug-info out of the block's DbgVariableRecords rather than dbg.value 2080assert(BB &&
"No BasicBlock to clone DbgVariableRecord(s) from.");
2081if (InsertedPHIs.
size() == 0)
2084// Map existing PHI nodes to their DbgVariableRecords. 2086for (
auto &
I : *BB) {
2088for (
Value *V : DVR.location_ops())
2089if (
auto *Loc = dyn_cast_or_null<PHINode>(V))
2090 DbgValueMap.
insert({Loc, &DVR});
2093if (DbgValueMap.
size() == 0)
2096// Map a pair of the destination BB and old DbgVariableRecord to the new 2097// DbgVariableRecord, so that if a DbgVariableRecord is being rewritten to use 2098// more than one of the inserted PHIs in the same destination BB, we can 2099// update the same DbgVariableRecord with all the new PHIs instead of creating 2100// one copy for each. 2103// Then iterate through the new PHIs and look to see if they use one of the 2104// previously mapped PHIs. If so, create a new DbgVariableRecord that will 2105// propagate the info through the new PHI. If we use more than one new PHI in 2106// a single destination BB with the same old dbg.value, merge the updates so 2107// that we get a single new DbgVariableRecord with all the new PHIs. 2108for (
autoPHI : InsertedPHIs) {
2110// Avoid inserting a debug-info record into an EH block. 2113for (
auto VI :
PHI->operand_values()) {
2114auto V = DbgValueMap.
find(VI);
2115if (V != DbgValueMap.
end()) {
2117auto NewDI = NewDbgValueMap.
find({Parent, DbgII});
2118if (NewDI == NewDbgValueMap.
end()) {
2120 NewDI = NewDbgValueMap.
insert({{Parent, DbgII}, NewDbgII}).first;
2123// If PHI contains VI as an operand more than once, we may 2124// replaced it in NewDbgII; confirm that it is present. 2130// Insert the new DbgVariableRecords into their destination blocks. 2131for (
auto DI : NewDbgValueMap) {
2135assert(InsertionPt != Parent->
end() &&
"Ill-formed basic block");
2141/// Propagate dbg.value intrinsics through the newly inserted PHIs. 2144assert(BB &&
"No BasicBlock to clone dbg.value(s) from.");
2145if (InsertedPHIs.
size() == 0)
2150// Map existing PHI nodes to their dbg.values. 2152for (
auto &
I : *BB) {
2153if (
auto DbgII = dyn_cast<DbgVariableIntrinsic>(&
I)) {
2154for (
Value *V : DbgII->location_ops())
2155if (
auto *Loc = dyn_cast_or_null<PHINode>(V))
2156 DbgValueMap.
insert({Loc, DbgII});
2159if (DbgValueMap.
size() == 0)
2162// Map a pair of the destination BB and old dbg.value to the new dbg.value, 2163// so that if a dbg.value is being rewritten to use more than one of the 2164// inserted PHIs in the same destination BB, we can update the same dbg.value 2165// with all the new PHIs instead of creating one copy for each. 2169// Then iterate through the new PHIs and look to see if they use one of the 2170// previously mapped PHIs. If so, create a new dbg.value intrinsic that will 2171// propagate the info through the new PHI. If we use more than one new PHI in 2172// a single destination BB with the same old dbg.value, merge the updates so 2173// that we get a single new dbg.value with all the new PHIs. 2174for (
auto *
PHI : InsertedPHIs) {
2176// Avoid inserting an intrinsic into an EH block. 2179for (
auto *VI :
PHI->operand_values()) {
2180auto V = DbgValueMap.
find(VI);
2181if (V != DbgValueMap.
end()) {
2182auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
2183auto [NewDI, Inserted] = NewDbgValueMap.
try_emplace({Parent, DbgII});
2185 NewDI->second = cast<DbgVariableIntrinsic>(DbgII->clone());
2187// If PHI contains VI as an operand more than once, we may 2188// replaced it in NewDbgII; confirm that it is present. 2194// Insert thew new dbg.values into their destination blocks. 2195for (
auto DI : NewDbgValueMap) {
2197auto *NewDbgII = DI.second;
2199assert(InsertionPt != Parent->
end() &&
"Ill-formed basic block");
2200 NewDbgII->insertBefore(InsertionPt);
2210auto ReplaceOne = [&](
auto *DII) {
2211assert(DII->getVariable() &&
"Missing variable");
2212auto *DIExpr = DII->getExpression();
2214 DII->setExpression(DIExpr);
2215 DII->replaceVariableLocationOp(
Address, NewAddress);
2221return !DbgDeclares.
empty() || !DVRDeclares.
empty();
2230assert(DIVar &&
"Missing variable");
2232// This is an alloca-based dbg.value/DbgVariableRecord. The first thing it 2233// should do with the alloca pointer is dereference it. Otherwise we don't 2234// know how to handle it and give up. 2239// Insert the offset before the first deref. 2259// Attempt to replace dbg.values that use this alloca. 2260for (
auto *DVI : DbgUsers)
2262 DVI->getExpression(), NewAllocaAddress, DVI,
2265// Replace any DbgVariableRecords that use this alloca. 2268 DVR->getExpression(), NewAllocaAddress,
nullptr,
2272/// Where possible to salvage debug information for \p I do so. 2273/// If not possible mark undef. 2282Instruction *
I = dyn_cast<Instruction>(Assign->getAddress());
2283// Only instructions can be salvaged at the moment. 2287assert(!Assign->getAddressExpression()->getFragmentInfo().has_value() &&
2288"address-expression shouldn't have fragment info");
2290// The address component of a dbg.assign cannot be variadic. 2296// Check if the salvage failed. 2301 Assign->getAddressExpression(), Ops, 0,
/*StackValue=*/false);
2303"address-expression shouldn't have fragment info");
2307// Salvage succeeds if no additional values are required. 2308if (AdditionalValues.
empty()) {
2309 Assign->setAddress(NewV);
2310 Assign->setAddressExpression(SalvagedExpr);
2312 Assign->setKillAddress();
2319// These are arbitrary chosen limits on the maximum number of values and the 2320// maximum size of a debug expression we can salvage up to, used for 2321// performance reasons. 2322constunsigned MaxDebugArgs = 16;
2323constunsigned MaxExpressionSize = 128;
2324bool Salvaged =
false;
2326for (
auto *DII : DbgUsers) {
2327if (
auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII)) {
2328if (DAI->getAddress() == &
I) {
2332if (DAI->getValue() != &
I)
2336// Do not add DW_OP_stack_value for DbgDeclare, because they are implicitly 2337// pointing out the value as a DWARF memory location description. 2338bool StackValue = isa<DbgValueInst>(DII);
2339auto DIILocation = DII->location_ops();
2342"DbgVariableIntrinsic must use salvaged instruction as its location");
2344// `I` may appear more than once in DII's location ops, and each use of `I` 2345// must be updated in the DIExpression and potentially have additional 2346// values added; thus we call salvageDebugInfoImpl for each `I` instance in 2350auto LocItr =
find(DIILocation, &
I);
2351while (SalvagedExpr && LocItr != DIILocation.end()) {
2353unsigned LocNo = std::distance(DIILocation.begin(), LocItr);
2360 LocItr = std::find(++LocItr, DIILocation.end(), &
I);
2362// salvageDebugInfoImpl should fail on examining the first element of 2363// DbgUsers, or none of them. 2368 DII->replaceVariableLocationOp(&
I, Op0);
2369bool IsValidSalvageExpr = SalvagedExpr->
getNumElements() <= MaxExpressionSize;
2370if (AdditionalValues.
empty() && IsValidSalvageExpr) {
2371 DII->setExpression(SalvagedExpr);
2372 }
elseif (isa<DbgValueInst>(DII) && IsValidSalvageExpr &&
2373 DII->getNumVariableLocationOps() + AdditionalValues.
size() <=
2375 DII->addVariableLocationOps(AdditionalValues, SalvagedExpr);
2377// Do not salvage using DIArgList for dbg.declare, as it is not currently 2378// supported in those instructions. Also do not salvage if the resulting 2379// DIArgList would contain an unreasonably large number of values. 2380 DII->setKillLocation();
2385// Duplicate of above block for DbgVariableRecords. 2386for (
auto *DVR : DPUsers) {
2387if (DVR->isDbgAssign()) {
2388if (DVR->getAddress() == &
I) {
2392if (DVR->getValue() != &
I)
2396// Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they 2397// are implicitly pointing out the value as a DWARF memory location 2400 DVR->getType() != DbgVariableRecord::LocationType::Declare;
2401auto DVRLocation = DVR->location_ops();
2404"DbgVariableIntrinsic must use salvaged instruction as its location");
2406// 'I' may appear more than once in DVR's location ops, and each use of 'I' 2407// must be updated in the DIExpression and potentially have additional 2408// values added; thus we call salvageDebugInfoImpl for each 'I' instance in 2412auto LocItr =
find(DVRLocation, &
I);
2413while (SalvagedExpr && LocItr != DVRLocation.end()) {
2415unsigned LocNo = std::distance(DVRLocation.begin(), LocItr);
2422 LocItr = std::find(++LocItr, DVRLocation.end(), &
I);
2424// salvageDebugInfoImpl should fail on examining the first element of 2425// DbgUsers, or none of them. 2430 DVR->replaceVariableLocationOp(&
I, Op0);
2431bool IsValidSalvageExpr =
2433if (AdditionalValues.
empty() && IsValidSalvageExpr) {
2434 DVR->setExpression(SalvagedExpr);
2435 }
elseif (DVR->getType() != DbgVariableRecord::LocationType::Declare &&
2436 IsValidSalvageExpr &&
2437 DVR->getNumVariableLocationOps() + AdditionalValues.
size() <=
2439 DVR->addVariableLocationOps(AdditionalValues, SalvagedExpr);
2441// Do not salvage using DIArgList for dbg.addr/dbg.declare, as it is 2442// currently only valid for stack value expressions. 2443// Also do not salvage if the resulting DIArgList would contain an 2444// unreasonably large number of values. 2445 DVR->setKillLocation();
2454for (
auto *DII : DbgUsers)
2455 DII->setKillLocation();
2457for (
auto *DVR : DPUsers)
2458 DVR->setKillLocation();
2465unsignedBitWidth =
DL.getIndexSizeInBits(
GEP->getPointerAddressSpace());
2466// Rewrite a GEP into a DIExpression. 2469if (!
GEP->collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset))
2471if (!VariableOffsets.
empty() && !CurrentLocOps) {
2472 Opcodes.
insert(Opcodes.
begin(), {dwarf::DW_OP_LLVM_arg, 0});
2475for (
constauto &
Offset : VariableOffsets) {
2478"Expected strictly positive multiplier for offset.");
2480Offset.second.getZExtValue(), dwarf::DW_OP_mul,
2481 dwarf::DW_OP_plus});
2484returnGEP->getOperand(0);
2489case Instruction::Add:
2490return dwarf::DW_OP_plus;
2491case Instruction::Sub:
2492return dwarf::DW_OP_minus;
2493case Instruction::Mul:
2494return dwarf::DW_OP_mul;
2495case Instruction::SDiv:
2496return dwarf::DW_OP_div;
2497case Instruction::SRem:
2498return dwarf::DW_OP_mod;
2499case Instruction::Or:
2500return dwarf::DW_OP_or;
2501case Instruction::And:
2502return dwarf::DW_OP_and;
2503case Instruction::Xor:
2504return dwarf::DW_OP_xor;
2505case Instruction::Shl:
2506return dwarf::DW_OP_shl;
2507case Instruction::LShr:
2508return dwarf::DW_OP_shr;
2509case Instruction::AShr:
2510return dwarf::DW_OP_shra;
2512// TODO: Salvage from each kind of binop we know about. 2521if (!CurrentLocOps) {
2526 AdditionalValues.
push_back(
I->getOperand(1));
2532// Handle binary operations with constant integer operands as a special case. 2533auto *ConstInt = dyn_cast<ConstantInt>(BI->
getOperand(1));
2534// Values wider than 64 bits cannot be represented within a DIExpression. 2535if (ConstInt && ConstInt->getBitWidth() > 64)
2539// Push any Constant Int operand onto the expression stack. 2541uint64_t Val = ConstInt->getSExtValue();
2542// Add or Sub Instructions with a constant operand can potentially be 2544if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
2545uint64_tOffset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
2549 Opcodes.
append({dwarf::DW_OP_constu, Val});
2554// Add salvaged binary operator to expression stack, if it has a valid 2555// representation in a DIExpression. 2564// The signedness of the operation is implicit in the typed stack, signed and 2565// unsigned instructions map to the same DWARF opcode. 2568return dwarf::DW_OP_eq;
2570return dwarf::DW_OP_ne;
2573return dwarf::DW_OP_gt;
2576return dwarf::DW_OP_ge;
2579return dwarf::DW_OP_lt;
2582return dwarf::DW_OP_le;
2591// Handle icmp operations with constant integer operands as a special case. 2592auto *ConstInt = dyn_cast<ConstantInt>(Icmp->
getOperand(1));
2593// Values wider than 64 bits cannot be represented within a DIExpression. 2594if (ConstInt && ConstInt->getBitWidth() > 64)
2596// Push any Constant Int operand onto the expression stack. 2602uint64_t Val = ConstInt->getSExtValue();
2608// Add salvaged binary operator to expression stack, if it has a valid 2609// representation in a DIExpression. 2620auto &M = *
I.getModule();
2621auto &
DL = M.getDataLayout();
2623if (
auto *CI = dyn_cast<CastInst>(&
I)) {
2624Value *FromValue = CI->getOperand(0);
2625// No-op casts are irrelevant for debug info. 2626if (CI->isNoopCast(
DL)) {
2633// Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged. 2635 !(isa<TruncInst>(&
I) || isa<SExtInst>(&
I) || isa<ZExtInst>(&
I) ||
2636 isa<IntToPtrInst>(&
I) || isa<PtrToIntInst>(&
I)))
2640if (FromType->isPointerTy())
2641 FromType =
DL.getIntPtrType(FromType);
2643unsigned FromTypeBitSize = FromType->getScalarSizeInBits();
2648 Ops.
append(ExtOps.begin(), ExtOps.end());
2652if (
auto *
GEP = dyn_cast<GetElementPtrInst>(&
I))
2654if (
auto *BI = dyn_cast<BinaryOperator>(&
I))
2656if (
auto *IC = dyn_cast<ICmpInst>(&
I))
2659// *Not* to do: we should not attempt to salvage load instructions, 2660// because the validity and lifetime of a dbg.value containing 2661// DW_OP_deref becomes difficult to analyze. See PR40628 for examples. 2665/// A replacement for a dbg.value expression. 2668/// Point debug users of \p From to \p To using exprs given by \p RewriteExpr, 2669/// possibly moving/undefing users to prevent use-before-def. Returns true if 2670/// changes are made. 2675// Find debug users of From. 2682// Prevent use-before-def of To. 2687if (isa<Instruction>(&To)) {
2688bool DomPointAfterFrom =
From.getNextNonDebugInstruction() == &DomPoint;
2690for (
auto *DII :
Users) {
2691// It's common to see a debug user between From and DomPoint. Move it 2692// after DomPoint to preserve the variable update without any reordering. 2698// Users which otherwise aren't dominated by the replacement value must 2699// be salvaged or deleted. 2700 }
elseif (!DT.
dominates(&DomPoint, DII)) {
2701 UndefOrSalvage.
insert(DII);
2705// DbgVariableRecord implementation of the above. 2706for (
auto *DVR : DPUsers) {
2709// The next instruction might still be a dbg.declare, skip over it. 2710if (isa<DbgVariableIntrinsic>(NextNonDebug))
2713if (DomPointAfterFrom && NextNonDebug == &DomPoint) {
2716// Ensure there's a marker. 2717 DomPoint.
getParent()->insertDbgRecordAfter(DVR, &DomPoint);
2719 }
elseif (!DT.
dominates(&DomPoint, MarkedInstr)) {
2720 UndefOrSalvageDVR.
insert(DVR);
2725// Update debug users without use-before-def risk. 2726for (
auto *DII :
Users) {
2727if (UndefOrSalvage.
count(DII))
2739for (
auto *DVR : DPUsers) {
2740if (UndefOrSalvageDVR.
count(DVR))
2753if (!UndefOrSalvage.
empty() || !UndefOrSalvageDVR.
empty()) {
2754// Try to salvage the remaining debug users. 2762/// Check if a bitcast between a value of type \p FromTy to type \p ToTy would 2763/// losslessly preserve the bits and semantics of the value. This predicate is 2764/// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result. 2766/// Note that Type::canLosslesslyBitCastTo is not suitable here because it 2767/// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>, 2768/// and also does not allow lossless pointer <-> integer conversions. 2771// Trivially compatible types. 2775// Handle compatible pointer <-> integer conversions. 2777bool SameSize =
DL.getTypeSizeInBits(FromTy) ==
DL.getTypeSizeInBits(ToTy);
2778bool LosslessConversion = !
DL.isNonIntegralPointerType(FromTy) &&
2779 !
DL.isNonIntegralPointerType(ToTy);
2780return SameSize && LosslessConversion;
2783// TODO: This is not exhaustive. 2789// Exit early if From has no debug users. 2790if (!
From.isUsedByMetadata())
2793assert(&
From != &To &&
"Can't replace something with itself");
2802return DVR.getExpression();
2805// Handle no-op conversions. 2811// Handle integer-to-integer widening and narrowing. 2812// FIXME: Use DW_OP_convert when it's available everywhere. 2816assert(FromBits != ToBits &&
"Unexpected no-op conversion");
2818// When the width of the result grows, assume that a debugger will only 2819// access the low `FromBits` bits when inspecting the source variable. 2820if (FromBits < ToBits)
2823// The width of the result has shrunk. Use sign/zero extension to describe 2824// the source variable's high bits. 2828// Without knowing signedness, sign/zero extension isn't possible. 2833boolSigned = *Signedness == DIBasicType::Signedness::Signed;
2837// RemoveDIs: duplicate implementation working on DbgVariableRecords rather 2838// than on dbg.value intrinsics. 2842// Without knowing signedness, sign/zero extension isn't possible. 2847boolSigned = *Signedness == DIBasicType::Signedness::Signed;
2855// TODO: Floating-point conversions, vectors. 2862// RemoveDIs: erase debug-info on this instruction manually. 2864for (
Use &U :
I->operands()) {
2866if (isa<Instruction>(
Op) && !
Op->getType()->isTokenTy()) {
2876std::pair<unsigned, unsigned>
2878unsigned NumDeadInst = 0;
2879unsigned NumDeadDbgInst = 0;
2880// Delete the instructions backwards, as it has a reduced likelihood of 2881// having to update as many def-use and use-def chains. 2886while (EndInst != &BB->
front()) {
2887// Delete the next to last instruction. 2892// EHPads can't have DbgVariableRecords attached to them, but it might be 2893// possible for things with token type. 2898if (isa<DbgInfoIntrinsic>(Inst))
2902// RemoveDIs: erasing debug-info must be done manually. 2906return {NumDeadInst, NumDeadDbgInst};
2919// Loop over all of the successors, removing BB's entry from any PHI 2922Successor->removePredecessor(BB, PreserveLCSSA);
2927 UI->setDebugLoc(
I->getDebugLoc());
2929// All instructions after this are dead. 2930unsigned NumInstrsRemoved = 0;
2933if (!BBI->use_empty())
2935 BBI++->eraseFromParent();
2941for (
BasicBlock *UniqueSuccessor : UniqueSuccessors)
2942 Updates.
push_back({DominatorTree::Delete, BB, UniqueSuccessor});
2946return NumInstrsRemoved;
2952II->getOperandBundlesAsDefs(OpBundles);
2954II->getCalledOperand(), Args, OpBundles);
2960// If the invoke had profile metadata, try converting them for CallInst. 2963// Set the total weight if it fits into i32, otherwise reset. 2965auto NewWeights =
uint32_t(TotalWeight) != TotalWeight
2968 NewCall->
setMetadata(LLVMContext::MD_prof, NewWeights);
2974// changeToCall - Convert the specified invoke into a normal call. 2979II->replaceAllUsesWith(NewCall);
2981// Follow the call by a branch to the normal destination. 2985// Update PHI nodes in the unwind destination 2989II->eraseFromParent();
2991 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
3000// Convert this function call into an invoke instruction. First, split the 3005// Delete the unconditional branch inserted by SplitBlock 3008// Create the new invoke instruction. 3014// Note: we're round tripping operand bundles through memory here, and that 3015// can potentially be avoided with a cleverer API design that we do not have 3020 UnwindEdge, InvokeArgs, OpBundles, CI->
getName(), BB);
3024II->setMetadata(LLVMContext::MD_prof, CI->
getMetadata(LLVMContext::MD_prof));
3027 DTU->
applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});
3029// Make sure that anything using the call now uses the invoke! This also 3030// updates the CallGraph if present, because it uses a WeakTrackingVH. 3033// Delete the original call 3034 Split->front().eraseFromParent();
3049// Do a quick scan of the basic block, turning any obviously unreachable 3050// instructions into LLVM unreachable insts. The instruction combining pass 3051// canonicalizes unreachable insts into stores to null or undef. 3053if (
auto *CI = dyn_cast<CallInst>(&
I)) {
3054Value *Callee = CI->getCalledOperand();
3055// Handle intrinsic calls. 3056if (
Function *
F = dyn_cast<Function>(Callee)) {
3057auto IntrinsicID =
F->getIntrinsicID();
3058// Assumptions that are known to be false are equivalent to 3059// unreachable. Also, if the condition is undefined, then we make the 3060// choice most beneficial to the optimizer, and choose that to also be 3062if (IntrinsicID == Intrinsic::assume) {
3064// Don't insert a call to llvm.trap right before the unreachable. 3069 }
elseif (IntrinsicID == Intrinsic::experimental_guard) {
3070// A call to the guard intrinsic bails out of the current 3071// compilation unit if the predicate passed to it is false. If the 3072// predicate is a constant false, then we know the guard will bail 3073// out of the current compile unconditionally, so all code following 3076// Note: unlike in llvm.assume, it is not "obviously profitable" for 3077// guards to treat `undef` as `false` since a guard on `undef` can 3078// still be useful for widening. 3080if (!isa<UnreachableInst>(CI->getNextNode())) {
3086 }
elseif ((isa<ConstantPointerNull>(Callee) &&
3088 cast<PointerType>(Callee->getType())
3089 ->getAddressSpace())) ||
3090 isa<UndefValue>(Callee)) {
3095if (CI->doesNotReturn() && !CI->isMustTailCall()) {
3096// If we found a call to a no-return function, insert an unreachable 3097// instruction after it. Make sure there isn't *already* one there 3099if (!isa<UnreachableInst>(CI->getNextNonDebugInstruction())) {
3100// Don't insert a call to llvm.trap right before the unreachable. 3106 }
elseif (
auto *SI = dyn_cast<StoreInst>(&
I)) {
3107// Store to undef and store to null are undefined and used to signal 3108// that they should be changed to unreachable by passes that can't 3111// Don't touch volatile stores. 3112if (SI->isVolatile())
continue;
3116if (isa<UndefValue>(
Ptr) ||
3117 (isa<ConstantPointerNull>(
Ptr) &&
3119 SI->getPointerAddressSpace()))) {
3128if (
auto *
II = dyn_cast<InvokeInst>(Terminator)) {
3129// Turn invokes that call 'nounwind' functions into ordinary calls. 3130Value *Callee =
II->getCalledOperand();
3131if ((isa<ConstantPointerNull>(Callee) &&
3133 isa<UndefValue>(Callee)) {
3137if (
II->doesNotReturn() &&
3138 !isa<UnreachableInst>(
II->getNormalDest()->front())) {
3139// If we found an invoke of a no-return function, 3140// create a new empty basic block with an `unreachable` terminator, 3141// and set it as the normal destination for the invoke, 3142// unless that is already the case. 3143// Note that the original normal destination could have other uses. 3148 Ctx, OrigNormalDest->
getName() +
".unreachable",
3149II->getFunction(), OrigNormalDest);
3151II->setNormalDest(UnreachableNormalDest);
3154 {{DominatorTree::Delete, BB, OrigNormalDest},
3155 {DominatorTree::Insert, BB, UnreachableNormalDest}});
3159if (
II->use_empty() && !
II->mayHaveSideEffects()) {
3160// jump to the normal destination branch. 3165II->eraseFromParent();
3167 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
3173 }
elseif (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
3174// Remove catchpads which cannot be reached. 3175structCatchPadDenseMapInfo {
3190if (
LHS == getEmptyKey() ||
LHS == getTombstoneKey() ||
3191RHS == getEmptyKey() ||
RHS == getTombstoneKey())
3193returnLHS->isIdenticalTo(
RHS);
3198// Set of unique CatchPads. 3204 E = CatchSwitch->handler_end();
3208 ++NumPerSuccessorCases[HandlerBB];
3210if (!HandlerSet.insert({CatchPad, Empty}).second) {
3212 --NumPerSuccessorCases[HandlerBB];
3213 CatchSwitch->removeHandler(
I);
3220 std::vector<DominatorTree::UpdateType> Updates;
3221for (
const std::pair<BasicBlock *, int> &
I : NumPerSuccessorCases)
3223 Updates.push_back({DominatorTree::Delete, BB,
I.first});
3224 DTU->applyUpdates(Updates);
3232 }
while (!Worklist.
empty());
3239if (
auto *
II = dyn_cast<InvokeInst>(TI))
3245if (
auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
3247 UnwindDest = CRI->getUnwindDest();
3248 }
elseif (
auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
3250 CatchSwitch->getParentPad(),
nullptr, CatchSwitch->getNumHandlers(),
3251 CatchSwitch->getName(), CatchSwitch->getIterator());
3252for (
BasicBlock *PadBB : CatchSwitch->handlers())
3253 NewCatchSwitch->addHandler(PadBB);
3255 NewTI = NewCatchSwitch;
3256 UnwindDest = CatchSwitch->getUnwindDest();
3267 DTU->
applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
3271/// removeUnreachableBlocks - Remove blocks that are not reachable, even 3272/// if they are in a dead cycle. Return true if a change was made, false 3279// If there are unreachable blocks in the CFG... 3280if (Reachable.
size() ==
F.size())
3285// Are there any blocks left to actually delete? 3288// Skip reachable basic blocks 3289if (Reachable.
count(&BB))
3291// Skip already-deleted blocks 3294 BlocksToRemove.
insert(&BB);
3297if (BlocksToRemove.
empty())
3301 NumRemoved += BlocksToRemove.
size();
3311/// If AAOnly is set, only intersect alias analysis metadata and preserve other 3312/// known metadata. Unknown metadata is always dropped. 3314bool DoesKMove,
bool AAOnly =
false) {
3316 K->getAllMetadataOtherThanDebugLoc(
Metadata);
3318unsigned Kind = MD.first;
3322// TODO: Assert that this switch is exhaustive for fixed MD kinds. 3325 K->setMetadata(Kind,
nullptr);
// Remove unknown metadata 3327case LLVMContext::MD_dbg:
3329case LLVMContext::MD_DIAssignID:
3331 K->mergeDIAssignID(J);
3333case LLVMContext::MD_tbaa:
3337case LLVMContext::MD_alias_scope:
3341case LLVMContext::MD_noalias:
3342case LLVMContext::MD_mem_parallel_loop_access:
3346case LLVMContext::MD_access_group:
3348 K->setMetadata(LLVMContext::MD_access_group,
3351case LLVMContext::MD_range:
3352if (!AAOnly && (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef)))
3355case LLVMContext::MD_fpmath:
3359case LLVMContext::MD_invariant_load:
3360// If K moves, only set the !invariant.load if it is present in both 3363 K->setMetadata(Kind, JMD);
3365case LLVMContext::MD_nonnull:
3366if (!AAOnly && (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef)))
3367 K->setMetadata(Kind, JMD);
3369case LLVMContext::MD_invariant_group:
3370// Preserve !invariant.group in K. 3372case LLVMContext::MD_mmra:
3375case LLVMContext::MD_align:
3376if (!AAOnly && (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef)))
3380case LLVMContext::MD_dereferenceable:
3381case LLVMContext::MD_dereferenceable_or_null:
3382if (!AAOnly && DoesKMove)
3383 K->setMetadata(Kind,
3386case LLVMContext::MD_memprof:
3390case LLVMContext::MD_callsite:
3394case LLVMContext::MD_preserve_access_index:
3395// Preserve !preserve.access.index in K. 3397case LLVMContext::MD_noundef:
3398// If K does move, keep noundef if it is present in both instructions. 3399if (!AAOnly && DoesKMove)
3400 K->setMetadata(Kind, JMD);
3402case LLVMContext::MD_nontemporal:
3403// Preserve !nontemporal if it is present on both instructions. 3405 K->setMetadata(Kind, JMD);
3407case LLVMContext::MD_prof:
3408if (!AAOnly && DoesKMove)
3411case LLVMContext::MD_noalias_addrspace:
3413 K->setMetadata(Kind,
3418// Set !invariant.group from J if J has it. If both instructions have it 3419// then we will just pick it from J - even when they are different. 3420// Also make sure that K is load or store - f.e. combining bitcast with load 3421// could produce bitcast with invariant.group metadata, which is invalid. 3422// FIXME: we should try to preserve both invariant.group md if they are 3423// different, but right now instruction can only have one invariant.group. 3424if (
auto *JMD = J->
getMetadata(LLVMContext::MD_invariant_group))
3425if (isa<LoadInst>(K) || isa<StoreInst>(K))
3426 K->setMetadata(LLVMContext::MD_invariant_group, JMD);
3429// This is handled separately because we also want to handle cases where K 3430// doesn't have tags but J does. 3432auto KMMRA = K->getMetadata(LLVMContext::MD_mmra);
3433if (JMMRA || KMMRA) {
3434 K->setMetadata(LLVMContext::MD_mmra,
3450 Source.getAllMetadata(MD);
3454for (
constauto &MDPair : MD) {
3455unsignedID = MDPair.first;
3457// Note, essentially every kind of metadata should be preserved here! This 3458// routine is supposed to clone a load instruction changing *only its type*. 3459// The only metadata it makes sense to drop is metadata which is invalidated 3460// when the pointer type changes. This should essentially never be the case 3461// in LLVM, but we explicitly switch over only known metadata to be 3462// conservatively correct. If you are adding metadata to LLVM which pertains 3463// to loads, you almost certainly want to add it here. 3465case LLVMContext::MD_dbg:
3466case LLVMContext::MD_tbaa:
3467case LLVMContext::MD_prof:
3468case LLVMContext::MD_fpmath:
3469case LLVMContext::MD_tbaa_struct:
3470case LLVMContext::MD_invariant_load:
3471case LLVMContext::MD_alias_scope:
3472case LLVMContext::MD_noalias:
3473case LLVMContext::MD_nontemporal:
3474case LLVMContext::MD_mem_parallel_loop_access:
3475case LLVMContext::MD_access_group:
3476case LLVMContext::MD_noundef:
3477// All of these directly apply. 3481case LLVMContext::MD_nonnull:
3485case LLVMContext::MD_align:
3486case LLVMContext::MD_dereferenceable:
3487case LLVMContext::MD_dereferenceable_or_null:
3488// These only directly apply if the new type is also a pointer. 3493case LLVMContext::MD_range:
3501auto *ReplInst = dyn_cast<Instruction>(Repl);
3505// Patch the replacement so that it is not more restrictive than the value 3508// When replacing the result of a llvm.*.with.overflow intrinsic with a 3509// overflowing binary operator, nuw/nsw flags may no longer hold. 3510if (isa<OverflowingBinaryOperator>(ReplInst) &&
3513// Note that if 'I' is a load being replaced by some operation, 3514// for example, by an arithmetic operation, then andIRFlags() 3515// would just erase all math flags from the original arithmetic 3516// operation, which is clearly not wanted and not needed. 3517elseif (!isa<LoadInst>(
I))
3518 ReplInst->andIRFlags(
I);
3520// Handle attributes. 3521if (
auto *CB1 = dyn_cast<CallBase>(ReplInst)) {
3522if (
auto *CB2 = dyn_cast<CallBase>(
I)) {
3523boolSuccess = CB1->tryIntersectAttributes(CB2);
3524assert(
Success &&
"We should not be trying to sink callbases " 3525"with non-intersectable attributes");
3526// For NDEBUG Compile. 3531// FIXME: If both the original and replacement value are part of the 3532// same control-flow region (meaning that the execution of one 3533// guarantees the execution of the other), then we can combine the 3534// noalias scopes here and do better than the general conservative 3535// answer used in combineMetadata(). 3537// In general, GVN unifies expressions over different control-flow 3538// regions, and so we need a conservative combination of the noalias 3543template <
typename RootType,
typename ShouldReplaceFn>
3545const RootType &Root,
3546const ShouldReplaceFn &ShouldReplace) {
3551auto *
II = dyn_cast<IntrinsicInst>(U.getUser());
3552if (
II &&
II->getIntrinsicID() == Intrinsic::fake_use)
3554if (!ShouldReplace(Root, U))
3558dbgs() <<
"' with " << *To <<
" in " << *U.getUser() <<
"\n");
3567auto *BB =
From->getParent();
3571auto *
I = cast<Instruction>(U.getUser());
3572if (
I->getParent() == BB)
3586 return ::replaceDominatedUsesWith(
From, To, Root, Dominates);
3595 return ::replaceDominatedUsesWith(
From, To, BB, Dominates);
3601auto DominatesAndShouldReplace =
3603return DT.
dominates(Root, U) && ShouldReplace(U, To);
3605 return ::replaceDominatedUsesWith(
From, To, Root, DominatesAndShouldReplace);
3611auto DominatesAndShouldReplace = [&DT, &ShouldReplace,
3613return DT.
dominates(BB, U) && ShouldReplace(U, To);
3615 return ::replaceDominatedUsesWith(
From, To, BB, DominatesAndShouldReplace);
3620// Check if the function is specifically marked as a gc leaf function. 3621if (Call->hasFnAttr(
"gc-leaf-function"))
3623if (
constFunction *
F = Call->getCalledFunction()) {
3624if (
F->hasFnAttribute(
"gc-leaf-function"))
3627if (
auto IID =
F->getIntrinsicID()) {
3628// Most LLVM intrinsics do not take safepoints. 3629return IID != Intrinsic::experimental_gc_statepoint &&
3630 IID != Intrinsic::experimental_deoptimize &&
3631 IID != Intrinsic::memcpy_element_unordered_atomic &&
3632 IID != Intrinsic::memmove_element_unordered_atomic;
3636// Lib calls can be materialized by some passes, and won't be 3637// marked as 'gc-leaf-function.' All available Libcalls are 3651// This only directly applies if the new type is also a pointer. 3652if (NewTy->isPointerTy()) {
3657// The only other translation we can do is to integral loads with !range 3659if (!NewTy->isIntegerTy())
3664auto *ITy = cast<IntegerType>(NewTy);
3675// Simply copy the metadata if the type did not change. 3676if (NewTy == OldLI.
getType()) {
3681// Give up unless it is converted to a pointer where there is a single very 3682// valuable mapping we can do reliably. 3683// FIXME: It would be nice to propagate this in more ways, but the type 3684// conversions make it hard. 3685if (!NewTy->isPointerTy())
3688unsignedBitWidth =
DL.getPointerTypeSizeInBits(NewTy);
3700for (
auto *DII : DbgUsers)
3702for (
auto *DVR : DPUsers)
3703 DVR->eraseFromParent();
3708// Since we are moving the instructions out of its basic block, we do not 3709// retain their original debug locations (DILocations) and debug intrinsic 3712// Doing so would degrade the debugging experience and adversely affect the 3713// accuracy of profiling information. 3715// Currently, when hoisting the instructions, we take the following actions: 3716// - Remove their debug intrinsic instructions. 3717// - Set their debug locations to the values from the insertion point. 3719// As per PR39141 (comment #8), the more fundamental reason why the dbg.values 3720// need to be deleted, is because there will not be any instructions with a 3721// DILocation in either branch left after performing the transformation. We 3722// can only insert a dbg.value after the two branches are joined again. 3724// See PR38762, PR39243 for more details. 3726// TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to 3727// encode predicated DIExpressions that yield different results on different 3732I->dropUBImplyingAttrsAndMetadata();
3733if (
I->isUsedByMetadata())
3735// RemoveDIs: drop debug-info too as the following code does. 3737if (
I->isDebugOrPseudoInst()) {
3738// Remove DbgInfo and pseudo probe Intrinsics. 3739II =
I->eraseFromParent();
3751// Create integer constant expression. 3753constAPInt &API = cast<ConstantInt>(&CV)->getValue();
3754 std::optional<int64_t> InitIntOpt = API.
trySExtValue();
3760if (isa<ConstantInt>(
C))
3761return createIntegerExpression(
C);
3763auto *
FP = dyn_cast<ConstantFP>(&
C);
3775if (isa<ConstantPointerNull>(
C))
3779if (CE->getOpcode() == Instruction::IntToPtr) {
3780constValue *V = CE->getOperand(0);
3781if (
auto CI = dyn_cast_or_null<ConstantInt>(V))
3782return createIntegerExpression(*CI);
3788auto RemapDebugOperands = [&Mapping](
auto *DV,
auto Set) {
3789for (
auto *
Op : Set) {
3791if (
I != Mapping.
end())
3792 DV->replaceVariableLocationOp(
Op,
I->second,
/*AllowEmpty=*/true);
3795auto RemapAssignAddress = [&Mapping](
auto *DA) {
3796autoI = Mapping.
find(DA->getAddress());
3797if (
I != Mapping.
end())
3798 DA->setAddress(
I->second);
3800if (
auto DVI = dyn_cast<DbgVariableIntrinsic>(Inst))
3801 RemapDebugOperands(DVI, DVI->location_ops());
3802if (
auto DAI = dyn_cast<DbgAssignIntrinsic>(Inst))
3803 RemapAssignAddress(DAI);
3805 RemapDebugOperands(&DVR, DVR.location_ops());
3806if (DVR.isDbgAssign())
3807 RemapAssignAddress(&DVR);
3813/// A potential constituent of a bitreverse or bswap expression. See 3814/// collectBitParts for a fuller explanation. 3816 BitPart(
Value *
P,
unsigned BW) : Provider(
P) {
3820 /// The Value that this is a bitreverse/bswap of. 3823 /// The "provenance" of each bit. Provenance[A] = B means that bit A 3824 /// in Provider becomes bit B in the result of this expression. 3830}
// end anonymous namespace 3832/// Analyze the specified subexpression and see if it is capable of providing 3833/// pieces of a bswap or bitreverse. The subexpression provides a potential 3834/// piece of a bswap or bitreverse if it can be proved that each non-zero bit in 3835/// the output of the expression came from a corresponding bit in some other 3836/// value. This function is recursive, and the end result is a mapping of 3837/// bitnumber to bitnumber. It is the caller's responsibility to validate that 3838/// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse. 3840/// For example, if the current subexpression if "(shl i32 %X, 24)" then we know 3841/// that the expression deposits the low byte of %X into the high byte of the 3842/// result and that all other bits are zero. This expression is accepted and a 3843/// BitPart is returned with Provider set to %X and Provenance[24-31] set to 3846/// For vector types, all analysis is performed at the per-element level. No 3847/// cross-element analysis is supported (shuffle/insertion/reduction), and all 3848/// constant masks must be splatted across all elements. 3850/// To avoid revisiting values, the BitPart results are memoized into the 3851/// provided map. To avoid unnecessary copying of BitParts, BitParts are 3852/// constructed in-place in the \c BPS map. Because of this \c BPS needs to 3853/// store BitParts objects, not pointers. As we need the concept of a nullptr 3854/// BitParts (Value has been analyzed and the analysis failed), we an Optional 3855/// type instead to provide the same functionality. 3857/// Because we pass around references into \c BPS, we must use a container that 3858/// does not invalidate internal references (std::map instead of DenseMap). 3859staticconst std::optional<BitPart> &
3861 std::map<
Value *, std::optional<BitPart>> &BPS,
intDepth,
3863auto [
I, Inserted] = BPS.try_emplace(V);
3867auto &Result =
I->second;
3868autoBitWidth = V->getType()->getScalarSizeInBits();
3870// Can't do integer/elements > 128 bits. 3874// Prevent stack overflow by limiting the recursion depth 3876LLVM_DEBUG(
dbgs() <<
"collectBitParts max recursion depth reached.\n");
3880if (
auto *
I = dyn_cast<Instruction>(V)) {
3884// If this is an or instruction, it may be an inner node of the bswap. 3886// Check we have both sources and they are from the same provider. 3888Depth + 1, FoundRoot);
3889if (!
A || !
A->Provider)
3893Depth + 1, FoundRoot);
3894if (!
B ||
A->Provider !=
B->Provider)
3897// Try and merge the two together. 3899for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx) {
3900if (
A->Provenance[BitIdx] != BitPart::Unset &&
3901B->Provenance[BitIdx] != BitPart::Unset &&
3902A->Provenance[BitIdx] !=
B->Provenance[BitIdx])
3903return Result = std::nullopt;
3905if (
A->Provenance[BitIdx] == BitPart::Unset)
3906 Result->Provenance[BitIdx] =
B->Provenance[BitIdx];
3908 Result->Provenance[BitIdx] =
A->Provenance[BitIdx];
3914// If this is a logical shift by a constant, recurse then shift the result. 3916constAPInt &BitShift = *
C;
3918// Ensure the shift amount is defined. 3922// For bswap-only, limit shift amounts to whole bytes, for an early exit. 3923if (!MatchBitReversals && (BitShift.
getZExtValue() % 8) != 0)
3927Depth + 1, FoundRoot);
3932// Perform the "shift" on BitProvenance. 3933auto &
P = Result->Provenance;
3934if (
I->getOpcode() == Instruction::Shl) {
3945// If this is a logical 'and' with a mask that clears bits, recurse then 3946// unset the appropriate bits. 3950// Check that the mask allows a multiple of 8 bits for a bswap, for an 3952unsigned NumMaskedBits = AndMask.
popcount();
3953if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3957Depth + 1, FoundRoot);
3962for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3963// If the AndMask is zero for this bit, clear the bit. 3964if (AndMask[BitIdx] == 0)
3965 Result->Provenance[BitIdx] = BitPart::Unset;
3969// If this is a zext instruction zero extend the result. 3972Depth + 1, FoundRoot);
3976 Result = BitPart(Res->Provider,
BitWidth);
3977auto NarrowBitWidth =
X->getType()->getScalarSizeInBits();
3978for (
unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3979 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3980for (
unsigned BitIdx = NarrowBitWidth; BitIdx <
BitWidth; ++BitIdx)
3981 Result->Provenance[BitIdx] = BitPart::Unset;
3985// If this is a truncate instruction, extract the lower bits. 3988Depth + 1, FoundRoot);
3992 Result = BitPart(Res->Provider,
BitWidth);
3993for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
3994 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3998// BITREVERSE - most likely due to us previous matching a partial 4002Depth + 1, FoundRoot);
4006 Result = BitPart(Res->Provider,
BitWidth);
4007for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
4008 Result->Provenance[(
BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
4012// BSWAP - most likely due to us previous matching a partial bswap. 4015Depth + 1, FoundRoot);
4020 Result = BitPart(Res->Provider,
BitWidth);
4021for (
unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
4022unsigned ByteBitOfs = ByteIdx * 8;
4023for (
unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
4024 Result->Provenance[(
BitWidth - 8 - ByteBitOfs) + BitIdx] =
4025 Res->Provenance[ByteBitOfs + BitIdx];
4030// Funnel 'double' shifts take 3 operands, 2 inputs and the shift 4032// fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW))) 4033// fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW)) 4036// We can treat fshr as a fshl by flipping the modulo amount. 4041// For bswap-only, limit shift amounts to whole bytes, for an early exit. 4042if (!MatchBitReversals && (ModAmt % 8) != 0)
4045// Check we have both sources and they are from the same provider. 4047Depth + 1, FoundRoot);
4048if (!
LHS || !
LHS->Provider)
4052Depth + 1, FoundRoot);
4053if (!
RHS ||
LHS->Provider !=
RHS->Provider)
4056unsigned StartBitRHS =
BitWidth - ModAmt;
4058for (
unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
4059 Result->Provenance[BitIdx + ModAmt] =
LHS->Provenance[BitIdx];
4060for (
unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
4061 Result->Provenance[BitIdx] =
RHS->Provenance[BitIdx + StartBitRHS];
4066// If we've already found a root input value then we're never going to merge 4067// these back together. 4071// Okay, we got to something that isn't a shift, 'or', 'and', etc. This must 4072// be the root input value to the bswap/bitreverse. 4075for (
unsigned BitIdx = 0; BitIdx <
BitWidth; ++BitIdx)
4076 Result->Provenance[BitIdx] = BitIdx;
4082if (
From % 8 != To % 8)
4084// Convert from bit indices to byte indices and check for a byte reversal. 4104if (!MatchBSwaps && !MatchBitReversals)
4106Type *ITy =
I->getType();
4108returnfalse;
// Can't do integer/elements > 128 bits. 4110// Try to find all the pieces corresponding to the bswap. 4111bool FoundRoot =
false;
4112 std::map<Value *, std::optional<BitPart>> BPS;
4119 [](int8_t
I) {
returnI == BitPart::Unset || 0 <=
I; }) &&
4120"Illegal bit provenance index");
4122// If the upper bits are zero, then attempt to perform as a truncated op. 4123Type *DemandedTy = ITy;
4124if (BitProvenance.
back() == BitPart::Unset) {
4125while (!BitProvenance.
empty() && BitProvenance.
back() == BitPart::Unset)
4126 BitProvenance = BitProvenance.
drop_back();
4127if (BitProvenance.
empty())
4128returnfalse;
// TODO - handle null value? 4130if (
auto *IVecTy = dyn_cast<VectorType>(ITy))
4131 DemandedTy = VectorType::get(DemandedTy, IVecTy);
4134// Check BitProvenance hasn't found a source larger than the result type. 4139// Now, is the bit permutation correct for a bswap or a bitreverse? We can 4140// only byteswap values with an even number of bytes. 4142bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
4143bool OKForBitReverse = MatchBitReversals;
4144for (
unsigned BitIdx = 0;
4145 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
4146if (BitProvenance[BitIdx] == BitPart::Unset) {
4153 BitIdx, DemandedBW);
4158 Intrin = Intrinsic::bswap;
4159elseif (OKForBitReverse)
4160 Intrin = Intrinsic::bitreverse;
4166Value *Provider = Res->Provider;
4168// We may need to truncate the provider. 4169if (DemandedTy != Provider->
getType()) {
4180auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
4185// We may need to zeroextend back to the result type. 4186if (ITy != Result->getType()) {
4194// CodeGen has special handling for some string functions that may replace 4195// them with target-specific intrinsics. Since that'd skip our interceptors 4196// in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses, 4197// we mark affected calls as NoBuiltin, which will disable optimization 4203if (
F && !
F->hasLocalLinkage() &&
F->hasName() &&
4205 !
F->doesNotAccessMemory())
4210// We can't have a PHI with a metadata type. 4211if (
I->getOperand(OpIdx)->getType()->isMetadataTy())
4215if (!isa<Constant>(
I->getOperand(OpIdx)))
4218switch (
I->getOpcode()) {
4221case Instruction::Call:
4222case Instruction::Invoke: {
4223constauto &CB = cast<CallBase>(*
I);
4225// Can't handle inline asm. Skip it. 4226if (CB.isInlineAsm())
4229// Constant bundle operands may need to retain their constant-ness for 4231if (CB.isBundleOperand(OpIdx))
4234if (OpIdx < CB.arg_size()) {
4235// Some variadic intrinsics require constants in the variadic arguments, 4236// which currently aren't markable as immarg. 4237if (isa<IntrinsicInst>(CB) &&
4238 OpIdx >= CB.getFunctionType()->getNumParams()) {
4239// This is known to be OK for stackmap. 4240return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
4243// gcroot is a special case, since it requires a constant argument which 4244// isn't also required to be a simple ConstantInt. 4245if (CB.getIntrinsicID() == Intrinsic::gcroot)
4248// Some intrinsic operands are required to be immediates. 4249return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
4252// It is never allowed to replace the call argument to an intrinsic, but it 4253// may be possible for a call. 4254return !isa<IntrinsicInst>(CB);
4256case Instruction::ShuffleVector:
4257// Shufflevector masks are constant. 4259case Instruction::Switch:
4260case Instruction::ExtractValue:
4261// All operands apart from the first are constant. 4263case Instruction::InsertValue:
4264// All operands apart from the first and the second are constant. 4266case Instruction::Alloca:
4267// Static allocas (constant size in the entry block) are handled by 4268// prologue/epilogue insertion so they're free anyway. We definitely don't 4269// want to make them non-constant. 4270return !cast<AllocaInst>(
I)->isStaticAlloca();
4271case Instruction::GetElementPtr:
4275for (
auto E = std::next(It, OpIdx); It != E; ++It)
4283// First: Check if it's a constant 4284if (
Constant *
C = dyn_cast<Constant>(Condition))
4287// Second: If the condition is already inverted, return the original value 4293Instruction *Inst = dyn_cast<Instruction>(Condition);
4296elseif (
Argument *Arg = dyn_cast<Argument>(Condition))
4298assert(Parent &&
"Unsupported condition to invert");
4300// Third: Check all the users for an invert 4306// Last option: Create a new instruction 4309if (Inst && !isa<PHINode>(Inst))
4317// Note: We explicitly check for attributes rather than using cover functions 4318// because some of the cover functions include the logic being implemented. 4321// readnone + not convergent implies nosync 4322if (!
F.hasFnAttribute(Attribute::NoSync) &&
4323F.doesNotAccessMemory() && !
F.isConvergent()) {
4328// readonly implies nofree 4329if (!
F.hasFnAttribute(Attribute::NoFree) &&
F.onlyReadsMemory()) {
4330F.setDoesNotFreeMemory();
4334// willreturn implies mustprogress 4335if (!
F.hasFnAttribute(Attribute::MustProgress) &&
F.willReturn()) {
4340// TODO: There are a bunch of cases of restrictive memory effects we 4341// can infer by inspecting arguments of argmemonly-ish functions. for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static unsigned getIntrinsicID(const SDNode *N)
This file implements a class to represent arbitrary precision integral constant values and operations...
ReachingDefAnalysis InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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")
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
iv Induction Variable Users
This file provides utility for Memory Model Relaxation Annotations (MMRAs).
This file contains the declarations for metadata subclasses.
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
Remove Loads Into Fake Uses
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
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)
static bool markAliveBlocks(Function &F, SmallPtrSetImpl< BasicBlock * > &Reachable, DomTreeUpdater *DTU=nullptr)
static bool valueCoversEntireFragment(Type *ValTy, DbgVariableIntrinsic *DII)
Check if the alloc size of ValTy is large enough to cover the variable (or fragment of the variable) ...
static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy, Type *ToTy)
Check if a bitcast between a value of type FromTy to type ToTy would losslessly preserve the bits and...
static bool isStructure(AllocaInst *AI)
Determine whether this alloca is a structure.
uint64_t getDwarfOpForBinOp(Instruction::BinaryOps Opcode)
static bool PhiHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr, PHINode *APN)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
static void gatherIncomingValuesToPhi(PHINode *PN, IncomingValueMap &IncomingValues)
Create a map from block to value for the operands of a given phi.
static void combineMetadata(Instruction *K, const Instruction *J, bool DoesKMove, bool AAOnly=false)
If AAOnly is set, only intersect alias analysis metadata and preserve other known metadata.
static void handleSSAValueOperands(uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues, Instruction *I)
std::optional< DIExpression * > DbgValReplacement
A replacement for a dbg.value expression.
static void insertDbgValueOrDbgVariableRecordAfter(DIBuilder &Builder, Value *DV, DILocalVariable *DIVar, DIExpression *DIExpr, const DebugLoc &NewLoc, BasicBlock::iterator Instr)
Value * getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
static DIExpression * dropInitialDeref(const DIExpression *DIExpr)
static void replaceUndefValuesInPhi(PHINode *PN, const IncomingValueMap &IncomingValues)
Replace the incoming undef values to a phi with the values from a block-to-value map.
Value * getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
static bool CanRedirectPredsOfEmptyBBToSucc(BasicBlock *BB, BasicBlock *Succ, const SmallPtrSetImpl< BasicBlock * > &BBPreds, BasicBlock *&CommonPred)
Value * getSalvageOpsForIcmpOp(ICmpInst *Icmp, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
static bool CanMergeValues(Value *First, Value *Second)
Return true if we can choose one of these values to use in place of the other.
static bool simplifyAndDCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const DataLayout &DL, const TargetLibraryInfo *TLI)
static bool isArray(AllocaInst *AI)
Determine whether this alloca is either a VLA or an array.
static bool areAllUsesEqual(Instruction *I)
areAllUsesEqual - Check whether the uses of a value are all the same.
static cl::opt< bool > PHICSEDebugHash("phicse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that PHINodes's hash " "function is well-behaved w.r.t. its isEqual predicate"))
static unsigned replaceDominatedUsesWith(Value *From, Value *To, const RootType &Root, const ShouldReplaceFn &ShouldReplace)
uint64_t getDwarfOpForIcmpPred(CmpInst::Predicate Pred)
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
static const std::optional< BitPart > & collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, std::map< Value *, std::optional< BitPart > > &BPS, int Depth, bool &FoundRoot)
Analyze the specified subexpression and see if it is capable of providing pieces of a bswap or bitrev...
static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB, SmallPtrSetImpl< PHINode * > &ToRemove)
static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ, const SmallPtrSetImpl< BasicBlock * > &BBPreds)
Return true if we can fold BB, an almost-empty BB ending in an unconditional branch to Succ,...
static cl::opt< unsigned > PHICSENumPHISmallSize("phicse-num-phi-smallsize", cl::init(32), cl::Hidden, cl::desc("When the basic block contains not more than this number of PHI nodes, " "perform a (faster!) exhaustive search instead of set-driven one."))
static bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB, SmallPtrSetImpl< PHINode * > &ToRemove)
static bool rewriteDebugUsers(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT, function_ref< DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr, function_ref< DbgValReplacement(DbgVariableRecord &DVR)> RewriteDVRExpr)
Point debug users of From to To using exprs given by RewriteExpr, possibly moving/undefing users to p...
static void insertDbgValueOrDbgVariableRecord(DIBuilder &Builder, Value *DV, DILocalVariable *DIVar, DIExpression *DIExpr, const DebugLoc &NewLoc, BasicBlock::iterator Instr)
static bool introduceTooManyPhiEntries(BasicBlock *BB, BasicBlock *Succ)
Check whether removing BB will make the phis in its Succ have too many incoming entries.
static Value * selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, IncomingValueMap &IncomingValues)
Determines the value to use as the phi node input for a block.
static void updateOneDbgValueForAlloca(const DebugLoc &Loc, DILocalVariable *DIVar, DIExpression *DIExpr, Value *NewAddress, DbgValueInst *DVI, DbgVariableRecord *DVR, DIBuilder &Builder, int Offset)
static void insertDbgVariableRecordsForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode * > &InsertedPHIs)
static const unsigned BitPartRecursionMaxDepth
static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, const PredBlockVector &BBPreds, PHINode *PN, BasicBlock *CommonPred)
Replace a value flowing from a block to a phi with potentially multiple instances of that value flowi...
static cl::opt< unsigned > MaxPhiEntriesIncreaseAfterRemovingEmptyBlock("max-phi-entries-increase-after-removing-empty-block", cl::init(1000), cl::Hidden, cl::desc("Stop removing an empty block if removing it will introduce more " "than this number of phi entries in its successor"))
cl::opt< bool > UseNewDbgInfoFormat
static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, unsigned BitWidth)
static void salvageDbgAssignAddress(T *Assign)
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.
ArrayRef< T > drop_front(size_t N=1) const
Drop the first N elements of the array.
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 & 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...
InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
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.
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 attributes for this call.
FunctionType * getFunctionType() const
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
AttributeList getAttributes() const
Return the 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...
ArrayRef< uint64_t > getElements() const
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< UpdateT > Updates)
Submit updates to all available trees.
void applyUpdates(ArrayRef< UpdateT > 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, bool IntersectAttrs=false) 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 * getMergedCallsiteMetadata(MDNode *A, MDNode *B)
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
static MDNode * getMostGenericNoaliasAddrspace(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 * getMergedMemProfMetadata(MDNode *A, MDNode *B)
static MDNode * intersect(MDNode *A, MDNode *B)
LLVMContext & getContext() const
static MDNode * getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B)
static MDNode * combine(LLVMContext &Ctx, const MMRAMetadata &A, const MMRAMetadata &B)
Combines A and B according to MMRA semantics.
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 > try_emplace(const KeyT &Key, Ts &&...Args)
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.
Root of the metadata hierarchy.
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.
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()
Value wrapper in the Metadata hierarchy.
static ValueAsMetadata * get(Value *V)
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 * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
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.
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...
auto pred_end(const MachineBasicBlock *BB)
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...
void InsertDebugValueAtStoreLoc(DbgVariableRecord *DVR, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
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...
auto pred_size(const MachineBasicBlock *BB)
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.
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)
Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value that has an associated llvm....
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.
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...
auto pred_begin(const MachineBasicBlock *BB)
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.
void combineAAMetadata(Instruction *K, const Instruction *J)
Combine metadata of two instructions, where instruction J is a memory access that has been merged int...
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...
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.
A MapVector that performs no allocations if smaller than a certain size.
