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 K->setMetadata(Kind,
2698 break;
2699 case LLVMContext::MD_dereferenceable:
2700 case LLVMContext::MD_dereferenceable_or_null:
2701 K->setMetadata(Kind,
2703 break;
2704 case LLVMContext::MD_preserve_access_index:
2705 // Preserve !preserve.access.index in K.
2706 break;
2707 case LLVMContext::MD_noundef:
2708 // If K does move, keep noundef if it is present in both instructions.
2709 if (DoesKMove)
2710 K->setMetadata(Kind, JMD);
2711 break;
2712 case LLVMContext::MD_nontemporal:
2713 // Preserve !nontemporal if it is present on both instructions.
2714 K->setMetadata(Kind, JMD);
2715 break;
2716 }
2717 }
2718 // Set !invariant.group from J if J has it. If both instructions have it
2719 // then we will just pick it from J - even when they are different.
2720 // Also make sure that K is load or store - f.e. combining bitcast with load
2721 // could produce bitcast with invariant.group metadata, which is invalid.
2722 // FIXME: we should try to preserve both invariant.group md if they are
2723 // different, but right now instruction can only have one invariant.group.
2724 if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2725 if (isa<LoadInst>(K) || isa<StoreInst>(K))
2726 K->setMetadata(LLVMContext::MD_invariant_group, JMD);
2727}
2728
2730 bool KDominatesJ) {
2731 unsigned KnownIDs[] = {
2732 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2733 LLVMContext::MD_noalias, LLVMContext::MD_range,
2734 LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull,
2735 LLVMContext::MD_invariant_group, LLVMContext::MD_align,
2736 LLVMContext::MD_dereferenceable,
2737 LLVMContext::MD_dereferenceable_or_null,
2738 LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index,
2739 LLVMContext::MD_nontemporal, LLVMContext::MD_noundef};
2740 combineMetadata(K, J, KnownIDs, KDominatesJ);
2741}
2742
2743void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) {
2745 Source.getAllMetadata(MD);
2746 MDBuilder MDB(Dest.getContext());
2747 Type *NewType = Dest.getType();
2748 const DataLayout &DL = Source.getModule()->getDataLayout();
2749 for (const auto &MDPair : MD) {
2750 unsigned ID = MDPair.first;
2751 MDNode *N = MDPair.second;
2752 // Note, essentially every kind of metadata should be preserved here! This
2753 // routine is supposed to clone a load instruction changing *only its type*.
2754 // The only metadata it makes sense to drop is metadata which is invalidated
2755 // when the pointer type changes. This should essentially never be the case
2756 // in LLVM, but we explicitly switch over only known metadata to be
2757 // conservatively correct. If you are adding metadata to LLVM which pertains
2758 // to loads, you almost certainly want to add it here.
2759 switch (ID) {
2760 case LLVMContext::MD_dbg:
2761 case LLVMContext::MD_tbaa:
2762 case LLVMContext::MD_prof:
2763 case LLVMContext::MD_fpmath:
2764 case LLVMContext::MD_tbaa_struct:
2765 case LLVMContext::MD_invariant_load:
2766 case LLVMContext::MD_alias_scope:
2767 case LLVMContext::MD_noalias:
2768 case LLVMContext::MD_nontemporal:
2769 case LLVMContext::MD_mem_parallel_loop_access:
2770 case LLVMContext::MD_access_group:
2771 case LLVMContext::MD_noundef:
2772 // All of these directly apply.
2773 Dest.setMetadata(ID, N);
2774 break;
2775
2776 case LLVMContext::MD_nonnull:
2777 copyNonnullMetadata(Source, N, Dest);
2778 break;
2779
2780 case LLVMContext::MD_align:
2781 case LLVMContext::MD_dereferenceable:
2782 case LLVMContext::MD_dereferenceable_or_null:
2783 // These only directly apply if the new type is also a pointer.
2784 if (NewType->isPointerTy())
2785 Dest.setMetadata(ID, N);
2786 break;
2787
2788 case LLVMContext::MD_range:
2789 copyRangeMetadata(DL, Source, N, Dest);
2790 break;
2791 }
2792 }
2793}
2794
2796 auto *ReplInst = dyn_cast<Instruction>(Repl);
2797 if (!ReplInst)
2798 return;
2799
2800 // Patch the replacement so that it is not more restrictive than the value
2801 // being replaced.
2802 // Note that if 'I' is a load being replaced by some operation,
2803 // for example, by an arithmetic operation, then andIRFlags()
2804 // would just erase all math flags from the original arithmetic
2805 // operation, which is clearly not wanted and not needed.
2806 if (!isa<LoadInst>(I))
2807 ReplInst->andIRFlags(I);
2808
2809 // FIXME: If both the original and replacement value are part of the
2810 // same control-flow region (meaning that the execution of one
2811 // guarantees the execution of the other), then we can combine the
2812 // noalias scopes here and do better than the general conservative
2813 // answer used in combineMetadata().
2814
2815 // In general, GVN unifies expressions over different control-flow
2816 // regions, and so we need a conservative combination of the noalias
2817 // scopes.
2818 static const unsigned KnownIDs[] = {
2819 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2820 LLVMContext::MD_noalias, LLVMContext::MD_range,
2821 LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
2822 LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull,
2823 LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index,
2824 LLVMContext::MD_noundef, LLVMContext::MD_nontemporal};
2825 combineMetadata(ReplInst, I, KnownIDs, false);
2826}
2827
2828template <typename RootType, typename DominatesFn>
2830 const RootType &Root,
2831 const DominatesFn &Dominates) {
2832 assert(From->getType() == To->getType());
2833
2834 unsigned Count = 0;
2835 for (Use &U : llvm::make_early_inc_range(From->uses())) {
2836 if (!Dominates(Root, U))
2837 continue;
2838 U.set(To);
2839 LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()
2840 << "' as " << *To << " in " << *U << "\n");
2841 ++Count;
2842 }
2843 return Count;
2844}
2845
2847 assert(From->getType() == To->getType());
2848 auto *BB = From->getParent();
2849 unsigned Count = 0;
2850
2851 for (Use &U : llvm::make_early_inc_range(From->uses())) {
2852 auto *I = cast<Instruction>(U.getUser());
2853 if (I->getParent() == BB)
2854 continue;
2855 U.set(To);
2856 ++Count;
2857 }
2858 return Count;
2859}
2860
2862 DominatorTree &DT,
2863 const BasicBlockEdge &Root) {
2864 auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2865 return DT.dominates(Root, U);
2866 };
2867 return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2868}
2869
2871 DominatorTree &DT,
2872 const BasicBlock *BB) {
2873 auto Dominates = [&DT](const BasicBlock *BB, const Use &U) {
2874 return DT.dominates(BB, U);
2875 };
2876 return ::replaceDominatedUsesWith(From, To, BB, Dominates);
2877}
2878
2880 const TargetLibraryInfo &TLI) {
2881 // Check if the function is specifically marked as a gc leaf function.
2882 if (Call->hasFnAttr("gc-leaf-function"))
2883 return true;
2884 if (const Function *F = Call->getCalledFunction()) {
2885 if (F->hasFnAttribute("gc-leaf-function"))
2886 return true;
2887
2888 if (auto IID = F->getIntrinsicID()) {
2889 // Most LLVM intrinsics do not take safepoints.
2890 return IID != Intrinsic::experimental_gc_statepoint &&
2891 IID != Intrinsic::experimental_deoptimize &&
2892 IID != Intrinsic::memcpy_element_unordered_atomic &&
2893 IID != Intrinsic::memmove_element_unordered_atomic;
2894 }
2895 }
2896
2897 // Lib calls can be materialized by some passes, and won't be
2898 // marked as 'gc-leaf-function.' All available Libcalls are
2899 // GC-leaf.
2900 LibFunc LF;
2901 if (TLI.getLibFunc(*Call, LF)) {
2902 return TLI.has(LF);
2903 }
2904
2905 return false;
2906}
2907
2909 LoadInst &NewLI) {
2910 auto *NewTy = NewLI.getType();
2911
2912 // This only directly applies if the new type is also a pointer.
2913 if (NewTy->isPointerTy()) {
2914 NewLI.setMetadata(LLVMContext::MD_nonnull, N);
2915 return;
2916 }
2917
2918 // The only other translation we can do is to integral loads with !range
2919 // metadata.
2920 if (!NewTy->isIntegerTy())
2921 return;
2922
2923 MDBuilder MDB(NewLI.getContext());
2924 const Value *Ptr = OldLI.getPointerOperand();
2925 auto *ITy = cast<IntegerType>(NewTy);
2926 auto *NullInt = ConstantExpr::getPtrToInt(
2927 ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
2928 auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
2929 NewLI.setMetadata(LLVMContext::MD_range,
2930 MDB.createRange(NonNullInt, NullInt));
2931}
2932
2934 MDNode *N, LoadInst &NewLI) {
2935 auto *NewTy = NewLI.getType();
2936 // Simply copy the metadata if the type did not change.
2937 if (NewTy == OldLI.getType()) {
2938 NewLI.setMetadata(LLVMContext::MD_range, N);
2939 return;
2940 }
2941
2942 // Give up unless it is converted to a pointer where there is a single very
2943 // valuable mapping we can do reliably.
2944 // FIXME: It would be nice to propagate this in more ways, but the type
2945 // conversions make it hard.
2946 if (!NewTy->isPointerTy())
2947 return;
2948
2949 unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
2951 MDNode *NN = MDNode::get(OldLI.getContext(), std::nullopt);
2952 NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
2953 }
2954}
2955
2958 findDbgUsers(DbgUsers, &I);
2959 for (auto *DII : DbgUsers)
2960 DII->eraseFromParent();
2961}
2962
2964 BasicBlock *BB) {
2965 // Since we are moving the instructions out of its basic block, we do not
2966 // retain their original debug locations (DILocations) and debug intrinsic
2967 // instructions.
2968 //
2969 // Doing so would degrade the debugging experience and adversely affect the
2970 // accuracy of profiling information.
2971 //
2972 // Currently, when hoisting the instructions, we take the following actions:
2973 // - Remove their debug intrinsic instructions.
2974 // - Set their debug locations to the values from the insertion point.
2975 //
2976 // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
2977 // need to be deleted, is because there will not be any instructions with a
2978 // DILocation in either branch left after performing the transformation. We
2979 // can only insert a dbg.value after the two branches are joined again.
2980 //
2981 // See PR38762, PR39243 for more details.
2982 //
2983 // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
2984 // encode predicated DIExpressions that yield different results on different
2985 // code paths.
2986
2987 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
2988 Instruction *I = &*II;
2989 I->dropUBImplyingAttrsAndUnknownMetadata();
2990 if (I->isUsedByMetadata())
2991 dropDebugUsers(*I);
2992 if (I->isDebugOrPseudoInst()) {
2993 // Remove DbgInfo and pseudo probe Intrinsics.
2994 II = I->eraseFromParent();
2995 continue;
2996 }
2997 I->setDebugLoc(InsertPt->getDebugLoc());
2998 ++II;
2999 }
3000 DomBlock->splice(InsertPt->getIterator(), BB, BB->begin(),
3001 BB->getTerminator()->getIterator());
3002}
3003
3004namespace {
3005
3006/// A potential constituent of a bitreverse or bswap expression. See
3007/// collectBitParts for a fuller explanation.
3008struct BitPart {
3009 BitPart(Value *P, unsigned BW) : Provider(P) {
3010 Provenance.resize(BW);
3011 }
3012
3013 /// The Value that this is a bitreverse/bswap of.
3014 Value *Provider;
3015
3016 /// The "provenance" of each bit. Provenance[A] = B means that bit A
3017 /// in Provider becomes bit B in the result of this expression.
3018 SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
3019
3020 enum { Unset = -1 };
3021};
3022
3023} // end anonymous namespace
3024
3025/// Analyze the specified subexpression and see if it is capable of providing
3026/// pieces of a bswap or bitreverse. The subexpression provides a potential
3027/// piece of a bswap or bitreverse if it can be proved that each non-zero bit in
3028/// the output of the expression came from a corresponding bit in some other
3029/// value. This function is recursive, and the end result is a mapping of
3030/// bitnumber to bitnumber. It is the caller's responsibility to validate that
3031/// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
3032///
3033/// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
3034/// that the expression deposits the low byte of %X into the high byte of the
3035/// result and that all other bits are zero. This expression is accepted and a
3036/// BitPart is returned with Provider set to %X and Provenance[24-31] set to
3037/// [0-7].
3038///
3039/// For vector types, all analysis is performed at the per-element level. No
3040/// cross-element analysis is supported (shuffle/insertion/reduction), and all
3041/// constant masks must be splatted across all elements.
3042///
3043/// To avoid revisiting values, the BitPart results are memoized into the
3044/// provided map. To avoid unnecessary copying of BitParts, BitParts are
3045/// constructed in-place in the \c BPS map. Because of this \c BPS needs to
3046/// store BitParts objects, not pointers. As we need the concept of a nullptr
3047/// BitParts (Value has been analyzed and the analysis failed), we an Optional
3048/// type instead to provide the same functionality.
3049///
3050/// Because we pass around references into \c BPS, we must use a container that
3051/// does not invalidate internal references (std::map instead of DenseMap).
3052static const std::optional<BitPart> &
3053collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
3054 std::map<Value *, std::optional<BitPart>> &BPS, int Depth,
3055 bool &FoundRoot) {
3056 auto I = BPS.find(V);
3057 if (I != BPS.end())
3058 return I->second;
3059
3060 auto &Result = BPS[V] = std::nullopt;
3061 auto BitWidth = V->getType()->getScalarSizeInBits();
3062
3063 // Can't do integer/elements > 128 bits.
3064 if (BitWidth > 128)
3065 return Result;
3066
3067 // Prevent stack overflow by limiting the recursion depth
3069 LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n");
3070 return Result;
3071 }
3072
3073 if (auto *I = dyn_cast<Instruction>(V)) {
3074 Value *X, *Y;
3075 const APInt *C;
3076
3077 // If this is an or instruction, it may be an inner node of the bswap.
3078 if (match(V, m_Or(m_Value(X), m_Value(Y)))) {
3079 // Check we have both sources and they are from the same provider.
3080 const auto &A = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3081 Depth + 1, FoundRoot);
3082 if (!A || !A->Provider)
3083 return Result;
3084
3085 const auto &B = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
3086 Depth + 1, FoundRoot);
3087 if (!B || A->Provider != B->Provider)
3088 return Result;
3089
3090 // Try and merge the two together.
3091 Result = BitPart(A->Provider, BitWidth);
3092 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) {
3093 if (A->Provenance[BitIdx] != BitPart::Unset &&
3094 B->Provenance[BitIdx] != BitPart::Unset &&
3095 A->Provenance[BitIdx] != B->Provenance[BitIdx])
3096 return Result = std::nullopt;
3097
3098 if (A->Provenance[BitIdx] == BitPart::Unset)
3099 Result->Provenance[BitIdx] = B->Provenance[BitIdx];
3100 else
3101 Result->Provenance[BitIdx] = A->Provenance[BitIdx];
3102 }
3103
3104 return Result;
3105 }
3106
3107 // If this is a logical shift by a constant, recurse then shift the result.
3108 if (match(V, m_LogicalShift(m_Value(X), m_APInt(C)))) {
3109 const APInt &BitShift = *C;
3110
3111 // Ensure the shift amount is defined.
3112 if (BitShift.uge(BitWidth))
3113 return Result;
3114
3115 // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3116 if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0)
3117 return Result;
3118
3119 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3120 Depth + 1, FoundRoot);
3121 if (!Res)
3122 return Result;
3123 Result = Res;
3124
3125 // Perform the "shift" on BitProvenance.
3126 auto &P = Result->Provenance;
3127 if (I->getOpcode() == Instruction::Shl) {
3128 P.erase(std::prev(P.end(), BitShift.getZExtValue()), P.end());
3129 P.insert(P.begin(), BitShift.getZExtValue(), BitPart::Unset);
3130 } else {
3131 P.erase(P.begin(), std::next(P.begin(), BitShift.getZExtValue()));
3132 P.insert(P.end(), BitShift.getZExtValue(), BitPart::Unset);
3133 }
3134
3135 return Result;
3136 }
3137
3138 // If this is a logical 'and' with a mask that clears bits, recurse then
3139 // unset the appropriate bits.
3140 if (match(V, m_And(m_Value(X), m_APInt(C)))) {
3141 const APInt &AndMask = *C;
3142
3143 // Check that the mask allows a multiple of 8 bits for a bswap, for an
3144 // early exit.
3145 unsigned NumMaskedBits = AndMask.popcount();
3146 if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3147 return Result;
3148
3149 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3150 Depth + 1, FoundRoot);
3151 if (!Res)
3152 return Result;
3153 Result = Res;
3154
3155 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3156 // If the AndMask is zero for this bit, clear the bit.
3157 if (AndMask[BitIdx] == 0)
3158 Result->Provenance[BitIdx] = BitPart::Unset;
3159 return Result;
3160 }
3161
3162 // If this is a zext instruction zero extend the result.
3163 if (match(V, m_ZExt(m_Value(X)))) {
3164 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3165 Depth + 1, FoundRoot);
3166 if (!Res)
3167 return Result;
3168
3169 Result = BitPart(Res->Provider, BitWidth);
3170 auto NarrowBitWidth = X->getType()->getScalarSizeInBits();
3171 for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3172 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3173 for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx)
3174 Result->Provenance[BitIdx] = BitPart::Unset;
3175 return Result;
3176 }
3177
3178 // If this is a truncate instruction, extract the lower bits.
3179 if (match(V, m_Trunc(m_Value(X)))) {
3180 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3181 Depth + 1, FoundRoot);
3182 if (!Res)
3183 return Result;
3184
3185 Result = BitPart(Res->Provider, BitWidth);
3186 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3187 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3188 return Result;
3189 }
3190
3191 // BITREVERSE - most likely due to us previous matching a partial
3192 // bitreverse.
3193 if (match(V, m_BitReverse(m_Value(X)))) {
3194 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3195 Depth + 1, FoundRoot);
3196 if (!Res)
3197 return Result;
3198
3199 Result = BitPart(Res->Provider, BitWidth);
3200 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3201 Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3202 return Result;
3203 }
3204
3205 // BSWAP - most likely due to us previous matching a partial bswap.
3206 if (match(V, m_BSwap(m_Value(X)))) {
3207 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3208 Depth + 1, FoundRoot);
3209 if (!Res)
3210 return Result;
3211
3212 unsigned ByteWidth = BitWidth / 8;
3213 Result = BitPart(Res->Provider, BitWidth);
3214 for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3215 unsigned ByteBitOfs = ByteIdx * 8;
3216 for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3217 Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] =
3218 Res->Provenance[ByteBitOfs + BitIdx];
3219 }
3220 return Result;
3221 }
3222
3223 // Funnel 'double' shifts take 3 operands, 2 inputs and the shift
3224 // amount (modulo).
3225 // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
3226 // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW))
3227 if (match(V, m_FShl(m_Value(X), m_Value(Y), m_APInt(C))) ||
3228 match(V, m_FShr(m_Value(X), m_Value(Y), m_APInt(C)))) {
3229 // We can treat fshr as a fshl by flipping the modulo amount.
3230 unsigned ModAmt = C->urem(BitWidth);
3231 if (cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fshr)
3232 ModAmt = BitWidth - ModAmt;
3233
3234 // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3235 if (!MatchBitReversals && (ModAmt % 8) != 0)
3236 return Result;
3237
3238 // Check we have both sources and they are from the same provider.
3239 const auto &LHS = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3240 Depth + 1, FoundRoot);
3241 if (!LHS || !LHS->Provider)
3242 return Result;
3243
3244 const auto &RHS = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
3245 Depth + 1, FoundRoot);
3246 if (!RHS || LHS->Provider != RHS->Provider)
3247 return Result;
3248
3249 unsigned StartBitRHS = BitWidth - ModAmt;
3250 Result = BitPart(LHS->Provider, BitWidth);
3251 for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3252 Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx];
3253 for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3254 Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS];
3255 return Result;
3256 }
3257 }
3258
3259 // If we've already found a root input value then we're never going to merge
3260 // these back together.
3261 if (FoundRoot)
3262 return Result;
3263
3264 // Okay, we got to something that isn't a shift, 'or', 'and', etc. This must
3265 // be the root input value to the bswap/bitreverse.
3266 FoundRoot = true;
3267 Result = BitPart(V, BitWidth);
3268 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3269 Result->Provenance[BitIdx] = BitIdx;
3270 return Result;
3271}
3272
3273static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
3274 unsigned BitWidth) {
3275 if (From % 8 != To % 8)
3276 return false;
3277 // Convert from bit indices to byte indices and check for a byte reversal.
3278 From >>= 3;
3279 To >>= 3;
3280 BitWidth >>= 3;
3281 return From == BitWidth - To - 1;
3282}
3283
3284static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
3285 unsigned BitWidth) {
3286 return From == BitWidth - To - 1;
3287}
3288
3290 Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
3291 SmallVectorImpl<Instruction *> &InsertedInsts) {
3292 if (!match(I, m_Or(m_Value(), m_Value())) &&
3293 !match(I, m_FShl(m_Value(), m_Value(), m_Value())) &&
3294 !match(I, m_FShr(m_Value(), m_Value(), m_Value())))
3295 return false;
3296 if (!MatchBSwaps && !MatchBitReversals)
3297 return false;
3298 Type *ITy = I->getType();
3299 if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() > 128)
3300 return false; // Can't do integer/elements > 128 bits.
3301
3302 // Try to find all the pieces corresponding to the bswap.
3303 bool FoundRoot = false;
3304 std::map<Value *, std::optional<BitPart>> BPS;
3305 const auto &Res =
3306 collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0, FoundRoot);
3307 if (!Res)
3308 return false;
3309 ArrayRef<int8_t> BitProvenance = Res->Provenance;
3310 assert(all_of(BitProvenance,
3311 [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) &&
3312 "Illegal bit provenance index");
3313
3314 // If the upper bits are zero, then attempt to perform as a truncated op.
3315 Type *DemandedTy = ITy;
3316 if (BitProvenance.back() == BitPart::Unset) {
3317 while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset)
3318 BitProvenance = BitProvenance.drop_back();
3319 if (BitProvenance.empty())
3320 return false; // TODO - handle null value?
3321 DemandedTy = Type::getIntNTy(I->getContext(), BitProvenance.size());
3322 if (auto *IVecTy = dyn_cast<VectorType>(ITy))
3323 DemandedTy = VectorType::get(DemandedTy, IVecTy);
3324 }
3325
3326 // Check BitProvenance hasn't found a source larger than the result type.
3327 unsigned DemandedBW = DemandedTy->getScalarSizeInBits();
3328 if (DemandedBW > ITy->getScalarSizeInBits())
3329 return false;
3330
3331 // Now, is the bit permutation correct for a bswap or a bitreverse? We can
3332 // only byteswap values with an even number of bytes.
3333 APInt DemandedMask = APInt::getAllOnes(DemandedBW);
3334 bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
3335 bool OKForBitReverse = MatchBitReversals;
3336 for (unsigned BitIdx = 0;
3337 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
3338 if (BitProvenance[BitIdx] == BitPart::Unset) {
3339 DemandedMask.clearBit(BitIdx);
3340 continue;
3341 }
3342 OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[BitIdx], BitIdx,
3343 DemandedBW);
3344 OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[BitIdx],
3345 BitIdx, DemandedBW);
3346 }
3347
3348 Intrinsic::ID Intrin;
3349 if (OKForBSwap)
3350 Intrin = Intrinsic::bswap;
3351 else if (OKForBitReverse)
3352 Intrin = Intrinsic::bitreverse;
3353 else
3354 return false;
3355
3356 Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
3357 Value *Provider = Res->Provider;
3358
3359 // We may need to truncate the provider.
3360 if (DemandedTy != Provider->getType()) {
3361 auto *Trunc =
3362 CastInst::CreateIntegerCast(Provider, DemandedTy, false, "trunc", I);
3363 InsertedInsts.push_back(Trunc);
3364 Provider = Trunc;
3365 }
3366
3367 Instruction *Result = CallInst::Create(F, Provider, "rev", I);
3368 InsertedInsts.push_back(Result);
3369
3370 if (!DemandedMask.isAllOnes()) {
3371 auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
3372 Result = BinaryOperator::Create(Instruction::And, Result, Mask, "mask", I);
3373 InsertedInsts.push_back(Result);
3374 }
3375
3376 // We may need to zeroextend back to the result type.
3377 if (ITy != Result->getType()) {
3378 auto *ExtInst = CastInst::CreateIntegerCast(Result, ITy, false, "zext", I);
3379 InsertedInsts.push_back(ExtInst);
3380 }
3381
3382 return true;
3383}
3384
3385// CodeGen has special handling for some string functions that may replace
3386// them with target-specific intrinsics. Since that'd skip our interceptors
3387// in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
3388// we mark affected calls as NoBuiltin, which will disable optimization
3389// in CodeGen.
3391 CallInst *CI, const TargetLibraryInfo *TLI) {
3392 Function *F = CI->getCalledFunction();
3393 LibFunc Func;
3394 if (F && !F->hasLocalLinkage() && F->hasName() &&
3395 TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
3396 !F->doesNotAccessMemory())
3397 CI->addFnAttr(Attribute::NoBuiltin);
3398}
3399
3401 // We can't have a PHI with a metadata type.
3402 if (I->getOperand(OpIdx)->getType()->isMetadataTy())
3403 return false;
3404
3405 // Early exit.
3406 if (!isa<Constant>(I->getOperand(OpIdx)))
3407 return true;
3408
3409 switch (I->getOpcode()) {
3410 default:
3411 return true;
3412 case Instruction::Call:
3413 case Instruction::Invoke: {
3414 const auto &CB = cast<CallBase>(*I);
3415
3416 // Can't handle inline asm. Skip it.
3417 if (CB.isInlineAsm())
3418 return false;
3419
3420 // Constant bundle operands may need to retain their constant-ness for
3421 // correctness.
3422 if (CB.isBundleOperand(OpIdx))
3423 return false;
3424
3425 if (OpIdx < CB.arg_size()) {
3426 // Some variadic intrinsics require constants in the variadic arguments,
3427 // which currently aren't markable as immarg.
3428 if (isa<IntrinsicInst>(CB) &&
3429 OpIdx >= CB.getFunctionType()->getNumParams()) {
3430 // This is known to be OK for stackmap.
3431 return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
3432 }
3433
3434 // gcroot is a special case, since it requires a constant argument which
3435 // isn't also required to be a simple ConstantInt.
3436 if (CB.getIntrinsicID() == Intrinsic::gcroot)
3437 return false;
3438
3439 // Some intrinsic operands are required to be immediates.
3440 return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
3441 }
3442
3443 // It is never allowed to replace the call argument to an intrinsic, but it
3444 // may be possible for a call.
3445 return !isa<IntrinsicInst>(CB);
3446 }
3447 case Instruction::ShuffleVector:
3448 // Shufflevector masks are constant.
3449 return OpIdx != 2;
3450 case Instruction::Switch:
3451 case Instruction::ExtractValue:
3452 // All operands apart from the first are constant.
3453 return OpIdx == 0;
3454 case Instruction::InsertValue:
3455 // All operands apart from the first and the second are constant.
3456 return OpIdx < 2;
3457 case Instruction::Alloca:
3458 // Static allocas (constant size in the entry block) are handled by
3459 // prologue/epilogue insertion so they're free anyway. We definitely don't
3460 // want to make them non-constant.
3461 return !cast<AllocaInst>(I)->isStaticAlloca();
3462 case Instruction::GetElementPtr:
3463 if (OpIdx == 0)
3464 return true;
3466 for (auto E = std::next(It, OpIdx); It != E; ++It)
3467 if (It.isStruct())
3468 return false;
3469 return true;
3470 }
3471}
3472
3474 // First: Check if it's a constant
3475 if (Constant *C = dyn_cast<Constant>(Condition))
3476 return ConstantExpr::getNot(C);
3477
3478 // Second: If the condition is already inverted, return the original value
3479 Value *NotCondition;
3480 if (match(Condition, m_Not(m_Value(NotCondition))))
3481 return NotCondition;
3482
3483 BasicBlock *Parent = nullptr;
3484 Instruction *Inst = dyn_cast<Instruction>(Condition);
3485 if (Inst)
3486 Parent = Inst->getParent();
3487 else if (Argument *Arg = dyn_cast<Argument>(Condition))
3488 Parent = &Arg->getParent()->getEntryBlock();
3489 assert(Parent && "Unsupported condition to invert");
3490
3491 // Third: Check all the users for an invert
3492 for (User *U : Condition->users())
3493 if (Instruction *I = dyn_cast<Instruction>(U))
3494 if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
3495 return I;
3496
3497 // Last option: Create a new instruction
3498 auto *Inverted =
3499 BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv");
3500 if (Inst && !isa<PHINode>(Inst))
3501 Inverted->insertAfter(Inst);
3502 else
3503 Inverted->insertBefore(&*Parent->getFirstInsertionPt());
3504 return Inverted;
3505}
3506
3508 // Note: We explicitly check for attributes rather than using cover functions
3509 // because some of the cover functions include the logic being implemented.
3510
3511 bool Changed = false;
3512 // readnone + not convergent implies nosync
3513 if (!F.hasFnAttribute(Attribute::NoSync) &&
3514 F.doesNotAccessMemory() && !F.isConvergent()) {
3515 F.setNoSync();
3516 Changed = true;
3517 }
3518
3519 // readonly implies nofree
3520 if (!F.hasFnAttribute(Attribute::NoFree) && F.onlyReadsMemory()) {
3521 F.setDoesNotFreeMemory();
3522 Changed = true;
3523 }
3524
3525 // willreturn implies mustprogress
3526 if (!F.hasFnAttribute(Attribute::MustProgress) && F.willReturn()) {
3527 F.setMustProgress();
3528 Changed = true;
3529 }
3530
3531 // TODO: There are a bunch of cases of restrictive memory effects we
3532 // can infer by inspecting arguments of argmemonly-ish functions.
3533
3534 return Changed;
3535}
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:2829
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:3273
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:3053
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:3284
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:316
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:314
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:372
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:245
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:495
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:208
const Instruction & front() const
Definition: BasicBlock.h:326
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:395
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:284
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:215
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:324
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:468
const Instruction & back() const
Definition: BasicBlock.h:328
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:341
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:2558
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:77
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:208
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:66
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:301
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:177
size_type size() const
Definition: SmallSet.h:159
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:532
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:994
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:381
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:2846
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:2743
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:2536
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:3289
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:2795
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:2861
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:2729
void dropDebugUsers(Instruction &I)
Remove the debug intrinsic instructions for the given instruction.
Definition: Local.cpp:2956
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:2963
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:2933
void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a nonnull metadata node to a new load instruction.
Definition: Local.cpp:2908
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:3400
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:3507
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3473
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:3390
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:2879
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