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