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