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