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