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