1//===- Local.cpp - Functions to perform local transformations -------------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This family of functions perform various local transformations to the
10// program.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/Utils/Local.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/Hashing.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SetVector.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/AssumeBundleQueries.h"
25#include "llvm/Analysis/ConstantFolding.h"
26#include "llvm/Analysis/DomTreeUpdater.h"
27#include "llvm/Analysis/InstructionSimplify.h"
28#include "llvm/Analysis/MemoryBuiltins.h"
29#include "llvm/Analysis/MemorySSAUpdater.h"
30#include "llvm/Analysis/TargetLibraryInfo.h"
31#include "llvm/Analysis/ValueTracking.h"
32#include "llvm/Analysis/VectorUtils.h"
33#include "llvm/BinaryFormat/Dwarf.h"
34#include "llvm/IR/Argument.h"
35#include "llvm/IR/Attributes.h"
36#include "llvm/IR/BasicBlock.h"
37#include "llvm/IR/CFG.h"
38#include "llvm/IR/Constant.h"
39#include "llvm/IR/ConstantRange.h"
40#include "llvm/IR/Constants.h"
41#include "llvm/IR/DIBuilder.h"
42#include "llvm/IR/DataLayout.h"
43#include "llvm/IR/DebugInfo.h"
44#include "llvm/IR/DebugInfoMetadata.h"
45#include "llvm/IR/DebugLoc.h"
46#include "llvm/IR/DerivedTypes.h"
47#include "llvm/IR/Dominators.h"
48#include "llvm/IR/EHPersonalities.h"
49#include "llvm/IR/Function.h"
50#include "llvm/IR/GetElementPtrTypeIterator.h"
51#include "llvm/IR/IRBuilder.h"
52#include "llvm/IR/InstrTypes.h"
53#include "llvm/IR/Instruction.h"
54#include "llvm/IR/Instructions.h"
55#include "llvm/IR/IntrinsicInst.h"
56#include "llvm/IR/Intrinsics.h"
57#include "llvm/IR/IntrinsicsWebAssembly.h"
58#include "llvm/IR/LLVMContext.h"
59#include "llvm/IR/MDBuilder.h"
60#include "llvm/IR/MemoryModelRelaxationAnnotations.h"
61#include "llvm/IR/Metadata.h"
62#include "llvm/IR/Module.h"
63#include "llvm/IR/PatternMatch.h"
64#include "llvm/IR/ProfDataUtils.h"
65#include "llvm/IR/Type.h"
66#include "llvm/IR/Use.h"
67#include "llvm/IR/User.h"
68#include "llvm/IR/Value.h"
69#include "llvm/IR/ValueHandle.h"
70#include "llvm/Support/Casting.h"
71#include "llvm/Support/CommandLine.h"
72#include "llvm/Support/Compiler.h"
73#include "llvm/Support/Debug.h"
74#include "llvm/Support/ErrorHandling.h"
75#include "llvm/Support/KnownBits.h"
76#include "llvm/Support/raw_ostream.h"
77#include "llvm/Transforms/Utils/BasicBlockUtils.h"
78#include "llvm/Transforms/Utils/ValueMapper.h"
79#include <algorithm>
80#include <cassert>
81#include <cstdint>
82#include <iterator>
83#include <map>
84#include <optional>
85#include <utility>
86
87using namespace llvm;
88using namespace llvm::PatternMatch;
89
90#define DEBUG_TYPE "local"
91
92STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
93STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd");
94
95static cl::opt<bool> PHICSEDebugHash(
96 "phicse-debug-hash",
97#ifdef EXPENSIVE_CHECKS
98 cl::init(true),
99#else
100 cl::init(Val: false),
101#endif
102 cl::Hidden,
103 cl::desc("Perform extra assertion checking to verify that PHINodes's hash "
104 "function is well-behaved w.r.t. its isEqual predicate"));
105
106static cl::opt<unsigned> PHICSENumPHISmallSize(
107 "phicse-num-phi-smallsize", cl::init(Val: 32), cl::Hidden,
108 cl::desc(
109 "When the basic block contains not more than this number of PHI nodes, "
110 "perform a (faster!) exhaustive search instead of set-driven one."));
111
112static cl::opt<unsigned> MaxPhiEntriesIncreaseAfterRemovingEmptyBlock(
113 "max-phi-entries-increase-after-removing-empty-block", cl::init(Val: 1000),
114 cl::Hidden,
115 cl::desc("Stop removing an empty block if removing it will introduce more "
116 "than this number of phi entries in its successor"));
117
118// Max recursion depth for collectBitParts used when detecting bswap and
119// bitreverse idioms.
120static const unsigned BitPartRecursionMaxDepth = 48;
121
122//===----------------------------------------------------------------------===//
123// Local constant propagation.
124//
125
126/// ConstantFoldTerminator - If a terminator instruction is predicated on a
127/// constant value, convert it into an unconditional branch to the constant
128/// destination. This is a nontrivial operation because the successors of this
129/// basic block must have their PHI nodes updated.
130/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
131/// conditions and indirectbr addresses this might make dead if
132/// DeleteDeadConditions is true.
133bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
134 const TargetLibraryInfo *TLI,
135 DomTreeUpdater *DTU) {
136 Instruction *T = BB->getTerminator();
137
138 // Branch - See if we are conditional jumping on constant
139 if (auto *BI = dyn_cast<CondBrInst>(Val: T)) {
140 BasicBlock *Dest1 = BI->getSuccessor(i: 0);
141 BasicBlock *Dest2 = BI->getSuccessor(i: 1);
142
143 if (Dest2 == Dest1) { // Conditional branch to same location?
144 // This branch matches something like this:
145 // br bool %cond, label %Dest, label %Dest
146 // and changes it into: br label %Dest
147
148 // Let the basic block know that we are letting go of one copy of it.
149 assert(BI->getParent() && "Terminator not inserted in block!");
150 Dest1->removePredecessor(Pred: BI->getParent());
151
152 // Replace the conditional branch with an unconditional one.
153 IRBuilder<> Builder(BI);
154 UncondBrInst *NewBI = Builder.CreateBr(Dest: Dest1);
155
156 // Transfer the metadata to the new branch instruction.
157 NewBI->copyMetadata(SrcInst: *BI, WL: {LLVMContext::MD_loop, LLVMContext::MD_dbg,
158 LLVMContext::MD_annotation});
159
160 Value *Cond = BI->getCondition();
161 BI->eraseFromParent();
162 if (DeleteDeadConditions)
163 RecursivelyDeleteTriviallyDeadInstructions(V: Cond, TLI);
164 return true;
165 }
166
167 if (auto *Cond = dyn_cast<ConstantInt>(Val: BI->getCondition())) {
168 // Are we branching on constant?
169 // YES. Change to unconditional branch...
170 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
171 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;
172
173 // Let the basic block know that we are letting go of it. Based on this,
174 // it will adjust its PHI nodes.
175 OldDest->removePredecessor(Pred: BB);
176
177 // Replace the conditional branch with an unconditional one.
178 IRBuilder<> Builder(BI);
179 UncondBrInst *NewBI = Builder.CreateBr(Dest: Destination);
180
181 // Transfer the metadata to the new branch instruction.
182 NewBI->copyMetadata(SrcInst: *BI, WL: {LLVMContext::MD_loop, LLVMContext::MD_dbg,
183 LLVMContext::MD_annotation});
184
185 BI->eraseFromParent();
186 if (DTU)
187 DTU->applyUpdates(Updates: {{DominatorTree::Delete, BB, OldDest}});
188 return true;
189 }
190
191 return false;
192 }
193
194 if (auto *SI = dyn_cast<SwitchInst>(Val: T)) {
195 // If we are switching on a constant, we can convert the switch to an
196 // unconditional branch.
197 auto *CI = dyn_cast<ConstantInt>(Val: SI->getCondition());
198 BasicBlock *DefaultDest = SI->getDefaultDest();
199 BasicBlock *TheOnlyDest = DefaultDest;
200
201 // If the default is unreachable, ignore it when searching for TheOnlyDest.
202 if (SI->defaultDestUnreachable() && SI->getNumCases() > 0)
203 TheOnlyDest = SI->case_begin()->getCaseSuccessor();
204
205 bool Changed = false;
206
207 // Figure out which case it goes to.
208 for (auto It = SI->case_begin(), End = SI->case_end(); It != End;) {
209 // Found case matching a constant operand?
210 if (It->getCaseValue() == CI) {
211 TheOnlyDest = It->getCaseSuccessor();
212 break;
213 }
214
215 // Check to see if this branch is going to the same place as the default
216 // dest. If so, eliminate it as an explicit compare.
217 if (It->getCaseSuccessor() == DefaultDest) {
218 MDNode *MD = getValidBranchWeightMDNode(I: *SI);
219 unsigned NCases = SI->getNumCases();
220 // Fold the case metadata into the default if there will be any branches
221 // left, unless the metadata doesn't match the switch.
222 if (NCases > 1 && MD) {
223 // Collect branch weights into a vector.
224 SmallVector<uint64_t, 8> Weights;
225 extractFromBranchWeightMD64(ProfileData: MD, Weights);
226
227 // Merge weight of this case to the default weight.
228 unsigned Idx = It->getCaseIndex();
229
230 // Check for and prevent uint64_t overflow by reducing branch weights.
231 if (Weights[0] > UINT64_MAX - Weights[Idx + 1])
232 fitWeights(Weights);
233
234 Weights[0] += Weights[Idx + 1];
235 // Remove weight for this case.
236 std::swap(a&: Weights[Idx + 1], b&: Weights.back());
237 Weights.pop_back();
238 setFittedBranchWeights(I&: *SI, Weights, IsExpected: hasBranchWeightOrigin(ProfileData: MD));
239 }
240 // Remove this entry.
241 BasicBlock *ParentBB = SI->getParent();
242 DefaultDest->removePredecessor(Pred: ParentBB);
243 It = SI->removeCase(I: It);
244 End = SI->case_end();
245
246 // Removing this case may have made the condition constant. In that
247 // case, update CI and restart iteration through the cases.
248 if (auto *NewCI = dyn_cast<ConstantInt>(Val: SI->getCondition())) {
249 CI = NewCI;
250 It = SI->case_begin();
251 }
252
253 Changed = true;
254 continue;
255 }
256
257 // Otherwise, check to see if the switch only branches to one destination.
258 // We do this by resetting "TheOnlyDest" to null when we find two
259 // non-equal destinations.
260 if (It->getCaseSuccessor() != TheOnlyDest)
261 TheOnlyDest = nullptr;
262
263 // Increment this iterator as we haven't removed the case.
264 ++It;
265 }
266
267 if (CI && !TheOnlyDest) {
268 // Branching on a constant, but not any of the cases, go to the default
269 // successor.
270 TheOnlyDest = SI->getDefaultDest();
271 }
272
273 // If we found a single destination that we can fold the switch into, do so
274 // now.
275 if (TheOnlyDest) {
276 // Insert the new branch.
277 IRBuilder<> Builder(SI);
278 Builder.CreateBr(Dest: TheOnlyDest);
279 BasicBlock *BB = SI->getParent();
280
281 SmallPtrSet<BasicBlock *, 8> RemovedSuccessors;
282
283 // Remove entries from PHI nodes which we no longer branch to...
284 BasicBlock *SuccToKeep = TheOnlyDest;
285 for (BasicBlock *Succ : successors(I: SI)) {
286 if (DTU && Succ != TheOnlyDest)
287 RemovedSuccessors.insert(Ptr: Succ);
288 // Found case matching a constant operand?
289 if (Succ == SuccToKeep) {
290 SuccToKeep = nullptr; // Don't modify the first branch to TheOnlyDest
291 } else {
292 Succ->removePredecessor(Pred: BB);
293 }
294 }
295
296 // Delete the old switch.
297 Value *Cond = SI->getCondition();
298 SI->eraseFromParent();
299 if (DeleteDeadConditions)
300 RecursivelyDeleteTriviallyDeadInstructions(V: Cond, TLI);
301 if (DTU) {
302 std::vector<DominatorTree::UpdateType> Updates;
303 Updates.reserve(n: RemovedSuccessors.size());
304 for (auto *RemovedSuccessor : RemovedSuccessors)
305 Updates.push_back(x: {DominatorTree::Delete, BB, RemovedSuccessor});
306 DTU->applyUpdates(Updates);
307 }
308 return true;
309 }
310
311 if (SI->getNumCases() == 1) {
312 // Otherwise, we can fold this switch into a conditional branch
313 // instruction if it has only one non-default destination.
314 auto FirstCase = *SI->case_begin();
315 IRBuilder<> Builder(SI);
316 Value *Cond = Builder.CreateICmpEQ(LHS: SI->getCondition(),
317 RHS: FirstCase.getCaseValue(), Name: "cond");
318
319 // Insert the new branch.
320 CondBrInst *NewBr = Builder.CreateCondBr(
321 Cond, True: FirstCase.getCaseSuccessor(), False: SI->getDefaultDest());
322 SmallVector<uint32_t> Weights;
323 if (extractBranchWeights(I: *SI, Weights) && Weights.size() == 2) {
324 uint32_t DefWeight = Weights[0];
325 uint32_t CaseWeight = Weights[1];
326 // The TrueWeight should be the weight for the single case of SI.
327 NewBr->setMetadata(KindID: LLVMContext::MD_prof,
328 Node: MDBuilder(BB->getContext())
329 .createBranchWeights(TrueWeight: CaseWeight, FalseWeight: DefWeight));
330 }
331
332 // Update make.implicit metadata to the newly-created conditional branch.
333 MDNode *MakeImplicitMD = SI->getMetadata(KindID: LLVMContext::MD_make_implicit);
334 if (MakeImplicitMD)
335 NewBr->setMetadata(KindID: LLVMContext::MD_make_implicit, Node: MakeImplicitMD);
336
337 // Delete the old switch.
338 SI->eraseFromParent();
339 return true;
340 }
341 return Changed;
342 }
343
344 if (auto *IBI = dyn_cast<IndirectBrInst>(Val: T)) {
345 // indirectbr blockaddress(@F, @BB) -> br label @BB
346 if (auto *BA =
347 dyn_cast<BlockAddress>(Val: IBI->getAddress()->stripPointerCasts())) {
348 BasicBlock *TheOnlyDest = BA->getBasicBlock();
349 SmallPtrSet<BasicBlock *, 8> RemovedSuccessors;
350
351 // Insert the new branch.
352 IRBuilder<> Builder(IBI);
353 Builder.CreateBr(Dest: TheOnlyDest);
354
355 BasicBlock *SuccToKeep = TheOnlyDest;
356 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
357 BasicBlock *DestBB = IBI->getDestination(i);
358 if (DTU && DestBB != TheOnlyDest)
359 RemovedSuccessors.insert(Ptr: DestBB);
360 if (IBI->getDestination(i) == SuccToKeep) {
361 SuccToKeep = nullptr;
362 } else {
363 DestBB->removePredecessor(Pred: BB);
364 }
365 }
366 Value *Address = IBI->getAddress();
367 IBI->eraseFromParent();
368 if (DeleteDeadConditions)
369 // Delete pointer cast instructions.
370 RecursivelyDeleteTriviallyDeadInstructions(V: Address, TLI);
371
372 // Also zap the blockaddress constant if there are no users remaining,
373 // otherwise the destination is still marked as having its address taken.
374 if (BA->use_empty())
375 BA->destroyConstant();
376
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.
380 if (SuccToKeep) {
381 BB->getTerminator()->eraseFromParent();
382 new UnreachableInst(BB->getContext(), BB);
383 }
384
385 if (DTU) {
386 std::vector<DominatorTree::UpdateType> Updates;
387 Updates.reserve(n: RemovedSuccessors.size());
388 for (auto *RemovedSuccessor : RemovedSuccessors)
389 Updates.push_back(x: {DominatorTree::Delete, BB, RemovedSuccessor});
390 DTU->applyUpdates(Updates);
391 }
392 return true;
393 }
394 }
395
396 return false;
397}
398
399//===----------------------------------------------------------------------===//
400// Local dead code elimination.
401//
402
403/// isInstructionTriviallyDead - Return true if the result produced by the
404/// instruction is not used, and the instruction has no side effects.
405///
406bool llvm::isInstructionTriviallyDead(Instruction *I,
407 const TargetLibraryInfo *TLI) {
408 if (!I->use_empty())
409 return false;
410 return wouldInstructionBeTriviallyDead(I, TLI);
411}
412
413bool llvm::wouldInstructionBeTriviallyDead(const Instruction *I,
414 const TargetLibraryInfo *TLI) {
415 if (I->isTerminator())
416 return false;
417
418 // We don't want the landingpad-like instructions removed by anything this
419 // general.
420 if (I->isEHPad())
421 return false;
422
423 if (const DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(Val: I)) {
424 if (DLI->getLabel())
425 return false;
426 return true;
427 }
428
429 if (auto *CB = dyn_cast<CallBase>(Val: I))
430 if (isRemovableAlloc(V: CB, TLI))
431 return true;
432
433 if (!I->willReturn()) {
434 auto *II = dyn_cast<IntrinsicInst>(Val: I);
435 if (!II)
436 return false;
437
438 switch (II->getIntrinsicID()) {
439 case Intrinsic::experimental_guard: {
440 // Guards on true are operationally no-ops. In the future we can
441 // consider more sophisticated tradeoffs for guards considering potential
442 // for check widening, but for now we keep things simple.
443 auto *Cond = dyn_cast<ConstantInt>(Val: II->getArgOperand(i: 0));
444 return Cond && Cond->isOne();
445 }
446 // TODO: These intrinsics are not safe to remove, because this may remove
447 // a well-defined trap.
448 case Intrinsic::wasm_trunc_signed:
449 case Intrinsic::wasm_trunc_unsigned:
450 case Intrinsic::ptrauth_auth:
451 case Intrinsic::ptrauth_resign:
452 case Intrinsic::ptrauth_resign_load_relative:
453 return true;
454 default:
455 return false;
456 }
457 }
458
459 if (!I->mayHaveSideEffects())
460 return true;
461
462 // Special case intrinsics that "may have side effects" but can be deleted
463 // when dead.
464 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: I)) {
465 // Safe to delete llvm.stacksave and launder.invariant.group if dead.
466 if (II->getIntrinsicID() == Intrinsic::stacksave ||
467 II->getIntrinsicID() == Intrinsic::launder_invariant_group)
468 return true;
469
470 // Intrinsics declare sideeffects to prevent them from moving, but they are
471 // nops without users.
472 if (II->getIntrinsicID() == Intrinsic::allow_runtime_check ||
473 II->getIntrinsicID() == Intrinsic::allow_ubsan_check)
474 return true;
475
476 if (II->isLifetimeStartOrEnd()) {
477 auto *Arg = II->getArgOperand(i: 0);
478 if (isa<PoisonValue>(Val: Arg))
479 return true;
480
481 // If the only uses of the alloca are lifetime intrinsics, then the
482 // intrinsics are dead.
483 return llvm::all_of(Range: Arg->uses(), P: [](Use &Use) {
484 return isa<LifetimeIntrinsic>(Val: Use.getUser());
485 });
486 }
487
488 // Assumptions are dead if their condition is trivially true.
489 if (II->getIntrinsicID() == Intrinsic::assume &&
490 isAssumeWithEmptyBundle(Assume: cast<AssumeInst>(Val: *II))) {
491 if (ConstantInt *Cond = dyn_cast<ConstantInt>(Val: II->getArgOperand(i: 0)))
492 return !Cond->isZero();
493
494 return false;
495 }
496
497 if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(Val: I)) {
498 std::optional<fp::ExceptionBehavior> ExBehavior =
499 FPI->getExceptionBehavior();
500 return *ExBehavior != fp::ebStrict;
501 }
502 }
503
504 if (auto *Call = dyn_cast<CallBase>(Val: I)) {
505 if (Value *FreedOp = getFreedOperand(CB: Call, TLI))
506 if (Constant *C = dyn_cast<Constant>(Val: FreedOp))
507 return C->isNullValue() || isa<UndefValue>(Val: C);
508 if (isMathLibCallNoop(Call, TLI))
509 return true;
510 }
511
512 // Non-volatile atomic loads from constants can be removed.
513 if (auto *LI = dyn_cast<LoadInst>(Val: I))
514 if (auto *GV = dyn_cast<GlobalVariable>(
515 Val: LI->getPointerOperand()->stripPointerCasts()))
516 if (!LI->isVolatile() && GV->isConstant())
517 return true;
518
519 return false;
520}
521
522/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
523/// trivially dead instruction, delete it. If that makes any of its operands
524/// trivially dead, delete them too, recursively. Return true if any
525/// instructions were deleted.
526bool llvm::RecursivelyDeleteTriviallyDeadInstructions(
527 Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU,
528 std::function<void(Value *)> AboutToDeleteCallback) {
529 Instruction *I = dyn_cast<Instruction>(Val: V);
530 if (!I || !isInstructionTriviallyDead(I, TLI))
531 return false;
532
533 SmallVector<WeakTrackingVH, 16> DeadInsts;
534 DeadInsts.push_back(Elt: I);
535 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
536 AboutToDeleteCallback);
537
538 return true;
539}
540
541bool llvm::RecursivelyDeleteTriviallyDeadInstructionsPermissive(
542 SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
543 MemorySSAUpdater *MSSAU,
544 std::function<void(Value *)> AboutToDeleteCallback) {
545 unsigned S = 0, E = DeadInsts.size(), Alive = 0;
546 for (; S != E; ++S) {
547 auto *I = dyn_cast_or_null<Instruction>(Val&: DeadInsts[S]);
548 if (!I || !isInstructionTriviallyDead(I)) {
549 DeadInsts[S] = nullptr;
550 ++Alive;
551 }
552 }
553 if (Alive == E)
554 return false;
555 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
556 AboutToDeleteCallback);
557 return true;
558}
559
560void llvm::RecursivelyDeleteTriviallyDeadInstructions(
561 SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
562 MemorySSAUpdater *MSSAU,
563 std::function<void(Value *)> AboutToDeleteCallback) {
564 // Process the dead instruction list until empty.
565 while (!DeadInsts.empty()) {
566 Value *V = DeadInsts.pop_back_val();
567 Instruction *I = cast_or_null<Instruction>(Val: V);
568 if (!I)
569 continue;
570 assert(isInstructionTriviallyDead(I, TLI) &&
571 "Live instruction found in dead worklist!");
572 assert(I->use_empty() && "Instructions with uses are not dead.");
573
574 // Don't lose the debug info while deleting the instructions.
575 salvageDebugInfo(I&: *I);
576
577 if (AboutToDeleteCallback)
578 AboutToDeleteCallback(I);
579
580 // Null out all of the instruction's operands to see if any operand becomes
581 // dead as we go.
582 for (Use &OpU : I->operands()) {
583 Value *OpV = OpU.get();
584 OpU.set(nullptr);
585
586 if (!OpV->use_empty())
587 continue;
588
589 // If the operand is an instruction that became dead as we nulled out the
590 // operand, and if it is 'trivially' dead, delete it in a future loop
591 // iteration.
592 if (Instruction *OpI = dyn_cast<Instruction>(Val: OpV))
593 if (isInstructionTriviallyDead(I: OpI, TLI))
594 DeadInsts.push_back(Elt: OpI);
595 }
596 if (MSSAU)
597 MSSAU->removeMemoryAccess(I);
598
599 I->eraseFromParent();
600 }
601}
602
603/// areAllUsesEqual - Check whether the uses of a value are all the same.
604/// This is similar to Instruction::hasOneUse() except this will also return
605/// true when there are no uses or multiple uses that all refer to the same
606/// value.
607static bool areAllUsesEqual(Instruction *I) {
608 Instruction::user_iterator UI = I->user_begin();
609 Instruction::user_iterator UE = I->user_end();
610 if (UI == UE)
611 return true;
612
613 User *TheUse = *UI;
614 for (++UI; UI != UE; ++UI) {
615 if (*UI != TheUse)
616 return false;
617 }
618 return true;
619}
620
621/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
622/// dead PHI node, due to being a def-use chain of single-use nodes that
623/// either forms a cycle or is terminated by a trivially dead instruction,
624/// delete it. If that makes any of its operands trivially dead, delete them
625/// too, recursively. Return true if a change was made.
626bool llvm::RecursivelyDeleteDeadPHINode(
627 PHINode *PN, const TargetLibraryInfo *TLI, llvm::MemorySSAUpdater *MSSAU,
628 SmallPtrSetImpl<PHINode *> *KnownNonDeadPHIs) {
629 SmallPtrSet<Instruction*, 4> Visited;
630 SmallVector<PHINode *, 8> VisitedPHIs;
631
632 for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
633 I = cast<Instruction>(Val: *I->user_begin())) {
634 if (I->use_empty())
635 return RecursivelyDeleteTriviallyDeadInstructions(V: I, TLI, MSSAU);
636
637 // If we find an instruction more than once, we're on a cycle that
638 // won't prove fruitful.
639 if (!Visited.insert(Ptr: I).second) {
640 // Break the cycle and delete the instruction and its operands.
641 I->replaceAllUsesWith(V: PoisonValue::get(T: I->getType()));
642 (void)RecursivelyDeleteTriviallyDeadInstructions(V: I, TLI, MSSAU);
643 return true;
644 }
645
646 if (PHINode *CurPN = dyn_cast<PHINode>(Val: I)) {
647 if (KnownNonDeadPHIs && KnownNonDeadPHIs->contains(Ptr: CurPN))
648 break;
649 VisitedPHIs.push_back(Elt: CurPN);
650 }
651 }
652
653 if (KnownNonDeadPHIs)
654 for (PHINode *VisitedPN : VisitedPHIs)
655 KnownNonDeadPHIs->insert(Ptr: VisitedPN);
656
657 return false;
658}
659
660static bool
661simplifyAndDCEInstruction(Instruction *I,
662 SmallSetVector<Instruction *, 16> &WorkList,
663 const DataLayout &DL,
664 const TargetLibraryInfo *TLI) {
665 if (isInstructionTriviallyDead(I, TLI)) {
666 salvageDebugInfo(I&: *I);
667
668 // Null out all of the instruction's operands to see if any operand becomes
669 // dead as we go.
670 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
671 Value *OpV = I->getOperand(i);
672 I->setOperand(i, Val: nullptr);
673
674 if (!OpV->use_empty() || I == OpV)
675 continue;
676
677 // If the operand is an instruction that became dead as we nulled out the
678 // operand, and if it is 'trivially' dead, delete it in a future loop
679 // iteration.
680 if (Instruction *OpI = dyn_cast<Instruction>(Val: OpV))
681 if (isInstructionTriviallyDead(I: OpI, TLI))
682 WorkList.insert(X: OpI);
683 }
684
685 I->eraseFromParent();
686
687 return true;
688 }
689
690 if (Value *SimpleV = simplifyInstruction(I, Q: DL)) {
691 // Add the users to the worklist. CAREFUL: an instruction can use itself,
692 // in the case of a phi node.
693 for (User *U : I->users()) {
694 if (U != I) {
695 WorkList.insert(X: cast<Instruction>(Val: U));
696 }
697 }
698
699 // Replace the instruction with its simplified value.
700 bool Changed = false;
701 if (!I->use_empty()) {
702 I->replaceAllUsesWith(V: SimpleV);
703 Changed = true;
704 }
705 if (isInstructionTriviallyDead(I, TLI)) {
706 I->eraseFromParent();
707 Changed = true;
708 }
709 return Changed;
710 }
711 return false;
712}
713
714/// SimplifyInstructionsInBlock - Scan the specified basic block and try to
715/// simplify any instructions in it and recursively delete dead instructions.
716///
717/// This returns true if it changed the code, note that it can delete
718/// instructions in other blocks as well in this block.
719bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB,
720 const TargetLibraryInfo *TLI) {
721 bool MadeChange = false;
722 const DataLayout &DL = BB->getDataLayout();
723
724#ifndef NDEBUG
725 // In debug builds, ensure that the terminator of the block is never replaced
726 // or deleted by these simplifications. The idea of simplification is that it
727 // cannot introduce new instructions, and there is no way to replace the
728 // terminator of a block without introducing a new instruction.
729 AssertingVH<Instruction> TerminatorVH(&BB->back());
730#endif
731
732 SmallSetVector<Instruction *, 16> WorkList;
733 // Iterate over the original function, only adding insts to the worklist
734 // if they actually need to be revisited. This avoids having to pre-init
735 // the worklist with the entire function's worth of instructions.
736 for (BasicBlock::iterator BI = BB->begin(), E = std::prev(x: BB->end());
737 BI != E;) {
738 assert(!BI->isTerminator());
739 Instruction *I = &*BI;
740 ++BI;
741
742 // We're visiting this instruction now, so make sure it's not in the
743 // worklist from an earlier visit.
744 if (!WorkList.count(key: I))
745 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
746 }
747
748 while (!WorkList.empty()) {
749 Instruction *I = WorkList.pop_back_val();
750 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
751 }
752 return MadeChange;
753}
754
755//===----------------------------------------------------------------------===//
756// Control Flow Graph Restructuring.
757//
758
759void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
760 DomTreeUpdater *DTU) {
761
762 // If BB has single-entry PHI nodes, fold them.
763 while (PHINode *PN = dyn_cast<PHINode>(Val: DestBB->begin())) {
764 Value *NewVal = PN->getIncomingValue(i: 0);
765 // Replace self referencing PHI with poison, it must be dead.
766 if (NewVal == PN) NewVal = PoisonValue::get(T: PN->getType());
767 PN->replaceAllUsesWith(V: NewVal);
768 PN->eraseFromParent();
769 }
770
771 BasicBlock *PredBB = DestBB->getSinglePredecessor();
772 assert(PredBB && "Block doesn't have a single predecessor!");
773
774 bool ReplaceEntryBB = PredBB->isEntryBlock();
775
776 // DTU updates: Collect all the edges that enter
777 // PredBB. These dominator edges will be redirected to DestBB.
778 SmallVector<DominatorTree::UpdateType, 32> Updates;
779
780 if (DTU) {
781 // To avoid processing the same predecessor more than once.
782 SmallPtrSet<BasicBlock *, 2> SeenPreds;
783 Updates.reserve(N: Updates.size() + 2 * pred_size(BB: PredBB) + 1);
784 for (BasicBlock *PredOfPredBB : predecessors(BB: PredBB))
785 // This predecessor of PredBB may already have DestBB as a successor.
786 if (PredOfPredBB != PredBB)
787 if (SeenPreds.insert(Ptr: PredOfPredBB).second)
788 Updates.push_back(Elt: {DominatorTree::Insert, PredOfPredBB, DestBB});
789 SeenPreds.clear();
790 for (BasicBlock *PredOfPredBB : predecessors(BB: PredBB))
791 if (SeenPreds.insert(Ptr: PredOfPredBB).second)
792 Updates.push_back(Elt: {DominatorTree::Delete, PredOfPredBB, PredBB});
793 Updates.push_back(Elt: {DominatorTree::Delete, PredBB, DestBB});
794 }
795
796 // Zap anything that took the address of DestBB. Not doing this will give the
797 // address an invalid value.
798 if (DestBB->hasAddressTaken()) {
799 BlockAddress *BA = BlockAddress::get(BB: DestBB);
800 Constant *Replacement =
801 ConstantInt::get(Ty: Type::getInt32Ty(C&: BA->getContext()), V: 1);
802 BA->replaceAllUsesWith(V: ConstantExpr::getIntToPtr(C: Replacement,
803 Ty: BA->getType()));
804 BA->destroyConstant();
805 }
806
807 // Anything that branched to PredBB now branches to DestBB.
808 PredBB->replaceAllUsesWith(V: DestBB);
809
810 // Splice all the instructions from PredBB to DestBB.
811 PredBB->getTerminator()->eraseFromParent();
812 DestBB->splice(ToIt: DestBB->begin(), FromBB: PredBB);
813 new UnreachableInst(PredBB->getContext(), PredBB);
814
815 // If the PredBB is the entry block of the function, move DestBB up to
816 // become the entry block after we erase PredBB.
817 if (ReplaceEntryBB)
818 DestBB->moveAfter(MovePos: PredBB);
819
820 if (DTU) {
821 assert(PredBB->size() == 1 &&
822 isa<UnreachableInst>(PredBB->getTerminator()) &&
823 "The successor list of PredBB isn't empty before "
824 "applying corresponding DTU updates.");
825 DTU->applyUpdatesPermissive(Updates);
826 DTU->deleteBB(DelBB: PredBB);
827 // Recalculation of DomTree is needed when updating a forward DomTree and
828 // the Entry BB is replaced.
829 if (ReplaceEntryBB && DTU->hasDomTree()) {
830 // The entry block was removed and there is no external interface for
831 // the dominator tree to be notified of this change. In this corner-case
832 // we recalculate the entire tree.
833 DTU->recalculate(F&: *(DestBB->getParent()));
834 }
835 }
836
837 else {
838 PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr.
839 }
840}
841
842/// Return true if we can choose one of these values to use in place of the
843/// other. Note that we will always choose the non-undef value to keep.
844static bool CanMergeValues(Value *First, Value *Second) {
845 return First == Second || isa<UndefValue>(Val: First) || isa<UndefValue>(Val: Second);
846}
847
848/// Return true if we can fold BB, an almost-empty BB ending in an unconditional
849/// branch to Succ, into Succ.
850///
851/// Assumption: Succ is the single successor for BB.
852static bool
853CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ,
854 const SmallPtrSetImpl<BasicBlock *> &BBPreds) {
855 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
856
857 LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
858 << Succ->getName() << "\n");
859 // Shortcut, if there is only a single predecessor it must be BB and merging
860 // is always safe
861 if (Succ->getSinglePredecessor())
862 return true;
863
864 // Look at all the phi nodes in Succ, to see if they present a conflict when
865 // merging these blocks
866 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(Val: I); ++I) {
867 PHINode *PN = cast<PHINode>(Val&: I);
868
869 // If the incoming value from BB is again a PHINode in
870 // BB which has the same incoming value for *PI as PN does, we can
871 // merge the phi nodes and then the blocks can still be merged
872 PHINode *BBPN = dyn_cast<PHINode>(Val: PN->getIncomingValueForBlock(BB));
873 if (BBPN && BBPN->getParent() == BB) {
874 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
875 BasicBlock *IBB = PN->getIncomingBlock(i: PI);
876 if (BBPreds.count(Ptr: IBB) &&
877 !CanMergeValues(First: BBPN->getIncomingValueForBlock(BB: IBB),
878 Second: PN->getIncomingValue(i: PI))) {
879 LLVM_DEBUG(dbgs()
880 << "Can't fold, phi node " << PN->getName() << " in "
881 << Succ->getName() << " is conflicting with "
882 << BBPN->getName() << " with regard to common predecessor "
883 << IBB->getName() << "\n");
884 return false;
885 }
886 }
887 } else {
888 Value* Val = PN->getIncomingValueForBlock(BB);
889 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
890 // See if the incoming value for the common predecessor is equal to the
891 // one for BB, in which case this phi node will not prevent the merging
892 // of the block.
893 BasicBlock *IBB = PN->getIncomingBlock(i: PI);
894 if (BBPreds.count(Ptr: IBB) &&
895 !CanMergeValues(First: Val, Second: PN->getIncomingValue(i: PI))) {
896 LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()
897 << " in " << Succ->getName()
898 << " is conflicting with regard to common "
899 << "predecessor " << IBB->getName() << "\n");
900 return false;
901 }
902 }
903 }
904 }
905
906 return true;
907}
908
909using PredBlockVector = SmallVector<BasicBlock *, 16>;
910using IncomingValueMap = SmallDenseMap<BasicBlock *, Value *, 16>;
911
912/// Determines the value to use as the phi node input for a block.
913///
914/// Select between \p OldVal any value that we know flows from \p BB
915/// to a particular phi on the basis of which one (if either) is not
916/// undef. Update IncomingValues based on the selected value.
917///
918/// \param OldVal The value we are considering selecting.
919/// \param BB The block that the value flows in from.
920/// \param IncomingValues A map from block-to-value for other phi inputs
921/// that we have examined.
922///
923/// \returns the selected value.
924static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB,
925 IncomingValueMap &IncomingValues) {
926 IncomingValueMap::const_iterator It = IncomingValues.find(Val: BB);
927 if (!isa<UndefValue>(Val: OldVal)) {
928 assert((It != IncomingValues.end() &&
929 (!(It->second) || It->second == OldVal)) &&
930 "Expected OldVal to match incoming value from BB!");
931
932 IncomingValues.insert_or_assign(Key: BB, Val&: OldVal);
933 return OldVal;
934 }
935
936 if (It != IncomingValues.end() && It->second)
937 return It->second;
938
939 return OldVal;
940}
941
942/// Create a map from block to value for the operands of a
943/// given phi.
944///
945/// This function initializes the map with UndefValue for all predecessors
946/// in BBPreds, and then updates the map with concrete non-undef values
947/// found in the PHI node.
948///
949/// \param PN The phi we are collecting the map for.
950/// \param BBPreds The list of all predecessor blocks to initialize with Undef.
951/// \param IncomingValues [out] The map from block to value for this phi.
952static void gatherIncomingValuesToPhi(PHINode *PN,
953 const PredBlockVector &BBPreds,
954 IncomingValueMap &IncomingValues) {
955 for (BasicBlock *Pred : BBPreds)
956 IncomingValues[Pred] = nullptr;
957
958 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
959 Value *V = PN->getIncomingValue(i);
960 if (isa<UndefValue>(Val: V))
961 continue;
962
963 BasicBlock *BB = PN->getIncomingBlock(i);
964 auto It = IncomingValues.find(Val: BB);
965 if (It != IncomingValues.end())
966 It->second = V;
967 }
968}
969
970/// Replace the incoming undef values to a phi with the values
971/// from a block-to-value map.
972///
973/// \param PN The phi we are replacing the undefs in.
974/// \param IncomingValues A map from block to value.
975static void replaceUndefValuesInPhi(PHINode *PN,
976 const IncomingValueMap &IncomingValues) {
977 SmallVector<unsigned> TrueUndefOps;
978 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
979 Value *V = PN->getIncomingValue(i);
980
981 if (!isa<UndefValue>(Val: V)) continue;
982
983 BasicBlock *BB = PN->getIncomingBlock(i);
984 IncomingValueMap::const_iterator It = IncomingValues.find(Val: BB);
985 if (It == IncomingValues.end())
986 continue;
987
988 // Keep track of undef/poison incoming values. Those must match, so we fix
989 // them up below if needed.
990 // Note: this is conservatively correct, but we could try harder and group
991 // the undef values per incoming basic block.
992 if (!It->second) {
993 TrueUndefOps.push_back(Elt: i);
994 continue;
995 }
996
997 // There is a defined value for this incoming block, so map this undef
998 // incoming value to the defined value.
999 PN->setIncomingValue(i, V: It->second);
1000 }
1001
1002 // If there are both undef and poison values incoming, then convert those
1003 // values to undef. It is invalid to have different values for the same
1004 // incoming block.
1005 unsigned PoisonCount = count_if(Range&: TrueUndefOps, P: [&](unsigned i) {
1006 return isa<PoisonValue>(Val: PN->getIncomingValue(i));
1007 });
1008 if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) {
1009 for (unsigned i : TrueUndefOps)
1010 PN->setIncomingValue(i, V: UndefValue::get(T: PN->getType()));
1011 }
1012}
1013
1014// Only when they shares a single common predecessor, return true.
1015// Only handles cases when BB can't be merged while its predecessors can be
1016// redirected.
1017static bool
1018CanRedirectPredsOfEmptyBBToSucc(BasicBlock *BB, BasicBlock *Succ,
1019 const SmallPtrSetImpl<BasicBlock *> &BBPreds,
1020 BasicBlock *&CommonPred) {
1021
1022 // There must be phis in BB, otherwise BB will be merged into Succ directly
1023 if (BB->phis().empty() || Succ->phis().empty())
1024 return false;
1025
1026 // BB must have predecessors not shared that can be redirected to Succ
1027 if (!BB->hasNPredecessorsOrMore(N: 2))
1028 return false;
1029
1030 if (any_of(Range: BBPreds, P: [](const BasicBlock *Pred) {
1031 return isa<IndirectBrInst>(Val: Pred->getTerminator());
1032 }))
1033 return false;
1034
1035 // Get the single common predecessor of both BB and Succ. Return false
1036 // when there are more than one common predecessors.
1037 for (BasicBlock *SuccPred : predecessors(BB: Succ)) {
1038 if (BBPreds.count(Ptr: SuccPred)) {
1039 if (CommonPred)
1040 return false;
1041 CommonPred = SuccPred;
1042 }
1043 }
1044
1045 return true;
1046}
1047
1048/// Check whether removing \p BB will make the phis in its \p Succ have too
1049/// many incoming entries. This function does not check whether \p BB is
1050/// foldable or not.
1051static bool introduceTooManyPhiEntries(BasicBlock *BB, BasicBlock *Succ) {
1052 // If BB only has one predecessor, then removing it will not introduce more
1053 // incoming edges for phis.
1054 if (BB->hasNPredecessors(N: 1))
1055 return false;
1056 unsigned NumPreds = pred_size(BB);
1057 unsigned NumChangedPhi = 0;
1058 for (auto &Phi : Succ->phis()) {
1059 // If the incoming value is a phi and the phi is defined in BB,
1060 // then removing BB will not increase the total phi entries of the ir.
1061 if (auto *IncomingPhi = dyn_cast<PHINode>(Val: Phi.getIncomingValueForBlock(BB)))
1062 if (IncomingPhi->getParent() == BB)
1063 continue;
1064 // Otherwise, we need to add entries to the phi
1065 NumChangedPhi++;
1066 }
1067 // For every phi that needs to be changed, (NumPreds - 1) new entries will be
1068 // added. If the total increase in phi entries exceeds
1069 // MaxPhiEntriesIncreaseAfterRemovingEmptyBlock, it will be considered as
1070 // introducing too many new phi entries.
1071 return (NumPreds - 1) * NumChangedPhi >
1072 MaxPhiEntriesIncreaseAfterRemovingEmptyBlock;
1073}
1074
1075/// Replace a value flowing from a block to a phi with
1076/// potentially multiple instances of that value flowing from the
1077/// block's predecessors to the phi.
1078///
1079/// \param BB The block with the value flowing into the phi.
1080/// \param BBPreds The predecessors of BB.
1081/// \param PN The phi that we are updating.
1082/// \param CommonPred The common predecessor of BB and PN's BasicBlock
1083static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
1084 const PredBlockVector &BBPreds,
1085 PHINode *PN,
1086 BasicBlock *CommonPred) {
1087 Value *OldVal = PN->removeIncomingValue(BB, DeletePHIIfEmpty: false);
1088 assert(OldVal && "No entry in PHI for Pred BB!");
1089
1090 // Map BBPreds to defined values or nullptr (representing undefined values).
1091 IncomingValueMap IncomingValues;
1092
1093 // We are merging two blocks - BB, and the block containing PN - and
1094 // as a result we need to redirect edges from the predecessors of BB
1095 // to go to the block containing PN, and update PN
1096 // accordingly. Since we allow merging blocks in the case where the
1097 // predecessor and successor blocks both share some predecessors,
1098 // and where some of those common predecessors might have undef
1099 // values flowing into PN, we want to rewrite those values to be
1100 // consistent with the non-undef values.
1101
1102 gatherIncomingValuesToPhi(PN, BBPreds, IncomingValues);
1103
1104 // If this incoming value is one of the PHI nodes in BB, the new entries
1105 // in the PHI node are the entries from the old PHI.
1106 if (isa<PHINode>(Val: OldVal) && cast<PHINode>(Val: OldVal)->getParent() == BB) {
1107 PHINode *OldValPN = cast<PHINode>(Val: OldVal);
1108 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
1109 // Note that, since we are merging phi nodes and BB and Succ might
1110 // have common predecessors, we could end up with a phi node with
1111 // identical incoming branches. This will be cleaned up later (and
1112 // will trigger asserts if we try to clean it up now, without also
1113 // simplifying the corresponding conditional branch).
1114 BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
1115
1116 if (PredBB == CommonPred)
1117 continue;
1118
1119 Value *PredVal = OldValPN->getIncomingValue(i);
1120 Value *Selected =
1121 selectIncomingValueForBlock(OldVal: PredVal, BB: PredBB, IncomingValues);
1122
1123 // And add a new incoming value for this predecessor for the
1124 // newly retargeted branch.
1125 PN->addIncoming(V: Selected, BB: PredBB);
1126 }
1127 if (CommonPred)
1128 PN->addIncoming(V: OldValPN->getIncomingValueForBlock(BB: CommonPred), BB);
1129
1130 } else {
1131 for (BasicBlock *PredBB : BBPreds) {
1132 // Update existing incoming values in PN for this
1133 // predecessor of BB.
1134 if (PredBB == CommonPred)
1135 continue;
1136
1137 Value *Selected =
1138 selectIncomingValueForBlock(OldVal, BB: PredBB, IncomingValues);
1139
1140 // And add a new incoming value for this predecessor for the
1141 // newly retargeted branch.
1142 PN->addIncoming(V: Selected, BB: PredBB);
1143 }
1144 if (CommonPred)
1145 PN->addIncoming(V: OldVal, BB);
1146 }
1147
1148 replaceUndefValuesInPhi(PN, IncomingValues);
1149}
1150
1151bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
1152 DomTreeUpdater *DTU) {
1153 assert(BB != &BB->getParent()->getEntryBlock() &&
1154 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
1155
1156 // We can't simplify infinite loops.
1157 BasicBlock *Succ = cast<UncondBrInst>(Val: BB->getTerminator())->getSuccessor(i: 0);
1158 if (BB == Succ)
1159 return false;
1160
1161 SmallPtrSet<BasicBlock *, 16> BBPreds(llvm::from_range, predecessors(BB));
1162
1163 // The single common predecessor of BB and Succ when BB cannot be killed
1164 BasicBlock *CommonPred = nullptr;
1165
1166 bool BBKillable = CanPropagatePredecessorsForPHIs(BB, Succ, BBPreds);
1167
1168 // Even if we can not fold BB into Succ, we may be able to redirect the
1169 // predecessors of BB to Succ.
1170 bool BBPhisMergeable = BBKillable || CanRedirectPredsOfEmptyBBToSucc(
1171 BB, Succ, BBPreds, CommonPred);
1172
1173 if ((!BBKillable && !BBPhisMergeable) || introduceTooManyPhiEntries(BB, Succ))
1174 return false;
1175
1176 // Check to see if merging these blocks/phis would cause conflicts for any of
1177 // the phi nodes in BB or Succ. If not, we can safely merge.
1178
1179 // Check for cases where Succ has multiple predecessors and a PHI node in BB
1180 // has uses which will not disappear when the PHI nodes are merged. It is
1181 // possible to handle such cases, but difficult: it requires checking whether
1182 // BB dominates Succ, which is non-trivial to calculate in the case where
1183 // Succ has multiple predecessors. Also, it requires checking whether
1184 // constructing the necessary self-referential PHI node doesn't introduce any
1185 // conflicts; this isn't too difficult, but the previous code for doing this
1186 // was incorrect.
1187 //
1188 // Note that if this check finds a live use, BB dominates Succ, so BB is
1189 // something like a loop pre-header (or rarely, a part of an irreducible CFG);
1190 // folding the branch isn't profitable in that case anyway.
1191 if (!Succ->getSinglePredecessor()) {
1192 BasicBlock::iterator BBI = BB->begin();
1193 while (isa<PHINode>(Val: *BBI)) {
1194 for (Use &U : BBI->uses()) {
1195 if (PHINode* PN = dyn_cast<PHINode>(Val: U.getUser())) {
1196 if (PN->getIncomingBlock(U) != BB)
1197 return false;
1198 } else {
1199 return false;
1200 }
1201 }
1202 ++BBI;
1203 }
1204 }
1205
1206 if (BBPhisMergeable && CommonPred)
1207 LLVM_DEBUG(dbgs() << "Found Common Predecessor between: " << BB->getName()
1208 << " and " << Succ->getName() << " : "
1209 << CommonPred->getName() << "\n");
1210
1211 // 'BB' and 'BB->Pred' are loop latches, bail out to preserve inner loop
1212 // metadata.
1213 //
1214 // FIXME: This is a stop-gap solution to preserve inner-loop metadata given
1215 // current status (that loop metadata is implemented as metadata attached to
1216 // the branch instruction in the loop latch block). To quote from review
1217 // comments, "the current representation of loop metadata (using a loop latch
1218 // terminator attachment) is known to be fundamentally broken. Loop latches
1219 // are not uniquely associated with loops (both in that a latch can be part of
1220 // multiple loops and a loop may have multiple latches). Loop headers are. The
1221 // solution to this problem is also known: Add support for basic block
1222 // metadata, and attach loop metadata to the loop header."
1223 //
1224 // Why bail out:
1225 // In this case, we expect 'BB' is the latch for outer-loop and 'BB->Pred' is
1226 // the latch for inner-loop (see reason below), so bail out to prerserve
1227 // inner-loop metadata rather than eliminating 'BB' and attaching its metadata
1228 // to this inner-loop.
1229 // - The reason we believe 'BB' and 'BB->Pred' have different inner-most
1230 // loops: assuming 'BB' and 'BB->Pred' are from the same inner-most loop L,
1231 // then 'BB' is the header and latch of 'L' and thereby 'L' must consist of
1232 // one self-looping basic block, which is contradictory with the assumption.
1233 //
1234 // To illustrate how inner-loop metadata is dropped:
1235 //
1236 // CFG Before
1237 //
1238 // BB is while.cond.exit, attached with loop metadata md2.
1239 // BB->Pred is for.body, attached with loop metadata md1.
1240 //
1241 // entry
1242 // |
1243 // v
1244 // ---> while.cond -------------> while.end
1245 // | |
1246 // | v
1247 // | while.body
1248 // | |
1249 // | v
1250 // | for.body <---- (md1)
1251 // | | |______|
1252 // | v
1253 // | while.cond.exit (md2)
1254 // | |
1255 // |_______|
1256 //
1257 // CFG After
1258 //
1259 // while.cond1 is the merge of while.cond.exit and while.cond above.
1260 // for.body is attached with md2, and md1 is dropped.
1261 // If LoopSimplify runs later (as a part of loop pass), it could create
1262 // dedicated exits for inner-loop (essentially adding `while.cond.exit`
1263 // back), but it won't see 'md1' nor restore it for the inner-loop.
1264 //
1265 // entry
1266 // |
1267 // v
1268 // ---> while.cond1 -------------> while.end
1269 // | |
1270 // | v
1271 // | while.body
1272 // | |
1273 // | v
1274 // | for.body <---- (md2)
1275 // |_______| |______|
1276 if (Instruction *TI = BB->getTerminatorOrNull())
1277 if (TI->hasNonDebugLocLoopMetadata())
1278 for (BasicBlock *Pred : predecessors(BB))
1279 if (Instruction *PredTI = Pred->getTerminatorOrNull())
1280 if (PredTI->hasNonDebugLocLoopMetadata())
1281 return false;
1282
1283 if (BBKillable)
1284 LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
1285 else if (BBPhisMergeable)
1286 LLVM_DEBUG(dbgs() << "Merge Phis in Trivial BB: \n" << *BB);
1287
1288 SmallVector<DominatorTree::UpdateType, 32> Updates;
1289
1290 if (DTU) {
1291 // To avoid processing the same predecessor more than once.
1292 SmallPtrSet<BasicBlock *, 8> SeenPreds;
1293 // All predecessors of BB (except the common predecessor) will be moved to
1294 // Succ.
1295 Updates.reserve(N: Updates.size() + 2 * pred_size(BB) + 1);
1296 SmallPtrSet<BasicBlock *, 16> SuccPreds(llvm::from_range,
1297 predecessors(BB: Succ));
1298 for (auto *PredOfBB : predecessors(BB)) {
1299 // Do not modify those common predecessors of BB and Succ
1300 if (!SuccPreds.contains(Ptr: PredOfBB))
1301 if (SeenPreds.insert(Ptr: PredOfBB).second)
1302 Updates.push_back(Elt: {DominatorTree::Insert, PredOfBB, Succ});
1303 }
1304
1305 SeenPreds.clear();
1306
1307 for (auto *PredOfBB : predecessors(BB))
1308 // When BB cannot be killed, do not remove the edge between BB and
1309 // CommonPred.
1310 if (SeenPreds.insert(Ptr: PredOfBB).second && PredOfBB != CommonPred)
1311 Updates.push_back(Elt: {DominatorTree::Delete, PredOfBB, BB});
1312
1313 if (BBKillable)
1314 Updates.push_back(Elt: {DominatorTree::Delete, BB, Succ});
1315 }
1316
1317 if (isa<PHINode>(Val: Succ->begin())) {
1318 // If there is more than one pred of succ, and there are PHI nodes in
1319 // the successor, then we need to add incoming edges for the PHI nodes
1320 //
1321 const PredBlockVector BBPreds(predecessors(BB));
1322
1323 // Loop over all of the PHI nodes in the successor of BB.
1324 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(Val: I); ++I) {
1325 PHINode *PN = cast<PHINode>(Val&: I);
1326 redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN, CommonPred);
1327 }
1328 }
1329
1330 if (Succ->getSinglePredecessor()) {
1331 // BB is the only predecessor of Succ, so Succ will end up with exactly
1332 // the same predecessors BB had.
1333 // Copy over any phi, debug or lifetime instruction.
1334 BB->getTerminator()->eraseFromParent();
1335 Succ->splice(ToIt: Succ->getFirstNonPHIIt(), FromBB: BB);
1336 } else {
1337 while (PHINode *PN = dyn_cast<PHINode>(Val: &BB->front())) {
1338 // We explicitly check for such uses for merging phis.
1339 assert(PN->use_empty() && "There shouldn't be any uses here!");
1340 PN->eraseFromParent();
1341 }
1342 }
1343
1344 // If the unconditional branch we replaced contains non-debug llvm.loop
1345 // metadata, we add the metadata to the branch instructions in the
1346 // predecessors.
1347 if (Instruction *TI = BB->getTerminatorOrNull())
1348 if (TI->hasNonDebugLocLoopMetadata()) {
1349 MDNode *LoopMD = TI->getMetadata(KindID: LLVMContext::MD_loop);
1350 for (BasicBlock *Pred : predecessors(BB))
1351 Pred->getTerminator()->setMetadata(KindID: LLVMContext::MD_loop, Node: LoopMD);
1352 }
1353
1354 if (BBKillable) {
1355 // Everything that jumped to BB now goes to Succ.
1356 BB->replaceAllUsesWith(V: Succ);
1357
1358 if (!Succ->hasName())
1359 Succ->takeName(V: BB);
1360
1361 // Clear the successor list of BB to match updates applying to DTU later.
1362 if (BB->hasTerminator())
1363 BB->back().eraseFromParent();
1364
1365 new UnreachableInst(BB->getContext(), BB);
1366 assert(succ_empty(BB) && "The successor list of BB isn't empty before "
1367 "applying corresponding DTU updates.");
1368 } else if (BBPhisMergeable) {
1369 // Everything except CommonPred that jumped to BB now goes to Succ.
1370 BB->replaceUsesWithIf(New: Succ, ShouldReplace: [BBPreds, CommonPred](Use &U) -> bool {
1371 if (Instruction *UseInst = dyn_cast<Instruction>(Val: U.getUser()))
1372 return UseInst->getParent() != CommonPred &&
1373 BBPreds.contains(Ptr: UseInst->getParent());
1374 return false;
1375 });
1376 }
1377
1378 if (DTU)
1379 DTU->applyUpdates(Updates);
1380
1381 if (BBKillable)
1382 DeleteDeadBlock(BB, DTU);
1383
1384 return true;
1385}
1386
1387static bool
1388EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB,
1389 SmallPtrSetImpl<PHINode *> &ToRemove) {
1390 // This implementation doesn't currently consider undef operands
1391 // specially. Theoretically, two phis which are identical except for
1392 // one having an undef where the other doesn't could be collapsed.
1393
1394 bool Changed = false;
1395
1396 // Examine each PHI.
1397 // Note that increment of I must *NOT* be in the iteration_expression, since
1398 // we don't want to immediately advance when we restart from the beginning.
1399 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(Val&: I);) {
1400 ++I;
1401 // Is there an identical PHI node in this basic block?
1402 // Note that we only look in the upper square's triangle,
1403 // we already checked that the lower triangle PHI's aren't identical.
1404 for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(Val&: J); ++J) {
1405 if (ToRemove.contains(Ptr: DuplicatePN))
1406 continue;
1407 if (!DuplicatePN->isIdenticalToWhenDefined(I: PN))
1408 continue;
1409 // A duplicate. Replace this PHI with the base PHI.
1410 ++NumPHICSEs;
1411 DuplicatePN->replaceAllUsesWith(V: PN);
1412 ToRemove.insert(Ptr: DuplicatePN);
1413 Changed = true;
1414
1415 // The RAUW can change PHIs that we already visited.
1416 I = BB->begin();
1417 break; // Start over from the beginning.
1418 }
1419 }
1420 return Changed;
1421}
1422
1423static bool
1424EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB,
1425 SmallPtrSetImpl<PHINode *> &ToRemove) {
1426 // This implementation doesn't currently consider undef operands
1427 // specially. Theoretically, two phis which are identical except for
1428 // one having an undef where the other doesn't could be collapsed.
1429
1430 struct PHIDenseMapInfo {
1431 // WARNING: this logic must be kept in sync with
1432 // Instruction::isIdenticalToWhenDefined()!
1433 static unsigned getHashValueImpl(PHINode *PN) {
1434 // Compute a hash value on the operands. Instcombine will likely have
1435 // sorted them, which helps expose duplicates, but we have to check all
1436 // the operands to be safe in case instcombine hasn't run.
1437 return static_cast<unsigned>(
1438 hash_combine(args: hash_combine_range(R: PN->operand_values()),
1439 args: hash_combine_range(R: PN->blocks())));
1440 }
1441
1442 static unsigned getHashValue(PHINode *PN) {
1443#ifndef NDEBUG
1444 // If -phicse-debug-hash was specified, return a constant -- this
1445 // will force all hashing to collide, so we'll exhaustively search
1446 // the table for a match, and the assertion in isEqual will fire if
1447 // there's a bug causing equal keys to hash differently.
1448 if (PHICSEDebugHash)
1449 return 0;
1450#endif
1451 return getHashValueImpl(PN);
1452 }
1453
1454 static bool isEqualImpl(PHINode *LHS, PHINode *RHS) {
1455 return LHS->isIdenticalTo(I: RHS);
1456 }
1457
1458 static bool isEqual(PHINode *LHS, PHINode *RHS) {
1459 // These comparisons are nontrivial, so assert that equality implies
1460 // hash equality (DenseMap demands this as an invariant).
1461 bool Result = isEqualImpl(LHS, RHS);
1462 assert(!Result || getHashValueImpl(LHS) == getHashValueImpl(RHS));
1463 return Result;
1464 }
1465 };
1466
1467 // Set of unique PHINodes.
1468 DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
1469 PHISet.reserve(Size: 4 * PHICSENumPHISmallSize);
1470
1471 // Examine each PHI.
1472 bool Changed = false;
1473 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(Val: I++);) {
1474 if (ToRemove.contains(Ptr: PN))
1475 continue;
1476 auto Inserted = PHISet.insert(V: PN);
1477 if (!Inserted.second) {
1478 // A duplicate. Replace this PHI with its duplicate.
1479 ++NumPHICSEs;
1480 PN->replaceAllUsesWith(V: *Inserted.first);
1481 ToRemove.insert(Ptr: PN);
1482 Changed = true;
1483
1484 // The RAUW can change PHIs that we already visited. Start over from the
1485 // beginning.
1486 PHISet.clear();
1487 I = BB->begin();
1488 }
1489 }
1490
1491 return Changed;
1492}
1493
1494bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB,
1495 SmallPtrSetImpl<PHINode *> &ToRemove) {
1496 if (
1497#ifndef NDEBUG
1498 !PHICSEDebugHash &&
1499#endif
1500 hasNItemsOrLess(C: BB->phis(), N: PHICSENumPHISmallSize))
1501 return EliminateDuplicatePHINodesNaiveImpl(BB, ToRemove);
1502 return EliminateDuplicatePHINodesSetBasedImpl(BB, ToRemove);
1503}
1504
1505bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
1506 SmallPtrSet<PHINode *, 8> ToRemove;
1507 bool Changed = EliminateDuplicatePHINodes(BB, ToRemove);
1508 for (PHINode *PN : ToRemove)
1509 PN->eraseFromParent();
1510 return Changed;
1511}
1512
1513Align llvm::tryEnforceAlignment(Value *V, Align PrefAlign,
1514 const DataLayout &DL) {
1515 V = V->stripPointerCasts();
1516
1517 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val: V)) {
1518 // TODO: Ideally, this function would not be called if PrefAlign is smaller
1519 // than the current alignment, as the known bits calculation should have
1520 // already taken it into account. However, this is not always the case,
1521 // as computeKnownBits() has a depth limit, while stripPointerCasts()
1522 // doesn't.
1523 Align CurrentAlign = AI->getAlign();
1524 if (PrefAlign <= CurrentAlign)
1525 return CurrentAlign;
1526
1527 // If the preferred alignment is greater than the natural stack alignment
1528 // then don't round up. This avoids dynamic stack realignment.
1529 MaybeAlign StackAlign = DL.getStackAlignment();
1530 if (StackAlign && PrefAlign > *StackAlign)
1531 return CurrentAlign;
1532 AI->setAlignment(PrefAlign);
1533 return PrefAlign;
1534 }
1535
1536 if (auto *GV = dyn_cast<GlobalVariable>(Val: V)) {
1537 // TODO: as above, this shouldn't be necessary.
1538 Align CurrentAlign = GV->getPointerAlignment(DL);
1539 if (PrefAlign <= CurrentAlign)
1540 return CurrentAlign;
1541
1542 // If there is a large requested alignment and we can, bump up the alignment
1543 // of the global. If the memory we set aside for the global may not be the
1544 // memory used by the final program then it is impossible for us to reliably
1545 // enforce the preferred alignment.
1546 if (!GV->canIncreaseAlignment())
1547 return CurrentAlign;
1548
1549 if (GV->isThreadLocal()) {
1550 unsigned MaxTLSAlign = GV->getParent()->getMaxTLSAlignment() / CHAR_BIT;
1551 if (MaxTLSAlign && PrefAlign > Align(MaxTLSAlign))
1552 PrefAlign = Align(MaxTLSAlign);
1553 }
1554
1555 GV->setAlignment(PrefAlign);
1556 return PrefAlign;
1557 }
1558
1559 return Align(1);
1560}
1561
1562Align llvm::getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign,
1563 const DataLayout &DL,
1564 const Instruction *CtxI,
1565 AssumptionCache *AC,
1566 const DominatorTree *DT) {
1567 assert(V->getType()->isPointerTy() &&
1568 "getOrEnforceKnownAlignment expects a pointer!");
1569
1570 KnownBits Known = computeKnownBits(V, DL, AC, CtxI, DT);
1571 unsigned TrailZ = Known.countMinTrailingZeros();
1572
1573 // Avoid trouble with ridiculously large TrailZ values, such as
1574 // those computed from a null pointer.
1575 // LLVM doesn't support alignments larger than (1 << MaxAlignmentExponent).
1576 TrailZ = std::min(a: TrailZ, b: +Value::MaxAlignmentExponent);
1577
1578 Align Alignment = Align(1ull << std::min(a: Known.getBitWidth() - 1, b: TrailZ));
1579
1580 if (PrefAlign && *PrefAlign > Alignment)
1581 Alignment = std::max(a: Alignment, b: tryEnforceAlignment(V, PrefAlign: *PrefAlign, DL));
1582
1583 // We don't need to make any adjustment.
1584 return Alignment;
1585}
1586
1587///===---------------------------------------------------------------------===//
1588/// Dbg Intrinsic utilities
1589///
1590
1591/// See if there is a dbg.value intrinsic for DIVar for the PHI node.
1592static bool PhiHasDebugValue(DILocalVariable *DIVar,
1593 DIExpression *DIExpr,
1594 PHINode *APN) {
1595 // Since we can't guarantee that the original dbg.declare intrinsic
1596 // is removed by LowerDbgDeclare(), we need to make sure that we are
1597 // not inserting the same dbg.value intrinsic over and over.
1598 SmallVector<DbgVariableRecord *, 1> DbgVariableRecords;
1599 findDbgValues(V: APN, DbgVariableRecords);
1600 for (DbgVariableRecord *DVR : DbgVariableRecords) {
1601 assert(is_contained(DVR->location_ops(), APN));
1602 if ((DVR->getVariable() == DIVar) && (DVR->getExpression() == DIExpr))
1603 return true;
1604 }
1605 return false;
1606}
1607
1608/// Check if the alloc size of \p ValTy is large enough to cover the variable
1609/// (or fragment of the variable) described by \p DII.
1610///
1611/// This is primarily intended as a helper for the different
1612/// ConvertDebugDeclareToDebugValue functions. The dbg.declare that is converted
1613/// describes an alloca'd variable, so we need to use the alloc size of the
1614/// value when doing the comparison. E.g. an i1 value will be identified as
1615/// covering an n-bit fragment, if the store size of i1 is at least n bits.
1616static bool valueCoversEntireFragment(Type *ValTy, DbgVariableRecord *DVR) {
1617 const DataLayout &DL = DVR->getModule()->getDataLayout();
1618 TypeSize ValueSize = DL.getTypeAllocSizeInBits(Ty: ValTy);
1619 if (std::optional<uint64_t> FragmentSize =
1620 DVR->getExpression()->getActiveBits(Var: DVR->getVariable()))
1621 return TypeSize::isKnownGE(LHS: ValueSize, RHS: TypeSize::getFixed(ExactSize: *FragmentSize));
1622
1623 // We can't always calculate the size of the DI variable (e.g. if it is a
1624 // VLA). Try to use the size of the alloca that the dbg intrinsic describes
1625 // instead.
1626 if (DVR->isAddressOfVariable()) {
1627 // DVR should have exactly 1 location when it is an address.
1628 assert(DVR->getNumVariableLocationOps() == 1 &&
1629 "address of variable must have exactly 1 location operand.");
1630 if (auto *AI =
1631 dyn_cast_or_null<AllocaInst>(Val: DVR->getVariableLocationOp(OpIdx: 0))) {
1632 if (std::optional<TypeSize> FragmentSize = AI->getAllocationSizeInBits(DL)) {
1633 return TypeSize::isKnownGE(LHS: ValueSize, RHS: *FragmentSize);
1634 }
1635 }
1636 }
1637 // Could not determine size of variable. Conservatively return false.
1638 return false;
1639}
1640
1641static void insertDbgValueOrDbgVariableRecord(DIBuilder &Builder, Value *DV,
1642 DILocalVariable *DIVar,
1643 DIExpression *DIExpr,
1644 const DebugLoc &NewLoc,
1645 BasicBlock::iterator Instr) {
1646 ValueAsMetadata *DVAM = ValueAsMetadata::get(V: DV);
1647 DbgVariableRecord *DVRec =
1648 new DbgVariableRecord(DVAM, DIVar, DIExpr, NewLoc.get());
1649 Instr->getParent()->insertDbgRecordBefore(DR: DVRec, Here: Instr);
1650}
1651
1652static DIExpression *dropInitialDeref(const DIExpression *DIExpr) {
1653 int NumEltDropped = DIExpr->getElements()[0] == dwarf::DW_OP_LLVM_arg ? 3 : 1;
1654 return DIExpression::get(Context&: DIExpr->getContext(),
1655 Elements: DIExpr->getElements().drop_front(N: NumEltDropped));
1656}
1657
1658void llvm::ConvertDebugDeclareToDebugValue(DbgVariableRecord *DVR,
1659 StoreInst *SI, DIBuilder &Builder) {
1660 assert(DVR->isAddressOfVariable() || DVR->isDbgAssign());
1661 auto *DIVar = DVR->getVariable();
1662 assert(DIVar && "Missing variable");
1663 auto *DIExpr = DVR->getExpression();
1664 Value *DV = SI->getValueOperand();
1665
1666 if (isa<UndefValue>(Val: DV) && !isa<PoisonValue>(Val: DV))
1667 return;
1668
1669 DebugLoc NewLoc = getDebugValueLoc(DVR);
1670
1671 // If the alloca describes the variable itself, i.e. the expression in the
1672 // dbg.declare doesn't start with a dereference, we can perform the
1673 // conversion if the value covers the entire fragment of DII.
1674 // If the alloca describes the *address* of DIVar, i.e. DIExpr is
1675 // *just* a DW_OP_deref, we use DV as is for the dbg.value.
1676 // We conservatively ignore other dereferences, because the following two are
1677 // not equivalent:
1678 // dbg.declare(alloca, ..., !Expr(deref, plus_uconstant, 2))
1679 // dbg.value(DV, ..., !Expr(deref, plus_uconstant, 2))
1680 // The former is adding 2 to the address of the variable, whereas the latter
1681 // is adding 2 to the value of the variable. As such, we insist on just a
1682 // deref expression.
1683 bool CanConvert =
1684 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1685 valueCoversEntireFragment(ValTy: DV->getType(), DVR));
1686 if (CanConvert) {
1687 insertDbgValueOrDbgVariableRecord(Builder, DV, DIVar, DIExpr, NewLoc,
1688 Instr: SI->getIterator());
1689 return;
1690 }
1691
1692 // FIXME: If storing to a part of the variable described by the dbg.declare,
1693 // then we want to insert a dbg.value for the corresponding fragment.
1694 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DVR
1695 << '\n');
1696
1697 // For now, when there is a store to parts of the variable (but we do not
1698 // know which part) we insert an dbg.value intrinsic to indicate that we
1699 // know nothing about the variable's content.
1700 DV = PoisonValue::get(T: DV->getType());
1701 ValueAsMetadata *DVAM = ValueAsMetadata::get(V: DV);
1702 DbgVariableRecord *NewDVR =
1703 new DbgVariableRecord(DVAM, DIVar, DIExpr, NewLoc.get());
1704 SI->getParent()->insertDbgRecordBefore(DR: NewDVR, Here: SI->getIterator());
1705}
1706
1707void llvm::InsertDebugValueAtStoreLoc(DbgVariableRecord *DVR, StoreInst *SI,
1708 DIBuilder &Builder) {
1709 auto *DIVar = DVR->getVariable();
1710 assert(DIVar && "Missing variable");
1711 auto *DIExpr = DVR->getExpression();
1712 DIExpr = dropInitialDeref(DIExpr);
1713 Value *DV = SI->getValueOperand();
1714
1715 DebugLoc NewLoc = getDebugValueLoc(DVR);
1716
1717 insertDbgValueOrDbgVariableRecord(Builder, DV, DIVar, DIExpr, NewLoc,
1718 Instr: SI->getIterator());
1719}
1720
1721void llvm::ConvertDebugDeclareToDebugValue(DbgVariableRecord *DVR, LoadInst *LI,
1722 DIBuilder &Builder) {
1723 auto *DIVar = DVR->getVariable();
1724 auto *DIExpr = DVR->getExpression();
1725 assert(DIVar && "Missing variable");
1726
1727 if (!valueCoversEntireFragment(ValTy: LI->getType(), DVR)) {
1728 // FIXME: If only referring to a part of the variable described by the
1729 // dbg.declare, then we want to insert a DbgVariableRecord for the
1730 // corresponding fragment.
1731 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to DbgVariableRecord: "
1732 << *DVR << '\n');
1733 return;
1734 }
1735
1736 DebugLoc NewLoc = getDebugValueLoc(DVR);
1737
1738 // We are now tracking the loaded value instead of the address. In the
1739 // future if multi-location support is added to the IR, it might be
1740 // preferable to keep tracking both the loaded value and the original
1741 // address in case the alloca can not be elided.
1742
1743 // Create a DbgVariableRecord directly and insert.
1744 ValueAsMetadata *LIVAM = ValueAsMetadata::get(V: LI);
1745 DbgVariableRecord *DV =
1746 new DbgVariableRecord(LIVAM, DIVar, DIExpr, NewLoc.get());
1747 LI->getParent()->insertDbgRecordAfter(DR: DV, I: LI);
1748}
1749
1750/// Determine whether this debug variable is a not a basic type.
1751/// We strip through DIDerivedType modifiers (typedefs, const, etc.)
1752/// to find the underlying type to decide if it seems perhaps worthwhile to
1753/// do LowerDbgDeclare.
1754static bool isCompositeType(DbgVariableRecord *DVR) {
1755 DIType *Ty = DVR->getVariable()->getType();
1756 if (Ty == nullptr)
1757 return true;
1758 // Strip through modifier types to find the underlying type.
1759 while (auto *DTy = dyn_cast<DIDerivedType>(Val: Ty)) {
1760 switch (DTy->getTag()) {
1761 case dwarf::DW_TAG_pointer_type:
1762 case dwarf::DW_TAG_reference_type:
1763 case dwarf::DW_TAG_rvalue_reference_type:
1764 case dwarf::DW_TAG_ptr_to_member_type:
1765 case dwarf::DW_TAG_LLVM_ptrauth_type:
1766 return false;
1767 case dwarf::DW_TAG_typedef:
1768 case dwarf::DW_TAG_const_type:
1769 case dwarf::DW_TAG_volatile_type:
1770 case dwarf::DW_TAG_restrict_type:
1771 case dwarf::DW_TAG_atomic_type:
1772 case dwarf::DW_TAG_immutable_type:
1773 Ty = DTy->getBaseType();
1774 continue;
1775 default:
1776 break;
1777 }
1778 break;
1779 }
1780 return !isa<DIBasicType>(Val: Ty);
1781}
1782
1783void llvm::ConvertDebugDeclareToDebugValue(DbgVariableRecord *DVR, PHINode *APN,
1784 DIBuilder &Builder) {
1785 auto *DIVar = DVR->getVariable();
1786 auto *DIExpr = DVR->getExpression();
1787 assert(DIVar && "Missing variable");
1788
1789 if (PhiHasDebugValue(DIVar, DIExpr, APN))
1790 return;
1791
1792 if (!valueCoversEntireFragment(ValTy: APN->getType(), DVR)) {
1793 // FIXME: If only referring to a part of the variable described by the
1794 // dbg.declare, then we want to insert a DbgVariableRecord for the
1795 // corresponding fragment.
1796 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to DbgVariableRecord: "
1797 << *DVR << '\n');
1798 return;
1799 }
1800
1801 BasicBlock *BB = APN->getParent();
1802 auto InsertionPt = BB->getFirstInsertionPt();
1803
1804 DebugLoc NewLoc = getDebugValueLoc(DVR);
1805
1806 // The block may be a catchswitch block, which does not have a valid
1807 // insertion point.
1808 // FIXME: Insert DbgVariableRecord markers in the successors when appropriate.
1809 if (InsertionPt != BB->end()) {
1810 insertDbgValueOrDbgVariableRecord(Builder, DV: APN, DIVar, DIExpr, NewLoc,
1811 Instr: InsertionPt);
1812 }
1813}
1814
1815/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1816/// of llvm.dbg.value intrinsics.
1817bool llvm::LowerDbgDeclare(Function &F) {
1818 bool Changed = false;
1819 DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1820 SmallVector<DbgDeclareInst *, 4> Dbgs;
1821 SmallVector<DbgVariableRecord *> DVRs;
1822 for (auto &FI : F) {
1823 for (Instruction &BI : FI) {
1824 if (auto *DDI = dyn_cast<DbgDeclareInst>(Val: &BI))
1825 Dbgs.push_back(Elt: DDI);
1826 for (DbgVariableRecord &DVR : filterDbgVars(R: BI.getDbgRecordRange())) {
1827 if (DVR.getType() == DbgVariableRecord::LocationType::Declare)
1828 DVRs.push_back(Elt: &DVR);
1829 }
1830 }
1831 }
1832
1833 if (Dbgs.empty() && DVRs.empty())
1834 return Changed;
1835
1836 auto LowerOne = [&](DbgVariableRecord *DDI) {
1837 AllocaInst *AI =
1838 dyn_cast_or_null<AllocaInst>(Val: DDI->getVariableLocationOp(OpIdx: 0));
1839 // If this is an alloca for a scalar variable, insert a dbg.value
1840 // at each load and store to the alloca and erase the dbg.declare.
1841 // The dbg.values allow tracking a variable even if it is not
1842 // stored on the stack, while the dbg.declare can only describe
1843 // the stack slot (and at a lexical-scope granularity). Later
1844 // passes will attempt to elide the stack slot.
1845 // Skip VLAs (dynamic allocas) and composite types (arrays/structs) since
1846 // they can't be represented as a single dbg.value.
1847 if (!AI || !isa<Constant>(Val: AI->getArraySize()) || isCompositeType(DVR: DDI))
1848 return;
1849
1850 // A volatile load/store means that the alloca can't be elided anyway.
1851 // Just look at direct uses however, and ignore any other instructions.
1852 if (llvm::any_of(Range: AI->users(), P: [](User *U) -> bool {
1853 if (LoadInst *LI = dyn_cast<LoadInst>(Val: U))
1854 return LI->isVolatile();
1855 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U))
1856 return SI->isVolatile();
1857 return false;
1858 }))
1859 return;
1860
1861 SmallVector<const Value *, 8> WorkList;
1862 WorkList.push_back(Elt: AI);
1863 while (!WorkList.empty()) {
1864 const Value *V = WorkList.pop_back_val();
1865 for (const auto &AIUse : V->uses()) {
1866 User *U = AIUse.getUser();
1867 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) {
1868 if (AIUse.getOperandNo() == 1)
1869 ConvertDebugDeclareToDebugValue(DVR: DDI, SI, Builder&: DIB);
1870 } else if (LoadInst *LI = dyn_cast<LoadInst>(Val: U)) {
1871 ConvertDebugDeclareToDebugValue(DVR: DDI, LI, Builder&: DIB);
1872 } else if (CallInst *CI = dyn_cast<CallInst>(Val: U)) {
1873 // This is a call by-value or some other instruction that takes a
1874 // pointer to the variable. Insert a *value* intrinsic that describes
1875 // the variable by dereferencing the alloca.
1876 if (!CI->isLifetimeStartOrEnd()) {
1877 DebugLoc NewLoc = getDebugValueLoc(DVR: DDI);
1878 auto *DerefExpr =
1879 DIExpression::append(Expr: DDI->getExpression(), Ops: dwarf::DW_OP_deref);
1880 insertDbgValueOrDbgVariableRecord(Builder&: DIB, DV: AI, DIVar: DDI->getVariable(),
1881 DIExpr: DerefExpr, NewLoc,
1882 Instr: CI->getIterator());
1883 }
1884 } else if (BitCastInst *BI = dyn_cast<BitCastInst>(Val: U)) {
1885 if (BI->getType()->isPointerTy())
1886 WorkList.push_back(Elt: BI);
1887 }
1888 }
1889 }
1890 DDI->eraseFromParent();
1891 Changed = true;
1892 };
1893
1894 for_each(Range&: DVRs, F: LowerOne);
1895
1896 if (Changed)
1897 for (BasicBlock &BB : F)
1898 RemoveRedundantDbgInstrs(BB: &BB);
1899
1900 return Changed;
1901}
1902
1903/// Propagate dbg.value records through the newly inserted PHIs.
1904void llvm::insertDebugValuesForPHIs(BasicBlock *BB,
1905 SmallVectorImpl<PHINode *> &InsertedPHIs) {
1906 assert(BB && "No BasicBlock to clone DbgVariableRecord(s) from.");
1907 if (InsertedPHIs.size() == 0)
1908 return;
1909
1910 // Map existing PHI nodes to their DbgVariableRecords.
1911 DenseMap<Value *, DbgVariableRecord *> DbgValueMap;
1912 for (auto &I : *BB) {
1913 for (DbgVariableRecord &DVR : filterDbgVars(R: I.getDbgRecordRange())) {
1914 for (Value *V : DVR.location_ops())
1915 if (auto *Loc = dyn_cast_or_null<PHINode>(Val: V))
1916 DbgValueMap.insert(KV: {Loc, &DVR});
1917 }
1918 }
1919 if (DbgValueMap.size() == 0)
1920 return;
1921
1922 // Map a pair of the destination BB and old DbgVariableRecord to the new
1923 // DbgVariableRecord, so that if a DbgVariableRecord is being rewritten to use
1924 // more than one of the inserted PHIs in the same destination BB, we can
1925 // update the same DbgVariableRecord with all the new PHIs instead of creating
1926 // one copy for each.
1927 MapVector<std::pair<BasicBlock *, DbgVariableRecord *>, DbgVariableRecord *>
1928 NewDbgValueMap;
1929 // Then iterate through the new PHIs and look to see if they use one of the
1930 // previously mapped PHIs. If so, create a new DbgVariableRecord that will
1931 // propagate the info through the new PHI. If we use more than one new PHI in
1932 // a single destination BB with the same old dbg.value, merge the updates so
1933 // that we get a single new DbgVariableRecord with all the new PHIs.
1934 for (auto PHI : InsertedPHIs) {
1935 BasicBlock *Parent = PHI->getParent();
1936 // Avoid inserting a debug-info record into an EH block.
1937 if (Parent->getFirstNonPHIIt()->isEHPad())
1938 continue;
1939 for (auto VI : PHI->operand_values()) {
1940 auto V = DbgValueMap.find(Val: VI);
1941 if (V != DbgValueMap.end()) {
1942 DbgVariableRecord *DbgII = cast<DbgVariableRecord>(Val: V->second);
1943 auto NewDI = NewDbgValueMap.find(Key: {Parent, DbgII});
1944 if (NewDI == NewDbgValueMap.end()) {
1945 DbgVariableRecord *NewDbgII = DbgII->clone();
1946 NewDI = NewDbgValueMap.insert(KV: {{Parent, DbgII}, NewDbgII}).first;
1947 }
1948 DbgVariableRecord *NewDbgII = NewDI->second;
1949 // If PHI contains VI as an operand more than once, we may
1950 // replaced it in NewDbgII; confirm that it is present.
1951 if (is_contained(Range: NewDbgII->location_ops(), Element: VI))
1952 NewDbgII->replaceVariableLocationOp(OldValue: VI, NewValue: PHI);
1953 }
1954 }
1955 }
1956 // Insert the new DbgVariableRecords into their destination blocks.
1957 for (auto DI : NewDbgValueMap) {
1958 BasicBlock *Parent = DI.first.first;
1959 DbgVariableRecord *NewDbgII = DI.second;
1960 auto InsertionPt = Parent->getFirstInsertionPt();
1961 assert(InsertionPt != Parent->end() && "Ill-formed basic block");
1962
1963 Parent->insertDbgRecordBefore(DR: NewDbgII, Here: InsertionPt);
1964 }
1965}
1966
1967bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress,
1968 DIBuilder &Builder, uint8_t DIExprFlags,
1969 int Offset) {
1970 TinyPtrVector<DbgVariableRecord *> DVRDeclares = findDVRDeclares(V: Address);
1971
1972 auto ReplaceOne = [&](DbgVariableRecord *DII) {
1973 assert(DII->getVariable() && "Missing variable");
1974 auto *DIExpr = DII->getExpression();
1975 DIExpr = DIExpression::prepend(Expr: DIExpr, Flags: DIExprFlags, Offset);
1976 DII->setExpression(DIExpr);
1977 DII->replaceVariableLocationOp(OldValue: Address, NewValue: NewAddress);
1978 };
1979
1980 for_each(Range&: DVRDeclares, F: ReplaceOne);
1981
1982 return !DVRDeclares.empty();
1983}
1984
1985static void updateOneDbgValueForAlloca(const DebugLoc &Loc,
1986 DILocalVariable *DIVar,
1987 DIExpression *DIExpr, Value *NewAddress,
1988 DbgVariableRecord *DVR,
1989 DIBuilder &Builder, int Offset) {
1990 assert(DIVar && "Missing variable");
1991
1992 // This is an alloca-based dbg.value/DbgVariableRecord. The first thing it
1993 // should do with the alloca pointer is dereference it. Otherwise we don't
1994 // know how to handle it and give up.
1995 if (!DIExpr || DIExpr->getNumElements() < 1 ||
1996 DIExpr->getElement(I: 0) != dwarf::DW_OP_deref)
1997 return;
1998
1999 // Insert the offset before the first deref.
2000 if (Offset)
2001 DIExpr = DIExpression::prepend(Expr: DIExpr, Flags: 0, Offset);
2002
2003 DVR->setExpression(DIExpr);
2004 DVR->replaceVariableLocationOp(OpIdx: 0u, NewValue: NewAddress);
2005}
2006
2007void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
2008 DIBuilder &Builder, int Offset) {
2009 SmallVector<DbgVariableRecord *, 1> DPUsers;
2010 findDbgValues(V: AI, DbgVariableRecords&: DPUsers);
2011
2012 // Replace any DbgVariableRecords that use this alloca.
2013 for (DbgVariableRecord *DVR : DPUsers)
2014 updateOneDbgValueForAlloca(Loc: DVR->getDebugLoc(), DIVar: DVR->getVariable(),
2015 DIExpr: DVR->getExpression(), NewAddress: NewAllocaAddress, DVR,
2016 Builder, Offset);
2017}
2018
2019void llvm::salvageDebugInfo(Instruction &I) {
2020 SmallVector<DbgVariableRecord *, 1> DbgRecords;
2021 findDbgUsers(V: &I, DbgVariableRecords&: DbgRecords);
2022 salvageDebugInfoForDbgValues(I, DbgRecords);
2023}
2024
2025/// Salvage the address of \p Assign, which the caller has checked is \p I. An
2026/// address we cannot salvage stays as it is rather than stopping the caller,
2027/// which counts the record as processed either way and goes on to salvage its
2028/// variable location.
2029static void salvageDbgAssignAddress(Instruction &I, DbgVariableRecord &Assign) {
2030 assert(Assign.isDbgAssign() && Assign.getAddress() == &I &&
2031 "dbg.assign must use salvaged instruction as its address");
2032 assert(!Assign.getAddressExpression()->getFragmentInfo().has_value() &&
2033 "address-expression shouldn't have fragment info");
2034
2035 // The address component of a dbg.assign cannot be variadic.
2036 uint64_t CurrentLocOps = 0;
2037 SmallVector<Value *, 4> AdditionalValues;
2038 SmallVector<uint64_t, 16> Ops;
2039 Value *NewAddress =
2040 salvageDebugInfoImpl(I, CurrentLocOps, Ops, AdditionalValues);
2041
2042 // Keep an address we cannot salvage. If I is deleted, its remaining metadata
2043 // use is replaced with poison.
2044 if (!NewAddress)
2045 return;
2046
2047 DIExpression *SalvagedExpr = DIExpression::appendOpsToArg(
2048 Expr: Assign.getAddressExpression(), Ops, ArgNo: 0, /*StackValue=*/false);
2049 assert(!SalvagedExpr->getFragmentInfo().has_value() &&
2050 "address-expression shouldn't have fragment info");
2051
2052 SalvagedExpr = SalvagedExpr->foldConstantMath();
2053
2054 // Salvage succeeds if no additional values are required.
2055 if (AdditionalValues.empty()) {
2056 Assign.setAddress(NewAddress);
2057 Assign.setAddressExpression(SalvagedExpr);
2058 } else {
2059 Assign.setKillAddress();
2060 }
2061}
2062
2063/// Rewrite \p DVR's variable location in terms of \p I's operands. Return false
2064/// and leave the record alone when the instruction cannot be salvaged. Return
2065/// true once it can, including when the location ends up killed.
2066static bool salvageDbgVariableLocation(Instruction &I, DbgVariableRecord &DVR) {
2067 // These are arbitrary chosen limits on the maximum number of values and the
2068 // maximum size of a debug expression we can salvage up to, used for
2069 // performance reasons.
2070 const unsigned MaxDebugArgs = 16;
2071 const unsigned MaxExpressionSize = 128;
2072
2073 // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they
2074 // are implicitly pointing out the value as a DWARF memory location
2075 // description.
2076 const bool StackValue = !DVR.isAddressOfVariable();
2077 auto LocationOps = DVR.location_ops();
2078 assert(is_contained(LocationOps, &I) &&
2079 "DbgVariableRecord must use salvaged instruction as its location");
2080 SmallVector<Value *, 4> AdditionalValues;
2081 // 'I' may appear more than once in DVR's location ops, and each use of 'I'
2082 // must be updated in the DIExpression and potentially have additional
2083 // values added; thus we call salvageDebugInfoImpl for each 'I' instance in
2084 // LocationOps.
2085 Value *Replacement = nullptr;
2086 DIExpression *SalvagedExpr = DVR.getExpression();
2087 auto LocIt = find(Range&: LocationOps, Val: &I);
2088 while (SalvagedExpr && LocIt != LocationOps.end()) {
2089 SmallVector<uint64_t, 16> Ops;
2090 unsigned LocationIndex = std::distance(first: LocationOps.begin(), last: LocIt);
2091 uint64_t CurrentLocOps = SalvagedExpr->getNumLocationOperands();
2092 Replacement = salvageDebugInfoImpl(I, CurrentLocOps, Ops, AdditionalValues);
2093 if (!Replacement)
2094 break;
2095 SalvagedExpr = DIExpression::appendOpsToArg(Expr: SalvagedExpr, Ops,
2096 ArgNo: LocationIndex, StackValue);
2097 LocIt = std::find(first: ++LocIt, last: LocationOps.end(), val: &I);
2098 }
2099 // The failure conditions in salvageDebugInfoImpl do not depend on
2100 // CurrentLocOps, so failure can only occur on the first occurrence.
2101 if (!Replacement)
2102 return false;
2103
2104 SalvagedExpr = SalvagedExpr->foldConstantMath();
2105 DVR.replaceVariableLocationOp(OldValue: &I, NewValue: Replacement);
2106 const bool FitsExpressionLimit =
2107 SalvagedExpr->getNumElements() <= MaxExpressionSize;
2108 if (AdditionalValues.empty() && FitsExpressionLimit) {
2109 DVR.setExpression(SalvagedExpr);
2110 } else if (!DVR.isAddressOfVariable() && FitsExpressionLimit &&
2111 DVR.getNumVariableLocationOps() + AdditionalValues.size() <=
2112 MaxDebugArgs) {
2113 DVR.addVariableLocationOps(NewValues: AdditionalValues, NewExpr: SalvagedExpr);
2114 } else {
2115 // Do not salvage using DIArgList for dbg.addr/dbg.declare, as it is
2116 // currently only valid for stack value expressions.
2117 // Also do not salvage if the resulting DIArgList would contain an
2118 // unreasonably large number of values.
2119 DVR.setKillLocation();
2120 }
2121 LLVM_DEBUG(dbgs() << "SALVAGE: " << DVR << '\n');
2122 return true;
2123}
2124
2125void llvm::salvageDebugInfoForDbgValues(
2126 Instruction &I, ArrayRef<DbgVariableRecord *> DbgRecords) {
2127 bool ProcessedAnyUse = false;
2128
2129 for (auto *DVR : DbgRecords) {
2130 // replaceVariableLocationOp also updates a matching dbg.assign address, so
2131 // salvage the address before changing the variable location.
2132 if (DVR->isDbgAssign()) {
2133 if (DVR->getAddress() == &I) {
2134 salvageDbgAssignAddress(I, Assign&: *DVR);
2135 ProcessedAnyUse = true;
2136 }
2137 if (DVR->getValue() != &I)
2138 continue;
2139 }
2140 if (!salvageDbgVariableLocation(I, DVR&: *DVR))
2141 break;
2142 ProcessedAnyUse = true;
2143 }
2144
2145 if (ProcessedAnyUse)
2146 return;
2147
2148 for (auto *DVR : DbgRecords)
2149 DVR->setKillLocation();
2150}
2151
2152Value *getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL,
2153 uint64_t CurrentLocOps,
2154 SmallVectorImpl<uint64_t> &Opcodes,
2155 SmallVectorImpl<Value *> &AdditionalValues) {
2156 unsigned BitWidth = DL.getIndexSizeInBits(AS: GEP->getPointerAddressSpace());
2157 // Rewrite a GEP into a DIExpression.
2158 SmallMapVector<Value *, APInt, 4> VariableOffsets;
2159 APInt ConstantOffset(BitWidth, 0);
2160 if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
2161 return nullptr;
2162 if (!VariableOffsets.empty() && !CurrentLocOps) {
2163 Opcodes.insert(I: Opcodes.begin(), IL: {dwarf::DW_OP_LLVM_arg, 0});
2164 CurrentLocOps = 1;
2165 }
2166 for (const auto &Offset : VariableOffsets) {
2167 AdditionalValues.push_back(Elt: Offset.first);
2168 assert(Offset.second.isStrictlyPositive() &&
2169 "Expected strictly positive multiplier for offset.");
2170 Opcodes.append(IL: {dwarf::DW_OP_LLVM_arg, CurrentLocOps++, dwarf::DW_OP_constu,
2171 Offset.second.getZExtValue(), dwarf::DW_OP_mul,
2172 dwarf::DW_OP_plus});
2173 }
2174 DIExpression::appendOffset(Ops&: Opcodes, Offset: ConstantOffset.getSExtValue());
2175 return GEP->getOperand(i_nocapture: 0);
2176}
2177
2178uint64_t getDwarfOpForBinOp(Instruction::BinaryOps Opcode) {
2179 switch (Opcode) {
2180 case Instruction::Add:
2181 return dwarf::DW_OP_plus;
2182 case Instruction::Sub:
2183 return dwarf::DW_OP_minus;
2184 case Instruction::Mul:
2185 return dwarf::DW_OP_mul;
2186 case Instruction::SDiv:
2187 return dwarf::DW_OP_div;
2188 case Instruction::SRem:
2189 return dwarf::DW_OP_mod;
2190 case Instruction::Or:
2191 return dwarf::DW_OP_or;
2192 case Instruction::And:
2193 return dwarf::DW_OP_and;
2194 case Instruction::Xor:
2195 return dwarf::DW_OP_xor;
2196 case Instruction::Shl:
2197 return dwarf::DW_OP_shl;
2198 case Instruction::LShr:
2199 return dwarf::DW_OP_shr;
2200 case Instruction::AShr:
2201 return dwarf::DW_OP_shra;
2202 default:
2203 // TODO: Salvage from each kind of binop we know about.
2204 return 0;
2205 }
2206}
2207
2208static void handleSSAValueOperands(uint64_t CurrentLocOps,
2209 SmallVectorImpl<uint64_t> &Opcodes,
2210 SmallVectorImpl<Value *> &AdditionalValues,
2211 Instruction *I) {
2212 if (!CurrentLocOps) {
2213 Opcodes.append(IL: {dwarf::DW_OP_LLVM_arg, 0});
2214 CurrentLocOps = 1;
2215 }
2216 Opcodes.append(IL: {dwarf::DW_OP_LLVM_arg, CurrentLocOps});
2217 AdditionalValues.push_back(Elt: I->getOperand(i: 1));
2218}
2219
2220Value *getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps,
2221 SmallVectorImpl<uint64_t> &Opcodes,
2222 SmallVectorImpl<Value *> &AdditionalValues) {
2223 // Handle binary operations with constant integer operands as a special case.
2224 auto *ConstInt = dyn_cast<ConstantInt>(Val: BI->getOperand(i_nocapture: 1));
2225 // Values wider than 64 bits cannot be represented within a DIExpression.
2226 if (ConstInt && ConstInt->getBitWidth() > 64)
2227 return nullptr;
2228
2229 Instruction::BinaryOps BinOpcode = BI->getOpcode();
2230 // Push any Constant Int operand onto the expression stack.
2231 if (ConstInt) {
2232 uint64_t Val = ConstInt->getSExtValue();
2233 // Add or Sub Instructions with a constant operand can potentially be
2234 // simplified.
2235 if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
2236 uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
2237 DIExpression::appendOffset(Ops&: Opcodes, Offset);
2238 return BI->getOperand(i_nocapture: 0);
2239 }
2240 Opcodes.append(IL: {dwarf::DW_OP_constu, Val});
2241 } else {
2242 handleSSAValueOperands(CurrentLocOps, Opcodes, AdditionalValues, I: BI);
2243 }
2244
2245 // Add salvaged binary operator to expression stack, if it has a valid
2246 // representation in a DIExpression.
2247 uint64_t DwarfBinOp = getDwarfOpForBinOp(Opcode: BinOpcode);
2248 if (!DwarfBinOp)
2249 return nullptr;
2250 Opcodes.push_back(Elt: DwarfBinOp);
2251 return BI->getOperand(i_nocapture: 0);
2252}
2253
2254uint64_t getDwarfOpForIcmpPred(CmpInst::Predicate Pred) {
2255 // The signedness of the operation is implicit in the typed stack, signed and
2256 // unsigned instructions map to the same DWARF opcode.
2257 switch (Pred) {
2258 case CmpInst::ICMP_EQ:
2259 return dwarf::DW_OP_eq;
2260 case CmpInst::ICMP_NE:
2261 return dwarf::DW_OP_ne;
2262 case CmpInst::ICMP_UGT:
2263 case CmpInst::ICMP_SGT:
2264 return dwarf::DW_OP_gt;
2265 case CmpInst::ICMP_UGE:
2266 case CmpInst::ICMP_SGE:
2267 return dwarf::DW_OP_ge;
2268 case CmpInst::ICMP_ULT:
2269 case CmpInst::ICMP_SLT:
2270 return dwarf::DW_OP_lt;
2271 case CmpInst::ICMP_ULE:
2272 case CmpInst::ICMP_SLE:
2273 return dwarf::DW_OP_le;
2274 default:
2275 return 0;
2276 }
2277}
2278
2279Value *getSalvageOpsForIcmpOp(ICmpInst *Icmp, uint64_t CurrentLocOps,
2280 SmallVectorImpl<uint64_t> &Opcodes,
2281 SmallVectorImpl<Value *> &AdditionalValues) {
2282 // Handle icmp operations with constant integer operands as a special case.
2283 auto *ConstInt = dyn_cast<ConstantInt>(Val: Icmp->getOperand(i_nocapture: 1));
2284 // Values wider than 64 bits cannot be represented within a DIExpression.
2285 if (ConstInt && ConstInt->getBitWidth() > 64)
2286 return nullptr;
2287 // Push any Constant Int operand onto the expression stack.
2288 if (ConstInt) {
2289 if (Icmp->isSigned())
2290 Opcodes.push_back(Elt: dwarf::DW_OP_consts);
2291 else
2292 Opcodes.push_back(Elt: dwarf::DW_OP_constu);
2293 uint64_t Val = ConstInt->getSExtValue();
2294 Opcodes.push_back(Elt: Val);
2295 } else {
2296 handleSSAValueOperands(CurrentLocOps, Opcodes, AdditionalValues, I: Icmp);
2297 }
2298
2299 // Add salvaged binary operator to expression stack, if it has a valid
2300 // representation in a DIExpression.
2301 uint64_t DwarfIcmpOp = getDwarfOpForIcmpPred(Pred: Icmp->getPredicate());
2302 if (!DwarfIcmpOp)
2303 return nullptr;
2304 Opcodes.push_back(Elt: DwarfIcmpOp);
2305 return Icmp->getOperand(i_nocapture: 0);
2306}
2307
2308Value *llvm::salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps,
2309 SmallVectorImpl<uint64_t> &Ops,
2310 SmallVectorImpl<Value *> &AdditionalValues) {
2311 auto &M = *I.getModule();
2312 auto &DL = M.getDataLayout();
2313
2314 if (auto *CI = dyn_cast<CastInst>(Val: &I)) {
2315 Value *FromValue = CI->getOperand(i_nocapture: 0);
2316 // No-op casts are irrelevant for debug info.
2317 if (CI->isNoopCast(DL)) {
2318 return FromValue;
2319 }
2320
2321 Type *Type = CI->getType();
2322 if (Type->isPointerTy())
2323 Type = DL.getIntPtrType(Type);
2324 // Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged.
2325 if (Type->isVectorTy() ||
2326 !(isa<TruncInst>(Val: &I) || isa<SExtInst>(Val: &I) || isa<ZExtInst>(Val: &I) ||
2327 isa<IntToPtrInst>(Val: &I) || isa<PtrToIntInst>(Val: &I)))
2328 return nullptr;
2329
2330 llvm::Type *FromType = FromValue->getType();
2331 if (FromType->isPointerTy())
2332 FromType = DL.getIntPtrType(FromType);
2333
2334 unsigned FromTypeBitSize = FromType->getScalarSizeInBits();
2335 unsigned ToTypeBitSize = Type->getScalarSizeInBits();
2336
2337 auto ExtOps = DIExpression::getExtOps(FromSize: FromTypeBitSize, ToSize: ToTypeBitSize,
2338 Signed: isa<SExtInst>(Val: &I));
2339 Ops.append(in_start: ExtOps.begin(), in_end: ExtOps.end());
2340 return FromValue;
2341 }
2342
2343 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: &I))
2344 return getSalvageOpsForGEP(GEP, DL, CurrentLocOps, Opcodes&: Ops, AdditionalValues);
2345 if (auto *BI = dyn_cast<BinaryOperator>(Val: &I))
2346 return getSalvageOpsForBinOp(BI, CurrentLocOps, Opcodes&: Ops, AdditionalValues);
2347 if (auto *IC = dyn_cast<ICmpInst>(Val: &I))
2348 return getSalvageOpsForIcmpOp(Icmp: IC, CurrentLocOps, Opcodes&: Ops, AdditionalValues);
2349
2350 // *Not* to do: we should not attempt to salvage load instructions,
2351 // because the validity and lifetime of a dbg.value containing
2352 // DW_OP_deref becomes difficult to analyze. See PR40628 for examples.
2353 return nullptr;
2354}
2355
2356/// A replacement for a dbg.value expression.
2357using DbgValReplacement = std::optional<DIExpression *>;
2358
2359/// Point debug users of \p From to \p To using exprs given by \p RewriteExpr,
2360/// possibly moving/undefing users to prevent use-before-def. Returns true if
2361/// changes are made.
2362static bool rewriteDebugUsers(
2363 Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT,
2364 function_ref<DbgValReplacement(DbgVariableRecord &DVR)> RewriteDVRExpr) {
2365 // Find debug users of From.
2366 SmallVector<DbgVariableRecord *, 1> DPUsers;
2367 findDbgUsers(V: &From, DbgVariableRecords&: DPUsers);
2368 if (DPUsers.empty())
2369 return false;
2370
2371 // Prevent use-before-def of To.
2372 bool Changed = false;
2373
2374 SmallPtrSet<DbgVariableRecord *, 1> UndefOrSalvageDVR;
2375 if (isa<Instruction>(Val: &To)) {
2376 bool DomPointAfterFrom = From.getNextNode() == &DomPoint;
2377
2378 // DbgVariableRecord implementation of the above.
2379 for (auto *DVR : DPUsers) {
2380 Instruction *MarkedInstr = DVR->getMarker()->MarkedInstr;
2381 Instruction *NextNonDebug = MarkedInstr;
2382
2383 // It's common to see a debug user between From and DomPoint. Move it
2384 // after DomPoint to preserve the variable update without any reordering.
2385 if (DomPointAfterFrom && NextNonDebug == &DomPoint) {
2386 LLVM_DEBUG(dbgs() << "MOVE: " << *DVR << '\n');
2387 DVR->removeFromParent();
2388 DomPoint.getParent()->insertDbgRecordAfter(DR: DVR, I: &DomPoint);
2389 Changed = true;
2390
2391 // Users which otherwise aren't dominated by the replacement value must
2392 // be salvaged or deleted.
2393 } else if (!DT.dominates(Def: &DomPoint, User: MarkedInstr)) {
2394 UndefOrSalvageDVR.insert(Ptr: DVR);
2395 }
2396 }
2397 }
2398
2399 // Update debug users without use-before-def risk.
2400 for (auto *DVR : DPUsers) {
2401 if (UndefOrSalvageDVR.count(Ptr: DVR))
2402 continue;
2403
2404 DbgValReplacement DVRepl = RewriteDVRExpr(*DVR);
2405 if (!DVRepl)
2406 continue;
2407
2408 DVR->replaceVariableLocationOp(OldValue: &From, NewValue: &To);
2409 DVR->setExpression(*DVRepl);
2410 LLVM_DEBUG(dbgs() << "REWRITE: " << DVR << '\n');
2411 Changed = true;
2412 }
2413
2414 if (!UndefOrSalvageDVR.empty()) {
2415 // Try to salvage the remaining debug users.
2416 salvageDebugInfo(I&: From);
2417 Changed = true;
2418 }
2419
2420 return Changed;
2421}
2422
2423/// Check if a bitcast between a value of type \p FromTy to type \p ToTy would
2424/// losslessly preserve the bits and semantics of the value. This predicate is
2425/// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result.
2426///
2427/// Note that Type::canLosslesslyBitCastTo is not suitable here because it
2428/// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>,
2429/// and also does not allow lossless pointer <-> integer conversions.
2430static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy,
2431 Type *ToTy) {
2432 // Trivially compatible types.
2433 if (FromTy == ToTy)
2434 return true;
2435
2436 // Handle compatible pointer <-> integer conversions.
2437 if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) {
2438 bool SameSize = DL.getTypeSizeInBits(Ty: FromTy) == DL.getTypeSizeInBits(Ty: ToTy);
2439 bool LosslessConversion = !DL.isNonIntegralPointerType(Ty: FromTy) &&
2440 !DL.isNonIntegralPointerType(Ty: ToTy);
2441 return SameSize && LosslessConversion;
2442 }
2443
2444 // TODO: This is not exhaustive.
2445 return false;
2446}
2447
2448bool llvm::replaceAllDbgUsesWith(Instruction &From, Value &To,
2449 Instruction &DomPoint, DominatorTree &DT) {
2450 // Exit early if From has no debug users.
2451 if (!From.isUsedByMetadata())
2452 return false;
2453
2454 assert(&From != &To && "Can't replace something with itself");
2455
2456 Type *FromTy = From.getType();
2457 Type *ToTy = To.getType();
2458
2459 auto IdentityDVR = [&](DbgVariableRecord &DVR) -> DbgValReplacement {
2460 return DVR.getExpression();
2461 };
2462
2463 // Handle no-op conversions.
2464 Module &M = *From.getModule();
2465 const DataLayout &DL = M.getDataLayout();
2466 if (isBitCastSemanticsPreserving(DL, FromTy, ToTy))
2467 return rewriteDebugUsers(From, To, DomPoint, DT, RewriteDVRExpr: IdentityDVR);
2468
2469 // Handle integer-to-integer widening and narrowing.
2470 // FIXME: Use DW_OP_convert when it's available everywhere.
2471 if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) {
2472 uint64_t FromBits = FromTy->getIntegerBitWidth();
2473 uint64_t ToBits = ToTy->getIntegerBitWidth();
2474 assert(FromBits != ToBits && "Unexpected no-op conversion");
2475
2476 // When the width of the result grows, assume that a debugger will only
2477 // access the low `FromBits` bits when inspecting the source variable.
2478 if (FromBits < ToBits)
2479 return rewriteDebugUsers(From, To, DomPoint, DT, RewriteDVRExpr: IdentityDVR);
2480
2481 // The width of the result has shrunk. Use sign/zero extension to describe
2482 // the source variable's high bits.
2483 auto SignOrZeroExtDVR = [&](DbgVariableRecord &DVR) -> DbgValReplacement {
2484 DILocalVariable *Var = DVR.getVariable();
2485
2486 // Without knowing signedness, sign/zero extension isn't possible.
2487 auto Signedness = Var->getSignedness();
2488 if (!Signedness)
2489 return std::nullopt;
2490
2491 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2492 return DIExpression::appendExt(Expr: DVR.getExpression(), FromSize: ToBits, ToSize: FromBits,
2493 Signed);
2494 };
2495 return rewriteDebugUsers(From, To, DomPoint, DT, RewriteDVRExpr: SignOrZeroExtDVR);
2496 }
2497
2498 // TODO: Floating-point conversions, vectors.
2499 return false;
2500}
2501
2502bool llvm::handleUnreachableTerminator(
2503 Instruction *I, SmallVectorImpl<Value *> &PoisonedValues) {
2504 bool Changed = false;
2505 // RemoveDIs: erase debug-info on this instruction manually.
2506 I->dropDbgRecords();
2507 for (Use &U : I->operands()) {
2508 Value *Op = U.get();
2509 if (isa<Instruction>(Val: Op) && !Op->getType()->isTokenTy()) {
2510 U.set(PoisonValue::get(T: Op->getType()));
2511 PoisonedValues.push_back(Elt: Op);
2512 Changed = true;
2513 }
2514 }
2515
2516 return Changed;
2517}
2518
2519unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) {
2520 unsigned NumDeadInst = 0;
2521 // Delete the instructions backwards, as it has a reduced likelihood of
2522 // having to update as many def-use and use-def chains.
2523 Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
2524 SmallVector<Value *> Uses;
2525 handleUnreachableTerminator(I: EndInst, PoisonedValues&: Uses);
2526
2527 while (EndInst != &BB->front()) {
2528 // Delete the next to last instruction.
2529 Instruction *Inst = &*--EndInst->getIterator();
2530 if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
2531 Inst->replaceAllUsesWith(V: PoisonValue::get(T: Inst->getType()));
2532 if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
2533 // EHPads can't have DbgVariableRecords attached to them, but it might be
2534 // possible for things with token type.
2535 Inst->dropDbgRecords();
2536 EndInst = Inst;
2537 continue;
2538 }
2539 ++NumDeadInst;
2540 // RemoveDIs: erasing debug-info must be done manually.
2541 Inst->dropDbgRecords();
2542 Inst->eraseFromParent();
2543 }
2544 return NumDeadInst;
2545}
2546
2547unsigned llvm::changeToUnreachable(Instruction *I, bool PreserveLCSSA,
2548 DomTreeUpdater *DTU,
2549 MemorySSAUpdater *MSSAU) {
2550 BasicBlock *BB = I->getParent();
2551
2552 if (MSSAU)
2553 MSSAU->changeToUnreachable(I);
2554
2555 SmallPtrSet<BasicBlock *, 8> UniqueSuccessors;
2556
2557 // Loop over all of the successors, removing BB's entry from any PHI
2558 // nodes.
2559 for (BasicBlock *Successor : successors(BB)) {
2560 Successor->removePredecessor(Pred: BB, KeepOneInputPHIs: PreserveLCSSA);
2561 if (DTU)
2562 UniqueSuccessors.insert(Ptr: Successor);
2563 }
2564 auto *UI = new UnreachableInst(I->getContext(), I->getIterator());
2565 UI->setDebugLoc(I->getDebugLoc());
2566
2567 // All instructions after this are dead.
2568 unsigned NumInstrsRemoved = 0;
2569 BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
2570 while (BBI != BBE) {
2571 if (!BBI->use_empty())
2572 BBI->replaceAllUsesWith(V: PoisonValue::get(T: BBI->getType()));
2573 BBI++->eraseFromParent();
2574 ++NumInstrsRemoved;
2575 }
2576 if (DTU) {
2577 SmallVector<DominatorTree::UpdateType, 8> Updates;
2578 Updates.reserve(N: UniqueSuccessors.size());
2579 for (BasicBlock *UniqueSuccessor : UniqueSuccessors)
2580 Updates.push_back(Elt: {DominatorTree::Delete, BB, UniqueSuccessor});
2581 DTU->applyUpdates(Updates);
2582 }
2583 BB->flushTerminatorDbgRecords();
2584 return NumInstrsRemoved;
2585}
2586
2587CallInst *llvm::createCallMatchingInvoke(InvokeInst *II) {
2588 SmallVector<Value *, 8> Args(II->args());
2589 SmallVector<OperandBundleDef, 1> OpBundles;
2590 II->getOperandBundlesAsDefs(Defs&: OpBundles);
2591 CallInst *NewCall = CallInst::Create(Ty: II->getFunctionType(),
2592 Func: II->getCalledOperand(), Args, Bundles: OpBundles);
2593 NewCall->setCallingConv(II->getCallingConv());
2594 NewCall->setAttributes(II->getAttributes());
2595 NewCall->copyMetadata(SrcInst: *II);
2596
2597 // If the invoke had profile metadata, try converting them for CallInst.
2598 uint64_t TotalWeight;
2599 if (NewCall->extractProfTotalWeight(TotalVal&: TotalWeight)) {
2600 // Set the total weight if it fits into i32, otherwise reset.
2601 MDBuilder MDB(NewCall->getContext());
2602 auto NewWeights = uint32_t(TotalWeight) != TotalWeight
2603 ? nullptr
2604 : MDB.createBranchWeights(Weights: {uint32_t(TotalWeight)});
2605 NewCall->setMetadata(KindID: LLVMContext::MD_prof, Node: NewWeights);
2606 }
2607
2608 return NewCall;
2609}
2610
2611// changeToCall - Convert the specified invoke into a normal call.
2612CallInst *llvm::changeToCall(InvokeInst *II, DomTreeUpdater *DTU) {
2613 CallInst *NewCall = createCallMatchingInvoke(II);
2614 NewCall->takeName(V: II);
2615 NewCall->insertBefore(InsertPos: II->getIterator());
2616 II->replaceAllUsesWith(V: NewCall);
2617
2618 // Follow the call by a branch to the normal destination.
2619 BasicBlock *NormalDestBB = II->getNormalDest();
2620 auto *BI = UncondBrInst::Create(Target: NormalDestBB, InsertBefore: II->getIterator());
2621 // Although it takes place after the call itself, the new branch is still
2622 // performing part of the control-flow functionality of the invoke, so we use
2623 // II's DebugLoc.
2624 BI->setDebugLoc(II->getDebugLoc());
2625
2626 // Update PHI nodes in the unwind destination
2627 BasicBlock *BB = II->getParent();
2628 BasicBlock *UnwindDestBB = II->getUnwindDest();
2629 UnwindDestBB->removePredecessor(Pred: BB);
2630 II->eraseFromParent();
2631 if (DTU)
2632 DTU->applyUpdates(Updates: {{DominatorTree::Delete, BB, UnwindDestBB}});
2633 return NewCall;
2634}
2635
2636BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
2637 BasicBlock *UnwindEdge,
2638 DomTreeUpdater *DTU) {
2639 BasicBlock *BB = CI->getParent();
2640
2641 // Convert this function call into an invoke instruction. First, split the
2642 // basic block.
2643 BasicBlock *Split = SplitBlock(Old: BB, SplitPt: CI, DTU, /*LI=*/nullptr, /*MSSAU*/ nullptr,
2644 BBName: CI->getName() + ".noexc");
2645
2646 // Delete the unconditional branch inserted by SplitBlock
2647 BB->back().eraseFromParent();
2648
2649 // Create the new invoke instruction.
2650 SmallVector<Value *, 8> InvokeArgs(CI->args());
2651 SmallVector<OperandBundleDef, 1> OpBundles;
2652
2653 CI->getOperandBundlesAsDefs(Defs&: OpBundles);
2654
2655 // Note: we're round tripping operand bundles through memory here, and that
2656 // can potentially be avoided with a cleverer API design that we do not have
2657 // as of this time.
2658
2659 InvokeInst *II =
2660 InvokeInst::Create(Ty: CI->getFunctionType(), Func: CI->getCalledOperand(), IfNormal: Split,
2661 IfException: UnwindEdge, Args: InvokeArgs, Bundles: OpBundles, NameStr: CI->getName(), InsertBefore: BB);
2662 II->setDebugLoc(CI->getDebugLoc());
2663 II->setCallingConv(CI->getCallingConv());
2664 II->setAttributes(CI->getAttributes());
2665 II->setMetadata(KindID: LLVMContext::MD_prof, Node: CI->getMetadata(KindID: LLVMContext::MD_prof));
2666
2667 if (DTU)
2668 DTU->applyUpdates(Updates: {{DominatorTree::Insert, BB, UnwindEdge}});
2669
2670 // Make sure that anything using the call now uses the invoke! This also
2671 // updates the CallGraph if present, because it uses a WeakTrackingVH.
2672 CI->replaceAllUsesWith(V: II);
2673
2674 // Delete the original call
2675 Split->front().eraseFromParent();
2676 return Split;
2677}
2678
2679static bool markAliveBlocks(Function &F, SmallVectorImpl<bool> &Reachable,
2680 DomTreeUpdater *DTU, bool FoldInstsToUnreachable) {
2681 SmallVector<BasicBlock*, 128> Worklist;
2682 BasicBlock *BB = &F.front();
2683 Worklist.push_back(Elt: BB);
2684 Reachable[BB->getNumber()] = true;
2685 bool Changed = false;
2686 do {
2687 BB = Worklist.pop_back_val();
2688
2689 // Do a scan of the basic block, turning any obviously unreachable
2690 // instructions into LLVM unreachable insts. The instruction combining pass
2691 // canonicalizes unreachable insts into stores to null or undef.
2692 // Note that it traverses the whole instruction list, so it may incur
2693 // significant performance overhead.
2694 if (FoldInstsToUnreachable) {
2695 for (Instruction &I : *BB) {
2696 if (auto *CI = dyn_cast<CallInst>(Val: &I)) {
2697 Value *Callee = CI->getCalledOperand();
2698 // Handle intrinsic calls.
2699 if (Function *F = dyn_cast<Function>(Val: Callee)) {
2700 auto IntrinsicID = F->getIntrinsicID();
2701 // Assumptions that are known to be false are equivalent to
2702 // unreachable. Also, if the condition is undefined, then we make
2703 // the choice most beneficial to the optimizer, and choose that to
2704 // also be unreachable.
2705 if (IntrinsicID == Intrinsic::assume) {
2706 if (match(V: CI->getArgOperand(i: 0),
2707 P: m_CombineOr(Ps: m_Zero(), Ps: m_Undef()))) {
2708 // Don't insert a call to llvm.trap right before the
2709 // unreachable.
2710 changeToUnreachable(I: CI, PreserveLCSSA: false, DTU);
2711 Changed = true;
2712 break;
2713 }
2714 } else if (IntrinsicID == Intrinsic::experimental_guard) {
2715 // A call to the guard intrinsic bails out of the current
2716 // compilation unit if the predicate passed to it is false. If the
2717 // predicate is a constant false, then we know the guard will bail
2718 // out of the current compile unconditionally, so all code
2719 // following it is dead.
2720 //
2721 // Note: unlike in llvm.assume, it is not "obviously profitable"
2722 // for guards to treat `undef` as `false` since a guard on `undef`
2723 // can still be useful for widening.
2724 if (match(V: CI->getArgOperand(i: 0), P: m_Zero()))
2725 if (!isa<UnreachableInst>(Val: CI->getNextNode())) {
2726 changeToUnreachable(I: CI->getNextNode(), PreserveLCSSA: false, DTU);
2727 Changed = true;
2728 break;
2729 }
2730 }
2731 } else if ((isa<ConstantPointerNull>(Val: Callee) &&
2732 !NullPointerIsDefined(F: CI->getFunction(),
2733 AS: cast<PointerType>(Val: Callee->getType())
2734 ->getAddressSpace())) ||
2735 isa<UndefValue>(Val: Callee)) {
2736 changeToUnreachable(I: CI, PreserveLCSSA: false, DTU);
2737 Changed = true;
2738 break;
2739 }
2740 if (CI->doesNotReturn() && !CI->isMustTailCall()) {
2741 // If we found a call to a no-return function, insert an unreachable
2742 // instruction after it. Make sure there isn't *already* one there
2743 // though.
2744 if (!isa<UnreachableInst>(Val: CI->getNextNode())) {
2745 // Don't insert a call to llvm.trap right before the unreachable.
2746 changeToUnreachable(I: CI->getNextNode(), PreserveLCSSA: false, DTU);
2747 Changed = true;
2748 }
2749 break;
2750 }
2751 } else if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
2752 // Store to undef and store to null are undefined and used to signal
2753 // that they should be changed to unreachable by passes that can't
2754 // modify the CFG.
2755
2756 // Don't touch volatile stores.
2757 if (SI->isVolatile())
2758 continue;
2759
2760 Value *Ptr = SI->getOperand(i_nocapture: 1);
2761
2762 if (isa<UndefValue>(Val: Ptr) ||
2763 (isa<ConstantPointerNull>(Val: Ptr) &&
2764 !NullPointerIsDefined(F: SI->getFunction(),
2765 AS: SI->getPointerAddressSpace()))) {
2766 changeToUnreachable(I: SI, PreserveLCSSA: false, DTU);
2767 Changed = true;
2768 break;
2769 }
2770 }
2771 }
2772
2773 Instruction *Terminator = BB->getTerminator();
2774 if (auto *II = dyn_cast<InvokeInst>(Val: Terminator)) {
2775 // Turn invokes that call 'nounwind' functions into ordinary calls.
2776 Value *Callee = II->getCalledOperand();
2777 if ((isa<ConstantPointerNull>(Val: Callee) &&
2778 !NullPointerIsDefined(F: BB->getParent())) ||
2779 isa<UndefValue>(Val: Callee)) {
2780 changeToUnreachable(I: II, PreserveLCSSA: false, DTU);
2781 Changed = true;
2782 } else {
2783 if (II->doesNotReturn() &&
2784 !isa<UnreachableInst>(Val: II->getNormalDest()->front())) {
2785 // If we found an invoke of a no-return function,
2786 // create a new empty basic block with an `unreachable` terminator,
2787 // and set it as the normal destination for the invoke,
2788 // unless that is already the case.
2789 // Note that the original normal destination could have other uses.
2790 BasicBlock *OrigNormalDest = II->getNormalDest();
2791 OrigNormalDest->removePredecessor(Pred: II->getParent());
2792 LLVMContext &Ctx = II->getContext();
2793 BasicBlock *UnreachableNormalDest = BasicBlock::Create(
2794 Context&: Ctx, Name: OrigNormalDest->getName() + ".unreachable",
2795 Parent: II->getFunction(), InsertBefore: OrigNormalDest);
2796 Reachable.resize(N: II->getFunction()->getMaxBlockNumber());
2797 auto *UI = new UnreachableInst(Ctx, UnreachableNormalDest);
2798 UI->setDebugLoc(DebugLoc::getTemporary());
2799 II->setNormalDest(UnreachableNormalDest);
2800 if (DTU)
2801 DTU->applyUpdates(
2802 Updates: {{DominatorTree::Delete, BB, OrigNormalDest},
2803 {DominatorTree::Insert, BB, UnreachableNormalDest}});
2804 Changed = true;
2805 }
2806 if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(F: &F)) {
2807 if (II->use_empty() && !II->mayHaveSideEffects()) {
2808 // jump to the normal destination branch.
2809 BasicBlock *NormalDestBB = II->getNormalDest();
2810 BasicBlock *UnwindDestBB = II->getUnwindDest();
2811 UncondBrInst::Create(Target: NormalDestBB, InsertBefore: II->getIterator());
2812 UnwindDestBB->removePredecessor(Pred: II->getParent());
2813 II->eraseFromParent();
2814 if (DTU)
2815 DTU->applyUpdates(Updates: {{DominatorTree::Delete, BB, UnwindDestBB}});
2816 } else
2817 changeToCall(II, DTU);
2818 Changed = true;
2819 }
2820 }
2821 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Val: Terminator)) {
2822 // Remove catchpads which cannot be reached.
2823 struct CatchPadDenseMapInfo {
2824 static unsigned getHashValue(CatchPadInst *CatchPad) {
2825 return static_cast<unsigned>(hash_combine_range(
2826 first: CatchPad->value_op_begin(), last: CatchPad->value_op_end()));
2827 }
2828
2829 static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
2830 return LHS->isIdenticalTo(I: RHS);
2831 }
2832 };
2833
2834 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
2835 // Set of unique CatchPads.
2836 SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4,
2837 CatchPadDenseMapInfo,
2838 detail::DenseSetPair<CatchPadInst *>>
2839 HandlerSet;
2840 detail::DenseSetEmpty Empty;
2841 for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
2842 E = CatchSwitch->handler_end();
2843 I != E; ++I) {
2844 BasicBlock *HandlerBB = *I;
2845 if (DTU)
2846 ++NumPerSuccessorCases[HandlerBB];
2847 auto *CatchPad = cast<CatchPadInst>(Val: HandlerBB->getFirstNonPHIIt());
2848 if (!HandlerSet.insert(KV: {CatchPad, Empty}).second) {
2849 if (DTU)
2850 --NumPerSuccessorCases[HandlerBB];
2851 CatchSwitch->removeHandler(HI: I);
2852 --I;
2853 --E;
2854 Changed = true;
2855 }
2856 }
2857 if (DTU) {
2858 std::vector<DominatorTree::UpdateType> Updates;
2859 for (const auto &I : NumPerSuccessorCases)
2860 if (I.second == 0)
2861 Updates.push_back(x: {DominatorTree::Delete, BB, I.first});
2862 DTU->applyUpdates(Updates);
2863 }
2864 }
2865
2866 Changed |= ConstantFoldTerminator(BB, DeleteDeadConditions: true, TLI: nullptr, DTU);
2867 }
2868 for (BasicBlock *Successor : successors(BB)) {
2869 if (!Reachable[Successor->getNumber()]) {
2870 Worklist.push_back(Elt: Successor);
2871 Reachable[Successor->getNumber()] = true;
2872 }
2873 }
2874 } while (!Worklist.empty());
2875 return Changed;
2876}
2877
2878Instruction *llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) {
2879 Instruction *TI = BB->getTerminator();
2880
2881 if (auto *II = dyn_cast<InvokeInst>(Val: TI))
2882 return changeToCall(II, DTU);
2883
2884 Instruction *NewTI;
2885 BasicBlock *UnwindDest;
2886
2887 if (auto *CRI = dyn_cast<CleanupReturnInst>(Val: TI)) {
2888 NewTI = CleanupReturnInst::Create(CleanupPad: CRI->getCleanupPad(), UnwindBB: nullptr, InsertBefore: CRI->getIterator());
2889 UnwindDest = CRI->getUnwindDest();
2890 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Val: TI)) {
2891 auto *NewCatchSwitch = CatchSwitchInst::Create(
2892 ParentPad: CatchSwitch->getParentPad(), UnwindDest: nullptr, NumHandlers: CatchSwitch->getNumHandlers(),
2893 NameStr: CatchSwitch->getName(), InsertBefore: CatchSwitch->getIterator());
2894 for (BasicBlock *PadBB : CatchSwitch->handlers())
2895 NewCatchSwitch->addHandler(Dest: PadBB);
2896
2897 NewTI = NewCatchSwitch;
2898 UnwindDest = CatchSwitch->getUnwindDest();
2899 } else {
2900 llvm_unreachable("Could not find unwind successor");
2901 }
2902
2903 NewTI->takeName(V: TI);
2904 NewTI->setDebugLoc(TI->getDebugLoc());
2905 UnwindDest->removePredecessor(Pred: BB);
2906 TI->replaceAllUsesWith(V: NewTI);
2907 TI->eraseFromParent();
2908 if (DTU)
2909 DTU->applyUpdates(Updates: {{DominatorTree::Delete, BB, UnwindDest}});
2910 return NewTI;
2911}
2912
2913/// removeUnreachableBlocks - Remove blocks that are not reachable, even
2914/// if they are in a dead cycle. Return true if a change was made, false
2915/// otherwise.
2916bool llvm::removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
2917 MemorySSAUpdater *MSSAU,
2918 bool FoldInstsToUnreachable) {
2919 SmallVector<bool, 16> Reachable(F.getMaxBlockNumber());
2920 bool Changed = markAliveBlocks(F, Reachable, DTU, FoldInstsToUnreachable);
2921
2922 // Are there any blocks left to actually delete?
2923 SmallSetVector<BasicBlock *, 8> BlocksToRemove;
2924 for (BasicBlock &BB : F) {
2925 // Skip reachable basic blocks
2926 if (Reachable[BB.getNumber()])
2927 continue;
2928 // Skip already-deleted blocks
2929 if (DTU && DTU->isBBPendingDeletion(DelBB: &BB))
2930 continue;
2931 BlocksToRemove.insert(X: &BB);
2932 }
2933
2934 if (BlocksToRemove.empty())
2935 return Changed;
2936
2937 Changed = true;
2938 NumRemoved += BlocksToRemove.size();
2939
2940 if (MSSAU)
2941 MSSAU->removeBlocks(DeadBlocks: BlocksToRemove);
2942
2943 DeleteDeadBlocks(BBs: BlocksToRemove.takeVector(), DTU);
2944
2945 return Changed;
2946}
2947
2948/// If AAOnly is set, only intersect alias analysis metadata and preserve other
2949/// known metadata. Unknown metadata is always dropped.
2950static void combineMetadata(Instruction *K, const Instruction *J,
2951 bool DoesKMove, bool AAOnly = false) {
2952 SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
2953 K->getAllMetadataOtherThanDebugLoc(MDs&: Metadata);
2954 for (const auto &MD : Metadata) {
2955 unsigned Kind = MD.first;
2956 MDNode *JMD = J->getMetadata(KindID: Kind);
2957 MDNode *KMD = MD.second;
2958
2959 // TODO: Assert that this switch is exhaustive for fixed MD kinds.
2960 switch (Kind) {
2961 default:
2962 K->setMetadata(KindID: Kind, Node: nullptr); // Remove unknown metadata
2963 break;
2964 case LLVMContext::MD_dbg:
2965 llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
2966 case LLVMContext::MD_DIAssignID:
2967 if (!AAOnly)
2968 K->mergeDIAssignID(SourceInstructions: J);
2969 break;
2970 case LLVMContext::MD_tbaa:
2971 if (DoesKMove)
2972 K->setMetadata(KindID: Kind, Node: MDNode::getMostGenericTBAA(A: JMD, B: KMD));
2973 break;
2974 case LLVMContext::MD_alias_scope:
2975 if (DoesKMove)
2976 K->setMetadata(KindID: Kind, Node: MDNode::getMostGenericAliasScope(A: JMD, B: KMD));
2977 break;
2978 case LLVMContext::MD_noalias:
2979 case LLVMContext::MD_mem_parallel_loop_access:
2980 if (DoesKMove)
2981 K->setMetadata(KindID: Kind, Node: MDNode::intersect(A: JMD, B: KMD));
2982 break;
2983 case LLVMContext::MD_access_group:
2984 if (DoesKMove)
2985 K->setMetadata(KindID: LLVMContext::MD_access_group,
2986 Node: intersectAccessGroups(Inst1: K, Inst2: J));
2987 break;
2988 case LLVMContext::MD_range:
2989 if (!AAOnly && (DoesKMove || !K->hasMetadata(KindID: LLVMContext::MD_noundef)))
2990 K->setMetadata(KindID: Kind, Node: MDNode::getMostGenericRange(A: JMD, B: KMD));
2991 break;
2992 case LLVMContext::MD_nofpclass:
2993 if (!AAOnly && (DoesKMove || !K->hasMetadata(KindID: LLVMContext::MD_noundef)))
2994 K->setMetadata(KindID: Kind, Node: MDNode::getMostGenericNoFPClass(A: JMD, B: KMD));
2995 break;
2996 case LLVMContext::MD_fpmath:
2997 if (!AAOnly)
2998 K->setMetadata(KindID: Kind, Node: MDNode::getMostGenericFPMath(A: JMD, B: KMD));
2999 break;
3000 case LLVMContext::MD_invariant_load:
3001 case LLVMContext::MD_invariant_group:
3002 // If K moves, only keep the invariant metadata if it is present on
3003 // both instructions; otherwise the invariant would be asserted on a
3004 // path (J's) that never promised it. If K does not move, K stays on
3005 // its original path, so its existing metadata remains valid.
3006 if (DoesKMove)
3007 K->setMetadata(KindID: Kind, Node: JMD);
3008 break;
3009 case LLVMContext::MD_nonnull:
3010 if (!AAOnly && (DoesKMove || !K->hasMetadata(KindID: LLVMContext::MD_noundef)))
3011 K->setMetadata(KindID: Kind, Node: JMD);
3012 break;
3013 // Keep empty cases for prof, mmra, memprof, and callsite to prevent them
3014 // from being removed as unknown metadata. The actual merging is handled
3015 // separately below.
3016 case LLVMContext::MD_prof:
3017 case LLVMContext::MD_mmra:
3018 case LLVMContext::MD_memprof:
3019 case LLVMContext::MD_callsite:
3020 break;
3021 case LLVMContext::MD_callee_type:
3022 if (!AAOnly) {
3023 K->setMetadata(KindID: LLVMContext::MD_callee_type,
3024 Node: MDNode::getMergedCalleeTypeMetadata(A: KMD, B: JMD));
3025 }
3026 break;
3027 case LLVMContext::MD_callees:
3028 // If K moves, it replaces J on J's path and must allow J's callees as
3029 // well. If K does not move, its callees remain valid.
3030 if (!AAOnly && DoesKMove)
3031 K->setMetadata(KindID: Kind, Node: MDNode::getMergedCalleesMetadata(A: KMD, B: JMD));
3032 break;
3033 case LLVMContext::MD_align:
3034 if (!AAOnly && (DoesKMove || !K->hasMetadata(KindID: LLVMContext::MD_noundef)))
3035 K->setMetadata(
3036 KindID: Kind, Node: MDNode::getMostGenericAlignmentOrDereferenceable(A: JMD, B: KMD));
3037 break;
3038 case LLVMContext::MD_dereferenceable:
3039 case LLVMContext::MD_dereferenceable_or_null:
3040 if (!AAOnly && DoesKMove)
3041 K->setMetadata(KindID: Kind,
3042 Node: MDNode::getMostGenericAlignmentOrDereferenceable(A: JMD, B: KMD));
3043 break;
3044 case LLVMContext::MD_preserve_access_index:
3045 // Preserve !preserve.access.index in K.
3046 break;
3047 case LLVMContext::MD_noundef:
3048 // If K does move, keep noundef if it is present in both instructions.
3049 if (!AAOnly && DoesKMove)
3050 K->setMetadata(KindID: Kind, Node: JMD);
3051 break;
3052 case LLVMContext::MD_nontemporal:
3053 // Preserve !nontemporal if it is present on both instructions.
3054 if (!AAOnly)
3055 K->setMetadata(KindID: Kind, Node: JMD);
3056 break;
3057 case LLVMContext::MD_mem_cache_hint:
3058 // Preserve !mem.cache_hint only if it is present and equivalent on both
3059 // instructions.
3060 if (!AAOnly && KMD != JMD)
3061 K->setMetadata(KindID: Kind, Node: nullptr);
3062 break;
3063 case LLVMContext::MD_noalias_addrspace:
3064 if (DoesKMove)
3065 K->setMetadata(KindID: Kind,
3066 Node: MDNode::getMostGenericNoaliasAddrspace(A: JMD, B: KMD));
3067 break;
3068 case LLVMContext::MD_nosanitize:
3069 // Preserve !nosanitize if both K and J have it.
3070 K->setMetadata(KindID: Kind, Node: JMD);
3071 break;
3072 case LLVMContext::MD_captures:
3073 K->setMetadata(
3074 KindID: Kind, Node: MDNode::fromCaptureComponents(
3075 Ctx&: K->getContext(), CC: MDNode::toCaptureComponents(MD: JMD) |
3076 MDNode::toCaptureComponents(MD: KMD)));
3077 break;
3078 case LLVMContext::MD_alloc_token:
3079 if (!AAOnly && KMD != JMD)
3080 K->setMetadata(KindID: Kind, Node: MDNode::getMergedAllocTokenMetadata(A: KMD, B: JMD));
3081 break;
3082 }
3083 }
3084
3085 // Merge MMRAs.
3086 // This is handled separately because we also want to handle cases where K
3087 // doesn't have tags but J does.
3088 auto JMMRA = J->getMetadata(KindID: LLVMContext::MD_mmra);
3089 auto KMMRA = K->getMetadata(KindID: LLVMContext::MD_mmra);
3090 if (JMMRA || KMMRA) {
3091 K->setMetadata(KindID: LLVMContext::MD_mmra,
3092 Node: MMRAMetadata::combine(Ctx&: K->getContext(), A: JMMRA, B: KMMRA));
3093 }
3094
3095 // Merge memprof metadata.
3096 // Handle separately to support cases where only one instruction has the
3097 // metadata.
3098 auto *JMemProf = J->getMetadata(KindID: LLVMContext::MD_memprof);
3099 auto *KMemProf = K->getMetadata(KindID: LLVMContext::MD_memprof);
3100 if (!AAOnly && (JMemProf || KMemProf)) {
3101 K->setMetadata(KindID: LLVMContext::MD_memprof,
3102 Node: MDNode::getMergedMemProfMetadata(A: KMemProf, B: JMemProf));
3103 }
3104
3105 // Merge callsite metadata.
3106 // Handle separately to support cases where only one instruction has the
3107 // metadata.
3108 auto *JCallSite = J->getMetadata(KindID: LLVMContext::MD_callsite);
3109 auto *KCallSite = K->getMetadata(KindID: LLVMContext::MD_callsite);
3110 if (!AAOnly && (JCallSite || KCallSite)) {
3111 K->setMetadata(KindID: LLVMContext::MD_callsite,
3112 Node: MDNode::getMergedCallsiteMetadata(A: KCallSite, B: JCallSite));
3113 }
3114
3115 // Merge prof metadata.
3116 // Handle separately to support cases where only one instruction has the
3117 // metadata.
3118 auto *JProf = J->getMetadata(KindID: LLVMContext::MD_prof);
3119 auto *KProf = K->getMetadata(KindID: LLVMContext::MD_prof);
3120 if (!AAOnly && (JProf || KProf)) {
3121 K->setMetadata(KindID: LLVMContext::MD_prof,
3122 Node: MDNode::getMergedProfMetadata(A: KProf, B: JProf, AInstr: K, BInstr: J));
3123 }
3124}
3125
3126void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J,
3127 bool DoesKMove) {
3128 combineMetadata(K, J, DoesKMove);
3129}
3130
3131void llvm::combineAAMetadata(Instruction *K, const Instruction *J) {
3132 combineMetadata(K, J, /*DoesKMove=*/true, /*AAOnly=*/true);
3133}
3134
3135void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) {
3136 SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
3137 Source.getAllMetadata(MDs&: MD);
3138 MDBuilder MDB(Dest.getContext());
3139 Type *NewType = Dest.getType();
3140 const DataLayout &DL = Source.getDataLayout();
3141 for (const auto &MDPair : MD) {
3142 unsigned ID = MDPair.first;
3143 MDNode *N = MDPair.second;
3144 // Note, essentially every kind of metadata should be preserved here! This
3145 // routine is supposed to clone a load instruction changing *only its type*.
3146 // The only metadata it makes sense to drop is metadata which is invalidated
3147 // when the pointer type changes. This should essentially never be the case
3148 // in LLVM, but we explicitly switch over only known metadata to be
3149 // conservatively correct. If you are adding metadata to LLVM which pertains
3150 // to loads, you almost certainly want to add it here.
3151 switch (ID) {
3152 case LLVMContext::MD_dbg:
3153 case LLVMContext::MD_tbaa:
3154 case LLVMContext::MD_prof:
3155 case LLVMContext::MD_fpmath:
3156 case LLVMContext::MD_tbaa_struct:
3157 case LLVMContext::MD_invariant_load:
3158 case LLVMContext::MD_alias_scope:
3159 case LLVMContext::MD_noalias:
3160 case LLVMContext::MD_nontemporal:
3161 case LLVMContext::MD_mem_cache_hint:
3162 case LLVMContext::MD_mem_parallel_loop_access:
3163 case LLVMContext::MD_access_group:
3164 case LLVMContext::MD_noundef:
3165 case LLVMContext::MD_noalias_addrspace:
3166 case LLVMContext::MD_invariant_group:
3167 // All of these directly apply.
3168 Dest.setMetadata(KindID: ID, Node: N);
3169 break;
3170
3171 case LLVMContext::MD_nonnull:
3172 copyNonnullMetadata(OldLI: Source, N, NewLI&: Dest);
3173 break;
3174
3175 case LLVMContext::MD_align:
3176 case LLVMContext::MD_dereferenceable:
3177 case LLVMContext::MD_dereferenceable_or_null:
3178 // These only directly apply if the new type is also a pointer.
3179 if (NewType->isPointerTy())
3180 Dest.setMetadata(KindID: ID, Node: N);
3181 break;
3182
3183 case LLVMContext::MD_range:
3184 copyRangeMetadata(DL, OldLI: Source, N, NewLI&: Dest);
3185 break;
3186
3187 case LLVMContext::MD_nofpclass:
3188 // This only applies if the floating-point type interpretation. This
3189 // should handle degenerate cases like casting between a scalar and single
3190 // element vector.
3191 if (NewType->getScalarType() == Source.getType()->getScalarType())
3192 Dest.setMetadata(KindID: ID, Node: N);
3193 break;
3194 }
3195 }
3196}
3197
3198void llvm::patchReplacementInstruction(Instruction *I, Value *Repl) {
3199 auto *ReplInst = dyn_cast<Instruction>(Val: Repl);
3200 if (!ReplInst)
3201 return;
3202
3203 // Patch the replacement so that it is not more restrictive than the value
3204 // being replaced.
3205 WithOverflowInst *UnusedWO;
3206 // When replacing the result of a llvm.*.with.overflow intrinsic with a
3207 // overflowing binary operator, nuw/nsw flags may no longer hold.
3208 if (isa<OverflowingBinaryOperator>(Val: ReplInst) &&
3209 match(V: I, P: m_ExtractValue<0>(V: m_WithOverflowInst(I&: UnusedWO))))
3210 ReplInst->dropPoisonGeneratingFlags();
3211 // Note that if 'I' is a load being replaced by some operation,
3212 // for example, by an arithmetic operation, then andIRFlags()
3213 // would just erase all math flags from the original arithmetic
3214 // operation, which is clearly not wanted and not needed.
3215 else if (!isa<LoadInst>(Val: I))
3216 ReplInst->andIRFlags(V: I);
3217
3218 // Handle attributes.
3219 if (auto *CB1 = dyn_cast<CallBase>(Val: ReplInst)) {
3220 if (auto *CB2 = dyn_cast<CallBase>(Val: I)) {
3221 bool Success = CB1->tryIntersectAttributes(Other: CB2);
3222 assert(Success && "We should not be trying to sink callbases "
3223 "with non-intersectable attributes");
3224 // For NDEBUG Compile.
3225 (void)Success;
3226 }
3227 }
3228
3229 // FIXME: If both the original and replacement value are part of the
3230 // same control-flow region (meaning that the execution of one
3231 // guarantees the execution of the other), then we can combine the
3232 // noalias scopes here and do better than the general conservative
3233 // answer used in combineMetadata().
3234
3235 // In general, GVN unifies expressions over different control-flow
3236 // regions, and so we need a conservative combination of the noalias
3237 // scopes.
3238 combineMetadataForCSE(K: ReplInst, J: I, DoesKMove: false);
3239}
3240
3241template <typename ShouldReplaceFn>
3242static unsigned replaceDominatedUsesWith(Value *From, Value *To,
3243 const ShouldReplaceFn &ShouldReplace) {
3244 assert(From->getType() == To->getType());
3245
3246 unsigned Count = 0;
3247 for (Use &U : llvm::make_early_inc_range(Range: From->uses())) {
3248 auto *II = dyn_cast<IntrinsicInst>(Val: U.getUser());
3249 if (II && II->getIntrinsicID() == Intrinsic::fake_use)
3250 continue;
3251 if (!ShouldReplace(U))
3252 continue;
3253 LLVM_DEBUG(dbgs() << "Replace dominated use of '";
3254 From->printAsOperand(dbgs());
3255 dbgs() << "' with " << *To << " in " << *U.getUser() << "\n");
3256 U.set(To);
3257 ++Count;
3258 }
3259 return Count;
3260}
3261
3262unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) {
3263 assert(From->getType() == To->getType());
3264 auto *BB = From->getParent();
3265 unsigned Count = 0;
3266
3267 for (Use &U : llvm::make_early_inc_range(Range: From->uses())) {
3268 auto *I = cast<Instruction>(Val: U.getUser());
3269 if (I->getParent() == BB)
3270 continue;
3271 U.set(To);
3272 ++Count;
3273 }
3274 return Count;
3275}
3276
3277unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
3278 DominatorTree &DT,
3279 const BasicBlockEdge &Root) {
3280 auto Dominates = [&](const Use &U) { return DT.dominates(BBE: Root, U); };
3281 return ::replaceDominatedUsesWith(From, To, ShouldReplace: Dominates);
3282}
3283
3284unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
3285 DominatorTree &DT,
3286 const BasicBlock *BB) {
3287 auto Dominates = [&](const Use &U) { return DT.dominates(BB, U); };
3288 return ::replaceDominatedUsesWith(From, To, ShouldReplace: Dominates);
3289}
3290
3291unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
3292 DominatorTree &DT,
3293 const Instruction *I) {
3294 auto Dominates = [&](const Use &U) { return DT.dominates(Def: I, U); };
3295 return ::replaceDominatedUsesWith(From, To, ShouldReplace: Dominates);
3296}
3297
3298unsigned llvm::replaceDominatedUsesWithIf(
3299 Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Root,
3300 function_ref<bool(const Use &U, const Value *To)> ShouldReplace) {
3301 auto DominatesAndShouldReplace = [&](const Use &U) {
3302 return DT.dominates(BBE: Root, U) && ShouldReplace(U, To);
3303 };
3304 return ::replaceDominatedUsesWith(From, To, ShouldReplace: DominatesAndShouldReplace);
3305}
3306
3307unsigned llvm::replaceDominatedUsesWithIf(
3308 Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB,
3309 function_ref<bool(const Use &U, const Value *To)> ShouldReplace) {
3310 auto DominatesAndShouldReplace = [&](const Use &U) {
3311 return DT.dominates(BB, U) && ShouldReplace(U, To);
3312 };
3313 return ::replaceDominatedUsesWith(From, To, ShouldReplace: DominatesAndShouldReplace);
3314}
3315
3316unsigned llvm::replaceDominatedUsesWithIf(
3317 Value *From, Value *To, DominatorTree &DT, const Instruction *I,
3318 function_ref<bool(const Use &U, const Value *To)> ShouldReplace) {
3319 auto DominatesAndShouldReplace = [&](const Use &U) {
3320 return DT.dominates(Def: I, U) && ShouldReplace(U, To);
3321 };
3322 return ::replaceDominatedUsesWith(From, To, ShouldReplace: DominatesAndShouldReplace);
3323}
3324
3325bool llvm::callsGCLeafFunction(const CallBase *Call,
3326 const TargetLibraryInfo &TLI) {
3327 // Check if the function is specifically marked as a gc leaf function.
3328 if (Call->hasFnAttr(Kind: "gc-leaf-function"))
3329 return true;
3330 if (const Function *F = Call->getCalledFunction()) {
3331 if (F->hasFnAttribute(Kind: "gc-leaf-function"))
3332 return true;
3333
3334 if (auto IID = F->getIntrinsicID()) {
3335 // Most LLVM intrinsics do not take safepoints.
3336 return IID != Intrinsic::experimental_gc_statepoint &&
3337 IID != Intrinsic::experimental_deoptimize &&
3338 IID != Intrinsic::memcpy_element_unordered_atomic &&
3339 IID != Intrinsic::memmove_element_unordered_atomic;
3340 }
3341 }
3342
3343 // Lib calls can be materialized by some passes, and won't be
3344 // marked as 'gc-leaf-function.' All available Libcalls are
3345 // GC-leaf.
3346 return TLI.has(F: TLI.getLibFunc(CB: *Call));
3347}
3348
3349void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N,
3350 LoadInst &NewLI) {
3351 auto *NewTy = NewLI.getType();
3352
3353 // This only directly applies if the new type is also a pointer.
3354 if (NewTy->isPointerTy()) {
3355 NewLI.setMetadata(KindID: LLVMContext::MD_nonnull, Node: N);
3356 return;
3357 }
3358
3359 // The only other translation we can do is to integral loads with !range
3360 // metadata.
3361 if (!NewTy->isIntegerTy())
3362 return;
3363
3364 MDBuilder MDB(NewLI.getContext());
3365 const Value *Ptr = OldLI.getPointerOperand();
3366 auto *ITy = cast<IntegerType>(Val: NewTy);
3367 auto *NullInt = ConstantExpr::getPtrToInt(
3368 C: ConstantPointerNull::get(T: cast<PointerType>(Val: Ptr->getType())), Ty: ITy);
3369 auto *NonNullInt = ConstantExpr::getAdd(C1: NullInt, C2: ConstantInt::get(Ty: ITy, V: 1));
3370 NewLI.setMetadata(KindID: LLVMContext::MD_range,
3371 Node: MDB.createRange(Lo: NonNullInt, Hi: NullInt));
3372}
3373
3374void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
3375 MDNode *N, LoadInst &NewLI) {
3376 auto *NewTy = NewLI.getType();
3377 // Simply copy the metadata if the type did not change.
3378 if (NewTy == OldLI.getType()) {
3379 NewLI.setMetadata(KindID: LLVMContext::MD_range, Node: N);
3380 return;
3381 }
3382
3383 // Give up unless it is converted to a pointer where there is a single very
3384 // valuable mapping we can do reliably.
3385 // FIXME: It would be nice to propagate this in more ways, but the type
3386 // conversions make it hard.
3387 if (!NewTy->isPointerTy())
3388 return;
3389
3390 unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
3391 if (BitWidth == OldLI.getType()->getScalarSizeInBits() &&
3392 !getConstantRangeFromMetadata(RangeMD: *N).contains(Val: APInt(BitWidth, 0))) {
3393 MDNode *NN = MDNode::get(Context&: OldLI.getContext(), MDs: {});
3394 NewLI.setMetadata(KindID: LLVMContext::MD_nonnull, Node: NN);
3395 }
3396}
3397
3398void llvm::dropDebugUsers(Instruction &I) {
3399 SmallVector<DbgVariableRecord *, 1> DPUsers;
3400 findDbgUsers(V: &I, DbgVariableRecords&: DPUsers);
3401 for (auto *DVR : DPUsers)
3402 DVR->eraseFromParent();
3403}
3404
3405void llvm::hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt,
3406 BasicBlock *BB) {
3407 // Since we are moving the instructions out of its basic block, we do not
3408 // retain their original debug locations (DILocations) and debug intrinsic
3409 // instructions.
3410 //
3411 // Doing so would degrade the debugging experience.
3412 //
3413 // FIXME: Issue #152767: debug info should also be the same as the
3414 // original branch, **if** the user explicitly indicated that (for sampling
3415 // PGO)
3416 //
3417 // Currently, when hoisting the instructions, we take the following actions:
3418 // - Remove their debug intrinsic instructions.
3419 // - Set their debug locations to the values from the insertion point.
3420 //
3421 // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
3422 // need to be deleted, is because there will not be any instructions with a
3423 // DILocation in either branch left after performing the transformation. We
3424 // can only insert a dbg.value after the two branches are joined again.
3425 //
3426 // See PR38762, PR39243 for more details.
3427 //
3428 // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
3429 // encode predicated DIExpressions that yield different results on different
3430 // code paths.
3431
3432 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
3433 Instruction *I = &*II;
3434 I->dropUBImplyingAttrsAndMetadata();
3435 if (I->isUsedByMetadata())
3436 dropDebugUsers(I&: *I);
3437 // RemoveDIs: drop debug-info too as the following code does.
3438 I->dropDbgRecords();
3439 if (I->isDebugOrPseudoInst()) {
3440 // Remove DbgInfo and pseudo probe Intrinsics.
3441 II = I->eraseFromParent();
3442 continue;
3443 }
3444 I->setDebugLoc(InsertPt->getDebugLoc());
3445 ++II;
3446 }
3447 DomBlock->splice(ToIt: InsertPt->getIterator(), FromBB: BB, FromBeginIt: BB->begin(),
3448 FromEndIt: BB->getTerminator()->getIterator());
3449}
3450
3451DIExpression *llvm::getExpressionForConstant(DIBuilder &DIB, const Constant &C,
3452 Type &Ty) {
3453 // Create integer constant expression.
3454 auto createIntegerExpression = [&DIB](const Constant &CV) -> DIExpression * {
3455 const APInt &API = cast<ConstantInt>(Val: &CV)->getValue();
3456 std::optional<int64_t> InitIntOpt;
3457 if (API.getBitWidth() == 1)
3458 InitIntOpt = API.tryZExtValue();
3459 else
3460 InitIntOpt = API.trySExtValue();
3461 return InitIntOpt ? DIB.createConstantValueExpression(
3462 Val: static_cast<uint64_t>(*InitIntOpt))
3463 : nullptr;
3464 };
3465
3466 if (isa<ConstantInt>(Val: C))
3467 return createIntegerExpression(C);
3468
3469 auto *FP = dyn_cast<ConstantFP>(Val: &C);
3470 if (FP && Ty.isFloatingPointTy() && Ty.getScalarSizeInBits() <= 64) {
3471 const APFloat &APF = FP->getValueAPF();
3472 APInt const &API = APF.bitcastToAPInt();
3473 if (uint64_t Temp = API.getZExtValue())
3474 return DIB.createConstantValueExpression(Val: Temp);
3475 return DIB.createConstantValueExpression(Val: *API.getRawData());
3476 }
3477
3478 if (!Ty.isPointerTy())
3479 return nullptr;
3480
3481 if (isa<ConstantPointerNull>(Val: C))
3482 return DIB.createConstantValueExpression(Val: 0);
3483
3484 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: &C))
3485 if (CE->getOpcode() == Instruction::IntToPtr) {
3486 const Value *V = CE->getOperand(i_nocapture: 0);
3487 if (auto CI = dyn_cast_or_null<ConstantInt>(Val: V))
3488 return createIntegerExpression(*CI);
3489 }
3490 return nullptr;
3491}
3492
3493void llvm::remapDebugVariable(ValueToValueMapTy &Mapping, Instruction *Inst) {
3494 auto RemapDebugOperands = [&Mapping](auto *DV, auto Set) {
3495 for (auto *Op : Set) {
3496 auto I = Mapping.find(Op);
3497 if (I != Mapping.end())
3498 DV->replaceVariableLocationOp(Op, I->second, /*AllowEmpty=*/true);
3499 }
3500 };
3501 auto RemapAssignAddress = [&Mapping](auto *DA) {
3502 auto I = Mapping.find(DA->getAddress());
3503 if (I != Mapping.end())
3504 DA->setAddress(I->second);
3505 };
3506 for (DbgVariableRecord &DVR : filterDbgVars(R: Inst->getDbgRecordRange())) {
3507 RemapDebugOperands(&DVR, DVR.location_ops());
3508 if (DVR.isDbgAssign())
3509 RemapAssignAddress(&DVR);
3510 }
3511}
3512
3513namespace {
3514
3515/// A potential constituent of a bitreverse or bswap expression. See
3516/// collectBitParts for a fuller explanation.
3517struct BitPart {
3518 BitPart(Value *P, unsigned BW) : Provider(P) {
3519 Provenance.resize(N: BW);
3520 }
3521
3522 /// The Value that this is a bitreverse/bswap of.
3523 Value *Provider;
3524
3525 /// The "provenance" of each bit. Provenance[A] = B means that bit A
3526 /// in Provider becomes bit B in the result of this expression.
3527 SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
3528
3529 enum { Unset = -1 };
3530};
3531
3532} // end anonymous namespace
3533
3534/// Analyze the specified subexpression and see if it is capable of providing
3535/// pieces of a bswap or bitreverse. The subexpression provides a potential
3536/// piece of a bswap or bitreverse if it can be proved that each non-zero bit in
3537/// the output of the expression came from a corresponding bit in some other
3538/// value. This function is recursive, and the end result is a mapping of
3539/// bitnumber to bitnumber. It is the caller's responsibility to validate that
3540/// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
3541///
3542/// For example, if the current subexpression is "(shl i32 %X, 24)" then we know
3543/// that the expression deposits the low byte of %X into the high byte of the
3544/// result and that all other bits are zero. This expression is accepted and a
3545/// BitPart is returned with Provider set to %X and Provenance[24-31] set to
3546/// [0-7].
3547///
3548/// For vector types, all analysis is performed at the per-element level. No
3549/// cross-element analysis is supported (shuffle/insertion/reduction), and all
3550/// constant masks must be splatted across all elements.
3551///
3552/// To avoid revisiting values, the BitPart results are memoized into the
3553/// provided map. To avoid unnecessary copying of BitParts, BitParts are
3554/// constructed in-place in the \c BPS map. Because of this \c BPS needs to
3555/// store BitParts objects, not pointers. As we need the concept of a nullptr
3556/// BitParts (Value has been analyzed and the analysis failed), we use an
3557/// Optional type instead to provide the same functionality.
3558///
3559/// Because we pass around references into \c BPS, we must use a container that
3560/// does not invalidate internal references (std::map instead of DenseMap).
3561static const std::optional<BitPart> &
3562collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
3563 std::map<Value *, std::optional<BitPart>> &BPS, int Depth,
3564 bool &FoundRoot) {
3565 auto [I, Inserted] = BPS.try_emplace(k: V);
3566 if (!Inserted)
3567 return I->second;
3568
3569 auto &Result = I->second;
3570 auto BitWidth = V->getType()->getScalarSizeInBits();
3571
3572 // Can't do integer/elements > 128 bits.
3573 if (BitWidth > 128)
3574 return Result;
3575
3576 // Prevent stack overflow by limiting the recursion depth
3577 if (Depth == BitPartRecursionMaxDepth) {
3578 LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n");
3579 return Result;
3580 }
3581
3582 if (auto *I = dyn_cast<Instruction>(Val: V)) {
3583 Value *X, *Y;
3584 const APInt *C;
3585
3586 // If this is an or instruction, it may be an inner node of the bswap.
3587 if (match(V, P: m_Or(L: m_Value(V&: X), R: m_Value(V&: Y)))) {
3588 // Check we have both sources and they are from the same provider.
3589 const auto &A = collectBitParts(V: X, MatchBSwaps, MatchBitReversals, BPS,
3590 Depth: Depth + 1, FoundRoot);
3591 if (!A || !A->Provider)
3592 return Result;
3593
3594 const auto &B = collectBitParts(V: Y, MatchBSwaps, MatchBitReversals, BPS,
3595 Depth: Depth + 1, FoundRoot);
3596 if (!B || A->Provider != B->Provider)
3597 return Result;
3598
3599 // Try and merge the two together.
3600 Result = BitPart(A->Provider, BitWidth);
3601 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) {
3602 if (A->Provenance[BitIdx] != BitPart::Unset &&
3603 B->Provenance[BitIdx] != BitPart::Unset &&
3604 A->Provenance[BitIdx] != B->Provenance[BitIdx])
3605 return Result = std::nullopt;
3606
3607 if (A->Provenance[BitIdx] == BitPart::Unset)
3608 Result->Provenance[BitIdx] = B->Provenance[BitIdx];
3609 else
3610 Result->Provenance[BitIdx] = A->Provenance[BitIdx];
3611 }
3612
3613 return Result;
3614 }
3615
3616 // If this is a logical shift by a constant, recurse then shift the result.
3617 if (match(V, P: m_LogicalShift(L: m_Value(V&: X), R: m_APInt(Res&: C)))) {
3618 const APInt &BitShift = *C;
3619
3620 // Ensure the shift amount is defined.
3621 if (BitShift.uge(RHS: BitWidth))
3622 return Result;
3623
3624 // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3625 if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0)
3626 return Result;
3627
3628 const auto &Res = collectBitParts(V: X, MatchBSwaps, MatchBitReversals, BPS,
3629 Depth: Depth + 1, FoundRoot);
3630 if (!Res)
3631 return Result;
3632 Result = Res;
3633
3634 // Perform the "shift" on BitProvenance.
3635 auto &P = Result->Provenance;
3636 if (I->getOpcode() == Instruction::Shl) {
3637 P.erase(CS: std::prev(x: P.end(), n: BitShift.getZExtValue()), CE: P.end());
3638 P.insert(I: P.begin(), NumToInsert: BitShift.getZExtValue(), Elt: BitPart::Unset);
3639 } else {
3640 P.erase(CS: P.begin(), CE: std::next(x: P.begin(), n: BitShift.getZExtValue()));
3641 P.insert(I: P.end(), NumToInsert: BitShift.getZExtValue(), Elt: BitPart::Unset);
3642 }
3643
3644 return Result;
3645 }
3646
3647 // If this is a logical 'and' with a mask that clears bits, recurse then
3648 // unset the appropriate bits.
3649 if (match(V, P: m_And(L: m_Value(V&: X), R: m_APInt(Res&: C)))) {
3650 const APInt &AndMask = *C;
3651
3652 // Check that the mask allows a multiple of 8 bits for a bswap, for an
3653 // early exit.
3654 unsigned NumMaskedBits = AndMask.popcount();
3655 if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3656 return Result;
3657
3658 const auto &Res = collectBitParts(V: X, MatchBSwaps, MatchBitReversals, BPS,
3659 Depth: Depth + 1, FoundRoot);
3660 if (!Res)
3661 return Result;
3662 Result = Res;
3663
3664 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3665 // If the AndMask is zero for this bit, clear the bit.
3666 if (AndMask[BitIdx] == 0)
3667 Result->Provenance[BitIdx] = BitPart::Unset;
3668 return Result;
3669 }
3670
3671 // If this is a zext instruction zero extend the result.
3672 if (match(V, P: m_ZExt(Op: m_Value(V&: X)))) {
3673 const auto &Res = collectBitParts(V: X, MatchBSwaps, MatchBitReversals, BPS,
3674 Depth: Depth + 1, FoundRoot);
3675 if (!Res)
3676 return Result;
3677
3678 Result = BitPart(Res->Provider, BitWidth);
3679 auto NarrowBitWidth = X->getType()->getScalarSizeInBits();
3680 for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3681 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3682 for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx)
3683 Result->Provenance[BitIdx] = BitPart::Unset;
3684 return Result;
3685 }
3686
3687 // If this is a truncate instruction, extract the lower bits.
3688 if (match(V, P: m_Trunc(Op: m_Value(V&: X)))) {
3689 const auto &Res = collectBitParts(V: X, MatchBSwaps, MatchBitReversals, BPS,
3690 Depth: Depth + 1, FoundRoot);
3691 if (!Res)
3692 return Result;
3693
3694 Result = BitPart(Res->Provider, BitWidth);
3695 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3696 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3697 return Result;
3698 }
3699
3700 // BITREVERSE - most likely due to us previously matching a partial
3701 // bitreverse.
3702 if (match(V, P: m_BitReverse(Op0: m_Value(V&: X)))) {
3703 const auto &Res = collectBitParts(V: X, MatchBSwaps, MatchBitReversals, BPS,
3704 Depth: Depth + 1, FoundRoot);
3705 if (!Res)
3706 return Result;
3707
3708 Result = BitPart(Res->Provider, BitWidth);
3709 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3710 Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3711 return Result;
3712 }
3713
3714 // BSWAP - most likely due to us previously matching a partial bswap.
3715 if (match(V, P: m_BSwap(Op0: m_Value(V&: X)))) {
3716 const auto &Res = collectBitParts(V: X, MatchBSwaps, MatchBitReversals, BPS,
3717 Depth: Depth + 1, FoundRoot);
3718 if (!Res)
3719 return Result;
3720
3721 unsigned ByteWidth = BitWidth / 8;
3722 Result = BitPart(Res->Provider, BitWidth);
3723 for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3724 unsigned ByteBitOfs = ByteIdx * 8;
3725 for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3726 Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] =
3727 Res->Provenance[ByteBitOfs + BitIdx];
3728 }
3729 return Result;
3730 }
3731
3732 // Funnel 'double' shifts take 3 operands, 2 inputs and the shift
3733 // amount (modulo).
3734 // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
3735 // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW))
3736 if (match(V, P: m_FShl(Op0: m_Value(V&: X), Op1: m_Value(V&: Y), Op2: m_APInt(Res&: C))) ||
3737 match(V, P: m_FShr(Op0: m_Value(V&: X), Op1: m_Value(V&: Y), Op2: m_APInt(Res&: C)))) {
3738 // We can treat fshr as a fshl by flipping the modulo amount.
3739 unsigned ModAmt = C->urem(RHS: BitWidth);
3740 if (cast<IntrinsicInst>(Val: I)->getIntrinsicID() == Intrinsic::fshr)
3741 ModAmt = BitWidth - ModAmt;
3742
3743 // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3744 if (!MatchBitReversals && (ModAmt % 8) != 0)
3745 return Result;
3746
3747 // Check we have both sources and they are from the same provider.
3748 const auto &LHS = collectBitParts(V: X, MatchBSwaps, MatchBitReversals, BPS,
3749 Depth: Depth + 1, FoundRoot);
3750 if (!LHS || !LHS->Provider)
3751 return Result;
3752
3753 const auto &RHS = collectBitParts(V: Y, MatchBSwaps, MatchBitReversals, BPS,
3754 Depth: Depth + 1, FoundRoot);
3755 if (!RHS || LHS->Provider != RHS->Provider)
3756 return Result;
3757
3758 unsigned StartBitRHS = BitWidth - ModAmt;
3759 Result = BitPart(LHS->Provider, BitWidth);
3760 for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3761 Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx];
3762 for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3763 Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS];
3764 return Result;
3765 }
3766 }
3767
3768 // If we've already found a root input value then we're never going to merge
3769 // these back together.
3770 if (FoundRoot)
3771 return Result;
3772
3773 // Okay, we got to something that isn't a shift, 'or', 'and', etc. This must
3774 // be the root input value to the bswap/bitreverse.
3775 FoundRoot = true;
3776 Result = BitPart(V, BitWidth);
3777 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3778 Result->Provenance[BitIdx] = BitIdx;
3779 return Result;
3780}
3781
3782static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
3783 unsigned BitWidth) {
3784 if (From % 8 != To % 8)
3785 return false;
3786 // Convert from bit indices to byte indices and check for a byte reversal.
3787 From >>= 3;
3788 To >>= 3;
3789 BitWidth >>= 3;
3790 return From == BitWidth - To - 1;
3791}
3792
3793static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
3794 unsigned BitWidth) {
3795 return From == BitWidth - To - 1;
3796}
3797
3798bool llvm::recognizeBSwapOrBitReverseIdiom(
3799 Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
3800 SmallVectorImpl<Instruction *> &InsertedInsts) {
3801 if (!match(V: I, P: m_Or(L: m_Value(), R: m_Value())) &&
3802 !match(V: I, P: m_FShl(Op0: m_Value(), Op1: m_Value(), Op2: m_Value())) &&
3803 !match(V: I, P: m_FShr(Op0: m_Value(), Op1: m_Value(), Op2: m_Value())) &&
3804 !match(V: I, P: m_BSwap(Op0: m_Value())))
3805 return false;
3806 if (!MatchBSwaps && !MatchBitReversals)
3807 return false;
3808 Type *ITy = I->getType();
3809 if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() == 1 ||
3810 ITy->getScalarSizeInBits() > 128)
3811 return false; // Can't do integer/elements > 128 bits.
3812
3813 // Try to find all the pieces corresponding to the bswap.
3814 bool FoundRoot = false;
3815 std::map<Value *, std::optional<BitPart>> BPS;
3816 const auto &Res =
3817 collectBitParts(V: I, MatchBSwaps, MatchBitReversals, BPS, Depth: 0, FoundRoot);
3818 if (!Res)
3819 return false;
3820 ArrayRef<int8_t> BitProvenance = Res->Provenance;
3821 assert(all_of(BitProvenance,
3822 [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) &&
3823 "Illegal bit provenance index");
3824
3825 // If the upper bits are zero, then attempt to perform as a truncated op.
3826 Type *DemandedTy = ITy;
3827 if (BitProvenance.back() == BitPart::Unset) {
3828 while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset)
3829 BitProvenance = BitProvenance.drop_back();
3830 if (BitProvenance.empty())
3831 return false; // TODO - handle null value?
3832 DemandedTy = Type::getIntNTy(C&: I->getContext(), N: BitProvenance.size());
3833 if (auto *IVecTy = dyn_cast<VectorType>(Val: ITy))
3834 DemandedTy = VectorType::get(ElementType: DemandedTy, Other: IVecTy);
3835 }
3836
3837 // Check BitProvenance hasn't found a source larger than the result type.
3838 unsigned DemandedBW = DemandedTy->getScalarSizeInBits();
3839 if (DemandedBW > ITy->getScalarSizeInBits())
3840 return false;
3841
3842 // Now, is the bit permutation correct for a bswap or a bitreverse? We can
3843 // only byteswap values with an even number of bytes.
3844 APInt DemandedMask = APInt::getAllOnes(numBits: DemandedBW);
3845 bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
3846 bool OKForBitReverse = MatchBitReversals;
3847 for (unsigned BitIdx = 0;
3848 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
3849 if (BitProvenance[BitIdx] == BitPart::Unset) {
3850 DemandedMask.clearBit(BitPosition: BitIdx);
3851 continue;
3852 }
3853 OKForBSwap &= bitTransformIsCorrectForBSwap(From: BitProvenance[BitIdx], To: BitIdx,
3854 BitWidth: DemandedBW);
3855 OKForBitReverse &= bitTransformIsCorrectForBitReverse(From: BitProvenance[BitIdx],
3856 To: BitIdx, BitWidth: DemandedBW);
3857 }
3858
3859 Intrinsic::ID Intrin;
3860 if (OKForBSwap)
3861 Intrin = Intrinsic::bswap;
3862 else if (OKForBitReverse)
3863 Intrin = Intrinsic::bitreverse;
3864 else
3865 return false;
3866
3867 Function *F =
3868 Intrinsic::getOrInsertDeclaration(M: I->getModule(), id: Intrin, OverloadTys: DemandedTy);
3869 Value *Provider = Res->Provider;
3870
3871 // We may need to truncate the provider.
3872 if (DemandedTy != Provider->getType()) {
3873 auto *Trunc =
3874 CastInst::CreateIntegerCast(S: Provider, Ty: DemandedTy, isSigned: false, Name: "trunc", InsertBefore: I->getIterator());
3875 InsertedInsts.push_back(Elt: Trunc);
3876 Provider = Trunc;
3877 }
3878
3879 Instruction *Result = CallInst::Create(Func: F, Args: Provider, NameStr: "rev", InsertBefore: I->getIterator());
3880 InsertedInsts.push_back(Elt: Result);
3881
3882 if (!DemandedMask.isAllOnes()) {
3883 auto *Mask = ConstantInt::get(Ty: DemandedTy, V: DemandedMask);
3884 Result = BinaryOperator::Create(Op: Instruction::And, S1: Result, S2: Mask, Name: "mask", InsertBefore: I->getIterator());
3885 InsertedInsts.push_back(Elt: Result);
3886 }
3887
3888 // We may need to zeroextend back to the result type.
3889 if (ITy != Result->getType()) {
3890 auto *ExtInst = CastInst::CreateIntegerCast(S: Result, Ty: ITy, isSigned: false, Name: "zext", InsertBefore: I->getIterator());
3891 InsertedInsts.push_back(Elt: ExtInst);
3892 }
3893
3894 return true;
3895}
3896
3897// CodeGen has special handling for some string functions that may replace
3898// them with target-specific intrinsics. Since that'd skip our interceptors
3899// in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
3900// we mark affected calls as NoBuiltin, which will disable optimization
3901// in CodeGen.
3902void llvm::maybeMarkSanitizerLibraryCallNoBuiltin(
3903 CallInst *CI, const TargetLibraryInfo *TLI) {
3904 Function *F = CI->getCalledFunction();
3905 if (F && !F->hasLocalLinkage() && F->hasName() &&
3906 TLI->hasOptimizedCodeGen(F: TLI->getLibFunc(funcName: F->getName())) &&
3907 !F->doesNotAccessMemory())
3908 CI->addFnAttr(Kind: Attribute::NoBuiltin);
3909}
3910
3911bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
3912 const auto *Op = I->getOperand(i: OpIdx);
3913 // We can't have a PHI with a metadata or token type.
3914 if (Op->getType()->isMetadataTy() || Op->getType()->isTokenLikeTy())
3915 return false;
3916
3917 // swifterror pointers can only be used by a load, store, or as a swifterror
3918 // argument; swifterror pointers are not allowed to be used in select or phi
3919 // instructions.
3920 if (Op->isSwiftError())
3921 return false;
3922
3923 // Cannot replace alloca argument with phi/select.
3924 if (I->isLifetimeStartOrEnd())
3925 return false;
3926
3927 // Early exit.
3928 if (!isa<Constant, InlineAsm>(Val: Op))
3929 return true;
3930
3931 switch (I->getOpcode()) {
3932 default:
3933 return true;
3934 case Instruction::Call:
3935 case Instruction::Invoke: {
3936 const auto &CB = cast<CallBase>(Val: *I);
3937
3938 // Can't handle inline asm. Skip it.
3939 if (CB.isInlineAsm())
3940 return false;
3941
3942 // Constant bundle operands may need to retain their constant-ness for
3943 // correctness.
3944 if (CB.isBundleOperand(Idx: OpIdx))
3945 return false;
3946
3947 if (OpIdx < CB.arg_size()) {
3948 // Some variadic intrinsics require constants in the variadic arguments,
3949 // which currently aren't markable as immarg.
3950 if (isa<IntrinsicInst>(Val: CB) &&
3951 OpIdx >= CB.getFunctionType()->getNumParams()) {
3952 // This is known to be OK for stackmap.
3953 return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
3954 }
3955
3956 // gcroot is a special case, since it requires a constant argument which
3957 // isn't also required to be a simple ConstantInt.
3958 if (CB.getIntrinsicID() == Intrinsic::gcroot)
3959 return false;
3960
3961 // threadlocal_address is a special case as it requires its only
3962 // argument to be a thread local global.
3963 if (CB.getIntrinsicID() == Intrinsic::threadlocal_address)
3964 return false;
3965
3966 // Some intrinsic operands are required to be immediates.
3967 return !CB.paramHasAttr(ArgNo: OpIdx, Kind: Attribute::ImmArg);
3968 }
3969
3970 // It is never allowed to replace the call argument to an intrinsic, but it
3971 // may be possible for a call.
3972 return !isa<IntrinsicInst>(Val: CB);
3973 }
3974 case Instruction::ShuffleVector:
3975 // Shufflevector masks are constant.
3976 return OpIdx != 2;
3977 case Instruction::Switch:
3978 case Instruction::ExtractValue:
3979 // All operands apart from the first are constant.
3980 return OpIdx == 0;
3981 case Instruction::InsertValue:
3982 // All operands apart from the first and the second are constant.
3983 return OpIdx < 2;
3984 case Instruction::Alloca:
3985 // Static allocas (constant size in the entry block) are handled by
3986 // prologue/epilogue insertion so they're free anyway. We definitely don't
3987 // want to make them non-constant.
3988 return !cast<AllocaInst>(Val: I)->isStaticAlloca();
3989 case Instruction::GetElementPtr:
3990 if (OpIdx == 0)
3991 return true;
3992 gep_type_iterator It = gep_type_begin(GEP: I);
3993 for (auto E = std::next(x: It, n: OpIdx); It != E; ++It)
3994 if (It.isStruct())
3995 return false;
3996 return true;
3997 }
3998}
3999
4000Value *llvm::invertCondition(Value *Condition) {
4001 // First: Check if it's a constant
4002 if (Constant *C = dyn_cast<Constant>(Val: Condition))
4003 return ConstantExpr::getNot(C);
4004
4005 // Second: If the condition is already inverted, return the original value
4006 Value *NotCondition;
4007 if (match(V: Condition, P: m_Not(V: m_Value(V&: NotCondition))))
4008 return NotCondition;
4009
4010 BasicBlock *Parent = nullptr;
4011 Instruction *Inst = dyn_cast<Instruction>(Val: Condition);
4012 if (Inst)
4013 Parent = Inst->getParent();
4014 else if (Argument *Arg = dyn_cast<Argument>(Val: Condition))
4015 Parent = &Arg->getParent()->getEntryBlock();
4016 assert(Parent && "Unsupported condition to invert");
4017
4018 // Third: Check all the users for an invert
4019 for (User *U : Condition->users())
4020 if (Instruction *I = dyn_cast<Instruction>(Val: U))
4021 if (I->getParent() == Parent && match(V: I, P: m_Not(V: m_Specific(V: Condition))))
4022 return I;
4023
4024 // Last option: Create a new instruction
4025 auto *Inverted =
4026 BinaryOperator::CreateNot(Op: Condition, Name: Condition->getName() + ".inv");
4027 if (Inst && !isa<PHINode>(Val: Inst))
4028 Inverted->insertAfter(InsertPos: Inst->getIterator());
4029 else
4030 Inverted->insertBefore(InsertPos: Parent->getFirstInsertionPt());
4031 return Inverted;
4032}
4033
4034bool llvm::inferAttributesFromOthers(Function &F) {
4035 // Note: We explicitly check for attributes rather than using cover functions
4036 // because some of the cover functions include the logic being implemented.
4037
4038 bool Changed = false;
4039 // readnone + not convergent implies nosync
4040 if (!F.hasFnAttribute(Kind: Attribute::NoSync) &&
4041 F.doesNotAccessMemory() && !F.isConvergent()) {
4042 F.setNoSync();
4043 Changed = true;
4044 }
4045
4046 // readonly implies nofree
4047 if (!F.hasFnAttribute(Kind: Attribute::NoFree) && F.onlyReadsMemory()) {
4048 F.setDoesNotFreeMemory();
4049 Changed = true;
4050 }
4051
4052 // willreturn implies mustprogress
4053 if (!F.hasFnAttribute(Kind: Attribute::MustProgress) && F.willReturn()) {
4054 F.setMustProgress();
4055 Changed = true;
4056 }
4057
4058 // TODO: There are a bunch of cases of restrictive memory effects we
4059 // can infer by inspecting arguments of argmemonly-ish functions.
4060
4061 return Changed;
4062}
4063
4064void OverflowTracking::mergeFlags(Instruction &I) {
4065#ifndef NDEBUG
4066 if (Opcode)
4067 assert(Opcode == I.getOpcode() &&
4068 "can only use mergeFlags on instructions with matching opcodes");
4069 else
4070 Opcode = I.getOpcode();
4071#endif
4072 if (isa<OverflowingBinaryOperator>(Val: &I)) {
4073 HasNUW &= I.hasNoUnsignedWrap();
4074 HasNSW &= I.hasNoSignedWrap();
4075 }
4076 if (auto *DisjointOp = dyn_cast<PossiblyDisjointInst>(Val: &I))
4077 IsDisjoint &= DisjointOp->isDisjoint();
4078}
4079
4080void OverflowTracking::applyFlags(Instruction &I) {
4081 I.dropPoisonGeneratingFlags();
4082 if (I.getOpcode() == Instruction::Add ||
4083 (I.getOpcode() == Instruction::Mul && AllKnownNonZero)) {
4084 if (HasNUW)
4085 I.setHasNoUnsignedWrap();
4086 if (HasNSW && (AllKnownNonNegative || HasNUW))
4087 I.setHasNoSignedWrap();
4088 }
4089 if (auto *DisjointOp = dyn_cast<PossiblyDisjointInst>(Val: &I))
4090 DisjointOp->setIsDisjoint(IsDisjoint);
4091}
4092