LLVM 17.0.0git
Local.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/DenseMap.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"
24#include "llvm/ADT/Statistic.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"
41#include "llvm/IR/Constants.h"
42#include "llvm/IR/DIBuilder.h"
43#include "llvm/IR/DataLayout.h"
44#include "llvm/IR/DebugInfo.h"
46#include "llvm/IR/DebugLoc.h"
48#include "llvm/IR/Dominators.h"
50#include "llvm/IR/Function.h"
53#include "llvm/IR/IRBuilder.h"
54#include "llvm/IR/InstrTypes.h"
55#include "llvm/IR/Instruction.h"
58#include "llvm/IR/Intrinsics.h"
59#include "llvm/IR/IntrinsicsWebAssembly.h"
60#include "llvm/IR/LLVMContext.h"
61#include "llvm/IR/MDBuilder.h"
62#include "llvm/IR/Metadata.h"
63#include "llvm/IR/Module.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"
72#include "llvm/Support/Debug.h"
78#include <algorithm>
79#include <cassert>
80#include <cstdint>
81#include <iterator>
82#include <map>
83#include <optional>
84#include <utility>
85
86using namespace llvm;
87using namespace llvm::PatternMatch;
88
89#define DEBUG_TYPE "local"
90
91STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
92STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd");
93
95 "phicse-debug-hash",
96#ifdef EXPENSIVE_CHECKS
97 cl::init(true),
98#else
99 cl::init(false),
100#endif
102 cl::desc("Perform extra assertion checking to verify that PHINodes's hash "
103 "function is well-behaved w.r.t. its isEqual predicate"));
104
106 "phicse-num-phi-smallsize", cl::init(32), cl::Hidden,
107 cl::desc(
108 "When the basic block contains not more than this number of PHI nodes, "
109 "perform a (faster!) exhaustive search instead of set-driven one."));
110
111// Max recursion depth for collectBitParts used when detecting bswap and
112// bitreverse idioms.
113static const unsigned BitPartRecursionMaxDepth = 48;
114
115//===----------------------------------------------------------------------===//
116// Local constant propagation.
117//
118
119/// ConstantFoldTerminator - If a terminator instruction is predicated on a
120/// constant value, convert it into an unconditional branch to the constant
121/// destination. This is a nontrivial operation because the successors of this
122/// basic block must have their PHI nodes updated.
123/// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
124/// conditions and indirectbr addresses this might make dead if
125/// DeleteDeadConditions is true.
126bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
127 const TargetLibraryInfo *TLI,
128 DomTreeUpdater *DTU) {
129 Instruction *T = BB->getTerminator();
131
132 // Branch - See if we are conditional jumping on constant
133 if (auto *BI = dyn_cast<BranchInst>(T)) {
134 if (BI->isUnconditional()) return false; // Can't optimize uncond branch
135
136 BasicBlock *Dest1 = BI->getSuccessor(0);
137 BasicBlock *Dest2 = BI->getSuccessor(1);
138
139 if (Dest2 == Dest1) { // Conditional branch to same location?
140 // This branch matches something like this:
141 // br bool %cond, label %Dest, label %Dest
142 // and changes it into: br label %Dest
143
144 // Let the basic block know that we are letting go of one copy of it.
145 assert(BI->getParent() && "Terminator not inserted in block!");
146 Dest1->removePredecessor(BI->getParent());
147
148 // Replace the conditional branch with an unconditional one.
149 BranchInst *NewBI = Builder.CreateBr(Dest1);
150
151 // Transfer the metadata to the new branch instruction.
152 NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
153 LLVMContext::MD_annotation});
154
155 Value *Cond = BI->getCondition();
156 BI->eraseFromParent();
157 if (DeleteDeadConditions)
159 return true;
160 }
161
162 if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
163 // Are we branching on constant?
164 // YES. Change to unconditional branch...
165 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
166 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;
167
168 // Let the basic block know that we are letting go of it. Based on this,
169 // it will adjust it's PHI nodes.
170 OldDest->removePredecessor(BB);
171
172 // Replace the conditional branch with an unconditional one.
173 BranchInst *NewBI = Builder.CreateBr(Destination);
174
175 // Transfer the metadata to the new branch instruction.
176 NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
177 LLVMContext::MD_annotation});
178
179 BI->eraseFromParent();
180 if (DTU)
181 DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}});
182 return true;
183 }
184
185 return false;
186 }
187
188 if (auto *SI = dyn_cast<SwitchInst>(T)) {
189 // If we are switching on a constant, we can convert the switch to an
190 // unconditional branch.
191 auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
192 BasicBlock *DefaultDest = SI->getDefaultDest();
193 BasicBlock *TheOnlyDest = DefaultDest;
194
195 // If the default is unreachable, ignore it when searching for TheOnlyDest.
196 if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) &&
197 SI->getNumCases() > 0) {
198 TheOnlyDest = SI->case_begin()->getCaseSuccessor();
199 }
200
201 bool Changed = false;
202
203 // Figure out which case it goes to.
204 for (auto It = SI->case_begin(), End = SI->case_end(); It != End;) {
205 // Found case matching a constant operand?
206 if (It->getCaseValue() == CI) {
207 TheOnlyDest = It->getCaseSuccessor();
208 break;
209 }
210
211 // Check to see if this branch is going to the same place as the default
212 // dest. If so, eliminate it as an explicit compare.
213 if (It->getCaseSuccessor() == DefaultDest) {
215 unsigned NCases = SI->getNumCases();
216 // Fold the case metadata into the default if there will be any branches
217 // left, unless the metadata doesn't match the switch.
218 if (NCases > 1 && MD) {
219 // Collect branch weights into a vector.
221 extractBranchWeights(MD, Weights);
222
223 // Merge weight of this case to the default weight.
224 unsigned Idx = It->getCaseIndex();
225 // TODO: Add overflow check.
226 Weights[0] += Weights[Idx + 1];
227 // Remove weight for this case.
228 std::swap(Weights[Idx + 1], Weights.back());
229 Weights.pop_back();
230 SI->setMetadata(LLVMContext::MD_prof,
231 MDBuilder(BB->getContext()).
232 createBranchWeights(Weights));
233 }
234 // Remove this entry.
235 BasicBlock *ParentBB = SI->getParent();
236 DefaultDest->removePredecessor(ParentBB);
237 It = SI->removeCase(It);
238 End = SI->case_end();
239
240 // Removing this case may have made the condition constant. In that
241 // case, update CI and restart iteration through the cases.
242 if (auto *NewCI = dyn_cast<ConstantInt>(SI->getCondition())) {
243 CI = NewCI;
244 It = SI->case_begin();
245 }
246
247 Changed = true;
248 continue;
249 }
250
251 // Otherwise, check to see if the switch only branches to one destination.
252 // We do this by reseting "TheOnlyDest" to null when we find two non-equal
253 // destinations.
254 if (It->getCaseSuccessor() != TheOnlyDest)
255 TheOnlyDest = nullptr;
256
257 // Increment this iterator as we haven't removed the case.
258 ++It;
259 }
260
261 if (CI && !TheOnlyDest) {
262 // Branching on a constant, but not any of the cases, go to the default
263 // successor.
264 TheOnlyDest = SI->getDefaultDest();
265 }
266
267 // If we found a single destination that we can fold the switch into, do so
268 // now.
269 if (TheOnlyDest) {
270 // Insert the new branch.
271 Builder.CreateBr(TheOnlyDest);
272 BasicBlock *BB = SI->getParent();
273
274 SmallSet<BasicBlock *, 8> RemovedSuccessors;
275
276 // Remove entries from PHI nodes which we no longer branch to...
277 BasicBlock *SuccToKeep = TheOnlyDest;
278 for (BasicBlock *Succ : successors(SI)) {
279 if (DTU && Succ != TheOnlyDest)
280 RemovedSuccessors.insert(Succ);
281 // Found case matching a constant operand?
282 if (Succ == SuccToKeep) {
283 SuccToKeep = nullptr; // Don't modify the first branch to TheOnlyDest
284 } else {
285 Succ->removePredecessor(BB);
286 }
287 }
288
289 // Delete the old switch.
290 Value *Cond = SI->getCondition();
291 SI->eraseFromParent();
292 if (DeleteDeadConditions)
294 if (DTU) {
295 std::vector<DominatorTree::UpdateType> Updates;
296 Updates.reserve(RemovedSuccessors.size());
297 for (auto *RemovedSuccessor : RemovedSuccessors)
298 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
299 DTU->applyUpdates(Updates);
300 }
301 return true;
302 }
303
304 if (SI->getNumCases() == 1) {
305 // Otherwise, we can fold this switch into a conditional branch
306 // instruction if it has only one non-default destination.
307 auto FirstCase = *SI->case_begin();
308 Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
309 FirstCase.getCaseValue(), "cond");
310
311 // Insert the new branch.
312 BranchInst *NewBr = Builder.CreateCondBr(Cond,
313 FirstCase.getCaseSuccessor(),
314 SI->getDefaultDest());
315 SmallVector<uint32_t> Weights;
316 if (extractBranchWeights(*SI, Weights) && Weights.size() == 2) {
317 uint32_t DefWeight = Weights[0];
318 uint32_t CaseWeight = Weights[1];
319 // The TrueWeight should be the weight for the single case of SI.
320 NewBr->setMetadata(LLVMContext::MD_prof,
321 MDBuilder(BB->getContext())
322 .createBranchWeights(CaseWeight, DefWeight));
323 }
324
325 // Update make.implicit metadata to the newly-created conditional branch.
326 MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
327 if (MakeImplicitMD)
328 NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
329
330 // Delete the old switch.
331 SI->eraseFromParent();
332 return true;
333 }
334 return Changed;
335 }
336
337 if (auto *IBI = dyn_cast<IndirectBrInst>(T)) {
338 // indirectbr blockaddress(@F, @BB) -> br label @BB
339 if (auto *BA =
340 dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
341 BasicBlock *TheOnlyDest = BA->getBasicBlock();
342 SmallSet<BasicBlock *, 8> RemovedSuccessors;
343
344 // Insert the new branch.
345 Builder.CreateBr(TheOnlyDest);
346
347 BasicBlock *SuccToKeep = TheOnlyDest;
348 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
349 BasicBlock *DestBB = IBI->getDestination(i);
350 if (DTU && DestBB != TheOnlyDest)
351 RemovedSuccessors.insert(DestBB);
352 if (IBI->getDestination(i) == SuccToKeep) {
353 SuccToKeep = nullptr;
354 } else {
355 DestBB->removePredecessor(BB);
356 }
357 }
358 Value *Address = IBI->getAddress();
359 IBI->eraseFromParent();
360 if (DeleteDeadConditions)
361 // Delete pointer cast instructions.
363
364 // Also zap the blockaddress constant if there are no users remaining,
365 // otherwise the destination is still marked as having its address taken.
366 if (BA->use_empty())
367 BA->destroyConstant();
368
369 // If we didn't find our destination in the IBI successor list, then we
370 // have undefined behavior. Replace the unconditional branch with an
371 // 'unreachable' instruction.
372 if (SuccToKeep) {
374 new UnreachableInst(BB->getContext(), BB);
375 }
376
377 if (DTU) {
378 std::vector<DominatorTree::UpdateType> Updates;
379 Updates.reserve(RemovedSuccessors.size());
380 for (auto *RemovedSuccessor : RemovedSuccessors)
381 Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
382 DTU->applyUpdates(Updates);
383 }
384 return true;
385 }
386 }
387
388 return false;
389}
390
391//===----------------------------------------------------------------------===//
392// Local dead code elimination.
393//
394
395/// isInstructionTriviallyDead - Return true if the result produced by the
396/// instruction is not used, and the instruction has no side effects.
397///
399 const TargetLibraryInfo *TLI) {
400 if (!I->use_empty())
401 return false;
403}
404
406 Instruction *I, const TargetLibraryInfo *TLI) {
407 // Instructions that are "markers" and have implied meaning on code around
408 // them (without explicit uses), are not dead on unused paths.
409 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
410 if (II->getIntrinsicID() == Intrinsic::stacksave ||
411 II->getIntrinsicID() == Intrinsic::launder_invariant_group ||
412 II->isLifetimeStartOrEnd())
413 return false;
415}
416
418 const TargetLibraryInfo *TLI) {
419 if (I->isTerminator())
420 return false;
421
422 // We don't want the landingpad-like instructions removed by anything this
423 // general.
424 if (I->isEHPad())
425 return false;
426
427 // We don't want debug info removed by anything this general, unless
428 // debug info is empty.
429 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
430 if (DDI->getAddress())
431 return false;
432 return true;
433 }
434 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
435 if (DVI->hasArgList() || DVI->getValue(0))
436 return false;
437 return true;
438 }
439 if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) {
440 if (DLI->getLabel())
441 return false;
442 return true;
443 }
444
445 if (auto *CB = dyn_cast<CallBase>(I))
446 if (isRemovableAlloc(CB, TLI))
447 return true;
448
449 if (!I->willReturn()) {
450 auto *II = dyn_cast<IntrinsicInst>(I);
451 if (!II)
452 return false;
453
454 // TODO: These intrinsics are not safe to remove, because this may remove
455 // a well-defined trap.
456 switch (II->getIntrinsicID()) {
457 case Intrinsic::wasm_trunc_signed:
458 case Intrinsic::wasm_trunc_unsigned:
459 case Intrinsic::ptrauth_auth:
460 case Intrinsic::ptrauth_resign:
461 return true;
462 default:
463 return false;
464 }
465 }
466
467 if (!I->mayHaveSideEffects())
468 return true;
469
470 // Special case intrinsics that "may have side effects" but can be deleted
471 // when dead.
472 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
473 // Safe to delete llvm.stacksave and launder.invariant.group if dead.
474 if (II->getIntrinsicID() == Intrinsic::stacksave ||
475 II->getIntrinsicID() == Intrinsic::launder_invariant_group)
476 return true;
477
478 if (II->isLifetimeStartOrEnd()) {
479 auto *Arg = II->getArgOperand(1);
480 // Lifetime intrinsics are dead when their right-hand is undef.
481 if (isa<UndefValue>(Arg))
482 return true;
483 // If the right-hand is an alloc, global, or argument and the only uses
484 // are lifetime intrinsics then the intrinsics are dead.
485 if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg))
486 return llvm::all_of(Arg->uses(), [](Use &Use) {
487 if (IntrinsicInst *IntrinsicUse =
488 dyn_cast<IntrinsicInst>(Use.getUser()))
489 return IntrinsicUse->isLifetimeStartOrEnd();
490 return false;
491 });
492 return false;
493 }
494
495 // Assumptions are dead if their condition is trivially true. Guards on
496 // true are operationally no-ops. In the future we can consider more
497 // sophisticated tradeoffs for guards considering potential for check
498 // widening, but for now we keep things simple.
499 if ((II->getIntrinsicID() == Intrinsic::assume &&
500 isAssumeWithEmptyBundle(cast<AssumeInst>(*II))) ||
501 II->getIntrinsicID() == Intrinsic::experimental_guard) {
502 if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
503 return !Cond->isZero();
504
505 return false;
506 }
507
508 if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(I)) {
509 std::optional<fp::ExceptionBehavior> ExBehavior =
510 FPI->getExceptionBehavior();
511 return *ExBehavior != fp::ebStrict;
512 }
513 }
514
515 if (auto *Call = dyn_cast<CallBase>(I)) {
516 if (Value *FreedOp = getFreedOperand(Call, TLI))
517 if (Constant *C = dyn_cast<Constant>(FreedOp))
518 return C->isNullValue() || isa<UndefValue>(C);
519 if (isMathLibCallNoop(Call, TLI))
520 return true;
521 }
522
523 // Non-volatile atomic loads from constants can be removed.
524 if (auto *LI = dyn_cast<LoadInst>(I))
525 if (auto *GV = dyn_cast<GlobalVariable>(
526 LI->getPointerOperand()->stripPointerCasts()))
527 if (!LI->isVolatile() && GV->isConstant())
528 return true;
529
530 return false;
531}
532
533/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
534/// trivially dead instruction, delete it. If that makes any of its operands
535/// trivially dead, delete them too, recursively. Return true if any
536/// instructions were deleted.
538 Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU,
539 std::function<void(Value *)> AboutToDeleteCallback) {
540 Instruction *I = dyn_cast<Instruction>(V);
541 if (!I || !isInstructionTriviallyDead(I, TLI))
542 return false;
543
545 DeadInsts.push_back(I);
546 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
547 AboutToDeleteCallback);
548
549 return true;
550}
551
554 MemorySSAUpdater *MSSAU,
555 std::function<void(Value *)> AboutToDeleteCallback) {
556 unsigned S = 0, E = DeadInsts.size(), Alive = 0;
557 for (; S != E; ++S) {
558 auto *I = dyn_cast_or_null<Instruction>(DeadInsts[S]);
559 if (!I || !isInstructionTriviallyDead(I)) {
560 DeadInsts[S] = nullptr;
561 ++Alive;
562 }
563 }
564 if (Alive == E)
565 return false;
566 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
567 AboutToDeleteCallback);
568 return true;
569}
570
573 MemorySSAUpdater *MSSAU,
574 std::function<void(Value *)> AboutToDeleteCallback) {
575 // Process the dead instruction list until empty.
576 while (!DeadInsts.empty()) {
577 Value *V = DeadInsts.pop_back_val();
578 Instruction *I = cast_or_null<Instruction>(V);
579 if (!I)
580 continue;
582 "Live instruction found in dead worklist!");
583 assert(I->use_empty() && "Instructions with uses are not dead.");
584
585 // Don't lose the debug info while deleting the instructions.
587
588 if (AboutToDeleteCallback)
589 AboutToDeleteCallback(I);
590
591 // Null out all of the instruction's operands to see if any operand becomes
592 // dead as we go.
593 for (Use &OpU : I->operands()) {
594 Value *OpV = OpU.get();
595 OpU.set(nullptr);
596
597 if (!OpV->use_empty())
598 continue;
599
600 // If the operand is an instruction that became dead as we nulled out the
601 // operand, and if it is 'trivially' dead, delete it in a future loop
602 // iteration.
603 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
604 if (isInstructionTriviallyDead(OpI, TLI))
605 DeadInsts.push_back(OpI);
606 }
607 if (MSSAU)
608 MSSAU->removeMemoryAccess(I);
609
610 I->eraseFromParent();
611 }
612}
613
616 findDbgUsers(DbgUsers, I);
617 for (auto *DII : DbgUsers)
618 DII->setKillLocation();
619 return !DbgUsers.empty();
620}
621
622/// areAllUsesEqual - Check whether the uses of a value are all the same.
623/// This is similar to Instruction::hasOneUse() except this will also return
624/// true when there are no uses or multiple uses that all refer to the same
625/// value.
627 Value::user_iterator UI = I->user_begin();
628 Value::user_iterator UE = I->user_end();
629 if (UI == UE)
630 return true;
631
632 User *TheUse = *UI;
633 for (++UI; UI != UE; ++UI) {
634 if (*UI != TheUse)
635 return false;
636 }
637 return true;
638}
639
640/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
641/// dead PHI node, due to being a def-use chain of single-use nodes that
642/// either forms a cycle or is terminated by a trivially dead instruction,
643/// delete it. If that makes any of its operands trivially dead, delete them
644/// too, recursively. Return true if a change was made.
646 const TargetLibraryInfo *TLI,
647 llvm::MemorySSAUpdater *MSSAU) {
649 for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
650 I = cast<Instruction>(*I->user_begin())) {
651 if (I->use_empty())
653
654 // If we find an instruction more than once, we're on a cycle that
655 // won't prove fruitful.
656 if (!Visited.insert(I).second) {
657 // Break the cycle and delete the instruction and its operands.
658 I->replaceAllUsesWith(PoisonValue::get(I->getType()));
660 return true;
661 }
662 }
663 return false;
664}
665
666static bool
669 const DataLayout &DL,
670 const TargetLibraryInfo *TLI) {
671 if (isInstructionTriviallyDead(I, TLI)) {
673
674 // Null out all of the instruction's operands to see if any operand becomes
675 // dead as we go.
676 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
677 Value *OpV = I->getOperand(i);
678 I->setOperand(i, nullptr);
679
680 if (!OpV->use_empty() || I == OpV)
681 continue;
682
683 // If the operand is an instruction that became dead as we nulled out the
684 // operand, and if it is 'trivially' dead, delete it in a future loop
685 // iteration.
686 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
687 if (isInstructionTriviallyDead(OpI, TLI))
688 WorkList.insert(OpI);
689 }
690
691 I->eraseFromParent();
692
693 return true;
694 }
695
696 if (Value *SimpleV = simplifyInstruction(I, DL)) {
697 // Add the users to the worklist. CAREFUL: an instruction can use itself,
698 // in the case of a phi node.
699 for (User *U : I->users()) {
700 if (U != I) {
701 WorkList.insert(cast<Instruction>(U));
702 }
703 }
704
705 // Replace the instruction with its simplified value.
706 bool Changed = false;
707 if (!I->use_empty()) {
708 I->replaceAllUsesWith(SimpleV);
709 Changed = true;
710 }
711 if (isInstructionTriviallyDead(I, TLI)) {
712 I->eraseFromParent();
713 Changed = true;
714 }
715 return Changed;
716 }
717 return false;
718}
719
720/// SimplifyInstructionsInBlock - Scan the specified basic block and try to
721/// simplify any instructions in it and recursively delete dead instructions.
722///
723/// This returns true if it changed the code, note that it can delete
724/// instructions in other blocks as well in this block.
726 const TargetLibraryInfo *TLI) {
727 bool MadeChange = false;
728 const DataLayout &DL = BB->getModule()->getDataLayout();
729
730#ifndef NDEBUG
731 // In debug builds, ensure that the terminator of the block is never replaced
732 // or deleted by these simplifications. The idea of simplification is that it
733 // cannot introduce new instructions, and there is no way to replace the
734 // terminator of a block without introducing a new instruction.
735 AssertingVH<Instruction> TerminatorVH(&BB->back());
736#endif
737
739 // Iterate over the original function, only adding insts to the worklist
740 // if they actually need to be revisited. This avoids having to pre-init
741 // the worklist with the entire function's worth of instructions.
742 for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end());
743 BI != E;) {
744 assert(!BI->isTerminator());
745 Instruction *I = &*BI;
746 ++BI;
747
748 // We're visiting this instruction now, so make sure it's not in the
749 // worklist from an earlier visit.
750 if (!WorkList.count(I))
751 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
752 }
753
754 while (!WorkList.empty()) {
755 Instruction *I = WorkList.pop_back_val();
756 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
757 }
758 return MadeChange;
759}
760
761//===----------------------------------------------------------------------===//
762// Control Flow Graph Restructuring.
763//
764
766 DomTreeUpdater *DTU) {
767
768 // If BB has single-entry PHI nodes, fold them.
769 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
770 Value *NewVal = PN->getIncomingValue(0);
771 // Replace self referencing PHI with poison, it must be dead.
772 if (NewVal == PN) NewVal = PoisonValue::get(PN->getType());
773 PN->replaceAllUsesWith(NewVal);
774 PN->eraseFromParent();
775 }
776
777 BasicBlock *PredBB = DestBB->getSinglePredecessor();
778 assert(PredBB && "Block doesn't have a single predecessor!");
779
780 bool ReplaceEntryBB = PredBB->isEntryBlock();
781
782 // DTU updates: Collect all the edges that enter
783 // PredBB. These dominator edges will be redirected to DestBB.
785
786 if (DTU) {
787 // To avoid processing the same predecessor more than once.
789 Updates.reserve(Updates.size() + 2 * pred_size(PredBB) + 1);
790 for (BasicBlock *PredOfPredBB : predecessors(PredBB))
791 // This predecessor of PredBB may already have DestBB as a successor.
792 if (PredOfPredBB != PredBB)
793 if (SeenPreds.insert(PredOfPredBB).second)
794 Updates.push_back({DominatorTree::Insert, PredOfPredBB, DestBB});
795 SeenPreds.clear();
796 for (BasicBlock *PredOfPredBB : predecessors(PredBB))
797 if (SeenPreds.insert(PredOfPredBB).second)
798 Updates.push_back({DominatorTree::Delete, PredOfPredBB, PredBB});
799 Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
800 }
801
802 // Zap anything that took the address of DestBB. Not doing this will give the
803 // address an invalid value.
804 if (DestBB->hasAddressTaken()) {
805 BlockAddress *BA = BlockAddress::get(DestBB);
806 Constant *Replacement =
809 BA->getType()));
810 BA->destroyConstant();
811 }
812
813 // Anything that branched to PredBB now branches to DestBB.
814 PredBB->replaceAllUsesWith(DestBB);
815
816 // Splice all the instructions from PredBB to DestBB.
817 PredBB->getTerminator()->eraseFromParent();
818 DestBB->splice(DestBB->begin(), PredBB);
819 new UnreachableInst(PredBB->getContext(), PredBB);
820
821 // If the PredBB is the entry block of the function, move DestBB up to
822 // become the entry block after we erase PredBB.
823 if (ReplaceEntryBB)
824 DestBB->moveAfter(PredBB);
825
826 if (DTU) {
827 assert(PredBB->size() == 1 &&
828 isa<UnreachableInst>(PredBB->getTerminator()) &&
829 "The successor list of PredBB isn't empty before "
830 "applying corresponding DTU updates.");
831 DTU->applyUpdatesPermissive(Updates);
832 DTU->deleteBB(PredBB);
833 // Recalculation of DomTree is needed when updating a forward DomTree and
834 // the Entry BB is replaced.
835 if (ReplaceEntryBB && DTU->hasDomTree()) {
836 // The entry block was removed and there is no external interface for
837 // the dominator tree to be notified of this change. In this corner-case
838 // we recalculate the entire tree.
839 DTU->recalculate(*(DestBB->getParent()));
840 }
841 }
842
843 else {
844 PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr.
845 }
846}
847
848/// Return true if we can choose one of these values to use in place of the
849/// other. Note that we will always choose the non-undef value to keep.
850static bool CanMergeValues(Value *First, Value *Second) {
851 return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
852}
853
854/// Return true if we can fold BB, an almost-empty BB ending in an unconditional
855/// branch to Succ, into Succ.
856///
857/// Assumption: Succ is the single successor for BB.
859 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
860
861 LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
862 << Succ->getName() << "\n");
863 // Shortcut, if there is only a single predecessor it must be BB and merging
864 // is always safe
865 if (Succ->getSinglePredecessor()) return true;
866
867 // Make a list of the predecessors of BB
869
870 // Look at all the phi nodes in Succ, to see if they present a conflict when
871 // merging these blocks
872 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
873 PHINode *PN = cast<PHINode>(I);
874
875 // If the incoming value from BB is again a PHINode in
876 // BB which has the same incoming value for *PI as PN does, we can
877 // merge the phi nodes and then the blocks can still be merged
878 PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
879 if (BBPN && BBPN->getParent() == BB) {
880 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
881 BasicBlock *IBB = PN->getIncomingBlock(PI);
882 if (BBPreds.count(IBB) &&
884 PN->getIncomingValue(PI))) {
886 << "Can't fold, phi node " << PN->getName() << " in "
887 << Succ->getName() << " is conflicting with "
888 << BBPN->getName() << " with regard to common predecessor "
889 << IBB->getName() << "\n");
890 return false;
891 }
892 }
893 } else {
894 Value* Val = PN->getIncomingValueForBlock(BB);
895 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
896 // See if the incoming value for the common predecessor is equal to the
897 // one for BB, in which case this phi node will not prevent the merging
898 // of the block.
899 BasicBlock *IBB = PN->getIncomingBlock(PI);
900 if (BBPreds.count(IBB) &&
901 !CanMergeValues(Val, PN->getIncomingValue(PI))) {
902 LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()
903 << " in " << Succ->getName()
904 << " is conflicting with regard to common "
905 << "predecessor " << IBB->getName() << "\n");
906 return false;
907 }
908 }
909 }
910 }
911
912 return true;
913}
914
917
918/// Determines the value to use as the phi node input for a block.
919///
920/// Select between \p OldVal any value that we know flows from \p BB
921/// to a particular phi on the basis of which one (if either) is not
922/// undef. Update IncomingValues based on the selected value.
923///
924/// \param OldVal The value we are considering selecting.
925/// \param BB The block that the value flows in from.
926/// \param IncomingValues A map from block-to-value for other phi inputs
927/// that we have examined.
928///
929/// \returns the selected value.
931 IncomingValueMap &IncomingValues) {
932 if (!isa<UndefValue>(OldVal)) {
933 assert((!IncomingValues.count(BB) ||
934 IncomingValues.find(BB)->second == OldVal) &&
935 "Expected OldVal to match incoming value from BB!");
936
937 IncomingValues.insert(std::make_pair(BB, OldVal));
938 return OldVal;
939 }
940
941 IncomingValueMap::const_iterator It = IncomingValues.find(BB);
942 if (It != IncomingValues.end()) return It->second;
943
944 return OldVal;
945}
946
947/// Create a map from block to value for the operands of a
948/// given phi.
949///
950/// Create a map from block to value for each non-undef value flowing
951/// into \p PN.
952///
953/// \param PN The phi we are collecting the map for.
954/// \param IncomingValues [out] The map from block to value for this phi.
956 IncomingValueMap &IncomingValues) {
957 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
958 BasicBlock *BB = PN->getIncomingBlock(i);
959 Value *V = PN->getIncomingValue(i);
960
961 if (!isa<UndefValue>(V))
962 IncomingValues.insert(std::make_pair(BB, V));
963 }
964}
965
966/// Replace the incoming undef values to a phi with the values
967/// from a block-to-value map.
968///
969/// \param PN The phi we are replacing the undefs in.
970/// \param IncomingValues A map from block to value.
972 const IncomingValueMap &IncomingValues) {
973 SmallVector<unsigned> TrueUndefOps;
974 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
975 Value *V = PN->getIncomingValue(i);
976
977 if (!isa<UndefValue>(V)) continue;
978
979 BasicBlock *BB = PN->getIncomingBlock(i);
980 IncomingValueMap::const_iterator It = IncomingValues.find(BB);
981
982 // Keep track of undef/poison incoming values. Those must match, so we fix
983 // them up below if needed.
984 // Note: this is conservatively correct, but we could try harder and group
985 // the undef values per incoming basic block.
986 if (It == IncomingValues.end()) {
987 TrueUndefOps.push_back(i);
988 continue;
989 }
990
991 // There is a defined value for this incoming block, so map this undef
992 // incoming value to the defined value.
993 PN->setIncomingValue(i, It->second);
994 }
995
996 // If there are both undef and poison values incoming, then convert those
997 // values to undef. It is invalid to have different values for the same
998 // incoming block.
999 unsigned PoisonCount = count_if(TrueUndefOps, [&](unsigned i) {
1000 return isa<PoisonValue>(PN->getIncomingValue(i));
1001 });
1002 if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) {
1003 for (unsigned i : TrueUndefOps)
1005 }
1006}
1007
1008/// Replace a value flowing from a block to a phi with
1009/// potentially multiple instances of that value flowing from the
1010/// block's predecessors to the phi.
1011///
1012/// \param BB The block with the value flowing into the phi.
1013/// \param BBPreds The predecessors of BB.
1014/// \param PN The phi that we are updating.
1016 const PredBlockVector &BBPreds,
1017 PHINode *PN) {
1018 Value *OldVal = PN->removeIncomingValue(BB, false);
1019 assert(OldVal && "No entry in PHI for Pred BB!");
1020
1021 IncomingValueMap IncomingValues;
1022
1023 // We are merging two blocks - BB, and the block containing PN - and
1024 // as a result we need to redirect edges from the predecessors of BB
1025 // to go to the block containing PN, and update PN
1026 // accordingly. Since we allow merging blocks in the case where the
1027 // predecessor and successor blocks both share some predecessors,
1028 // and where some of those common predecessors might have undef
1029 // values flowing into PN, we want to rewrite those values to be
1030 // consistent with the non-undef values.
1031
1032 gatherIncomingValuesToPhi(PN, IncomingValues);
1033
1034 // If this incoming value is one of the PHI nodes in BB, the new entries
1035 // in the PHI node are the entries from the old PHI.
1036 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
1037 PHINode *OldValPN = cast<PHINode>(OldVal);
1038 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
1039 // Note that, since we are merging phi nodes and BB and Succ might
1040 // have common predecessors, we could end up with a phi node with
1041 // identical incoming branches. This will be cleaned up later (and
1042 // will trigger asserts if we try to clean it up now, without also
1043 // simplifying the corresponding conditional branch).
1044 BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
1045 Value *PredVal = OldValPN->getIncomingValue(i);
1046 Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
1047 IncomingValues);
1048
1049 // And add a new incoming value for this predecessor for the
1050 // newly retargeted branch.
1051 PN->addIncoming(Selected, PredBB);
1052 }
1053 } else {
1054 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
1055 // Update existing incoming values in PN for this
1056 // predecessor of BB.
1057 BasicBlock *PredBB = BBPreds[i];
1058 Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
1059 IncomingValues);
1060
1061 // And add a new incoming value for this predecessor for the
1062 // newly retargeted branch.
1063 PN->addIncoming(Selected, PredBB);
1064 }
1065 }
1066
1067 replaceUndefValuesInPhi(PN, IncomingValues);
1068}
1069
1071 DomTreeUpdater *DTU) {
1072 assert(BB != &BB->getParent()->getEntryBlock() &&
1073 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
1074
1075 // We can't eliminate infinite loops.
1076 BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
1077 if (BB == Succ) return false;
1078
1079 // Check to see if merging these blocks would cause conflicts for any of the
1080 // phi nodes in BB or Succ. If not, we can safely merge.
1081 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
1082
1083 // Check for cases where Succ has multiple predecessors and a PHI node in BB
1084 // has uses which will not disappear when the PHI nodes are merged. It is
1085 // possible to handle such cases, but difficult: it requires checking whether
1086 // BB dominates Succ, which is non-trivial to calculate in the case where
1087 // Succ has multiple predecessors. Also, it requires checking whether
1088 // constructing the necessary self-referential PHI node doesn't introduce any
1089 // conflicts; this isn't too difficult, but the previous code for doing this
1090 // was incorrect.
1091 //
1092 // Note that if this check finds a live use, BB dominates Succ, so BB is
1093 // something like a loop pre-header (or rarely, a part of an irreducible CFG);
1094 // folding the branch isn't profitable in that case anyway.
1095 if (!Succ->getSinglePredecessor()) {
1096 BasicBlock::iterator BBI = BB->begin();
1097 while (isa<PHINode>(*BBI)) {
1098 for (Use &U : BBI->uses()) {
1099 if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
1100 if (PN->getIncomingBlock(U) != BB)
1101 return false;
1102 } else {
1103 return false;
1104 }
1105 }
1106 ++BBI;
1107 }
1108 }
1109
1110 // 'BB' and 'BB->Pred' are loop latches, bail out to presrve inner loop
1111 // metadata.
1112 //
1113 // FIXME: This is a stop-gap solution to preserve inner-loop metadata given
1114 // current status (that loop metadata is implemented as metadata attached to
1115 // the branch instruction in the loop latch block). To quote from review
1116 // comments, "the current representation of loop metadata (using a loop latch
1117 // terminator attachment) is known to be fundamentally broken. Loop latches
1118 // are not uniquely associated with loops (both in that a latch can be part of
1119 // multiple loops and a loop may have multiple latches). Loop headers are. The
1120 // solution to this problem is also known: Add support for basic block
1121 // metadata, and attach loop metadata to the loop header."
1122 //
1123 // Why bail out:
1124 // In this case, we expect 'BB' is the latch for outer-loop and 'BB->Pred' is
1125 // the latch for inner-loop (see reason below), so bail out to prerserve
1126 // inner-loop metadata rather than eliminating 'BB' and attaching its metadata
1127 // to this inner-loop.
1128 // - The reason we believe 'BB' and 'BB->Pred' have different inner-most
1129 // loops: assuming 'BB' and 'BB->Pred' are from the same inner-most loop L,
1130 // then 'BB' is the header and latch of 'L' and thereby 'L' must consist of
1131 // one self-looping basic block, which is contradictory with the assumption.
1132 //
1133 // To illustrate how inner-loop metadata is dropped:
1134 //
1135 // CFG Before
1136 //
1137 // BB is while.cond.exit, attached with loop metdata md2.
1138 // BB->Pred is for.body, attached with loop metadata md1.
1139 //
1140 // entry
1141 // |
1142 // v
1143 // ---> while.cond -------------> while.end
1144 // | |
1145 // | v
1146 // | while.body
1147 // | |
1148 // | v
1149 // | for.body <---- (md1)
1150 // | | |______|
1151 // | v
1152 // | while.cond.exit (md2)
1153 // | |
1154 // |_______|
1155 //
1156 // CFG After
1157 //
1158 // while.cond1 is the merge of while.cond.exit and while.cond above.
1159 // for.body is attached with md2, and md1 is dropped.
1160 // If LoopSimplify runs later (as a part of loop pass), it could create
1161 // dedicated exits for inner-loop (essentially adding `while.cond.exit`
1162 // back), but won't it won't see 'md1' nor restore it for the inner-loop.
1163 //
1164 // entry
1165 // |
1166 // v
1167 // ---> while.cond1 -------------> while.end
1168 // | |
1169 // | v
1170 // | while.body
1171 // | |
1172 // | v
1173 // | for.body <---- (md2)
1174 // |_______| |______|
1175 if (Instruction *TI = BB->getTerminator())
1176 if (TI->hasMetadata(LLVMContext::MD_loop))
1177 for (BasicBlock *Pred : predecessors(BB))
1178 if (Instruction *PredTI = Pred->getTerminator())
1179 if (PredTI->hasMetadata(LLVMContext::MD_loop))
1180 return false;
1181
1182 LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
1183
1185 if (DTU) {
1186 // To avoid processing the same predecessor more than once.
1188 // All predecessors of BB will be moved to Succ.
1189 SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ));
1190 Updates.reserve(Updates.size() + 2 * pred_size(BB) + 1);
1191 for (auto *PredOfBB : predecessors(BB))
1192 // This predecessor of BB may already have Succ as a successor.
1193 if (!PredsOfSucc.contains(PredOfBB))
1194 if (SeenPreds.insert(PredOfBB).second)
1195 Updates.push_back({DominatorTree::Insert, PredOfBB, Succ});
1196 SeenPreds.clear();
1197 for (auto *PredOfBB : predecessors(BB))
1198 if (SeenPreds.insert(PredOfBB).second)
1199 Updates.push_back({DominatorTree::Delete, PredOfBB, BB});
1200 Updates.push_back({DominatorTree::Delete, BB, Succ});
1201 }
1202
1203 if (isa<PHINode>(Succ->begin())) {
1204 // If there is more than one pred of succ, and there are PHI nodes in
1205 // the successor, then we need to add incoming edges for the PHI nodes
1206 //
1207 const PredBlockVector BBPreds(predecessors(BB));
1208
1209 // Loop over all of the PHI nodes in the successor of BB.
1210 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
1211 PHINode *PN = cast<PHINode>(I);
1212
1213 redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
1214 }
1215 }
1216
1217 if (Succ->getSinglePredecessor()) {
1218 // BB is the only predecessor of Succ, so Succ will end up with exactly
1219 // the same predecessors BB had.
1220
1221 // Copy over any phi, debug or lifetime instruction.
1223 Succ->splice(Succ->getFirstNonPHI()->getIterator(), BB);
1224 } else {
1225 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
1226 // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
1227 assert(PN->use_empty() && "There shouldn't be any uses here!");
1228 PN->eraseFromParent();
1229 }
1230 }
1231
1232 // If the unconditional branch we replaced contains llvm.loop metadata, we
1233 // add the metadata to the branch instructions in the predecessors.
1234 unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
1235 Instruction *TI = BB->getTerminator();
1236 if (TI)
1237 if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
1238 for (BasicBlock *Pred : predecessors(BB))
1239 Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
1240
1241 // Everything that jumped to BB now goes to Succ.
1242 BB->replaceAllUsesWith(Succ);
1243 if (!Succ->hasName()) Succ->takeName(BB);
1244
1245 // Clear the successor list of BB to match updates applying to DTU later.
1246 if (BB->getTerminator())
1247 BB->back().eraseFromParent();
1248 new UnreachableInst(BB->getContext(), BB);
1249 assert(succ_empty(BB) && "The successor list of BB isn't empty before "
1250 "applying corresponding DTU updates.");
1251
1252 if (DTU)
1253 DTU->applyUpdates(Updates);
1254
1255 DeleteDeadBlock(BB, DTU);
1256
1257 return true;
1258}
1259
1261 // This implementation doesn't currently consider undef operands
1262 // specially. Theoretically, two phis which are identical except for
1263 // one having an undef where the other doesn't could be collapsed.
1264
1265 bool Changed = false;
1266
1267 // Examine each PHI.
1268 // Note that increment of I must *NOT* be in the iteration_expression, since
1269 // we don't want to immediately advance when we restart from the beginning.
1270 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) {
1271 ++I;
1272 // Is there an identical PHI node in this basic block?
1273 // Note that we only look in the upper square's triangle,
1274 // we already checked that the lower triangle PHI's aren't identical.
1275 for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
1276 if (!DuplicatePN->isIdenticalToWhenDefined(PN))
1277 continue;
1278 // A duplicate. Replace this PHI with the base PHI.
1279 ++NumPHICSEs;
1280 DuplicatePN->replaceAllUsesWith(PN);
1281 DuplicatePN->eraseFromParent();
1282 Changed = true;
1283
1284 // The RAUW can change PHIs that we already visited.
1285 I = BB->begin();
1286 break; // Start over from the beginning.
1287 }
1288 }
1289 return Changed;
1290}
1291
1293 // This implementation doesn't currently consider undef operands
1294 // specially. Theoretically, two phis which are identical except for
1295 // one having an undef where the other doesn't could be collapsed.
1296
1297 struct PHIDenseMapInfo {
1298 static PHINode *getEmptyKey() {
1300 }
1301
1302 static PHINode *getTombstoneKey() {
1304 }
1305
1306 static bool isSentinel(PHINode *PN) {
1307 return PN == getEmptyKey() || PN == getTombstoneKey();
1308 }
1309
1310 // WARNING: this logic must be kept in sync with
1311 // Instruction::isIdenticalToWhenDefined()!
1312 static unsigned getHashValueImpl(PHINode *PN) {
1313 // Compute a hash value on the operands. Instcombine will likely have
1314 // sorted them, which helps expose duplicates, but we have to check all
1315 // the operands to be safe in case instcombine hasn't run.
1316 return static_cast<unsigned>(hash_combine(
1319 }
1320
1321 static unsigned getHashValue(PHINode *PN) {
1322#ifndef NDEBUG
1323 // If -phicse-debug-hash was specified, return a constant -- this
1324 // will force all hashing to collide, so we'll exhaustively search
1325 // the table for a match, and the assertion in isEqual will fire if
1326 // there's a bug causing equal keys to hash differently.
1327 if (PHICSEDebugHash)
1328 return 0;
1329#endif
1330 return getHashValueImpl(PN);
1331 }
1332
1333 static bool isEqualImpl(PHINode *LHS, PHINode *RHS) {
1334 if (isSentinel(LHS) || isSentinel(RHS))
1335 return LHS == RHS;
1336 return LHS->isIdenticalTo(RHS);
1337 }
1338
1339 static bool isEqual(PHINode *LHS, PHINode *RHS) {
1340 // These comparisons are nontrivial, so assert that equality implies
1341 // hash equality (DenseMap demands this as an invariant).
1342 bool Result = isEqualImpl(LHS, RHS);
1343 assert(!Result || (isSentinel(LHS) && LHS == RHS) ||
1345 return Result;
1346 }
1347 };
1348
1349 // Set of unique PHINodes.
1351 PHISet.reserve(4 * PHICSENumPHISmallSize);
1352
1353 // Examine each PHI.
1354 bool Changed = false;
1355 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
1356 auto Inserted = PHISet.insert(PN);
1357 if (!Inserted.second) {
1358 // A duplicate. Replace this PHI with its duplicate.
1359 ++NumPHICSEs;
1360 PN->replaceAllUsesWith(*Inserted.first);
1361 PN->eraseFromParent();
1362 Changed = true;
1363
1364 // The RAUW can change PHIs that we already visited. Start over from the
1365 // beginning.
1366 PHISet.clear();
1367 I = BB->begin();
1368 }
1369 }
1370
1371 return Changed;
1372}
1373
1375 if (
1376#ifndef NDEBUG
1377 !PHICSEDebugHash &&
1378#endif
1382}
1383
1384/// If the specified pointer points to an object that we control, try to modify
1385/// the object's alignment to PrefAlign. Returns a minimum known alignment of
1386/// the value after the operation, which may be lower than PrefAlign.
1387///
1388/// Increating value alignment isn't often possible though. If alignment is
1389/// important, a more reliable approach is to simply align all global variables
1390/// and allocation instructions to their preferred alignment from the beginning.
1392 const DataLayout &DL) {
1393 V = V->stripPointerCasts();
1394
1395 if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1396 // TODO: Ideally, this function would not be called if PrefAlign is smaller
1397 // than the current alignment, as the known bits calculation should have
1398 // already taken it into account. However, this is not always the case,
1399 // as computeKnownBits() has a depth limit, while stripPointerCasts()
1400 // doesn't.
1401 Align CurrentAlign = AI->getAlign();
1402 if (PrefAlign <= CurrentAlign)
1403 return CurrentAlign;
1404
1405 // If the preferred alignment is greater than the natural stack alignment
1406 // then don't round up. This avoids dynamic stack realignment.
1407 if (DL.exceedsNaturalStackAlignment(PrefAlign))
1408 return CurrentAlign;
1409 AI->setAlignment(PrefAlign);
1410 return PrefAlign;
1411 }
1412
1413 if (auto *GO = dyn_cast<GlobalObject>(V)) {
1414 // TODO: as above, this shouldn't be necessary.
1415 Align CurrentAlign = GO->getPointerAlignment(DL);
1416 if (PrefAlign <= CurrentAlign)
1417 return CurrentAlign;
1418
1419 // If there is a large requested alignment and we can, bump up the alignment
1420 // of the global. If the memory we set aside for the global may not be the
1421 // memory used by the final program then it is impossible for us to reliably
1422 // enforce the preferred alignment.
1423 if (!GO->canIncreaseAlignment())
1424 return CurrentAlign;
1425
1426 if (GO->isThreadLocal()) {
1427 unsigned MaxTLSAlign = GO->getParent()->getMaxTLSAlignment() / CHAR_BIT;
1428 if (MaxTLSAlign && PrefAlign > Align(MaxTLSAlign))
1429 PrefAlign = Align(MaxTLSAlign);
1430 }
1431
1432 GO->setAlignment(PrefAlign);
1433 return PrefAlign;
1434 }
1435
1436 return Align(1);
1437}
1438
1440 const DataLayout &DL,
1441 const Instruction *CxtI,
1442 AssumptionCache *AC,
1443 const DominatorTree *DT) {
1444 assert(V->getType()->isPointerTy() &&
1445 "getOrEnforceKnownAlignment expects a pointer!");
1446
1447 KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT);
1448 unsigned TrailZ = Known.countMinTrailingZeros();
1449
1450 // Avoid trouble with ridiculously large TrailZ values, such as
1451 // those computed from a null pointer.
1452 // LLVM doesn't support alignments larger than (1 << MaxAlignmentExponent).
1453 TrailZ = std::min(TrailZ, +Value::MaxAlignmentExponent);
1454
1455 Align Alignment = Align(1ull << std::min(Known.getBitWidth() - 1, TrailZ));
1456
1457 if (PrefAlign && *PrefAlign > Alignment)
1458 Alignment = std::max(Alignment, tryEnforceAlignment(V, *PrefAlign, DL));
1459
1460 // We don't need to make any adjustment.
1461 return Alignment;
1462}
1463
1464///===---------------------------------------------------------------------===//
1465/// Dbg Intrinsic utilities
1466///
1467
1468/// See if there is a dbg.value intrinsic for DIVar for the PHI node.
1470 DIExpression *DIExpr,
1471 PHINode *APN) {
1472 // Since we can't guarantee that the original dbg.declare intrinsic
1473 // is removed by LowerDbgDeclare(), we need to make sure that we are
1474 // not inserting the same dbg.value intrinsic over and over.
1476 findDbgValues(DbgValues, APN);
1477 for (auto *DVI : DbgValues) {
1478 assert(is_contained(DVI->getValues(), APN));
1479 if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1480 return true;
1481 }
1482 return false;
1483}
1484
1485/// Check if the alloc size of \p ValTy is large enough to cover the variable
1486/// (or fragment of the variable) described by \p DII.
1487///
1488/// This is primarily intended as a helper for the different
1489/// ConvertDebugDeclareToDebugValue functions. The dbg.declare that is converted
1490/// describes an alloca'd variable, so we need to use the alloc size of the
1491/// value when doing the comparison. E.g. an i1 value will be identified as
1492/// covering an n-bit fragment, if the store size of i1 is at least n bits.
1494 const DataLayout &DL = DII->getModule()->getDataLayout();
1495 TypeSize ValueSize = DL.getTypeAllocSizeInBits(ValTy);
1496 if (std::optional<uint64_t> FragmentSize = DII->getFragmentSizeInBits())
1497 return TypeSize::isKnownGE(ValueSize, TypeSize::getFixed(*FragmentSize));
1498
1499 // We can't always calculate the size of the DI variable (e.g. if it is a
1500 // VLA). Try to use the size of the alloca that the dbg intrinsic describes
1501 // intead.
1502 if (DII->isAddressOfVariable()) {
1503 // DII should have exactly 1 location when it is an address.
1504 assert(DII->getNumVariableLocationOps() == 1 &&
1505 "address of variable must have exactly 1 location operand.");
1506 if (auto *AI =
1507 dyn_cast_or_null<AllocaInst>(DII->getVariableLocationOp(0))) {
1508 if (std::optional<TypeSize> FragmentSize =
1509 AI->getAllocationSizeInBits(DL)) {
1510 return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1511 }
1512 }
1513 }
1514 // Could not determine size of variable. Conservatively return false.
1515 return false;
1516}
1517
1518/// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1519/// that has an associated llvm.dbg.declare intrinsic.
1521 StoreInst *SI, DIBuilder &Builder) {
1522 assert(DII->isAddressOfVariable() || isa<DbgAssignIntrinsic>(DII));
1523 auto *DIVar = DII->getVariable();
1524 assert(DIVar && "Missing variable");
1525 auto *DIExpr = DII->getExpression();
1526 Value *DV = SI->getValueOperand();
1527
1528 DebugLoc NewLoc = getDebugValueLoc(DII);
1529
1530 // If the alloca describes the variable itself, i.e. the expression in the
1531 // dbg.declare doesn't start with a dereference, we can perform the
1532 // conversion if the value covers the entire fragment of DII.
1533 // If the alloca describes the *address* of DIVar, i.e. DIExpr is
1534 // *just* a DW_OP_deref, we use DV as is for the dbg.value.
1535 // We conservatively ignore other dereferences, because the following two are
1536 // not equivalent:
1537 // dbg.declare(alloca, ..., !Expr(deref, plus_uconstant, 2))
1538 // dbg.value(DV, ..., !Expr(deref, plus_uconstant, 2))
1539 // The former is adding 2 to the address of the variable, whereas the latter
1540 // is adding 2 to the value of the variable. As such, we insist on just a
1541 // deref expression.
1542 bool CanConvert =
1543 DIExpr->isDeref() || (!DIExpr->startsWithDeref() &&
1545 if (CanConvert) {
1546 Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1547 return;
1548 }
1549
1550 // FIXME: If storing to a part of the variable described by the dbg.declare,
1551 // then we want to insert a dbg.value for the corresponding fragment.
1552 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: " << *DII
1553 << '\n');
1554 // For now, when there is a store to parts of the variable (but we do not
1555 // know which part) we insert an dbg.value intrinsic to indicate that we
1556 // know nothing about the variable's content.
1557 DV = UndefValue::get(DV->getType());
1558 Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1559}
1560
1561/// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1562/// that has an associated llvm.dbg.declare intrinsic.
1564 LoadInst *LI, DIBuilder &Builder) {
1565 auto *DIVar = DII->getVariable();
1566 auto *DIExpr = DII->getExpression();
1567 assert(DIVar && "Missing variable");
1568
1569 if (!valueCoversEntireFragment(LI->getType(), DII)) {
1570 // FIXME: If only referring to a part of the variable described by the
1571 // dbg.declare, then we want to insert a dbg.value for the corresponding
1572 // fragment.
1573 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1574 << *DII << '\n');
1575 return;
1576 }
1577
1578 DebugLoc NewLoc = getDebugValueLoc(DII);
1579
1580 // We are now tracking the loaded value instead of the address. In the
1581 // future if multi-location support is added to the IR, it might be
1582 // preferable to keep tracking both the loaded value and the original
1583 // address in case the alloca can not be elided.
1584 Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
1585 LI, DIVar, DIExpr, NewLoc, (Instruction *)nullptr);
1586 DbgValue->insertAfter(LI);
1587}
1588
1589/// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
1590/// llvm.dbg.declare intrinsic.
1592 PHINode *APN, DIBuilder &Builder) {
1593 auto *DIVar = DII->getVariable();
1594 auto *DIExpr = DII->getExpression();
1595 assert(DIVar && "Missing variable");
1596
1597 if (PhiHasDebugValue(DIVar, DIExpr, APN))
1598 return;
1599
1600 if (!valueCoversEntireFragment(APN->getType(), DII)) {
1601 // FIXME: If only referring to a part of the variable described by the
1602 // dbg.declare, then we want to insert a dbg.value for the corresponding
1603 // fragment.
1604 LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1605 << *DII << '\n');
1606 return;
1607 }
1608
1609 BasicBlock *BB = APN->getParent();
1610 auto InsertionPt = BB->getFirstInsertionPt();
1611
1612 DebugLoc NewLoc = getDebugValueLoc(DII);
1613
1614 // The block may be a catchswitch block, which does not have a valid
1615 // insertion point.
1616 // FIXME: Insert dbg.value markers in the successors when appropriate.
1617 if (InsertionPt != BB->end())
1618 Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, NewLoc, &*InsertionPt);
1619}
1620
1621/// Determine whether this alloca is either a VLA or an array.
1622static bool isArray(AllocaInst *AI) {
1623 return AI->isArrayAllocation() ||
1624 (AI->getAllocatedType() && AI->getAllocatedType()->isArrayTy());
1625}
1626
1627/// Determine whether this alloca is a structure.
1628static bool isStructure(AllocaInst *AI) {
1629 return AI->getAllocatedType() && AI->getAllocatedType()->isStructTy();
1630}
1631
1632/// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1633/// of llvm.dbg.value intrinsics.
1635 bool Changed = false;
1636 DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1638 for (auto &FI : F)
1639 for (Instruction &BI : FI)
1640 if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
1641 Dbgs.push_back(DDI);
1642
1643 if (Dbgs.empty())
1644 return Changed;
1645
1646 for (auto &I : Dbgs) {
1647 DbgDeclareInst *DDI = I;
1648 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1649 // If this is an alloca for a scalar variable, insert a dbg.value
1650 // at each load and store to the alloca and erase the dbg.declare.
1651 // The dbg.values allow tracking a variable even if it is not
1652 // stored on the stack, while the dbg.declare can only describe
1653 // the stack slot (and at a lexical-scope granularity). Later
1654 // passes will attempt to elide the stack slot.
1655 if (!AI || isArray(AI) || isStructure(AI))
1656 continue;
1657
1658 // A volatile load/store means that the alloca can't be elided anyway.
1659 if (llvm::any_of(AI->users(), [](User *U) -> bool {
1660 if (LoadInst *LI = dyn_cast<LoadInst>(U))
1661 return LI->isVolatile();
1662 if (StoreInst *SI = dyn_cast<StoreInst>(U))
1663 return SI->isVolatile();
1664 return false;
1665 }))
1666 continue;
1667
1669 WorkList.push_back(AI);
1670 while (!WorkList.empty()) {
1671 const Value *V = WorkList.pop_back_val();
1672 for (const auto &AIUse : V->uses()) {
1673 User *U = AIUse.getUser();
1674 if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1675 if (AIUse.getOperandNo() == 1)
1677 } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1678 ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1679 } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1680 // This is a call by-value or some other instruction that takes a
1681 // pointer to the variable. Insert a *value* intrinsic that describes
1682 // the variable by dereferencing the alloca.
1683 if (!CI->isLifetimeStartOrEnd()) {
1684 DebugLoc NewLoc = getDebugValueLoc(DDI);
1685 auto *DerefExpr =
1686 DIExpression::append(DDI->getExpression(), dwarf::DW_OP_deref);
1687 DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DerefExpr,
1688 NewLoc, CI);
1689 }
1690 } else if (BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
1691 if (BI->getType()->isPointerTy())
1692 WorkList.push_back(BI);
1693 }
1694 }
1695 }
1696 DDI->eraseFromParent();
1697 Changed = true;
1698 }
1699
1700 if (Changed)
1701 for (BasicBlock &BB : F)
1703
1704 return Changed;
1705}
1706
1707/// Propagate dbg.value intrinsics through the newly inserted PHIs.
1709 SmallVectorImpl<PHINode *> &InsertedPHIs) {
1710 assert(BB && "No BasicBlock to clone dbg.value(s) from.");
1711 if (InsertedPHIs.size() == 0)
1712 return;
1713
1714 // Map existing PHI nodes to their dbg.values.
1715 ValueToValueMapTy DbgValueMap;
1716 for (auto &I : *BB) {
1717 if (auto DbgII = dyn_cast<DbgVariableIntrinsic>(&I)) {
1718 for (Value *V : DbgII->location_ops())
1719 if (auto *Loc = dyn_cast_or_null<PHINode>(V))
1720 DbgValueMap.insert({Loc, DbgII});
1721 }
1722 }
1723 if (DbgValueMap.size() == 0)
1724 return;
1725
1726 // Map a pair of the destination BB and old dbg.value to the new dbg.value,
1727 // so that if a dbg.value is being rewritten to use more than one of the
1728 // inserted PHIs in the same destination BB, we can update the same dbg.value
1729 // with all the new PHIs instead of creating one copy for each.
1732 NewDbgValueMap;
1733 // Then iterate through the new PHIs and look to see if they use one of the
1734 // previously mapped PHIs. If so, create a new dbg.value intrinsic that will
1735 // propagate the info through the new PHI. If we use more than one new PHI in
1736 // a single destination BB with the same old dbg.value, merge the updates so
1737 // that we get a single new dbg.value with all the new PHIs.
1738 for (auto *PHI : InsertedPHIs) {
1739 BasicBlock *Parent = PHI->getParent();
1740 // Avoid inserting an intrinsic into an EH block.
1741 if (Parent->getFirstNonPHI()->isEHPad())
1742 continue;
1743 for (auto *VI : PHI->operand_values()) {
1744 auto V = DbgValueMap.find(VI);
1745 if (V != DbgValueMap.end()) {
1746 auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
1747 auto NewDI = NewDbgValueMap.find({Parent, DbgII});
1748 if (NewDI == NewDbgValueMap.end()) {
1749 auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone());
1750 NewDI = NewDbgValueMap.insert({{Parent, DbgII}, NewDbgII}).first;
1751 }
1752 DbgVariableIntrinsic *NewDbgII = NewDI->second;
1753 // If PHI contains VI as an operand more than once, we may
1754 // replaced it in NewDbgII; confirm that it is present.
1755 if (is_contained(NewDbgII->location_ops(), VI))
1756 NewDbgII->replaceVariableLocationOp(VI, PHI);
1757 }
1758 }
1759 }
1760 // Insert thew new dbg.values into their destination blocks.
1761 for (auto DI : NewDbgValueMap) {
1762 BasicBlock *Parent = DI.first.first;
1763 auto *NewDbgII = DI.second;
1764 auto InsertionPt = Parent->getFirstInsertionPt();
1765 assert(InsertionPt != Parent->end() && "Ill-formed basic block");
1766 NewDbgII->insertBefore(&*InsertionPt);
1767 }
1768}
1769
1770bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress,
1771 DIBuilder &Builder, uint8_t DIExprFlags,
1772 int Offset) {
1773 auto DbgDeclares = FindDbgDeclareUses(Address);
1774 for (DbgVariableIntrinsic *DII : DbgDeclares) {
1775 const DebugLoc &Loc = DII->getDebugLoc();
1776 auto *DIVar = DII->getVariable();
1777 auto *DIExpr = DII->getExpression();
1778 assert(DIVar && "Missing variable");
1779 DIExpr = DIExpression::prepend(DIExpr, DIExprFlags, Offset);
1780 // Insert llvm.dbg.declare immediately before DII, and remove old
1781 // llvm.dbg.declare.
1782 Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, DII);
1783 DII->eraseFromParent();
1784 }
1785 return !DbgDeclares.empty();
1786}
1787
1788static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
1789 DIBuilder &Builder, int Offset) {
1790 const DebugLoc &Loc = DVI->getDebugLoc();
1791 auto *DIVar = DVI->getVariable();
1792 auto *DIExpr = DVI->getExpression();
1793 assert(DIVar && "Missing variable");
1794
1795 // This is an alloca-based llvm.dbg.value. The first thing it should do with
1796 // the alloca pointer is dereference it. Otherwise we don't know how to handle
1797 // it and give up.
1798 if (!DIExpr || DIExpr->getNumElements() < 1 ||
1799 DIExpr->getElement(0) != dwarf::DW_OP_deref)
1800 return;
1801
1802 // Insert the offset before the first deref.
1803 // We could just change the offset argument of dbg.value, but it's unsigned...
1804 if (Offset)
1805 DIExpr = DIExpression::prepend(DIExpr, 0, Offset);
1806
1807 Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI);
1808 DVI->eraseFromParent();
1809}
1810
1812 DIBuilder &Builder, int Offset) {
1813 if (auto *L = LocalAsMetadata::getIfExists(AI))
1814 if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
1815 for (Use &U : llvm::make_early_inc_range(MDV->uses()))
1816 if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
1817 replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1818}
1819
1820/// Where possible to salvage debug information for \p I do so.
1821/// If not possible mark undef.
1824 findDbgUsers(DbgUsers, &I);
1826}
1827
1828/// Salvage the address component of \p DAI.
1830 Instruction *I = dyn_cast<Instruction>(DAI->getAddress());
1831 // Only instructions can be salvaged at the moment.
1832 if (!I)
1833 return;
1834
1835 assert(!DAI->getAddressExpression()->getFragmentInfo().has_value() &&
1836 "address-expression shouldn't have fragment info");
1837
1838 // The address component of a dbg.assign cannot be variadic.
1839 uint64_t CurrentLocOps = 0;
1840 SmallVector<Value *, 4> AdditionalValues;
1842 Value *NewV = salvageDebugInfoImpl(*I, CurrentLocOps, Ops, AdditionalValues);
1843
1844 // Check if the salvage failed.
1845 if (!NewV)
1846 return;
1847
1849 DAI->getAddressExpression(), Ops, 0, /*StackValue=*/false);
1850 assert(!SalvagedExpr->getFragmentInfo().has_value() &&
1851 "address-expression shouldn't have fragment info");
1852
1853 // Salvage succeeds if no additional values are required.
1854 if (AdditionalValues.empty()) {
1855 DAI->setAddress(NewV);
1856 DAI->setAddressExpression(SalvagedExpr);
1857 } else {
1858 DAI->setKillAddress();
1859 }
1860}
1861
1864 // These are arbitrary chosen limits on the maximum number of values and the
1865 // maximum size of a debug expression we can salvage up to, used for
1866 // performance reasons.
1867 const unsigned MaxDebugArgs = 16;
1868 const unsigned MaxExpressionSize = 128;
1869 bool Salvaged = false;
1870
1871 for (auto *DII : DbgUsers) {
1872 if (auto *DAI = dyn_cast<DbgAssignIntrinsic>(DII)) {
1873 if (DAI->getAddress() == &I) {
1875 Salvaged = true;
1876 }
1877 if (DAI->getValue() != &I)
1878 continue;
1879 }
1880
1881 // Do not add DW_OP_stack_value for DbgDeclare, because they are implicitly
1882 // pointing out the value as a DWARF memory location description.
1883 bool StackValue = isa<DbgValueInst>(DII);
1884 auto DIILocation = DII->location_ops();
1885 assert(
1886 is_contained(DIILocation, &I) &&
1887 "DbgVariableIntrinsic must use salvaged instruction as its location");
1888 SmallVector<Value *, 4> AdditionalValues;
1889 // `I` may appear more than once in DII's location ops, and each use of `I`
1890 // must be updated in the DIExpression and potentially have additional
1891 // values added; thus we call salvageDebugInfoImpl for each `I` instance in
1892 // DIILocation.
1893 Value *Op0 = nullptr;
1894 DIExpression *SalvagedExpr = DII->getExpression();
1895 auto LocItr = find(DIILocation, &I);
1896 while (SalvagedExpr && LocItr != DIILocation.end()) {
1898 unsigned LocNo = std::distance(DIILocation.begin(), LocItr);
1899 uint64_t CurrentLocOps = SalvagedExpr->getNumLocationOperands();
1900 Op0 = salvageDebugInfoImpl(I, CurrentLocOps, Ops, AdditionalValues);
1901 if (!Op0)
1902 break;
1903 SalvagedExpr =
1904 DIExpression::appendOpsToArg(SalvagedExpr, Ops, LocNo, StackValue);
1905 LocItr = std::find(++LocItr, DIILocation.end(), &I);
1906 }
1907 // salvageDebugInfoImpl should fail on examining the first element of
1908 // DbgUsers, or none of them.
1909 if (!Op0)
1910 break;
1911
1912 DII->replaceVariableLocationOp(&I, Op0);
1913 bool IsValidSalvageExpr = SalvagedExpr->getNumElements() <= MaxExpressionSize;
1914 if (AdditionalValues.empty() && IsValidSalvageExpr) {
1915 DII->setExpression(SalvagedExpr);
1916 } else if (isa<DbgValueInst>(DII) && IsValidSalvageExpr &&
1917 DII->getNumVariableLocationOps() + AdditionalValues.size() <=
1918 MaxDebugArgs) {
1919 DII->addVariableLocationOps(AdditionalValues, SalvagedExpr);
1920 } else {
1921 // Do not salvage using DIArgList for dbg.declare, as it is not currently
1922 // supported in those instructions. Also do not salvage if the resulting
1923 // DIArgList would contain an unreasonably large number of values.
1924 DII->setKillLocation();
1925 }
1926 LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
1927 Salvaged = true;
1928 }
1929
1930 if (Salvaged)
1931 return;
1932
1933 for (auto *DII : DbgUsers)
1934 DII->setKillLocation();
1935}
1936
1938 uint64_t CurrentLocOps,
1940 SmallVectorImpl<Value *> &AdditionalValues) {
1941 unsigned BitWidth = DL.getIndexSizeInBits(GEP->getPointerAddressSpace());
1942 // Rewrite a GEP into a DIExpression.
1943 MapVector<Value *, APInt> VariableOffsets;
1944 APInt ConstantOffset(BitWidth, 0);
1945 if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
1946 return nullptr;
1947 if (!VariableOffsets.empty() && !CurrentLocOps) {
1948 Opcodes.insert(Opcodes.begin(), {dwarf::DW_OP_LLVM_arg, 0});
1949 CurrentLocOps = 1;
1950 }
1951 for (auto Offset : VariableOffsets) {
1952 AdditionalValues.push_back(Offset.first);
1953 assert(Offset.second.isStrictlyPositive() &&
1954 "Expected strictly positive multiplier for offset.");
1955 Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps++, dwarf::DW_OP_constu,
1956 Offset.second.getZExtValue(), dwarf::DW_OP_mul,
1957 dwarf::DW_OP_plus});
1958 }
1959 DIExpression::appendOffset(Opcodes, ConstantOffset.getSExtValue());
1960 return GEP->getOperand(0);
1961}
1962
1964 switch (Opcode) {
1965 case Instruction::Add:
1966 return dwarf::DW_OP_plus;
1967 case Instruction::Sub:
1968 return dwarf::DW_OP_minus;
1969 case Instruction::Mul:
1970 return dwarf::DW_OP_mul;
1971 case Instruction::SDiv:
1972 return dwarf::DW_OP_div;
1973 case Instruction::SRem:
1974 return dwarf::DW_OP_mod;
1975 case Instruction::Or:
1976 return dwarf::DW_OP_or;
1977 case Instruction::And:
1978 return dwarf::DW_OP_and;
1979 case Instruction::Xor:
1980 return dwarf::DW_OP_xor;
1981 case Instruction::Shl:
1982 return dwarf::DW_OP_shl;
1983 case Instruction::LShr:
1984 return dwarf::DW_OP_shr;
1985 case Instruction::AShr:
1986 return dwarf::DW_OP_shra;
1987 default:
1988 // TODO: Salvage from each kind of binop we know about.
1989 return 0;
1990 }
1991}
1992
1995 SmallVectorImpl<Value *> &AdditionalValues) {
1996 // Handle binary operations with constant integer operands as a special case.
1997 auto *ConstInt = dyn_cast<ConstantInt>(BI->getOperand(1));
1998 // Values wider than 64 bits cannot be represented within a DIExpression.
1999 if (ConstInt && ConstInt->getBitWidth() > 64)
2000 return nullptr;
2001
2002 Instruction::BinaryOps BinOpcode = BI->getOpcode();
2003 // Push any Constant Int operand onto the expression stack.
2004 if (ConstInt) {
2005 uint64_t Val = ConstInt->getSExtValue();
2006 // Add or Sub Instructions with a constant operand can potentially be
2007 // simplified.
2008 if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
2009 uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
2011 return BI->getOperand(0);
2012 }
2013 Opcodes.append({dwarf::DW_OP_constu, Val});
2014 } else {
2015 if (!CurrentLocOps) {
2016 Opcodes.append({dwarf::DW_OP_LLVM_arg, 0});
2017 CurrentLocOps = 1;
2018 }
2019 Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps});
2020 AdditionalValues.push_back(BI->getOperand(1));
2021 }
2022
2023 // Add salvaged binary operator to expression stack, if it has a valid
2024 // representation in a DIExpression.
2025 uint64_t DwarfBinOp = getDwarfOpForBinOp(BinOpcode);
2026 if (!DwarfBinOp)
2027 return nullptr;
2028 Opcodes.push_back(DwarfBinOp);
2029 return BI->getOperand(0);
2030}
2031
2034 SmallVectorImpl<Value *> &AdditionalValues) {
2035 auto &M = *I.getModule();
2036 auto &DL = M.getDataLayout();
2037
2038 if (auto *CI = dyn_cast<CastInst>(&I)) {
2039 Value *FromValue = CI->getOperand(0);
2040 // No-op casts are irrelevant for debug info.
2041 if (CI->isNoopCast(DL)) {
2042 return FromValue;
2043 }
2044
2045 Type *Type = CI->getType();
2046 if (Type->isPointerTy())
2047 Type = DL.getIntPtrType(Type);
2048 // Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged.
2049 if (Type->isVectorTy() ||
2050 !(isa<TruncInst>(&I) || isa<SExtInst>(&I) || isa<ZExtInst>(&I) ||
2051 isa<IntToPtrInst>(&I) || isa<PtrToIntInst>(&I)))
2052 return nullptr;
2053
2054 llvm::Type *FromType = FromValue->getType();
2055 if (FromType->isPointerTy())
2056 FromType = DL.getIntPtrType(FromType);
2057
2058 unsigned FromTypeBitSize = FromType->getScalarSizeInBits();
2059 unsigned ToTypeBitSize = Type->getScalarSizeInBits();
2060
2061 auto ExtOps = DIExpression::getExtOps(FromTypeBitSize, ToTypeBitSize,
2062 isa<SExtInst>(&I));
2063 Ops.append(ExtOps.begin(), ExtOps.end());
2064 return FromValue;
2065 }
2066
2067 if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))
2068 return getSalvageOpsForGEP(GEP, DL, CurrentLocOps, Ops, AdditionalValues);
2069 if (auto *BI = dyn_cast<BinaryOperator>(&I))
2070 return getSalvageOpsForBinOp(BI, CurrentLocOps, Ops, AdditionalValues);
2071
2072 // *Not* to do: we should not attempt to salvage load instructions,
2073 // because the validity and lifetime of a dbg.value containing
2074 // DW_OP_deref becomes difficult to analyze. See PR40628 for examples.
2075 return nullptr;
2076}
2077
2078/// A replacement for a dbg.value expression.
2079using DbgValReplacement = std::optional<DIExpression *>;
2080
2081/// Point debug users of \p From to \p To using exprs given by \p RewriteExpr,
2082/// possibly moving/undefing users to prevent use-before-def. Returns true if
2083/// changes are made.
2085 Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT,
2087 // Find debug users of From.
2090 if (Users.empty())
2091 return false;
2092
2093 // Prevent use-before-def of To.
2094 bool Changed = false;
2096 if (isa<Instruction>(&To)) {
2097 bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint;
2098
2099 for (auto *DII : Users) {
2100 // It's common to see a debug user between From and DomPoint. Move it
2101 // after DomPoint to preserve the variable update without any reordering.
2102 if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) {
2103 LLVM_DEBUG(dbgs() << "MOVE: " << *DII << '\n');
2104 DII->moveAfter(&DomPoint);
2105 Changed = true;
2106
2107 // Users which otherwise aren't dominated by the replacement value must
2108 // be salvaged or deleted.
2109 } else if (!DT.dominates(&DomPoint, DII)) {
2110 UndefOrSalvage.insert(DII);
2111 }
2112 }
2113 }
2114
2115 // Update debug users without use-before-def risk.
2116 for (auto *DII : Users) {
2117 if (UndefOrSalvage.count(DII))
2118 continue;
2119
2120 DbgValReplacement DVR = RewriteExpr(*DII);
2121 if (!DVR)
2122 continue;
2123
2124 DII->replaceVariableLocationOp(&From, &To);
2125 DII->setExpression(*DVR);
2126 LLVM_DEBUG(dbgs() << "REWRITE: " << *DII << '\n');
2127 Changed = true;
2128 }
2129
2130 if (!UndefOrSalvage.empty()) {
2131 // Try to salvage the remaining debug users.
2133 Changed = true;
2134 }
2135
2136 return Changed;
2137}
2138
2139/// Check if a bitcast between a value of type \p FromTy to type \p ToTy would
2140/// losslessly preserve the bits and semantics of the value. This predicate is
2141/// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result.
2142///
2143/// Note that Type::canLosslesslyBitCastTo is not suitable here because it
2144/// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>,
2145/// and also does not allow lossless pointer <-> integer conversions.
2147 Type *ToTy) {
2148 // Trivially compatible types.
2149 if (FromTy == ToTy)
2150 return true;
2151
2152 // Handle compatible pointer <-> integer conversions.
2153 if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) {
2154 bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy);
2155 bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) &&
2156 !DL.isNonIntegralPointerType(ToTy);
2157 return SameSize && LosslessConversion;
2158 }
2159
2160 // TODO: This is not exhaustive.
2161 return false;
2162}
2163
2165 Instruction &DomPoint, DominatorTree &DT) {
2166 // Exit early if From has no debug users.
2167 if (!From.isUsedByMetadata())
2168 return false;
2169
2170 assert(&From != &To && "Can't replace something with itself");
2171
2172 Type *FromTy = From.getType();
2173 Type *ToTy = To.getType();
2174
2175 auto Identity = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
2176 return DII.getExpression();
2177 };
2178
2179 // Handle no-op conversions.
2180 Module &M = *From.getModule();
2181 const DataLayout &DL = M.getDataLayout();
2182 if (isBitCastSemanticsPreserving(DL, FromTy, ToTy))
2183 return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
2184
2185 // Handle integer-to-integer widening and narrowing.
2186 // FIXME: Use DW_OP_convert when it's available everywhere.
2187 if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) {
2188 uint64_t FromBits = FromTy->getPrimitiveSizeInBits();
2189 uint64_t ToBits = ToTy->getPrimitiveSizeInBits();
2190 assert(FromBits != ToBits && "Unexpected no-op conversion");
2191
2192 // When the width of the result grows, assume that a debugger will only
2193 // access the low `FromBits` bits when inspecting the source variable.
2194 if (FromBits < ToBits)
2195 return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
2196
2197 // The width of the result has shrunk. Use sign/zero extension to describe
2198 // the source variable's high bits.
2199 auto SignOrZeroExt = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
2200 DILocalVariable *Var = DII.getVariable();
2201
2202 // Without knowing signedness, sign/zero extension isn't possible.
2203 auto Signedness = Var->getSignedness();
2204 if (!Signedness)
2205 return std::nullopt;
2206
2207 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2208 return DIExpression::appendExt(DII.getExpression(), ToBits, FromBits,
2209 Signed);
2210 };
2211 return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt);
2212 }
2213
2214 // TODO: Floating-point conversions, vectors.
2215 return false;
2216}
2217
2218std::pair<unsigned, unsigned>
2220 unsigned NumDeadInst = 0;
2221 unsigned NumDeadDbgInst = 0;
2222 // Delete the instructions backwards, as it has a reduced likelihood of
2223 // having to update as many def-use and use-def chains.
2224 Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
2225 while (EndInst != &BB->front()) {
2226 // Delete the next to last instruction.
2227 Instruction *Inst = &*--EndInst->getIterator();
2228 if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
2230 if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
2231 EndInst = Inst;
2232 continue;
2233 }
2234 if (isa<DbgInfoIntrinsic>(Inst))
2235 ++NumDeadDbgInst;
2236 else
2237 ++NumDeadInst;
2238 Inst->eraseFromParent();
2239 }
2240 return {NumDeadInst, NumDeadDbgInst};
2241}
2242
2243unsigned llvm::changeToUnreachable(Instruction *I, bool PreserveLCSSA,
2244 DomTreeUpdater *DTU,
2245 MemorySSAUpdater *MSSAU) {
2246 BasicBlock *BB = I->getParent();
2247
2248 if (MSSAU)
2249 MSSAU->changeToUnreachable(I);
2250
2251 SmallSet<BasicBlock *, 8> UniqueSuccessors;
2252
2253 // Loop over all of the successors, removing BB's entry from any PHI
2254 // nodes.
2255 for (BasicBlock *Successor : successors(BB)) {
2256 Successor->removePredecessor(BB, PreserveLCSSA);
2257 if (DTU)
2258 UniqueSuccessors.insert(Successor);
2259 }
2260 auto *UI = new UnreachableInst(I->getContext(), I);
2261 UI->setDebugLoc(I->getDebugLoc());
2262
2263 // All instructions after this are dead.
2264 unsigned NumInstrsRemoved = 0;
2265 BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
2266 while (BBI != BBE) {
2267 if (!BBI->use_empty())
2268 BBI->replaceAllUsesWith(PoisonValue::get(BBI->getType()));
2269 BBI++->eraseFromParent();
2270 ++NumInstrsRemoved;
2271 }
2272 if (DTU) {
2274 Updates.reserve(UniqueSuccessors.size());
2275 for (BasicBlock *UniqueSuccessor : UniqueSuccessors)
2276 Updates.push_back({DominatorTree::Delete, BB, UniqueSuccessor});
2277 DTU->applyUpdates(Updates);
2278 }
2279 return NumInstrsRemoved;
2280}
2281
2283 SmallVector<Value *, 8> Args(II->args());
2285 II->getOperandBundlesAsDefs(OpBundles);
2286 CallInst *NewCall = CallInst::Create(II->getFunctionType(),
2287 II->getCalledOperand(), Args, OpBundles);
2288 NewCall->setCallingConv(II->getCallingConv());
2289 NewCall->setAttributes(II->getAttributes());
2290 NewCall->setDebugLoc(II->getDebugLoc());
2291 NewCall->copyMetadata(*II);
2292
2293 // If the invoke had profile metadata, try converting them for CallInst.
2294 uint64_t TotalWeight;
2295 if (NewCall->extractProfTotalWeight(TotalWeight)) {
2296 // Set the total weight if it fits into i32, otherwise reset.
2297 MDBuilder MDB(NewCall->getContext());
2298 auto NewWeights = uint32_t(TotalWeight) != TotalWeight
2299 ? nullptr
2300 : MDB.createBranchWeights({uint32_t(TotalWeight)});
2301 NewCall->setMetadata(LLVMContext::MD_prof, NewWeights);
2302 }
2303
2304 return NewCall;
2305}
2306
2307// changeToCall - Convert the specified invoke into a normal call.
2309 CallInst *NewCall = createCallMatchingInvoke(II);
2310 NewCall->takeName(II);
2311 NewCall->insertBefore(II);
2312 II->replaceAllUsesWith(NewCall);
2313
2314 // Follow the call by a branch to the normal destination.
2315 BasicBlock *NormalDestBB = II->getNormalDest();
2316 BranchInst::Create(NormalDestBB, II);
2317
2318 // Update PHI nodes in the unwind destination
2319 BasicBlock *BB = II->getParent();
2320 BasicBlock *UnwindDestBB = II->getUnwindDest();
2321 UnwindDestBB->removePredecessor(BB);
2322 II->eraseFromParent();
2323 if (DTU)
2324 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2325 return NewCall;
2326}
2327
2329 BasicBlock *UnwindEdge,
2330 DomTreeUpdater *DTU) {
2331 BasicBlock *BB = CI->getParent();
2332
2333 // Convert this function call into an invoke instruction. First, split the
2334 // basic block.
2335 BasicBlock *Split = SplitBlock(BB, CI, DTU, /*LI=*/nullptr, /*MSSAU*/ nullptr,
2336 CI->getName() + ".noexc");
2337
2338 // Delete the unconditional branch inserted by SplitBlock
2339 BB->back().eraseFromParent();
2340
2341 // Create the new invoke instruction.
2342 SmallVector<Value *, 8> InvokeArgs(CI->args());
2344
2345 CI->getOperandBundlesAsDefs(OpBundles);
2346
2347 // Note: we're round tripping operand bundles through memory here, and that
2348 // can potentially be avoided with a cleverer API design that we do not have
2349 // as of this time.
2350
2351 InvokeInst *II =
2353 UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB);
2354 II->setDebugLoc(CI->getDebugLoc());
2355 II->setCallingConv(CI->getCallingConv());
2356 II->setAttributes(CI->getAttributes());
2357 II->setMetadata(LLVMContext::MD_prof, CI->getMetadata(LLVMContext::MD_prof));
2358
2359 if (DTU)
2360 DTU->applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});
2361
2362 // Make sure that anything using the call now uses the invoke! This also
2363 // updates the CallGraph if present, because it uses a WeakTrackingVH.
2364 CI->replaceAllUsesWith(II);
2365
2366 // Delete the original call
2367 Split->front().eraseFromParent();
2368 return Split;
2369}
2370
2373 DomTreeUpdater *DTU = nullptr) {
2375 BasicBlock *BB = &F.front();
2376 Worklist.push_back(BB);
2377 Reachable.insert(BB);
2378 bool Changed = false;
2379 do {
2380 BB = Worklist.pop_back_val();
2381
2382 // Do a quick scan of the basic block, turning any obviously unreachable
2383 // instructions into LLVM unreachable insts. The instruction combining pass
2384 // canonicalizes unreachable insts into stores to null or undef.
2385 for (Instruction &I : *BB) {
2386 if (auto *CI = dyn_cast<CallInst>(&I)) {
2387 Value *Callee = CI->getCalledOperand();
2388 // Handle intrinsic calls.
2389 if (Function *F = dyn_cast<Function>(Callee)) {
2390 auto IntrinsicID = F->getIntrinsicID();
2391 // Assumptions that are known to be false are equivalent to
2392 // unreachable. Also, if the condition is undefined, then we make the
2393 // choice most beneficial to the optimizer, and choose that to also be
2394 // unreachable.
2395 if (IntrinsicID == Intrinsic::assume) {
2396 if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
2397 // Don't insert a call to llvm.trap right before the unreachable.
2398 changeToUnreachable(CI, false, DTU);
2399 Changed = true;
2400 break;
2401 }
2402 } else if (IntrinsicID == Intrinsic::experimental_guard) {
2403 // A call to the guard intrinsic bails out of the current
2404 // compilation unit if the predicate passed to it is false. If the
2405 // predicate is a constant false, then we know the guard will bail
2406 // out of the current compile unconditionally, so all code following
2407 // it is dead.
2408 //
2409 // Note: unlike in llvm.assume, it is not "obviously profitable" for
2410 // guards to treat `undef` as `false` since a guard on `undef` can
2411 // still be useful for widening.
2412 if (match(CI->getArgOperand(0), m_Zero()))
2413 if (!isa<UnreachableInst>(CI->getNextNode())) {
2414 changeToUnreachable(CI->getNextNode(), false, DTU);
2415 Changed = true;
2416 break;
2417 }
2418 }
2419 } else if ((isa<ConstantPointerNull>(Callee) &&
2420 !NullPointerIsDefined(CI->getFunction(),
2421 cast<PointerType>(Callee->getType())
2422 ->getAddressSpace())) ||
2423 isa<UndefValue>(Callee)) {
2424 changeToUnreachable(CI, false, DTU);
2425 Changed = true;
2426 break;
2427 }
2428 if (CI->doesNotReturn() && !CI->isMustTailCall()) {
2429 // If we found a call to a no-return function, insert an unreachable
2430 // instruction after it. Make sure there isn't *already* one there
2431 // though.
2432 if (!isa<UnreachableInst>(CI->getNextNode())) {
2433 // Don't insert a call to llvm.trap right before the unreachable.
2434 changeToUnreachable(CI->getNextNode(), false, DTU);
2435 Changed = true;
2436 }
2437 break;
2438 }
2439 } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
2440 // Store to undef and store to null are undefined and used to signal
2441 // that they should be changed to unreachable by passes that can't
2442 // modify the CFG.
2443
2444 // Don't touch volatile stores.
2445 if (SI->isVolatile()) continue;
2446
2447 Value *Ptr = SI->getOperand(1);
2448
2449 if (isa<UndefValue>(Ptr) ||
2450 (isa<ConstantPointerNull>(Ptr) &&
2451 !NullPointerIsDefined(SI->getFunction(),
2452 SI->getPointerAddressSpace()))) {
2453 changeToUnreachable(SI, false, DTU);
2454 Changed = true;
2455 break;
2456 }
2457 }
2458 }
2459
2460 Instruction *Terminator = BB->getTerminator();
2461 if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
2462 // Turn invokes that call 'nounwind' functions into ordinary calls.
2463 Value *Callee = II->getCalledOperand();
2464 if ((isa<ConstantPointerNull>(Callee) &&
2465 !NullPointerIsDefined(BB->getParent())) ||
2466 isa<UndefValue>(Callee)) {
2467 changeToUnreachable(II, false, DTU);
2468 Changed = true;
2469 } else {
2470 if (II->doesNotReturn() &&
2471 !isa<UnreachableInst>(II->getNormalDest()->front())) {
2472 // If we found an invoke of a no-return function,
2473 // create a new empty basic block with an `unreachable` terminator,
2474 // and set it as the normal destination for the invoke,
2475 // unless that is already the case.
2476 // Note that the original normal destination could have other uses.
2477 BasicBlock *OrigNormalDest = II->getNormalDest();
2478 OrigNormalDest->removePredecessor(II->getParent());
2479 LLVMContext &Ctx = II->getContext();
2480 BasicBlock *UnreachableNormalDest = BasicBlock::Create(
2481 Ctx, OrigNormalDest->getName() + ".unreachable",
2482 II->getFunction(), OrigNormalDest);
2483 new UnreachableInst(Ctx, UnreachableNormalDest);
2484 II->setNormalDest(UnreachableNormalDest);
2485 if (DTU)
2486 DTU->applyUpdates(
2487 {{DominatorTree::Delete, BB, OrigNormalDest},
2488 {DominatorTree::Insert, BB, UnreachableNormalDest}});
2489 Changed = true;
2490 }
2491 if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
2492 if (II->use_empty() && !II->mayHaveSideEffects()) {
2493 // jump to the normal destination branch.
2494 BasicBlock *NormalDestBB = II->getNormalDest();
2495 BasicBlock *UnwindDestBB = II->getUnwindDest();
2496 BranchInst::Create(NormalDestBB, II);
2497 UnwindDestBB->removePredecessor(II->getParent());
2498 II->eraseFromParent();
2499 if (DTU)
2500 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2501 } else
2502 changeToCall(II, DTU);
2503 Changed = true;
2504 }
2505 }
2506 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
2507 // Remove catchpads which cannot be reached.
2508 struct CatchPadDenseMapInfo {
2509 static CatchPadInst *getEmptyKey() {
2511 }
2512
2513 static CatchPadInst *getTombstoneKey() {
2515 }
2516
2517 static unsigned getHashValue(CatchPadInst *CatchPad) {
2518 return static_cast<unsigned>(hash_combine_range(
2519 CatchPad->value_op_begin(), CatchPad->value_op_end()));
2520 }
2521
2522 static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
2523 if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
2524 RHS == getEmptyKey() || RHS == getTombstoneKey())
2525 return LHS == RHS;
2526 return LHS->isIdenticalTo(RHS);
2527 }
2528 };
2529
2530 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
2531 // Set of unique CatchPads.
2533 CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
2534 HandlerSet;
2536 for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
2537 E = CatchSwitch->handler_end();
2538 I != E; ++I) {
2539 BasicBlock *HandlerBB = *I;
2540 if (DTU)
2541 ++NumPerSuccessorCases[HandlerBB];
2542 auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
2543 if (!HandlerSet.insert({CatchPad, Empty}).second) {
2544 if (DTU)
2545 --NumPerSuccessorCases[HandlerBB];
2546 CatchSwitch->removeHandler(I);
2547 --I;
2548 --E;
2549 Changed = true;
2550 }
2551 }
2552 if (DTU) {
2553 std::vector<DominatorTree::UpdateType> Updates;
2554 for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases)
2555 if (I.second == 0)
2556 Updates.push_back({DominatorTree::Delete, BB, I.first});
2557 DTU->applyUpdates(Updates);
2558 }
2559 }
2560
2561 Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
2562 for (BasicBlock *Successor : successors(BB))
2563 if (Reachable.insert(Successor).second)
2564 Worklist.push_back(Successor);
2565 } while (!Worklist.empty());
2566 return Changed;
2567}
2568
2570 Instruction *TI = BB->getTerminator();
2571
2572 if (auto *II = dyn_cast<InvokeInst>(TI))
2573 return changeToCall(II, DTU);
2574
2575 Instruction *NewTI;
2576 BasicBlock *UnwindDest;
2577
2578 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
2579 NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
2580 UnwindDest = CRI->getUnwindDest();
2581 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
2582 auto *NewCatchSwitch = CatchSwitchInst::Create(
2583 CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
2584 CatchSwitch->getName(), CatchSwitch);
2585 for (BasicBlock *PadBB : CatchSwitch->handlers())
2586 NewCatchSwitch->addHandler(PadBB);
2587
2588 NewTI = NewCatchSwitch;
2589 UnwindDest = CatchSwitch->getUnwindDest();
2590 } else {
2591 llvm_unreachable("Could not find unwind successor");
2592 }
2593
2594 NewTI->takeName(TI);
2595 NewTI->setDebugLoc(TI->getDebugLoc());
2596 UnwindDest->removePredecessor(BB);
2597 TI->replaceAllUsesWith(NewTI);
2598 TI->eraseFromParent();
2599 if (DTU)
2600 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
2601 return NewTI;
2602}
2603
2604/// removeUnreachableBlocks - Remove blocks that are not reachable, even
2605/// if they are in a dead cycle. Return true if a change was made, false
2606/// otherwise.
2608 MemorySSAUpdater *MSSAU) {
2610 bool Changed = markAliveBlocks(F, Reachable, DTU);
2611
2612 // If there are unreachable blocks in the CFG...
2613 if (Reachable.size() == F.size())
2614 return Changed;
2615
2616 assert(Reachable.size() < F.size());
2617
2618 // Are there any blocks left to actually delete?
2619 SmallSetVector<BasicBlock *, 8> BlocksToRemove;
2620 for (BasicBlock &BB : F) {
2621 // Skip reachable basic blocks
2622 if (Reachable.count(&BB))
2623 continue;
2624 // Skip already-deleted blocks
2625 if (DTU && DTU->isBBPendingDeletion(&BB))
2626 continue;
2627 BlocksToRemove.insert(&BB);
2628 }
2629
2630 if (BlocksToRemove.empty())
2631 return Changed;
2632
2633 Changed = true;
2634 NumRemoved += BlocksToRemove.size();
2635
2636 if (MSSAU)
2637 MSSAU->removeBlocks(BlocksToRemove);
2638
2639 DeleteDeadBlocks(BlocksToRemove.takeVector(), DTU);
2640
2641 return Changed;
2642}
2643
2645 ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
2647 K->dropUnknownNonDebugMetadata(KnownIDs);
2648 K->getAllMetadataOtherThanDebugLoc(Metadata);
2649 for (const auto &MD : Metadata) {
2650 unsigned Kind = MD.first;
2651 MDNode *JMD = J->getMetadata(Kind);
2652 MDNode *KMD = MD.second;
2653
2654 switch (Kind) {
2655 default:
2656 K->setMetadata(Kind, nullptr); // Remove unknown metadata
2657 break;
2658 case LLVMContext::MD_dbg:
2659 llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
2660 case LLVMContext::MD_DIAssignID:
2661 K->mergeDIAssignID(J);
2662 break;
2663 case LLVMContext::MD_tbaa:
2664 K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
2665 break;
2666 case LLVMContext::MD_alias_scope:
2667 K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
2668 break;
2669 case LLVMContext::MD_noalias:
2670 case LLVMContext::MD_mem_parallel_loop_access:
2671 K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
2672 break;
2673 case LLVMContext::MD_access_group:
2674 K->setMetadata(LLVMContext::MD_access_group,
2675 intersectAccessGroups(K, J));
2676 break;
2677 case LLVMContext::MD_range:
2678 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
2679 K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
2680 break;
2681 case LLVMContext::MD_fpmath:
2682 K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
2683 break;
2684 case LLVMContext::MD_invariant_load:
2685 // Only set the !invariant.load if it is present in both instructions.
2686 K->setMetadata(Kind, JMD);
2687 break;
2688 case LLVMContext::MD_nonnull:
2689 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
2690 K->setMetadata(Kind, JMD);
2691 break;
2692 case LLVMContext::MD_invariant_group:
2693 // Preserve !invariant.group in K.
2694 break;
2695 case LLVMContext::MD_align:
2696 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
2697 K->setMetadata(
2699 break;
2700 case LLVMContext::MD_dereferenceable:
2701 case LLVMContext::MD_dereferenceable_or_null:
2702 K->setMetadata(Kind,
2704 break;
2705 case LLVMContext::MD_preserve_access_index:
2706 // Preserve !preserve.access.index in K.
2707 break;
2708 case LLVMContext::MD_noundef:
2709 // If K does move, keep noundef if it is present in both instructions.
2710 if (DoesKMove)
2711 K->setMetadata(Kind, JMD);
2712 break;
2713 case LLVMContext::MD_nontemporal:
2714 // Preserve !nontemporal if it is present on both instructions.
2715 K->setMetadata(Kind, JMD);
2716 break;
2717 }
2718 }
2719 // Set !invariant.group from J if J has it. If both instructions have it
2720 // then we will just pick it from J - even when they are different.
2721 // Also make sure that K is load or store - f.e. combining bitcast with load
2722 // could produce bitcast with invariant.group metadata, which is invalid.
2723 // FIXME: we should try to preserve both invariant.group md if they are
2724 // different, but right now instruction can only have one invariant.group.
2725 if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2726 if (isa<LoadInst>(K) || isa<StoreInst>(K))
2727 K->setMetadata(LLVMContext::MD_invariant_group, JMD);
2728}
2729
2731 bool KDominatesJ) {
2732 unsigned KnownIDs[] = {
2733 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2734 LLVMContext::MD_noalias, LLVMContext::MD_range,
2735 LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull,
2736 LLVMContext::MD_invariant_group, LLVMContext::MD_align,
2737 LLVMContext::MD_dereferenceable,
2738 LLVMContext::MD_dereferenceable_or_null,
2739 LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index,
2740 LLVMContext::MD_nontemporal, LLVMContext::MD_noundef};
2741 combineMetadata(K, J, KnownIDs, KDominatesJ);
2742}
2743
2744void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) {
2746 Source.getAllMetadata(MD);
2747 MDBuilder MDB(Dest.getContext());
2748 Type *NewType = Dest.getType();
2749 const DataLayout &DL = Source.getModule()->getDataLayout();
2750 for (const auto &MDPair : MD) {
2751 unsigned ID = MDPair.first;
2752 MDNode *N = MDPair.second;
2753 // Note, essentially every kind of metadata should be preserved here! This
2754 // routine is supposed to clone a load instruction changing *only its type*.
2755 // The only metadata it makes sense to drop is metadata which is invalidated
2756 // when the pointer type changes. This should essentially never be the case
2757 // in LLVM, but we explicitly switch over only known metadata to be
2758 // conservatively correct. If you are adding metadata to LLVM which pertains
2759 // to loads, you almost certainly want to add it here.
2760 switch (ID) {
2761 case LLVMContext::MD_dbg:
2762 case LLVMContext::MD_tbaa:
2763 case LLVMContext::MD_prof:
2764 case LLVMContext::MD_fpmath:
2765 case LLVMContext::MD_tbaa_struct:
2766 case LLVMContext::MD_invariant_load:
2767 case LLVMContext::MD_alias_scope:
2768 case LLVMContext::MD_noalias:
2769 case LLVMContext::MD_nontemporal:
2770 case LLVMContext::MD_mem_parallel_loop_access:
2771 case LLVMContext::MD_access_group:
2772 case LLVMContext::MD_noundef:
2773 // All of these directly apply.
2774 Dest.setMetadata(ID, N);
2775 break;
2776
2777 case LLVMContext::MD_nonnull:
2778 copyNonnullMetadata(Source, N, Dest);
2779 break;
2780
2781 case LLVMContext::MD_align:
2782 case LLVMContext::MD_dereferenceable:
2783 case LLVMContext::MD_dereferenceable_or_null:
2784 // These only directly apply if the new type is also a pointer.
2785 if (NewType->isPointerTy())
2786 Dest.setMetadata(ID, N);
2787 break;
2788
2789 case LLVMContext::MD_range:
2790 copyRangeMetadata(DL, Source, N, Dest);
2791 break;
2792 }
2793 }
2794}
2795
2797 auto *ReplInst = dyn_cast<Instruction>(Repl);
2798 if (!ReplInst)
2799 return;
2800
2801 // Patch the replacement so that it is not more restrictive than the value
2802 // being replaced.
2803 // Note that if 'I' is a load being replaced by some operation,
2804 // for example, by an arithmetic operation, then andIRFlags()
2805 // would just erase all math flags from the original arithmetic
2806 // operation, which is clearly not wanted and not needed.
2807 if (!isa<LoadInst>(I))
2808 ReplInst->andIRFlags(I);
2809
2810 // FIXME: If both the original and replacement value are part of the
2811 // same control-flow region (meaning that the execution of one
2812 // guarantees the execution of the other), then we can combine the
2813 // noalias scopes here and do better than the general conservative
2814 // answer used in combineMetadata().
2815
2816 // In general, GVN unifies expressions over different control-flow
2817 // regions, and so we need a conservative combination of the noalias
2818 // scopes.
2819 static const unsigned KnownIDs[] = {
2820 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2821 LLVMContext::MD_noalias, LLVMContext::MD_range,
2822 LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
2823 LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull,
2824 LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index,
2825 LLVMContext::MD_noundef, LLVMContext::MD_nontemporal};
2826 combineMetadata(ReplInst, I, KnownIDs, false);
2827}
2828
2829template <typename RootType, typename DominatesFn>
2831 const RootType &Root,
2832 const DominatesFn &Dominates) {
2833 assert(From->getType() == To->getType());
2834
2835 unsigned Count = 0;
2836 for (Use &U : llvm::make_early_inc_range(From->uses())) {
2837 if (!Dominates(Root, U))
2838 continue;
2839 U.set(To);
2840 LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()
2841 << "' as " << *To << " in " << *U << "\n");
2842 ++Count;
2843 }
2844 return Count;
2845}
2846
2848 assert(From->getType() == To->getType());
2849 auto *BB = From->getParent();
2850 unsigned Count = 0;
2851
2852 for (Use &U : llvm::make_early_inc_range(From->uses())) {
2853 auto *I = cast<Instruction>(U.getUser());
2854 if (I->getParent() == BB)
2855 continue;
2856 U.set(To);
2857 ++Count;
2858 }
2859 return Count;
2860}
2861
2863 DominatorTree &DT,
2864 const BasicBlockEdge &Root) {
2865 auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2866 return DT.dominates(Root, U);
2867 };
2868 return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2869}
2870
2872 DominatorTree &DT,
2873 const BasicBlock *BB) {
2874 auto Dominates = [&DT](const BasicBlock *BB, const Use &U) {
2875 return DT.dominates(BB, U);
2876 };
2877 return ::replaceDominatedUsesWith(From, To, BB, Dominates);
2878}
2879
2881 const TargetLibraryInfo &TLI) {
2882 // Check if the function is specifically marked as a gc leaf function.
2883 if (Call->hasFnAttr("gc-leaf-function"))
2884 return true;
2885 if (const Function *F = Call->getCalledFunction()) {
2886 if (F->hasFnAttribute("gc-leaf-function"))
2887 return true;
2888
2889 if (auto IID = F->getIntrinsicID()) {
2890 // Most LLVM intrinsics do not take safepoints.
2891 return IID != Intrinsic::experimental_gc_statepoint &&
2892 IID != Intrinsic::experimental_deoptimize &&
2893 IID != Intrinsic::memcpy_element_unordered_atomic &&
2894 IID != Intrinsic::memmove_element_unordered_atomic;
2895 }
2896 }
2897
2898 // Lib calls can be materialized by some passes, and won't be
2899 // marked as 'gc-leaf-function.' All available Libcalls are
2900 // GC-leaf.
2901 LibFunc LF;
2902 if (TLI.getLibFunc(*Call, LF)) {
2903 return TLI.has(LF);
2904 }
2905
2906 return false;
2907}
2908
2910 LoadInst &NewLI) {
2911 auto *NewTy = NewLI.getType();
2912
2913 // This only directly applies if the new type is also a pointer.
2914 if (NewTy->isPointerTy()) {
2915 NewLI.setMetadata(LLVMContext::MD_nonnull, N);
2916 return;
2917 }
2918
2919 // The only other translation we can do is to integral loads with !range
2920 // metadata.
2921 if (!NewTy->isIntegerTy())
2922 return;
2923
2924 MDBuilder MDB(NewLI.getContext());
2925 const Value *Ptr = OldLI.getPointerOperand();
2926 auto *ITy = cast<IntegerType>(NewTy);
2927 auto *NullInt = ConstantExpr::getPtrToInt(
2928 ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
2929 auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
2930 NewLI.setMetadata(LLVMContext::MD_range,
2931 MDB.createRange(NonNullInt, NullInt));
2932}
2933
2935 MDNode *N, LoadInst &NewLI) {
2936 auto *NewTy = NewLI.getType();
2937 // Simply copy the metadata if the type did not change.
2938 if (NewTy == OldLI.getType()) {
2939 NewLI.setMetadata(LLVMContext::MD_range, N);
2940 return;
2941 }
2942
2943 // Give up unless it is converted to a pointer where there is a single very
2944 // valuable mapping we can do reliably.
2945 // FIXME: It would be nice to propagate this in more ways, but the type
2946 // conversions make it hard.
2947 if (!NewTy->isPointerTy())
2948 return;
2949
2950 unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
2952 MDNode *NN = MDNode::get(OldLI.getContext(), std::nullopt);
2953 NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
2954 }
2955}
2956
2959 findDbgUsers(DbgUsers, &I);
2960 for (auto *DII : DbgUsers)
2961 DII->eraseFromParent();
2962}
2963
2965 BasicBlock *BB) {
2966 // Since we are moving the instructions out of its basic block, we do not
2967 // retain their original debug locations (DILocations) and debug intrinsic
2968 // instructions.
2969 //
2970 // Doing so would degrade the debugging experience and adversely affect the
2971 // accuracy of profiling information.
2972 //
2973 // Currently, when hoisting the instructions, we take the following actions:
2974 // - Remove their debug intrinsic instructions.
2975 // - Set their debug locations to the values from the insertion point.
2976 //
2977 // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
2978 // need to be deleted, is because there will not be any instructions with a
2979 // DILocation in either branch left after performing the transformation. We
2980 // can only insert a dbg.value after the two branches are joined again.
2981 //
2982 // See PR38762, PR39243 for more details.
2983 //
2984 // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
2985 // encode predicated DIExpressions that yield different results on different
2986 // code paths.
2987
2988 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
2989 Instruction *I = &*II;
2990 I->dropUBImplyingAttrsAndUnknownMetadata();
2991 if (I->isUsedByMetadata())
2992 dropDebugUsers(*I);
2993 if (I->isDebugOrPseudoInst()) {
2994 // Remove DbgInfo and pseudo probe Intrinsics.
2995 II = I->eraseFromParent();
2996 continue;
2997 }
2998 I->setDebugLoc(InsertPt->getDebugLoc());
2999 ++II;
3000 }
3001 DomBlock->splice(InsertPt->getIterator(), BB, BB->begin(),
3002 BB->getTerminator()->getIterator());
3003}
3004
3005namespace {
3006
3007/// A potential constituent of a bitreverse or bswap expression. See
3008/// collectBitParts for a fuller explanation.
3009struct BitPart {
3010 BitPart(Value *P, unsigned BW) : Provider(P) {
3011 Provenance.resize(BW);
3012 }
3013
3014 /// The Value that this is a bitreverse/bswap of.
3015 Value *Provider;
3016
3017 /// The "provenance" of each bit. Provenance[A] = B means that bit A
3018 /// in Provider becomes bit B in the result of this expression.
3019 SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
3020
3021 enum { Unset = -1 };
3022};
3023
3024} // end anonymous namespace
3025
3026/// Analyze the specified subexpression and see if it is capable of providing
3027/// pieces of a bswap or bitreverse. The subexpression provides a potential
3028/// piece of a bswap or bitreverse if it can be proved that each non-zero bit in
3029/// the output of the expression came from a corresponding bit in some other
3030/// value. This function is recursive, and the end result is a mapping of
3031/// bitnumber to bitnumber. It is the caller's responsibility to validate that
3032/// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
3033///
3034/// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
3035/// that the expression deposits the low byte of %X into the high byte of the
3036/// result and that all other bits are zero. This expression is accepted and a
3037/// BitPart is returned with Provider set to %X and Provenance[24-31] set to
3038/// [0-7].
3039///
3040/// For vector types, all analysis is performed at the per-element level. No
3041/// cross-element analysis is supported (shuffle/insertion/reduction), and all
3042/// constant masks must be splatted across all elements.
3043///
3044/// To avoid revisiting values, the BitPart results are memoized into the
3045/// provided map. To avoid unnecessary copying of BitParts, BitParts are
3046/// constructed in-place in the \c BPS map. Because of this \c BPS needs to
3047/// store BitParts objects, not pointers. As we need the concept of a nullptr
3048/// BitParts (Value has been analyzed and the analysis failed), we an Optional
3049/// type instead to provide the same functionality.
3050///
3051/// Because we pass around references into \c BPS, we must use a container that
3052/// does not invalidate internal references (std::map instead of DenseMap).
3053static const std::optional<BitPart> &
3054collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
3055 std::map<Value *, std::optional<BitPart>> &BPS, int Depth,
3056 bool &FoundRoot) {
3057 auto I = BPS.find(V);
3058 if (I != BPS.end())
3059 return I->second;
3060
3061 auto &Result = BPS[V] = std::nullopt;
3062 auto BitWidth = V->getType()->getScalarSizeInBits();
3063
3064 // Can't do integer/elements > 128 bits.
3065 if (BitWidth > 128)
3066 return Result;
3067
3068 // Prevent stack overflow by limiting the recursion depth
3070 LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n");
3071 return Result;
3072 }
3073
3074 if (auto *I = dyn_cast<Instruction>(V)) {
3075 Value *X, *Y;
3076 const APInt *C;
3077
3078 // If this is an or instruction, it may be an inner node of the bswap.
3079 if (match(V, m_Or(m_Value(X), m_Value(Y)))) {
3080 // Check we have both sources and they are from the same provider.
3081 const auto &A = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3082 Depth + 1, FoundRoot);
3083 if (!A || !A->Provider)
3084 return Result;
3085
3086 const auto &B = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
3087 Depth + 1, FoundRoot);
3088 if (!B || A->Provider != B->Provider)
3089 return Result;
3090
3091 // Try and merge the two together.
3092 Result = BitPart(A->Provider, BitWidth);
3093 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) {
3094 if (A->Provenance[BitIdx] != BitPart::Unset &&
3095 B->Provenance[BitIdx] != BitPart::Unset &&
3096 A->Provenance[BitIdx] != B->Provenance[BitIdx])
3097 return Result = std::nullopt;
3098
3099 if (A->Provenance[BitIdx] == BitPart::Unset)
3100 Result->Provenance[BitIdx] = B->Provenance[BitIdx];
3101 else
3102 Result->Provenance[BitIdx] = A->Provenance[BitIdx];
3103 }
3104
3105 return Result;
3106 }
3107
3108 // If this is a logical shift by a constant, recurse then shift the result.
3109 if (match(V, m_LogicalShift(m_Value(X), m_APInt(C)))) {
3110 const APInt &BitShift = *C;
3111
3112 // Ensure the shift amount is defined.
3113 if (BitShift.uge(BitWidth))
3114 return Result;
3115
3116 // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3117 if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0)
3118 return Result;
3119
3120 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3121 Depth + 1, FoundRoot);
3122 if (!Res)
3123 return Result;
3124 Result = Res;
3125
3126 // Perform the "shift" on BitProvenance.
3127 auto &P = Result->Provenance;
3128 if (I->getOpcode() == Instruction::Shl) {
3129 P.erase(std::prev(P.end(), BitShift.getZExtValue()), P.end());
3130 P.insert(P.begin(), BitShift.getZExtValue(), BitPart::Unset);
3131 } else {
3132 P.erase(P.begin(), std::next(P.begin(), BitShift.getZExtValue()));
3133 P.insert(P.end(), BitShift.getZExtValue(), BitPart::Unset);
3134 }
3135
3136 return Result;
3137 }
3138
3139 // If this is a logical 'and' with a mask that clears bits, recurse then
3140 // unset the appropriate bits.
3141 if (match(V, m_And(m_Value(X), m_APInt(C)))) {
3142 const APInt &AndMask = *C;
3143
3144 // Check that the mask allows a multiple of 8 bits for a bswap, for an
3145 // early exit.
3146 unsigned NumMaskedBits = AndMask.popcount();
3147 if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3148 return Result;
3149
3150 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3151 Depth + 1, FoundRoot);
3152 if (!Res)
3153 return Result;
3154 Result = Res;
3155
3156 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3157 // If the AndMask is zero for this bit, clear the bit.
3158 if (AndMask[BitIdx] == 0)
3159 Result->Provenance[BitIdx] = BitPart::Unset;
3160 return Result;
3161 }
3162
3163 // If this is a zext instruction zero extend the result.
3164 if (match(V, m_ZExt(m_Value(X)))) {
3165 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3166 Depth + 1, FoundRoot);
3167 if (!Res)
3168 return Result;
3169
3170 Result = BitPart(Res->Provider, BitWidth);
3171 auto NarrowBitWidth = X->getType()->getScalarSizeInBits();
3172 for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3173 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3174 for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx)
3175 Result->Provenance[BitIdx] = BitPart::Unset;
3176 return Result;
3177 }
3178
3179 // If this is a truncate instruction, extract the lower bits.
3180 if (match(V, m_Trunc(m_Value(X)))) {
3181 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3182 Depth + 1, FoundRoot);
3183 if (!Res)
3184 return Result;
3185
3186 Result = BitPart(Res->Provider, BitWidth);
3187 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3188 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3189 return Result;
3190 }
3191
3192 // BITREVERSE - most likely due to us previous matching a partial
3193 // bitreverse.
3194 if (match(V, m_BitReverse(m_Value(X)))) {
3195 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3196 Depth + 1, FoundRoot);
3197 if (!Res)
3198 return Result;
3199
3200 Result = BitPart(Res->Provider, BitWidth);
3201 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3202 Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3203 return Result;
3204 }
3205
3206 // BSWAP - most likely due to us previous matching a partial bswap.
3207 if (match(V, m_BSwap(m_Value(X)))) {
3208 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3209 Depth + 1, FoundRoot);
3210 if (!Res)
3211 return Result;
3212
3213 unsigned ByteWidth = BitWidth / 8;
3214 Result = BitPart(Res->Provider, BitWidth);
3215 for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3216 unsigned ByteBitOfs = ByteIdx * 8;
3217 for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3218 Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] =
3219 Res->Provenance[ByteBitOfs + BitIdx];
3220 }
3221 return Result;
3222 }
3223
3224 // Funnel 'double' shifts take 3 operands, 2 inputs and the shift
3225 // amount (modulo).
3226 // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
3227 // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW))
3228 if (match(V, m_FShl(m_Value(X), m_Value(Y), m_APInt(C))) ||
3229 match(V, m_FShr(m_Value(X), m_Value(Y), m_APInt(C)))) {
3230 // We can treat fshr as a fshl by flipping the modulo amount.
3231 unsigned ModAmt = C->urem(BitWidth);
3232 if (cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fshr)
3233 ModAmt = BitWidth - ModAmt;
3234
3235 // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3236 if (!MatchBitReversals && (ModAmt % 8) != 0)
3237 return Result;
3238
3239 // Check we have both sources and they are from the same provider.
3240 const auto &LHS = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3241 Depth + 1, FoundRoot);
3242 if (!LHS || !LHS->Provider)
3243 return Result;
3244
3245 const auto &RHS = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
3246 Depth + 1, FoundRoot);
3247 if (!RHS || LHS->Provider != RHS->Provider)
3248 return Result;
3249
3250 unsigned StartBitRHS = BitWidth - ModAmt;
3251 Result = BitPart(LHS->Provider, BitWidth);
3252 for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3253 Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx];
3254 for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3255 Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS];
3256 return Result;
3257 }
3258 }
3259
3260 // If we've already found a root input value then we're never going to merge
3261 // these back together.
3262 if (FoundRoot)
3263 return Result;
3264
3265 // Okay, we got to something that isn't a shift, 'or', 'and', etc. This must
3266 // be the root input value to the bswap/bitreverse.
3267 FoundRoot = true;
3268 Result = BitPart(V, BitWidth);
3269 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3270 Result->Provenance[BitIdx] = BitIdx;
3271 return Result;
3272}
3273
3274static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
3275 unsigned BitWidth) {
3276 if (From % 8 != To % 8)
3277 return false;
3278 // Convert from bit indices to byte indices and check for a byte reversal.
3279 From >>= 3;
3280 To >>= 3;
3281 BitWidth >>= 3;
3282 return From == BitWidth - To - 1;
3283}
3284
3285static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
3286 unsigned BitWidth) {
3287 return From == BitWidth - To - 1;
3288}
3289
3291 Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
3292 SmallVectorImpl<Instruction *> &InsertedInsts) {
3293 if (!match(I, m_Or(m_Value(), m_Value())) &&
3294 !match(I, m_FShl(m_Value(), m_Value(), m_Value())) &&
3295 !match(I, m_FShr(m_Value(), m_Value(), m_Value())))
3296 return false;
3297 if (!MatchBSwaps && !MatchBitReversals)
3298 return false;
3299 Type *ITy = I->getType();
3300 if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() > 128)
3301 return false; // Can't do integer/elements > 128 bits.
3302
3303 // Try to find all the pieces corresponding to the bswap.
3304 bool FoundRoot = false;
3305 std::map<Value *, std::optional<BitPart>> BPS;
3306 const auto &Res =
3307 collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0, FoundRoot);
3308 if (!Res)
3309 return false;
3310 ArrayRef<int8_t> BitProvenance = Res->Provenance;
3311 assert(all_of(BitProvenance,
3312 [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) &&
3313 "Illegal bit provenance index");
3314
3315 // If the upper bits are zero, then attempt to perform as a truncated op.
3316 Type *DemandedTy = ITy;
3317 if (BitProvenance.back() == BitPart::Unset) {
3318 while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset)
3319 BitProvenance = BitProvenance.drop_back();
3320 if (BitProvenance.empty())
3321 return false; // TODO - handle null value?
3322 DemandedTy = Type::getIntNTy(I->getContext(), BitProvenance.size());
3323 if (auto *IVecTy = dyn_cast<VectorType>(ITy))
3324 DemandedTy = VectorType::get(DemandedTy, IVecTy);
3325 }
3326
3327 // Check BitProvenance hasn't found a source larger than the result type.
3328 unsigned DemandedBW = DemandedTy->getScalarSizeInBits();
3329 if (DemandedBW > ITy->getScalarSizeInBits())
3330 return false;
3331
3332 // Now, is the bit permutation correct for a bswap or a bitreverse? We can
3333 // only byteswap values with an even number of bytes.
3334 APInt DemandedMask = APInt::getAllOnes(DemandedBW);
3335 bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
3336 bool OKForBitReverse = MatchBitReversals;
3337 for (unsigned BitIdx = 0;
3338 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
3339 if (BitProvenance[BitIdx] == BitPart::Unset) {
3340 DemandedMask.clearBit(BitIdx);
3341 continue;
3342 }
3343 OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[BitIdx], BitIdx,
3344 DemandedBW);
3345 OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[BitIdx],
3346 BitIdx, DemandedBW);
3347 }
3348
3349 Intrinsic::ID Intrin;
3350 if (OKForBSwap)
3351 Intrin = Intrinsic::bswap;
3352 else if (OKForBitReverse)
3353 Intrin = Intrinsic::bitreverse;
3354 else
3355 return false;
3356
3357 Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
3358 Value *Provider = Res->Provider;
3359
3360 // We may need to truncate the provider.
3361 if (DemandedTy != Provider->getType()) {
3362 auto *Trunc =
3363 CastInst::CreateIntegerCast(Provider, DemandedTy, false, "trunc", I);
3364 InsertedInsts.push_back(Trunc);
3365 Provider = Trunc;
3366 }
3367
3368 Instruction *Result = CallInst::Create(F, Provider, "rev", I);
3369 InsertedInsts.push_back(Result);
3370
3371 if (!DemandedMask.isAllOnes()) {
3372 auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
3373 Result = BinaryOperator::Create(Instruction::And, Result, Mask, "mask", I);
3374 InsertedInsts.push_back(Result);
3375 }
3376
3377 // We may need to zeroextend back to the result type.
3378 if (ITy != Result->getType()) {
3379 auto *ExtInst = CastInst::CreateIntegerCast(Result, ITy, false, "zext", I);
3380 InsertedInsts.push_back(ExtInst);
3381 }
3382
3383 return true;
3384}
3385
3386// CodeGen has special handling for some string functions that may replace
3387// them with target-specific intrinsics. Since that'd skip our interceptors
3388// in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
3389// we mark affected calls as NoBuiltin, which will disable optimization
3390// in CodeGen.
3392 CallInst *CI, const TargetLibraryInfo *TLI) {
3393 Function *F = CI->getCalledFunction();
3394 LibFunc Func;
3395 if (F && !F->hasLocalLinkage() && F->hasName() &&
3396 TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
3397 !F->doesNotAccessMemory())
3398 CI->addFnAttr(Attribute::NoBuiltin);
3399}
3400
3402 // We can't have a PHI with a metadata type.
3403 if (I->getOperand(OpIdx)->getType()->isMetadataTy())
3404 return false;
3405
3406 // Early exit.
3407 if (!isa<Constant>(I->getOperand(OpIdx)))
3408 return true;
3409
3410 switch (I->getOpcode()) {
3411 default:
3412 return true;
3413 case Instruction::Call:
3414 case Instruction::Invoke: {
3415 const auto &CB = cast<CallBase>(*I);
3416
3417 // Can't handle inline asm. Skip it.
3418 if (CB.isInlineAsm())
3419 return false;
3420
3421 // Constant bundle operands may need to retain their constant-ness for
3422 // correctness.
3423 if (CB.isBundleOperand(OpIdx))
3424 return false;
3425
3426 if (OpIdx < CB.arg_size()) {
3427 // Some variadic intrinsics require constants in the variadic arguments,
3428 // which currently aren't markable as immarg.
3429 if (isa<IntrinsicInst>(CB) &&
3430 OpIdx >= CB.getFunctionType()->getNumParams()) {
3431 // This is known to be OK for stackmap.
3432 return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
3433 }
3434
3435 // gcroot is a special case, since it requires a constant argument which
3436 // isn't also required to be a simple ConstantInt.
3437 if (CB.getIntrinsicID() == Intrinsic::gcroot)
3438 return false;
3439
3440 // Some intrinsic operands are required to be immediates.
3441 return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
3442 }
3443
3444 // It is never allowed to replace the call argument to an intrinsic, but it
3445 // may be possible for a call.
3446 return !isa<IntrinsicInst>(CB);
3447 }
3448 case Instruction::ShuffleVector:
3449 // Shufflevector masks are constant.
3450 return OpIdx != 2;
3451 case Instruction::Switch:
3452 case Instruction::ExtractValue:
3453 // All operands apart from the first are constant.
3454 return OpIdx == 0;
3455 case Instruction::InsertValue:
3456 // All operands apart from the first and the second are constant.
3457 return OpIdx < 2;
3458 case Instruction::Alloca:
3459 // Static allocas (constant size in the entry block) are handled by
3460 // prologue/epilogue insertion so they're free anyway. We definitely don't
3461 // want to make them non-constant.
3462 return !cast<AllocaInst>(I)->isStaticAlloca();
3463 case Instruction::GetElementPtr:
3464 if (OpIdx == 0)
3465 return true;
3467 for (auto E = std::next(It, OpIdx); It != E; ++It)
3468 if (It.isStruct())
3469 return false;
3470 return true;
3471 }
3472}
3473
3475 // First: Check if it's a constant
3476 if (Constant *C = dyn_cast<Constant>(Condition))
3477 return ConstantExpr::getNot(C);
3478
3479 // Second: If the condition is already inverted, return the original value
3480 Value *NotCondition;
3481 if (match(Condition, m_Not(m_Value(NotCondition))))
3482 return NotCondition;
3483
3484 BasicBlock *Parent = nullptr;
3485 Instruction *Inst = dyn_cast<Instruction>(Condition);
3486 if (Inst)
3487 Parent = Inst->getParent();
3488 else if (Argument *Arg = dyn_cast<Argument>(Condition))
3489 Parent = &Arg->getParent()->getEntryBlock();
3490 assert(Parent && "Unsupported condition to invert");
3491
3492 // Third: Check all the users for an invert
3493 for (User *U : Condition->users())
3494 if (Instruction *I = dyn_cast<Instruction>(U))
3495 if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
3496 return I;
3497
3498 // Last option: Create a new instruction
3499 auto *Inverted =
3500 BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv");
3501 if (Inst && !isa<PHINode>(Inst))
3502 Inverted->insertAfter(Inst);
3503 else
3504 Inverted->insertBefore(&*Parent->getFirstInsertionPt());
3505 return Inverted;
3506}
3507
3509 // Note: We explicitly check for attributes rather than using cover functions
3510 // because some of the cover functions include the logic being implemented.
3511
3512 bool Changed = false;
3513 // readnone + not convergent implies nosync
3514 if (!F.hasFnAttribute(Attribute::NoSync) &&
3515 F.doesNotAccessMemory() && !F.isConvergent()) {
3516 F.setNoSync();
3517 Changed = true;
3518 }
3519
3520 // readonly implies nofree
3521 if (!F.hasFnAttribute(Attribute::NoFree) && F.onlyReadsMemory()) {
3522 F.setDoesNotFreeMemory();
3523 Changed = true;
3524 }
3525
3526 // willreturn implies mustprogress
3527 if (!F.hasFnAttribute(Attribute::MustProgress) && F.willReturn()) {
3528 F.setMustProgress();
3529 Changed = true;
3530 }
3531
3532 // TODO: There are a bunch of cases of restrictive memory effects we
3533 // can infer by inspecting arguments of argmemonly-ish functions.
3534
3535 return Changed;
3536}
static unsigned getIntrinsicID(const SDNode *N)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Callee
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
assume Assume Builder
static bool isEqual(const Function &Caller, const Function &Callee)
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
for(auto &MBB :MF)
SmallVector< MachineOperand, 4 > Cond
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file contains constants used for implementing Dwarf debug support.
static unsigned getHashValueImpl(SimpleValue Val)
Definition: EarlyCSE.cpp:221
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
Definition: EarlyCSE.cpp:339
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Hexagon Common GEP
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
Definition: IVUsers.cpp:48
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file contains the declarations for metadata subclasses.
Module.h This file contains the declarations for the Module class.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
#define P(N)
This file contains the declarations for profiling metadata utility functions.
@ SI
@ VI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
static bool markAliveBlocks(Function &F, SmallPtrSetImpl< BasicBlock * > &Reachable, DomTreeUpdater *DTU=nullptr)
Definition: Local.cpp:2371
static bool valueCoversEntireFragment(Type *ValTy, DbgVariableIntrinsic *DII)
Check if the alloc size of ValTy is large enough to cover the variable (or fragment of the variable) ...
Definition: Local.cpp:1493
static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy, Type *ToTy)
Check if a bitcast between a value of type FromTy to type ToTy would losslessly preserve the bits and...
Definition: Local.cpp:2146
static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB)
Definition: Local.cpp:1260
static bool isStructure(AllocaInst *AI)
Determine whether this alloca is a structure.
Definition: Local.cpp:1628
uint64_t getDwarfOpForBinOp(Instruction::BinaryOps Opcode)
Definition: Local.cpp:1963
static bool PhiHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr, PHINode *APN)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
Definition: Local.cpp:1469
static bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB)
Definition: Local.cpp:1292
static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ)
Return true if we can fold BB, an almost-empty BB ending in an unconditional branch to Succ,...
Definition: Local.cpp:858
static void gatherIncomingValuesToPhi(PHINode *PN, IncomingValueMap &IncomingValues)
Create a map from block to value for the operands of a given phi.
Definition: Local.cpp:955
std::optional< DIExpression * > DbgValReplacement
A replacement for a dbg.value expression.
Definition: Local.cpp:2079
static Align tryEnforceAlignment(Value *V, Align PrefAlign, const DataLayout &DL)
If the specified pointer points to an object that we control, try to modify the object's alignment to...
Definition: Local.cpp:1391
Value * getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1993
static void replaceUndefValuesInPhi(PHINode *PN, const IncomingValueMap &IncomingValues)
Replace the incoming undef values to a phi with the values from a block-to-value map.
Definition: Local.cpp:971
Value * getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1937
static unsigned replaceDominatedUsesWith(Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates)
Definition: Local.cpp:2830
static bool CanMergeValues(Value *First, Value *Second)
Return true if we can choose one of these values to use in place of the other.
Definition: Local.cpp:850
static bool simplifyAndDCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Local.cpp:667
static bool isArray(AllocaInst *AI)
Determine whether this alloca is either a VLA or an array.
Definition: Local.cpp:1622
static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress, DIBuilder &Builder, int Offset)
Definition: Local.cpp:1788
static bool areAllUsesEqual(Instruction *I)
areAllUsesEqual - Check whether the uses of a value are all the same.
Definition: Local.cpp:626
static cl::opt< bool > PHICSEDebugHash("phicse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that PHINodes's hash " "function is well-behaved w.r.t. its isEqual predicate"))
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:3274
static const std::optional< BitPart > & collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, std::map< Value *, std::optional< BitPart > > &BPS, int Depth, bool &FoundRoot)
Analyze the specified subexpression and see if it is capable of providing pieces of a bswap or bitrev...
Definition: Local.cpp:3054
static cl::opt< unsigned > PHICSENumPHISmallSize("phicse-num-phi-smallsize", cl::init(32), cl::Hidden, cl::desc("When the basic block contains not more than this number of PHI nodes, " "perform a (faster!) exhaustive search instead of set-driven one."))
static void salvageDbgAssignAddress(DbgAssignIntrinsic *DAI)
Salvage the address component of DAI.
Definition: Local.cpp:1829
static Value * selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, IncomingValueMap &IncomingValues)
Determines the value to use as the phi node input for a block.
Definition: Local.cpp:930
static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, const PredBlockVector &BBPreds, PHINode *PN)
Replace a value flowing from a block to a phi with potentially multiple instances of that value flowi...
Definition: Local.cpp:1015
static const unsigned BitPartRecursionMaxDepth
Definition: Local.cpp:113
static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:3285
static bool rewriteDebugUsers(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT, function_ref< DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr)
Point debug users of From to To using exprs given by RewriteExpr, possibly moving/undefing users to p...
Definition: Local.cpp:2084
This defines the Use class.
Value * RHS
Value * LHS
Class recording the (high level) value of a variable.
Class for arbitrary precision integers.
Definition: APInt.h:75
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1385
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1494
unsigned popcount() const
Count the number of bits set.
Definition: APInt.h:1623
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:354
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1516
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1199
an instruction to allocate memory on the stack
Definition: Instructions.h:58
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:118
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1.
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
const T & back() const
back - Get the last element.
Definition: ArrayRef.h:172
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
ArrayRef< T > drop_back(size_t N=1) const
Drop the last N elements of the array.
Definition: ArrayRef.h:208
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:264
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:325
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:323
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:381
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:254
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:504
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:217
const Instruction & front() const
Definition: BasicBlock.h:335
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:105
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:404
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
Definition: BasicBlock.cpp:141
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:293
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:132
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:224
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
size_t size() const
Definition: BasicBlock.h:333
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
void splice(BasicBlock::iterator ToIt, BasicBlock *FromBB)
Transfer all instructions from FromBB to this basic block at ToIt.
Definition: BasicBlock.h:477
const Instruction & back() const
Definition: BasicBlock.h:337
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:146
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:350
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
Definition: InstrTypes.h:391
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
This class represents a no-op cast from one type to another.
The address of a basic block.
Definition: Constants.h:879
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1769
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1471
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
Definition: InstrTypes.h:1518
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1408
CallingConv::ID getCallingConv() const
Definition: InstrTypes.h:1467
Value * getCalledOperand() const
Definition: InstrTypes.h:1401
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1490
FunctionType * getFunctionType() const
Definition: InstrTypes.h:1266
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1344
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1486
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static CastInst * CreateIntegerCast(Value *S, Type *Ty, bool isSigned, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt, BitCast, or Trunc for int -> int casts.
static CatchSwitchInst * Create(Value *ParentPad, BasicBlock *UnwindDest, unsigned NumHandlers, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2206
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2608
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2192
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2614
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1698
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This is an important base class in LLVM.
Definition: Constant.h:41
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:458
DWARF expression.
static DIExpression * append(const DIExpression *Expr, ArrayRef< uint64_t > Ops)
Append the opcodes Ops to DIExpr.
unsigned getNumElements() const
static ExtOps getExtOps(unsigned FromSize, unsigned ToSize, bool Signed)
Returns the ops for a zero- or sign-extension in a DIExpression.
static void appendOffset(SmallVectorImpl< uint64_t > &Ops, int64_t Offset)
Append Ops with operations to apply the Offset.
static DIExpression * appendOpsToArg(const DIExpression *Expr, ArrayRef< uint64_t > Ops, unsigned ArgNo, bool StackValue=false)
Create a copy of Expr by appending the given list of Ops to each instance of the operand DW_OP_LLVM_a...
static std::optional< FragmentInfo > getFragmentInfo(expr_op_iterator Start, expr_op_iterator End)
Retrieve the details of this fragment expression.
uint64_t getNumLocationOperands() const
Return the number of unique location operands referred to (via DW_OP_LLVM_arg) in this expression; th...
static DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...
static DIExpression * appendExt(const DIExpression *Expr, unsigned FromSize, unsigned ToSize, bool Signed)
Append a zero- or sign-extension to Expr.
std::optional< DIBasicType::Signedness > getSignedness() const
Return the signedness of this variable's type, or std::nullopt if this type is neither signed nor uns...
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
This represents the llvm.dbg.assign instruction.
void setKillAddress()
Kill the address component.
DIExpression * getAddressExpression() const
Value * getAddress() const
void setAddressExpression(DIExpression *NewExpr)
This represents the llvm.dbg.declare instruction.
Value * getAddress() const
This represents the llvm.dbg.label instruction.
This represents the llvm.dbg.value instruction.
This is the common base class for debug info intrinsics for variables.
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
void replaceVariableLocationOp(Value *OldValue, Value *NewValue)
Value * getVariableLocationOp(unsigned OpIdx) const
void setExpression(DIExpression *NewExpr)
DILocalVariable * getVariable() const
unsigned getNumVariableLocationOps() const
bool isAddressOfVariable() const
Does this describe the address of a local variable.
std::optional< uint64_t > getFragmentSizeInBits() const
Get the size (in bits) of the variable, or fragment of the variable that is described.
DIExpression * getExpression() const
A debug info location.
Definition: DebugLoc.h:33
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
bool hasDomTree() const
Returns true if it holds a DominatorTree.
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
const BasicBlock & getEntryBlock() const
Definition: Function.h:740
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2564
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:88
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:70
bool extractProfTotalWeight(uint64_t &TotalVal) const
Retrieve total raw weight values of a branch.
Definition: Metadata.cpp:1539
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:684
const BasicBlock * getParent() const
Definition: Instruction.h:90
bool isIdenticalToWhenDefined(const Instruction *I) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:275
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1455
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:355
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Invoke instruction.
BasicBlock * getUnwindDest() const
BasicBlock * getNormalDest() const
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
unsigned getMDKindID(StringRef Name) const
getMDKindID - Return a unique non-zero ID for the specified metadata kind.
An instruction for reading from memory.
Definition: Instructions.h:177
Value * getPointerOperand()
Definition: Instructions.h:264
static LocalAsMetadata * getIfExists(Value *Local)
Definition: Metadata.h:449
MDNode * createRange(const APInt &Lo, const APInt &Hi)
Return metadata describing the range [Lo, Hi).
Definition: MDBuilder.cpp:84
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
Metadata node.
Definition: Metadata.h:943
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1032
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1399
static MDNode * getMostGenericFPMath(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1064
static MDNode * getMostGenericRange(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1112
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1019
static MDNode * getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1184
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
iterator end()
Definition: MapVector.h:72
iterator find(const KeyT &Key)
Definition: MapVector.h:147
bool empty() const
Definition: MapVector.h:80
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:118
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
static MetadataAsValue * getIfExists(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:110
Root of the metadata hierarchy.
Definition: Metadata.h:61
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
const_block_iterator block_begin() const
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
void setIncomingValue(unsigned i, Value *V)
const_block_iterator block_end() const
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1750
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:88
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:219
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:83
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:77
value_type pop_back_val()
Definition: SetVector.h:236
size_type size() const
Definition: SmallPtrSet.h:93
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:312
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
size_type size() const
Definition: SmallSet.h:161
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void reserve(size_type N)
Definition: SmallVector.h:667
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:809
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Provides information about what library functions are available for the current target.
bool hasOptimizedCodeGen(LibFunc F) const
Tests if the function is both available and a candidate for optimized code generation.
bool has(LibFunc F) const
Tests whether a library function is available.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
Definition: TypeSize.h:322
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:267
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:255
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:237
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:258
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:252
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
Definition: Type.h:246
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:231
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:228
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1731
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
value_op_iterator value_op_end()
Definition: User.h:263
Value * getOperand(unsigned i) const
Definition: User.h:169
value_op_iterator value_op_begin()
Definition: User.h:260
iterator find(const KeyT &Val)
Definition: ValueMap.h:155
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: ValueMap.h:172
size_type size() const
Definition: ValueMap.h:140
iterator end()
Definition: ValueMap.h:135
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
iterator_range< user_iterator > users()
Definition: Value.h:421
bool use_empty() const
Definition: Value.h:344
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:996
static constexpr unsigned MaxAlignmentExponent
The maximum alignment for instructions.
Definition: Value.h:789
user_iterator_impl< User > user_iterator
Definition: Value.h:390
bool hasName() const
Definition: Value.h:261
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:383
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
Definition: DenseSet.h:90
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
Definition: ilist_node.h:82
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1506
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
m_Intrinsic_Ty< Opnd0 >::Ty m_BitReverse(const Opnd0 &Op0)
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2 >::Ty m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2 >::Ty m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:136
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:537
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:218
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
@ DW_OP_LLVM_arg
Only used in LLVM metadata.
Definition: Dwarf.h:146
@ ebStrict
This corresponds to "fpexcept.strict".
Definition: FPEnv.h:41
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
TinyPtrVector< DbgDeclareInst * > FindDbgDeclareUses(Value *V)
Finds dbg.declare intrinsics declaring local variables as living in the memory that 'V' points to.
Definition: DebugInfo.cpp:46
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1839
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:537
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
BasicBlock * changeToInvokeAndSplitBasicBlock(CallInst *CI, BasicBlock *UnwindEdge, DomTreeUpdater *DTU=nullptr)
Convert the CallInst to InvokeInst with the specified unwind edge basic block.
Definition: Local.cpp:2328
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:126
std::pair< unsigned, unsigned > removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than its terminator and any present EH pad instructi...
Definition: Local.cpp:2219
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:2847
void salvageDebugInfoForDbgValues(Instruction &I, ArrayRef< DbgVariableIntrinsic * > Insns)
Implementation of salvageDebugInfo, applying only to instructions in Insns, rather than all debug use...
Definition: Local.cpp:1862
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1367
auto successors(const MachineBasicBlock *BB)
bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI)
Return true if this is a call to an allocation function that does not have side effects that we are r...
CallInst * changeToCall(InvokeInst *II, DomTreeUpdater *DTU=nullptr)
This function converts the specified invoke into a normal call.
Definition: Local.cpp:2308
bool isMathLibCallNoop(const CallBase *Call, const TargetLibraryInfo *TLI)
Check whether the given call has no side-effects.
void copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source)
Copy the metadata from the source instruction to the destination (the replacement for the source inst...
Definition: Local.cpp:2744
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
bool hasNItemsOrLess(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;})
Returns true if the sequence [Begin, End) has N or less items.
Definition: STLExtras.h:2535
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:748
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:725
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode * > &InsertedPHIs)
Propagate dbg.value intrinsics through the newly inserted PHIs.
Definition: Local.cpp:1708
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
MDNode * intersectAccessGroups(const Instruction *Inst1, const Instruction *Inst2)
Compute the access-group list of access groups that Inst1 and Inst2 are both in.
bool canSimplifyInvokeNoUnwind(const Function *F)
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1826
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:398
bool wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
Definition: Local.cpp:417
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
Definition: Local.cpp:1070
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: DebugInfo.cpp:93
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:3290
MDNode * getValidBranchWeightMDNode(const Instruction &I)
Get the valid branch weights metadata node.
Align getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to ensure that the alignment of V is at least PrefAlign bytes.
Definition: Local.cpp:1439
bool wouldInstructionBeTriviallyDeadOnUnusedPaths(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction has no side effects on any paths other than whe...
Definition: Local.cpp:405
bool LowerDbgDeclare(Function &F)
Lowers llvm.dbg.declare intrinsics into appropriate set of llvm.dbg.value intrinsics.
Definition: Local.cpp:1634
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
Definition: Function.cpp:2140
CallInst * createCallMatchingInvoke(InvokeInst *II)
Create a call that matches the invoke II in terms of arguments, attributes, debug information,...
Definition: Local.cpp:2282
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
Instruction * removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
Definition: Local.cpp:2569
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition: Local.cpp:2796
DebugLoc getDebugValueLoc(DbgVariableIntrinsic *DII)
Produce a DebugLoc to use for each dbg.declare that is promoted to a dbg.value.
Definition: DebugInfo.cpp:126
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:67
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
Definition: Local.cpp:1520
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
Definition: Local.cpp:2862
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2644
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2243
bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)
Point debug users of From to To or salvage them.
Definition: Local.cpp:2164
Value * salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Ops, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:2032
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2730
void dropDebugUsers(Instruction &I)
Remove the debug intrinsic instructions for the given instruction.
Definition: Local.cpp:2957
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!...
Definition: Local.cpp:765
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in @llvm.dbg intrinsics with undef.
Definition: Local.cpp:614
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
Definition: Local.cpp:2964
void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a range metadata node to a new load instruction.
Definition: Local.cpp:2934
void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a nonnull metadata node to a new load instruction.
Definition: Local.cpp:2909
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
Definition: Local.cpp:3401
void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, int Offset=0)
Replaces multiple llvm.dbg.value instructions when the alloca it describes is replaced with a new val...
Definition: Local.cpp:1811
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
bool RecursivelyDeleteTriviallyDeadInstructionsPermissive(SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
Same functionality as RecursivelyDeleteTriviallyDeadInstructions, but allow instructions that are not...
Definition: Local.cpp:552
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:184
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:2018
gep_type_iterator gep_type_begin(const User *GEP)
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1976
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
Definition: Local.cpp:645
bool inferAttributesFromOthers(Function &F)
If we can infer one attribute from another on the declaration of a function, explicitly materialize t...
Definition: Local.cpp:3508
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3474
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:613
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, const TargetLibraryInfo *TLI)
Given a CallInst, check if it calls a string function known to CodeGen, and mark it with NoBuiltin if...
Definition: Local.cpp:3391
unsigned pred_size(const MachineBasicBlock *BB)
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
Definition: Local.cpp:2607
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
Definition: Local.cpp:1374
bool isAssumeWithEmptyBundle(AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
Definition: Local.cpp:2880
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:491
bool replaceDbgDeclare(Value *Address, Value *NewAddress, DIBuilder &Builder, uint8_t DIExprFlags, int Offset)
Replaces llvm.dbg.declare instruction when the address it describes is replaced with a new value.
Definition: Local.cpp:1770
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
#define NDEBUG
Definition: regutils.h:48
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:51
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:233
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117