LLVM 18.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.
428 if (isa<DbgVariableIntrinsic>(I))
429 return false;
430
431 if (const DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) {
432 if (DLI->getLabel())
433 return false;
434 return true;
435 }
436
437 if (auto *CB = dyn_cast<CallBase>(I))
438 if (isRemovableAlloc(CB, TLI))
439 return true;
440
441 if (!I->willReturn()) {
442 auto *II = dyn_cast<IntrinsicInst>(I);
443 if (!II)
444 return false;
445
446 // TODO: These intrinsics are not safe to remove, because this may remove
447 // a well-defined trap.
448 switch (II->getIntrinsicID()) {
449 case Intrinsic::wasm_trunc_signed:
450 case Intrinsic::wasm_trunc_unsigned:
451 case Intrinsic::ptrauth_auth:
452 case Intrinsic::ptrauth_resign:
453 return true;
454 default:
455 return false;
456 }
457 }
458
459 if (!I->mayHaveSideEffects())
460 return true;
461
462 // Special case intrinsics that "may have side effects" but can be deleted
463 // when dead.
464 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
465 // Safe to delete llvm.stacksave and launder.invariant.group if dead.
466 if (II->getIntrinsicID() == Intrinsic::stacksave ||
467 II->getIntrinsicID() == Intrinsic::launder_invariant_group)
468 return true;
469
470 if (II->isLifetimeStartOrEnd()) {
471 auto *Arg = II->getArgOperand(1);
472 // Lifetime intrinsics are dead when their right-hand is undef.
473 if (isa<UndefValue>(Arg))
474 return true;
475 // If the right-hand is an alloc, global, or argument and the only uses
476 // are lifetime intrinsics then the intrinsics are dead.
477 if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg))
478 return llvm::all_of(Arg->uses(), [](Use &Use) {
479 if (IntrinsicInst *IntrinsicUse =
480 dyn_cast<IntrinsicInst>(Use.getUser()))
481 return IntrinsicUse->isLifetimeStartOrEnd();
482 return false;
483 });
484 return false;
485 }
486
487 // Assumptions are dead if their condition is trivially true. Guards on
488 // true are operationally no-ops. In the future we can consider more
489 // sophisticated tradeoffs for guards considering potential for check
490 // widening, but for now we keep things simple.
491 if ((II->getIntrinsicID() == Intrinsic::assume &&
492 isAssumeWithEmptyBundle(cast<AssumeInst>(*II))) ||
493 II->getIntrinsicID() == Intrinsic::experimental_guard) {
494 if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
495 return !Cond->isZero();
496
497 return false;
498 }
499
500 if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(I)) {
501 std::optional<fp::ExceptionBehavior> ExBehavior =
502 FPI->getExceptionBehavior();
503 return *ExBehavior != fp::ebStrict;
504 }
505 }
506
507 if (auto *Call = dyn_cast<CallBase>(I)) {
508 if (Value *FreedOp = getFreedOperand(Call, TLI))
509 if (Constant *C = dyn_cast<Constant>(FreedOp))
510 return C->isNullValue() || isa<UndefValue>(C);
511 if (isMathLibCallNoop(Call, TLI))
512 return true;
513 }
514
515 // Non-volatile atomic loads from constants can be removed.
516 if (auto *LI = dyn_cast<LoadInst>(I))
517 if (auto *GV = dyn_cast<GlobalVariable>(
518 LI->getPointerOperand()->stripPointerCasts()))
519 if (!LI->isVolatile() && GV->isConstant())
520 return true;
521
522 return false;
523}
524
525/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
526/// trivially dead instruction, delete it. If that makes any of its operands
527/// trivially dead, delete them too, recursively. Return true if any
528/// instructions were deleted.
530 Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU,
531 std::function<void(Value *)> AboutToDeleteCallback) {
532 Instruction *I = dyn_cast<Instruction>(V);
533 if (!I || !isInstructionTriviallyDead(I, TLI))
534 return false;
535
537 DeadInsts.push_back(I);
538 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
539 AboutToDeleteCallback);
540
541 return true;
542}
543
546 MemorySSAUpdater *MSSAU,
547 std::function<void(Value *)> AboutToDeleteCallback) {
548 unsigned S = 0, E = DeadInsts.size(), Alive = 0;
549 for (; S != E; ++S) {
550 auto *I = dyn_cast_or_null<Instruction>(DeadInsts[S]);
551 if (!I || !isInstructionTriviallyDead(I)) {
552 DeadInsts[S] = nullptr;
553 ++Alive;
554 }
555 }
556 if (Alive == E)
557 return false;
558 RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
559 AboutToDeleteCallback);
560 return true;
561}
562
565 MemorySSAUpdater *MSSAU,
566 std::function<void(Value *)> AboutToDeleteCallback) {
567 // Process the dead instruction list until empty.
568 while (!DeadInsts.empty()) {
569 Value *V = DeadInsts.pop_back_val();
570 Instruction *I = cast_or_null<Instruction>(V);
571 if (!I)
572 continue;
574 "Live instruction found in dead worklist!");
575 assert(I->use_empty() && "Instructions with uses are not dead.");
576
577 // Don't lose the debug info while deleting the instructions.
579
580 if (AboutToDeleteCallback)
581 AboutToDeleteCallback(I);
582
583 // Null out all of the instruction's operands to see if any operand becomes
584 // dead as we go.
585 for (Use &OpU : I->operands()) {
586 Value *OpV = OpU.get();
587 OpU.set(nullptr);
588
589 if (!OpV->use_empty())
590 continue;
591
592 // If the operand is an instruction that became dead as we nulled out the
593 // operand, and if it is 'trivially' dead, delete it in a future loop
594 // iteration.
595 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
596 if (isInstructionTriviallyDead(OpI, TLI))
597 DeadInsts.push_back(OpI);
598 }
599 if (MSSAU)
600 MSSAU->removeMemoryAccess(I);
601
602 I->eraseFromParent();
603 }
604}
605
608 findDbgUsers(DbgUsers, I);
609 for (auto *DII : DbgUsers)
610 DII->setKillLocation();
611 return !DbgUsers.empty();
612}
613
614/// areAllUsesEqual - Check whether the uses of a value are all the same.
615/// This is similar to Instruction::hasOneUse() except this will also return
616/// true when there are no uses or multiple uses that all refer to the same
617/// value.
619 Value::user_iterator UI = I->user_begin();
620 Value::user_iterator UE = I->user_end();
621 if (UI == UE)
622 return true;
623
624 User *TheUse = *UI;
625 for (++UI; UI != UE; ++UI) {
626 if (*UI != TheUse)
627 return false;
628 }
629 return true;
630}
631
632/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
633/// dead PHI node, due to being a def-use chain of single-use nodes that
634/// either forms a cycle or is terminated by a trivially dead instruction,
635/// delete it. If that makes any of its operands trivially dead, delete them
636/// too, recursively. Return true if a change was made.
638 const TargetLibraryInfo *TLI,
639 llvm::MemorySSAUpdater *MSSAU) {
641 for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
642 I = cast<Instruction>(*I->user_begin())) {
643 if (I->use_empty())
645
646 // If we find an instruction more than once, we're on a cycle that
647 // won't prove fruitful.
648 if (!Visited.insert(I).second) {
649 // Break the cycle and delete the instruction and its operands.
650 I->replaceAllUsesWith(PoisonValue::get(I->getType()));
652 return true;
653 }
654 }
655 return false;
656}
657
658static bool
661 const DataLayout &DL,
662 const TargetLibraryInfo *TLI) {
663 if (isInstructionTriviallyDead(I, TLI)) {
665
666 // Null out all of the instruction's operands to see if any operand becomes
667 // dead as we go.
668 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
669 Value *OpV = I->getOperand(i);
670 I->setOperand(i, nullptr);
671
672 if (!OpV->use_empty() || I == OpV)
673 continue;
674
675 // If the operand is an instruction that became dead as we nulled out the
676 // operand, and if it is 'trivially' dead, delete it in a future loop
677 // iteration.
678 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
679 if (isInstructionTriviallyDead(OpI, TLI))
680 WorkList.insert(OpI);
681 }
682
683 I->eraseFromParent();
684
685 return true;
686 }
687
688 if (Value *SimpleV = simplifyInstruction(I, DL)) {
689 // Add the users to the worklist. CAREFUL: an instruction can use itself,
690 // in the case of a phi node.
691 for (User *U : I->users()) {
692 if (U != I) {
693 WorkList.insert(cast<Instruction>(U));
694 }
695 }
696
697 // Replace the instruction with its simplified value.
698 bool Changed = false;
699 if (!I->use_empty()) {
700 I->replaceAllUsesWith(SimpleV);
701 Changed = true;
702 }
703 if (isInstructionTriviallyDead(I, TLI)) {
704 I->eraseFromParent();
705 Changed = true;
706 }
707 return Changed;
708 }
709 return false;
710}
711
712/// SimplifyInstructionsInBlock - Scan the specified basic block and try to
713/// simplify any instructions in it and recursively delete dead instructions.
714///
715/// This returns true if it changed the code, note that it can delete
716/// instructions in other blocks as well in this block.
718 const TargetLibraryInfo *TLI) {
719 bool MadeChange = false;
720 const DataLayout &DL = BB->getModule()->getDataLayout();
721
722#ifndef NDEBUG
723 // In debug builds, ensure that the terminator of the block is never replaced
724 // or deleted by these simplifications. The idea of simplification is that it
725 // cannot introduce new instructions, and there is no way to replace the
726 // terminator of a block without introducing a new instruction.
727 AssertingVH<Instruction> TerminatorVH(&BB->back());
728#endif
729
731 // Iterate over the original function, only adding insts to the worklist
732 // if they actually need to be revisited. This avoids having to pre-init
733 // the worklist with the entire function's worth of instructions.
734 for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end());
735 BI != E;) {
736 assert(!BI->isTerminator());
737 Instruction *I = &*BI;
738 ++BI;
739
740 // We're visiting this instruction now, so make sure it's not in the
741 // worklist from an earlier visit.
742 if (!WorkList.count(I))
743 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
744 }
745
746 while (!WorkList.empty()) {
747 Instruction *I = WorkList.pop_back_val();
748 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
749 }
750 return MadeChange;
751}
752
753//===----------------------------------------------------------------------===//
754// Control Flow Graph Restructuring.
755//
756
758 DomTreeUpdater *DTU) {
759
760 // If BB has single-entry PHI nodes, fold them.
761 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
762 Value *NewVal = PN->getIncomingValue(0);
763 // Replace self referencing PHI with poison, it must be dead.
764 if (NewVal == PN) NewVal = PoisonValue::get(PN->getType());
765 PN->replaceAllUsesWith(NewVal);
766 PN->eraseFromParent();
767 }
768
769 BasicBlock *PredBB = DestBB->getSinglePredecessor();
770 assert(PredBB && "Block doesn't have a single predecessor!");
771
772 bool ReplaceEntryBB = PredBB->isEntryBlock();
773
774 // DTU updates: Collect all the edges that enter
775 // PredBB. These dominator edges will be redirected to DestBB.
777
778 if (DTU) {
779 // To avoid processing the same predecessor more than once.
781 Updates.reserve(Updates.size() + 2 * pred_size(PredBB) + 1);
782 for (BasicBlock *PredOfPredBB : predecessors(PredBB))
783 // This predecessor of PredBB may already have DestBB as a successor.
784 if (PredOfPredBB != PredBB)
785 if (SeenPreds.insert(PredOfPredBB).second)
786 Updates.push_back({DominatorTree::Insert, PredOfPredBB, DestBB});
787 SeenPreds.clear();
788 for (BasicBlock *PredOfPredBB : predecessors(PredBB))
789 if (SeenPreds.insert(PredOfPredBB).second)
790 Updates.push_back({DominatorTree::Delete, PredOfPredBB, PredBB});
791 Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
792 }
793
794 // Zap anything that took the address of DestBB. Not doing this will give the
795 // address an invalid value.
796 if (DestBB->hasAddressTaken()) {
797 BlockAddress *BA = BlockAddress::get(DestBB);
798 Constant *Replacement =
801 BA->getType()));
802 BA->destroyConstant();
803 }
804
805 // Anything that branched to PredBB now branches to DestBB.
806 PredBB->replaceAllUsesWith(DestBB);
807
808 // Splice all the instructions from PredBB to DestBB.
809 PredBB->getTerminator()->eraseFromParent();
810 DestBB->splice(DestBB->begin(), PredBB);
811 new UnreachableInst(PredBB->getContext(), PredBB);
812
813 // If the PredBB is the entry block of the function, move DestBB up to
814 // become the entry block after we erase PredBB.
815 if (ReplaceEntryBB)
816 DestBB->moveAfter(PredBB);
817
818 if (DTU) {
819 assert(PredBB->size() == 1 &&
820 isa<UnreachableInst>(PredBB->getTerminator()) &&
821 "The successor list of PredBB isn't empty before "
822 "applying corresponding DTU updates.");
823 DTU->applyUpdatesPermissive(Updates);
824 DTU->deleteBB(PredBB);
825 // Recalculation of DomTree is needed when updating a forward DomTree and
826 // the Entry BB is replaced.
827 if (ReplaceEntryBB && DTU->hasDomTree()) {
828 // The entry block was removed and there is no external interface for
829 // the dominator tree to be notified of this change. In this corner-case
830 // we recalculate the entire tree.
831 DTU->recalculate(*(DestBB->getParent()));
832 }
833 }
834
835 else {
836 PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr.
837 }
838}
839
840/// Return true if we can choose one of these values to use in place of the
841/// other. Note that we will always choose the non-undef value to keep.
842static bool CanMergeValues(Value *First, Value *Second) {
843 return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
844}
845
846/// Return true if we can fold BB, an almost-empty BB ending in an unconditional
847/// branch to Succ, into Succ.
848///
849/// Assumption: Succ is the single successor for BB.
851 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
852
853 LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
854 << Succ->getName() << "\n");
855 // Shortcut, if there is only a single predecessor it must be BB and merging
856 // is always safe
857 if (Succ->getSinglePredecessor()) return true;
858
859 // Make a list of the predecessors of BB
861
862 // Look at all the phi nodes in Succ, to see if they present a conflict when
863 // merging these blocks
864 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
865 PHINode *PN = cast<PHINode>(I);
866
867 // If the incoming value from BB is again a PHINode in
868 // BB which has the same incoming value for *PI as PN does, we can
869 // merge the phi nodes and then the blocks can still be merged
870 PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
871 if (BBPN && BBPN->getParent() == BB) {
872 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
873 BasicBlock *IBB = PN->getIncomingBlock(PI);
874 if (BBPreds.count(IBB) &&
876 PN->getIncomingValue(PI))) {
878 << "Can't fold, phi node " << PN->getName() << " in "
879 << Succ->getName() << " is conflicting with "
880 << BBPN->getName() << " with regard to common predecessor "
881 << IBB->getName() << "\n");
882 return false;
883 }
884 }
885 } else {
886 Value* Val = PN->getIncomingValueForBlock(BB);
887 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
888 // See if the incoming value for the common predecessor is equal to the
889 // one for BB, in which case this phi node will not prevent the merging
890 // of the block.
891 BasicBlock *IBB = PN->getIncomingBlock(PI);
892 if (BBPreds.count(IBB) &&
893 !CanMergeValues(Val, PN->getIncomingValue(PI))) {
894 LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()
895 << " in " << Succ->getName()
896 << " is conflicting with regard to common "
897 << "predecessor " << IBB->getName() << "\n");
898 return false;
899 }
900 }
901 }
902 }
903
904 return true;
905}
906
909
910/// Determines the value to use as the phi node input for a block.
911///
912/// Select between \p OldVal any value that we know flows from \p BB
913/// to a particular phi on the basis of which one (if either) is not
914/// undef. Update IncomingValues based on the selected value.
915///
916/// \param OldVal The value we are considering selecting.
917/// \param BB The block that the value flows in from.
918/// \param IncomingValues A map from block-to-value for other phi inputs
919/// that we have examined.
920///
921/// \returns the selected value.
923 IncomingValueMap &IncomingValues) {
924 if (!isa<UndefValue>(OldVal)) {
925 assert((!IncomingValues.count(BB) ||
926 IncomingValues.find(BB)->second == OldVal) &&
927 "Expected OldVal to match incoming value from BB!");
928
929 IncomingValues.insert(std::make_pair(BB, OldVal));
930 return OldVal;
931 }
932
933 IncomingValueMap::const_iterator It = IncomingValues.find(BB);
934 if (It != IncomingValues.end()) return It->second;
935
936 return OldVal;
937}
938
939/// Create a map from block to value for the operands of a
940/// given phi.
941///
942/// Create a map from block to value for each non-undef value flowing
943/// into \p PN.
944///
945/// \param PN The phi we are collecting the map for.
946/// \param IncomingValues [out] The map from block to value for this phi.
948 IncomingValueMap &IncomingValues) {
949 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
950 BasicBlock *BB = PN->getIncomingBlock(i);
951 Value *V = PN->getIncomingValue(i);
952
953 if (!isa<UndefValue>(V))
954 IncomingValues.insert(std::make_pair(BB, V));
955 }
956}
957
958/// Replace the incoming undef values to a phi with the values
959/// from a block-to-value map.
960///
961/// \param PN The phi we are replacing the undefs in.
962/// \param IncomingValues A map from block to value.
964 const IncomingValueMap &IncomingValues) {
965 SmallVector<unsigned> TrueUndefOps;
966 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
967 Value *V = PN->getIncomingValue(i);
968
969 if (!isa<UndefValue>(V)) continue;
970
971 BasicBlock *BB = PN->getIncomingBlock(i);
972 IncomingValueMap::const_iterator It = IncomingValues.find(BB);
973
974 // Keep track of undef/poison incoming values. Those must match, so we fix
975 // them up below if needed.
976 // Note: this is conservatively correct, but we could try harder and group
977 // the undef values per incoming basic block.
978 if (It == IncomingValues.end()) {
979 TrueUndefOps.push_back(i);
980 continue;
981 }
982
983 // There is a defined value for this incoming block, so map this undef
984 // incoming value to the defined value.
985 PN->setIncomingValue(i, It->second);
986 }
987
988 // If there are both undef and poison values incoming, then convert those
989 // values to undef. It is invalid to have different values for the same
990 // incoming block.
991 unsigned PoisonCount = count_if(TrueUndefOps, [&](unsigned i) {
992 return isa<PoisonValue>(PN->getIncomingValue(i));
993 });
994 if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) {
995 for (unsigned i : TrueUndefOps)
997 }
998}
999
1000/// Replace a value flowing from a block to a phi with
1001/// potentially multiple instances of that value flowing from the
1002/// block's predecessors to the phi.
1003///
1004/// \param BB The block with the value flowing into the phi.
1005/// \param BBPreds The predecessors of BB.
1006/// \param PN The phi that we are updating.
1008 const PredBlockVector &BBPreds,
1009 PHINode *PN) {
1010 Value *OldVal = PN->removeIncomingValue(BB, false);
1011 assert(OldVal && "No entry in PHI for Pred BB!");
1012
1013 IncomingValueMap IncomingValues;
1014
1015 // We are merging two blocks - BB, and the block containing PN - and
1016 // as a result we need to redirect edges from the predecessors of BB
1017 // to go to the block containing PN, and update PN
1018 // accordingly. Since we allow merging blocks in the case where the
1019 // predecessor and successor blocks both share some predecessors,
1020 // and where some of those common predecessors might have undef
1021 // values flowing into PN, we want to rewrite those values to be
1022 // consistent with the non-undef values.
1023
1024 gatherIncomingValuesToPhi(PN, IncomingValues);
1025
1026 // If this incoming value is one of the PHI nodes in BB, the new entries
1027 // in the PHI node are the entries from the old PHI.
1028 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
1029 PHINode *OldValPN = cast<PHINode>(OldVal);
1030 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
1031 // Note that, since we are merging phi nodes and BB and Succ might
1032 // have common predecessors, we could end up with a phi node with
1033 // identical incoming branches. This will be cleaned up later (and
1034 // will trigger asserts if we try to clean it up now, without also
1035 // simplifying the corresponding conditional branch).
1036 BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
1037 Value *PredVal = OldValPN->getIncomingValue(i);
1038 Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
1039 IncomingValues);
1040
1041 // And add a new incoming value for this predecessor for the
1042 // newly retargeted branch.
1043 PN->addIncoming(Selected, PredBB);
1044 }
1045 } else {
1046 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
1047 // Update existing incoming values in PN for this
1048 // predecessor of BB.
1049 BasicBlock *PredBB = BBPreds[i];
1050 Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
1051 IncomingValues);
1052
1053 // And add a new incoming value for this predecessor for the
1054 // newly retargeted branch.
1055 PN->addIncoming(Selected, PredBB);
1056 }
1057 }
1058
1059 replaceUndefValuesInPhi(PN, IncomingValues);
1060}
1061
1063 DomTreeUpdater *DTU) {
1064 assert(BB != &BB->getParent()->getEntryBlock() &&
1065 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
1066
1067 // We can't eliminate infinite loops.
1068 BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
1069 if (BB == Succ) return false;
1070
1071 // Check to see if merging these blocks would cause conflicts for any of the
1072 // phi nodes in BB or Succ. If not, we can safely merge.
1073 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
1074
1075 // Check for cases where Succ has multiple predecessors and a PHI node in BB
1076 // has uses which will not disappear when the PHI nodes are merged. It is
1077 // possible to handle such cases, but difficult: it requires checking whether
1078 // BB dominates Succ, which is non-trivial to calculate in the case where
1079 // Succ has multiple predecessors. Also, it requires checking whether
1080 // constructing the necessary self-referential PHI node doesn't introduce any
1081 // conflicts; this isn't too difficult, but the previous code for doing this
1082 // was incorrect.
1083 //
1084 // Note that if this check finds a live use, BB dominates Succ, so BB is
1085 // something like a loop pre-header (or rarely, a part of an irreducible CFG);
1086 // folding the branch isn't profitable in that case anyway.
1087 if (!Succ->getSinglePredecessor()) {
1088 BasicBlock::iterator BBI = BB->begin();
1089 while (isa<PHINode>(*BBI)) {
1090 for (Use &U : BBI->uses()) {
1091 if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
1092 if (PN->getIncomingBlock(U) != BB)
1093 return false;
1094 } else {
1095 return false;
1096 }
1097 }
1098 ++BBI;
1099 }
1100 }
1101
1102 // 'BB' and 'BB->Pred' are loop latches, bail out to presrve inner loop
1103 // metadata.
1104 //
1105 // FIXME: This is a stop-gap solution to preserve inner-loop metadata given
1106 // current status (that loop metadata is implemented as metadata attached to
1107 // the branch instruction in the loop latch block). To quote from review
1108 // comments, "the current representation of loop metadata (using a loop latch
1109 // terminator attachment) is known to be fundamentally broken. Loop latches
1110 // are not uniquely associated with loops (both in that a latch can be part of
1111 // multiple loops and a loop may have multiple latches). Loop headers are. The
1112 // solution to this problem is also known: Add support for basic block
1113 // metadata, and attach loop metadata to the loop header."
1114 //
1115 // Why bail out:
1116 // In this case, we expect 'BB' is the latch for outer-loop and 'BB->Pred' is
1117 // the latch for inner-loop (see reason below), so bail out to prerserve
1118 // inner-loop metadata rather than eliminating 'BB' and attaching its metadata
1119 // to this inner-loop.
1120 // - The reason we believe 'BB' and 'BB->Pred' have different inner-most
1121 // loops: assuming 'BB' and 'BB->Pred' are from the same inner-most loop L,
1122 // then 'BB' is the header and latch of 'L' and thereby 'L' must consist of
1123 // one self-looping basic block, which is contradictory with the assumption.
1124 //
1125 // To illustrate how inner-loop metadata is dropped:
1126 //
1127 // CFG Before
1128 //
1129 // BB is while.cond.exit, attached with loop metdata md2.
1130 // BB->Pred is for.body, attached with loop metadata md1.
1131 //
1132 // entry
1133 // |
1134 // v
1135 // ---> while.cond -------------> while.end
1136 // | |
1137 // | v
1138 // | while.body
1139 // | |
1140 // | v
1141 // | for.body <---- (md1)
1142 // | | |______|
1143 // | v
1144 // | while.cond.exit (md2)
1145 // | |
1146 // |_______|
1147 //
1148 // CFG After
1149 //
1150 // while.cond1 is the merge of while.cond.exit and while.cond above.
1151 // for.body is attached with md2, and md1 is dropped.
1152 // If LoopSimplify runs later (as a part of loop pass), it could create
1153 // dedicated exits for inner-loop (essentially adding `while.cond.exit`
1154 // back), but won't it won't see 'md1' nor restore it for the inner-loop.
1155 //
1156 // entry
1157 // |
1158 // v
1159 // ---> while.cond1 -------------> while.end
1160 // | |
1161 // | v
1162 // | while.body
1163 // | |
1164 // | v
1165 // | for.body <---- (md2)
1166 // |_______| |______|
1167 if (Instruction *TI = BB->getTerminator())
1168 if (TI->hasMetadata(LLVMContext::MD_loop))
1169 for (BasicBlock *Pred : predecessors(BB))
1170 if (Instruction *PredTI = Pred->getTerminator())
1171 if (PredTI->hasMetadata(LLVMContext::MD_loop))
1172 return false;
1173
1174 LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
1175
1177 if (DTU) {
1178 // To avoid processing the same predecessor more than once.
1180 // All predecessors of BB will be moved to Succ.
1181 SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ));
1182 Updates.reserve(Updates.size() + 2 * pred_size(BB) + 1);
1183 for (auto *PredOfBB : predecessors(BB))
1184 // This predecessor of BB may already have Succ as a successor.
1185 if (!PredsOfSucc.contains(PredOfBB))
1186 if (SeenPreds.insert(PredOfBB).second)
1187 Updates.push_back({DominatorTree::Insert, PredOfBB, Succ});
1188 SeenPreds.clear();
1189 for (auto *PredOfBB : predecessors(BB))
1190 if (SeenPreds.insert(PredOfBB).second)
1191 Updates.push_back({DominatorTree::Delete, PredOfBB, BB});
1192 Updates.push_back({DominatorTree::Delete, BB, Succ});
1193 }
1194
1195 if (isa<PHINode>(Succ->begin())) {
1196 // If there is more than one pred of succ, and there are PHI nodes in
1197 // the successor, then we need to add incoming edges for the PHI nodes
1198 //
1199 const PredBlockVector BBPreds(predecessors(BB));
1200
1201 // Loop over all of the PHI nodes in the successor of BB.
1202 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
1203 PHINode *PN = cast<PHINode>(I);
1204
1205 redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
1206 }
1207 }
1208
1209 if (Succ->getSinglePredecessor()) {
1210 // BB is the only predecessor of Succ, so Succ will end up with exactly
1211 // the same predecessors BB had.
1212
1213 // Copy over any phi, debug or lifetime instruction.
1215 Succ->splice(Succ->getFirstNonPHI()->getIterator(), BB);
1216 } else {
1217 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
1218 // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
1219 assert(PN->use_empty() && "There shouldn't be any uses here!");
1220 PN->eraseFromParent();
1221 }
1222 }
1223
1224 // If the unconditional branch we replaced contains llvm.loop metadata, we
1225 // add the metadata to the branch instructions in the predecessors.
1226 if (Instruction *TI = BB->getTerminator())
1227 if (MDNode *LoopMD = TI->getMetadata(LLVMContext::MD_loop))
1228 for (BasicBlock *Pred : predecessors(BB))
1229 Pred->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopMD);
1230
1231 // Everything that jumped to BB now goes to Succ.
1232 BB->replaceAllUsesWith(Succ);
1233 if (!Succ->hasName()) Succ->takeName(BB);
1234
1235 // Clear the successor list of BB to match updates applying to DTU later.
1236 if (BB->getTerminator())
1237 BB->back().eraseFromParent();
1238 new UnreachableInst(BB->getContext(), BB);
1239 assert(succ_empty(BB) && "The successor list of BB isn't empty before "
1240 "applying corresponding DTU updates.");
1241
1242 if (DTU)
1243 DTU->applyUpdates(Updates);
1244
1245 DeleteDeadBlock(BB, DTU);
1246
1247 return true;
1248}
1249
1250static bool
1253 // This implementation doesn't currently consider undef operands
1254 // specially. Theoretically, two phis which are identical except for
1255 // one having an undef where the other doesn't could be collapsed.
1256
1257 bool Changed = false;
1258
1259 // Examine each PHI.
1260 // Note that increment of I must *NOT* be in the iteration_expression, since
1261 // we don't want to immediately advance when we restart from the beginning.
1262 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) {
1263 ++I;
1264 // Is there an identical PHI node in this basic block?
1265 // Note that we only look in the upper square's triangle,
1266 // we already checked that the lower triangle PHI's aren't identical.
1267 for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
1268 if (ToRemove.contains(DuplicatePN))
1269 continue;
1270 if (!DuplicatePN->isIdenticalToWhenDefined(PN))
1271 continue;
1272 // A duplicate. Replace this PHI with the base PHI.
1273 ++NumPHICSEs;
1274 DuplicatePN->replaceAllUsesWith(PN);
1275 ToRemove.insert(DuplicatePN);
1276 Changed = true;
1277
1278 // The RAUW can change PHIs that we already visited.
1279 I = BB->begin();
1280 break; // Start over from the beginning.
1281 }
1282 }
1283 return Changed;
1284}
1285
1286static bool
1289 // This implementation doesn't currently consider undef operands
1290 // specially. Theoretically, two phis which are identical except for
1291 // one having an undef where the other doesn't could be collapsed.
1292
1293 struct PHIDenseMapInfo {
1294 static PHINode *getEmptyKey() {
1296 }
1297
1298 static PHINode *getTombstoneKey() {
1300 }
1301
1302 static bool isSentinel(PHINode *PN) {
1303 return PN == getEmptyKey() || PN == getTombstoneKey();
1304 }
1305
1306 // WARNING: this logic must be kept in sync with
1307 // Instruction::isIdenticalToWhenDefined()!
1308 static unsigned getHashValueImpl(PHINode *PN) {
1309 // Compute a hash value on the operands. Instcombine will likely have
1310 // sorted them, which helps expose duplicates, but we have to check all
1311 // the operands to be safe in case instcombine hasn't run.
1312 return static_cast<unsigned>(hash_combine(
1315 }
1316
1317 static unsigned getHashValue(PHINode *PN) {
1318#ifndef NDEBUG
1319 // If -phicse-debug-hash was specified, return a constant -- this
1320 // will force all hashing to collide, so we'll exhaustively search
1321 // the table for a match, and the assertion in isEqual will fire if
1322 // there's a bug causing equal keys to hash differently.
1323 if (PHICSEDebugHash)
1324 return 0;
1325#endif
1326 return getHashValueImpl(PN);
1327 }
1328
1329 static bool isEqualImpl(PHINode *LHS, PHINode *RHS) {
1330 if (isSentinel(LHS) || isSentinel(RHS))
1331 return LHS == RHS;
1332 return LHS->isIdenticalTo(RHS);
1333 }
1334
1335 static bool isEqual(PHINode *LHS, PHINode *RHS) {
1336 // These comparisons are nontrivial, so assert that equality implies
1337 // hash equality (DenseMap demands this as an invariant).
1338 bool Result = isEqualImpl(LHS, RHS);
1339 assert(!Result || (isSentinel(LHS) && LHS == RHS) ||
1341 return Result;
1342 }
1343 };
1344
1345 // Set of unique PHINodes.
1347 PHISet.reserve(4 * PHICSENumPHISmallSize);
1348
1349 // Examine each PHI.
1350 bool Changed = false;
1351 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
1352 if (ToRemove.contains(PN))
1353 continue;
1354 auto Inserted = PHISet.insert(PN);
1355 if (!Inserted.second) {
1356 // A duplicate. Replace this PHI with its duplicate.
1357 ++NumPHICSEs;
1358 PN->replaceAllUsesWith(*Inserted.first);
1359 ToRemove.insert(PN);
1360 Changed = true;
1361
1362 // The RAUW can change PHIs that we already visited. Start over from the
1363 // beginning.
1364 PHISet.clear();
1365 I = BB->begin();
1366 }
1367 }
1368
1369 return Changed;
1370}
1371
1374 if (
1375#ifndef NDEBUG
1376 !PHICSEDebugHash &&
1377#endif
1381}
1382
1385 bool Changed = EliminateDuplicatePHINodes(BB, ToRemove);
1386 for (PHINode *PN : ToRemove)
1387 PN->eraseFromParent();
1388 return Changed;
1389}
1390
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)
1676 ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
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 (const 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
1993static void handleSSAValueOperands(uint64_t CurrentLocOps,
1995 SmallVectorImpl<Value *> &AdditionalValues,
1996 Instruction *I) {
1997 if (!CurrentLocOps) {
1998 Opcodes.append({dwarf::DW_OP_LLVM_arg, 0});
1999 CurrentLocOps = 1;
2000 }
2001 Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps});
2002 AdditionalValues.push_back(I->getOperand(1));
2003}
2004
2007 SmallVectorImpl<Value *> &AdditionalValues) {
2008 // Handle binary operations with constant integer operands as a special case.
2009 auto *ConstInt = dyn_cast<ConstantInt>(BI->getOperand(1));
2010 // Values wider than 64 bits cannot be represented within a DIExpression.
2011 if (ConstInt && ConstInt->getBitWidth() > 64)
2012 return nullptr;
2013
2014 Instruction::BinaryOps BinOpcode = BI->getOpcode();
2015 // Push any Constant Int operand onto the expression stack.
2016 if (ConstInt) {
2017 uint64_t Val = ConstInt->getSExtValue();
2018 // Add or Sub Instructions with a constant operand can potentially be
2019 // simplified.
2020 if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
2021 uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
2023 return BI->getOperand(0);
2024 }
2025 Opcodes.append({dwarf::DW_OP_constu, Val});
2026 } else {
2027 handleSSAValueOperands(CurrentLocOps, Opcodes, AdditionalValues, BI);
2028 }
2029
2030 // Add salvaged binary operator to expression stack, if it has a valid
2031 // representation in a DIExpression.
2032 uint64_t DwarfBinOp = getDwarfOpForBinOp(BinOpcode);
2033 if (!DwarfBinOp)
2034 return nullptr;
2035 Opcodes.push_back(DwarfBinOp);
2036 return BI->getOperand(0);
2037}
2038
2040 // The signedness of the operation is implicit in the typed stack, signed and
2041 // unsigned instructions map to the same DWARF opcode.
2042 switch (Pred) {
2043 case CmpInst::ICMP_EQ:
2044 return dwarf::DW_OP_eq;
2045 case CmpInst::ICMP_NE:
2046 return dwarf::DW_OP_ne;
2047 case CmpInst::ICMP_UGT:
2048 case CmpInst::ICMP_SGT:
2049 return dwarf::DW_OP_gt;
2050 case CmpInst::ICMP_UGE:
2051 case CmpInst::ICMP_SGE:
2052 return dwarf::DW_OP_ge;
2053 case CmpInst::ICMP_ULT:
2054 case CmpInst::ICMP_SLT:
2055 return dwarf::DW_OP_lt;
2056 case CmpInst::ICMP_ULE:
2057 case CmpInst::ICMP_SLE:
2058 return dwarf::DW_OP_le;
2059 default:
2060 return 0;
2061 }
2062}
2063
2066 SmallVectorImpl<Value *> &AdditionalValues) {
2067 // Handle icmp operations with constant integer operands as a special case.
2068 auto *ConstInt = dyn_cast<ConstantInt>(Icmp->getOperand(1));
2069 // Values wider than 64 bits cannot be represented within a DIExpression.
2070 if (ConstInt && ConstInt->getBitWidth() > 64)
2071 return nullptr;
2072 // Push any Constant Int operand onto the expression stack.
2073 if (ConstInt) {
2074 if (Icmp->isSigned())
2075 Opcodes.push_back(dwarf::DW_OP_consts);
2076 else
2077 Opcodes.push_back(dwarf::DW_OP_constu);
2078 uint64_t Val = ConstInt->getSExtValue();
2079 Opcodes.push_back(Val);
2080 } else {
2081 handleSSAValueOperands(CurrentLocOps, Opcodes, AdditionalValues, Icmp);
2082 }
2083
2084 // Add salvaged binary operator to expression stack, if it has a valid
2085 // representation in a DIExpression.
2086 uint64_t DwarfIcmpOp = getDwarfOpForIcmpPred(Icmp->getPredicate());
2087 if (!DwarfIcmpOp)
2088 return nullptr;
2089 Opcodes.push_back(DwarfIcmpOp);
2090 return Icmp->getOperand(0);
2091}
2092
2095 SmallVectorImpl<Value *> &AdditionalValues) {
2096 auto &M = *I.getModule();
2097 auto &DL = M.getDataLayout();
2098
2099 if (auto *CI = dyn_cast<CastInst>(&I)) {
2100 Value *FromValue = CI->getOperand(0);
2101 // No-op casts are irrelevant for debug info.
2102 if (CI->isNoopCast(DL)) {
2103 return FromValue;
2104 }
2105
2106 Type *Type = CI->getType();
2107 if (Type->isPointerTy())
2108 Type = DL.getIntPtrType(Type);
2109 // Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged.
2110 if (Type->isVectorTy() ||
2111 !(isa<TruncInst>(&I) || isa<SExtInst>(&I) || isa<ZExtInst>(&I) ||
2112 isa<IntToPtrInst>(&I) || isa<PtrToIntInst>(&I)))
2113 return nullptr;
2114
2115 llvm::Type *FromType = FromValue->getType();
2116 if (FromType->isPointerTy())
2117 FromType = DL.getIntPtrType(FromType);
2118
2119 unsigned FromTypeBitSize = FromType->getScalarSizeInBits();
2120 unsigned ToTypeBitSize = Type->getScalarSizeInBits();
2121
2122 auto ExtOps = DIExpression::getExtOps(FromTypeBitSize, ToTypeBitSize,
2123 isa<SExtInst>(&I));
2124 Ops.append(ExtOps.begin(), ExtOps.end());
2125 return FromValue;
2126 }
2127
2128 if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))
2129 return getSalvageOpsForGEP(GEP, DL, CurrentLocOps, Ops, AdditionalValues);
2130 if (auto *BI = dyn_cast<BinaryOperator>(&I))
2131 return getSalvageOpsForBinOp(BI, CurrentLocOps, Ops, AdditionalValues);
2132 if (auto *IC = dyn_cast<ICmpInst>(&I))
2133 return getSalvageOpsForIcmpOp(IC, CurrentLocOps, Ops, AdditionalValues);
2134
2135 // *Not* to do: we should not attempt to salvage load instructions,
2136 // because the validity and lifetime of a dbg.value containing
2137 // DW_OP_deref becomes difficult to analyze. See PR40628 for examples.
2138 return nullptr;
2139}
2140
2141/// A replacement for a dbg.value expression.
2142using DbgValReplacement = std::optional<DIExpression *>;
2143
2144/// Point debug users of \p From to \p To using exprs given by \p RewriteExpr,
2145/// possibly moving/undefing users to prevent use-before-def. Returns true if
2146/// changes are made.
2148 Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT,
2150 // Find debug users of From.
2153 if (Users.empty())
2154 return false;
2155
2156 // Prevent use-before-def of To.
2157 bool Changed = false;
2159 if (isa<Instruction>(&To)) {
2160 bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint;
2161
2162 for (auto *DII : Users) {
2163 // It's common to see a debug user between From and DomPoint. Move it
2164 // after DomPoint to preserve the variable update without any reordering.
2165 if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) {
2166 LLVM_DEBUG(dbgs() << "MOVE: " << *DII << '\n');
2167 DII->moveAfter(&DomPoint);
2168 Changed = true;
2169
2170 // Users which otherwise aren't dominated by the replacement value must
2171 // be salvaged or deleted.
2172 } else if (!DT.dominates(&DomPoint, DII)) {
2173 UndefOrSalvage.insert(DII);
2174 }
2175 }
2176 }
2177
2178 // Update debug users without use-before-def risk.
2179 for (auto *DII : Users) {
2180 if (UndefOrSalvage.count(DII))
2181 continue;
2182
2183 DbgValReplacement DVR = RewriteExpr(*DII);
2184 if (!DVR)
2185 continue;
2186
2187 DII->replaceVariableLocationOp(&From, &To);
2188 DII->setExpression(*DVR);
2189 LLVM_DEBUG(dbgs() << "REWRITE: " << *DII << '\n');
2190 Changed = true;
2191 }
2192
2193 if (!UndefOrSalvage.empty()) {
2194 // Try to salvage the remaining debug users.
2196 Changed = true;
2197 }
2198
2199 return Changed;
2200}
2201
2202/// Check if a bitcast between a value of type \p FromTy to type \p ToTy would
2203/// losslessly preserve the bits and semantics of the value. This predicate is
2204/// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result.
2205///
2206/// Note that Type::canLosslesslyBitCastTo is not suitable here because it
2207/// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>,
2208/// and also does not allow lossless pointer <-> integer conversions.
2210 Type *ToTy) {
2211 // Trivially compatible types.
2212 if (FromTy == ToTy)
2213 return true;
2214
2215 // Handle compatible pointer <-> integer conversions.
2216 if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) {
2217 bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy);
2218 bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) &&
2219 !DL.isNonIntegralPointerType(ToTy);
2220 return SameSize && LosslessConversion;
2221 }
2222
2223 // TODO: This is not exhaustive.
2224 return false;
2225}
2226
2228 Instruction &DomPoint, DominatorTree &DT) {
2229 // Exit early if From has no debug users.
2230 if (!From.isUsedByMetadata())
2231 return false;
2232
2233 assert(&From != &To && "Can't replace something with itself");
2234
2235 Type *FromTy = From.getType();
2236 Type *ToTy = To.getType();
2237
2238 auto Identity = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
2239 return DII.getExpression();
2240 };
2241
2242 // Handle no-op conversions.
2243 Module &M = *From.getModule();
2244 const DataLayout &DL = M.getDataLayout();
2245 if (isBitCastSemanticsPreserving(DL, FromTy, ToTy))
2246 return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
2247
2248 // Handle integer-to-integer widening and narrowing.
2249 // FIXME: Use DW_OP_convert when it's available everywhere.
2250 if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) {
2251 uint64_t FromBits = FromTy->getPrimitiveSizeInBits();
2252 uint64_t ToBits = ToTy->getPrimitiveSizeInBits();
2253 assert(FromBits != ToBits && "Unexpected no-op conversion");
2254
2255 // When the width of the result grows, assume that a debugger will only
2256 // access the low `FromBits` bits when inspecting the source variable.
2257 if (FromBits < ToBits)
2258 return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
2259
2260 // The width of the result has shrunk. Use sign/zero extension to describe
2261 // the source variable's high bits.
2262 auto SignOrZeroExt = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
2263 DILocalVariable *Var = DII.getVariable();
2264
2265 // Without knowing signedness, sign/zero extension isn't possible.
2266 auto Signedness = Var->getSignedness();
2267 if (!Signedness)
2268 return std::nullopt;
2269
2270 bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2271 return DIExpression::appendExt(DII.getExpression(), ToBits, FromBits,
2272 Signed);
2273 };
2274 return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt);
2275 }
2276
2277 // TODO: Floating-point conversions, vectors.
2278 return false;
2279}
2280
2281std::pair<unsigned, unsigned>
2283 unsigned NumDeadInst = 0;
2284 unsigned NumDeadDbgInst = 0;
2285 // Delete the instructions backwards, as it has a reduced likelihood of
2286 // having to update as many def-use and use-def chains.
2287 Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
2288 while (EndInst != &BB->front()) {
2289 // Delete the next to last instruction.
2290 Instruction *Inst = &*--EndInst->getIterator();
2291 if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
2293 if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
2294 EndInst = Inst;
2295 continue;
2296 }
2297 if (isa<DbgInfoIntrinsic>(Inst))
2298 ++NumDeadDbgInst;
2299 else
2300 ++NumDeadInst;
2301 Inst->eraseFromParent();
2302 }
2303 return {NumDeadInst, NumDeadDbgInst};
2304}
2305
2306unsigned llvm::changeToUnreachable(Instruction *I, bool PreserveLCSSA,
2307 DomTreeUpdater *DTU,
2308 MemorySSAUpdater *MSSAU) {
2309 BasicBlock *BB = I->getParent();
2310
2311 if (MSSAU)
2312 MSSAU->changeToUnreachable(I);
2313
2314 SmallSet<BasicBlock *, 8> UniqueSuccessors;
2315
2316 // Loop over all of the successors, removing BB's entry from any PHI
2317 // nodes.
2318 for (BasicBlock *Successor : successors(BB)) {
2319 Successor->removePredecessor(BB, PreserveLCSSA);
2320 if (DTU)
2321 UniqueSuccessors.insert(Successor);
2322 }
2323 auto *UI = new UnreachableInst(I->getContext(), I);
2324 UI->setDebugLoc(I->getDebugLoc());
2325
2326 // All instructions after this are dead.
2327 unsigned NumInstrsRemoved = 0;
2328 BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
2329 while (BBI != BBE) {
2330 if (!BBI->use_empty())
2331 BBI->replaceAllUsesWith(PoisonValue::get(BBI->getType()));
2332 BBI++->eraseFromParent();
2333 ++NumInstrsRemoved;
2334 }
2335 if (DTU) {
2337 Updates.reserve(UniqueSuccessors.size());
2338 for (BasicBlock *UniqueSuccessor : UniqueSuccessors)
2339 Updates.push_back({DominatorTree::Delete, BB, UniqueSuccessor});
2340 DTU->applyUpdates(Updates);
2341 }
2342 return NumInstrsRemoved;
2343}
2344
2346 SmallVector<Value *, 8> Args(II->args());
2348 II->getOperandBundlesAsDefs(OpBundles);
2349 CallInst *NewCall = CallInst::Create(II->getFunctionType(),
2350 II->getCalledOperand(), Args, OpBundles);
2351 NewCall->setCallingConv(II->getCallingConv());
2352 NewCall->setAttributes(II->getAttributes());
2353 NewCall->setDebugLoc(II->getDebugLoc());
2354 NewCall->copyMetadata(*II);
2355
2356 // If the invoke had profile metadata, try converting them for CallInst.
2357 uint64_t TotalWeight;
2358 if (NewCall->extractProfTotalWeight(TotalWeight)) {
2359 // Set the total weight if it fits into i32, otherwise reset.
2360 MDBuilder MDB(NewCall->getContext());
2361 auto NewWeights = uint32_t(TotalWeight) != TotalWeight
2362 ? nullptr
2363 : MDB.createBranchWeights({uint32_t(TotalWeight)});
2364 NewCall->setMetadata(LLVMContext::MD_prof, NewWeights);
2365 }
2366
2367 return NewCall;
2368}
2369
2370// changeToCall - Convert the specified invoke into a normal call.
2372 CallInst *NewCall = createCallMatchingInvoke(II);
2373 NewCall->takeName(II);
2374 NewCall->insertBefore(II);
2375 II->replaceAllUsesWith(NewCall);
2376
2377 // Follow the call by a branch to the normal destination.
2378 BasicBlock *NormalDestBB = II->getNormalDest();
2379 BranchInst::Create(NormalDestBB, II);
2380
2381 // Update PHI nodes in the unwind destination
2382 BasicBlock *BB = II->getParent();
2383 BasicBlock *UnwindDestBB = II->getUnwindDest();
2384 UnwindDestBB->removePredecessor(BB);
2385 II->eraseFromParent();
2386 if (DTU)
2387 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2388 return NewCall;
2389}
2390
2392 BasicBlock *UnwindEdge,
2393 DomTreeUpdater *DTU) {
2394 BasicBlock *BB = CI->getParent();
2395
2396 // Convert this function call into an invoke instruction. First, split the
2397 // basic block.
2398 BasicBlock *Split = SplitBlock(BB, CI, DTU, /*LI=*/nullptr, /*MSSAU*/ nullptr,
2399 CI->getName() + ".noexc");
2400
2401 // Delete the unconditional branch inserted by SplitBlock
2402 BB->back().eraseFromParent();
2403
2404 // Create the new invoke instruction.
2405 SmallVector<Value *, 8> InvokeArgs(CI->args());
2407
2408 CI->getOperandBundlesAsDefs(OpBundles);
2409
2410 // Note: we're round tripping operand bundles through memory here, and that
2411 // can potentially be avoided with a cleverer API design that we do not have
2412 // as of this time.
2413
2414 InvokeInst *II =
2416 UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB);
2417 II->setDebugLoc(CI->getDebugLoc());
2418 II->setCallingConv(CI->getCallingConv());
2419 II->setAttributes(CI->getAttributes());
2420 II->setMetadata(LLVMContext::MD_prof, CI->getMetadata(LLVMContext::MD_prof));
2421
2422 if (DTU)
2423 DTU->applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});
2424
2425 // Make sure that anything using the call now uses the invoke! This also
2426 // updates the CallGraph if present, because it uses a WeakTrackingVH.
2427 CI->replaceAllUsesWith(II);
2428
2429 // Delete the original call
2430 Split->front().eraseFromParent();
2431 return Split;
2432}
2433
2436 DomTreeUpdater *DTU = nullptr) {
2438 BasicBlock *BB = &F.front();
2439 Worklist.push_back(BB);
2440 Reachable.insert(BB);
2441 bool Changed = false;
2442 do {
2443 BB = Worklist.pop_back_val();
2444
2445 // Do a quick scan of the basic block, turning any obviously unreachable
2446 // instructions into LLVM unreachable insts. The instruction combining pass
2447 // canonicalizes unreachable insts into stores to null or undef.
2448 for (Instruction &I : *BB) {
2449 if (auto *CI = dyn_cast<CallInst>(&I)) {
2450 Value *Callee = CI->getCalledOperand();
2451 // Handle intrinsic calls.
2452 if (Function *F = dyn_cast<Function>(Callee)) {
2453 auto IntrinsicID = F->getIntrinsicID();
2454 // Assumptions that are known to be false are equivalent to
2455 // unreachable. Also, if the condition is undefined, then we make the
2456 // choice most beneficial to the optimizer, and choose that to also be
2457 // unreachable.
2458 if (IntrinsicID == Intrinsic::assume) {
2459 if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
2460 // Don't insert a call to llvm.trap right before the unreachable.
2461 changeToUnreachable(CI, false, DTU);
2462 Changed = true;
2463 break;
2464 }
2465 } else if (IntrinsicID == Intrinsic::experimental_guard) {
2466 // A call to the guard intrinsic bails out of the current
2467 // compilation unit if the predicate passed to it is false. If the
2468 // predicate is a constant false, then we know the guard will bail
2469 // out of the current compile unconditionally, so all code following
2470 // it is dead.
2471 //
2472 // Note: unlike in llvm.assume, it is not "obviously profitable" for
2473 // guards to treat `undef` as `false` since a guard on `undef` can
2474 // still be useful for widening.
2475 if (match(CI->getArgOperand(0), m_Zero()))
2476 if (!isa<UnreachableInst>(CI->getNextNode())) {
2477 changeToUnreachable(CI->getNextNode(), false, DTU);
2478 Changed = true;
2479 break;
2480 }
2481 }
2482 } else if ((isa<ConstantPointerNull>(Callee) &&
2483 !NullPointerIsDefined(CI->getFunction(),
2484 cast<PointerType>(Callee->getType())
2485 ->getAddressSpace())) ||
2486 isa<UndefValue>(Callee)) {
2487 changeToUnreachable(CI, false, DTU);
2488 Changed = true;
2489 break;
2490 }
2491 if (CI->doesNotReturn() && !CI->isMustTailCall()) {
2492 // If we found a call to a no-return function, insert an unreachable
2493 // instruction after it. Make sure there isn't *already* one there
2494 // though.
2495 if (!isa<UnreachableInst>(CI->getNextNode())) {
2496 // Don't insert a call to llvm.trap right before the unreachable.
2497 changeToUnreachable(CI->getNextNode(), false, DTU);
2498 Changed = true;
2499 }
2500 break;
2501 }
2502 } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
2503 // Store to undef and store to null are undefined and used to signal
2504 // that they should be changed to unreachable by passes that can't
2505 // modify the CFG.
2506
2507 // Don't touch volatile stores.
2508 if (SI->isVolatile()) continue;
2509
2510 Value *Ptr = SI->getOperand(1);
2511
2512 if (isa<UndefValue>(Ptr) ||
2513 (isa<ConstantPointerNull>(Ptr) &&
2514 !NullPointerIsDefined(SI->getFunction(),
2515 SI->getPointerAddressSpace()))) {
2516 changeToUnreachable(SI, false, DTU);
2517 Changed = true;
2518 break;
2519 }
2520 }
2521 }
2522
2523 Instruction *Terminator = BB->getTerminator();
2524 if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
2525 // Turn invokes that call 'nounwind' functions into ordinary calls.
2526 Value *Callee = II->getCalledOperand();
2527 if ((isa<ConstantPointerNull>(Callee) &&
2528 !NullPointerIsDefined(BB->getParent())) ||
2529 isa<UndefValue>(Callee)) {
2530 changeToUnreachable(II, false, DTU);
2531 Changed = true;
2532 } else {
2533 if (II->doesNotReturn() &&
2534 !isa<UnreachableInst>(II->getNormalDest()->front())) {
2535 // If we found an invoke of a no-return function,
2536 // create a new empty basic block with an `unreachable` terminator,
2537 // and set it as the normal destination for the invoke,
2538 // unless that is already the case.
2539 // Note that the original normal destination could have other uses.
2540 BasicBlock *OrigNormalDest = II->getNormalDest();
2541 OrigNormalDest->removePredecessor(II->getParent());
2542 LLVMContext &Ctx = II->getContext();
2543 BasicBlock *UnreachableNormalDest = BasicBlock::Create(
2544 Ctx, OrigNormalDest->getName() + ".unreachable",
2545 II->getFunction(), OrigNormalDest);
2546 new UnreachableInst(Ctx, UnreachableNormalDest);
2547 II->setNormalDest(UnreachableNormalDest);
2548 if (DTU)
2549 DTU->applyUpdates(
2550 {{DominatorTree::Delete, BB, OrigNormalDest},
2551 {DominatorTree::Insert, BB, UnreachableNormalDest}});
2552 Changed = true;
2553 }
2554 if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
2555 if (II->use_empty() && !II->mayHaveSideEffects()) {
2556 // jump to the normal destination branch.
2557 BasicBlock *NormalDestBB = II->getNormalDest();
2558 BasicBlock *UnwindDestBB = II->getUnwindDest();
2559 BranchInst::Create(NormalDestBB, II);
2560 UnwindDestBB->removePredecessor(II->getParent());
2561 II->eraseFromParent();
2562 if (DTU)
2563 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2564 } else
2565 changeToCall(II, DTU);
2566 Changed = true;
2567 }
2568 }
2569 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
2570 // Remove catchpads which cannot be reached.
2571 struct CatchPadDenseMapInfo {
2572 static CatchPadInst *getEmptyKey() {
2574 }
2575
2576 static CatchPadInst *getTombstoneKey() {
2578 }
2579
2580 static unsigned getHashValue(CatchPadInst *CatchPad) {
2581 return static_cast<unsigned>(hash_combine_range(
2582 CatchPad->value_op_begin(), CatchPad->value_op_end()));
2583 }
2584
2585 static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
2586 if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
2587 RHS == getEmptyKey() || RHS == getTombstoneKey())
2588 return LHS == RHS;
2589 return LHS->isIdenticalTo(RHS);
2590 }
2591 };
2592
2593 SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
2594 // Set of unique CatchPads.
2596 CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
2597 HandlerSet;
2599 for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
2600 E = CatchSwitch->handler_end();
2601 I != E; ++I) {
2602 BasicBlock *HandlerBB = *I;
2603 if (DTU)
2604 ++NumPerSuccessorCases[HandlerBB];
2605 auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
2606 if (!HandlerSet.insert({CatchPad, Empty}).second) {
2607 if (DTU)
2608 --NumPerSuccessorCases[HandlerBB];
2609 CatchSwitch->removeHandler(I);
2610 --I;
2611 --E;
2612 Changed = true;
2613 }
2614 }
2615 if (DTU) {
2616 std::vector<DominatorTree::UpdateType> Updates;
2617 for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases)
2618 if (I.second == 0)
2619 Updates.push_back({DominatorTree::Delete, BB, I.first});
2620 DTU->applyUpdates(Updates);
2621 }
2622 }
2623
2624 Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
2625 for (BasicBlock *Successor : successors(BB))
2626 if (Reachable.insert(Successor).second)
2627 Worklist.push_back(Successor);
2628 } while (!Worklist.empty());
2629 return Changed;
2630}
2631
2633 Instruction *TI = BB->getTerminator();
2634
2635 if (auto *II = dyn_cast<InvokeInst>(TI))
2636 return changeToCall(II, DTU);
2637
2638 Instruction *NewTI;
2639 BasicBlock *UnwindDest;
2640
2641 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
2642 NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
2643 UnwindDest = CRI->getUnwindDest();
2644 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
2645 auto *NewCatchSwitch = CatchSwitchInst::Create(
2646 CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
2647 CatchSwitch->getName(), CatchSwitch);
2648 for (BasicBlock *PadBB : CatchSwitch->handlers())
2649 NewCatchSwitch->addHandler(PadBB);
2650
2651 NewTI = NewCatchSwitch;
2652 UnwindDest = CatchSwitch->getUnwindDest();
2653 } else {
2654 llvm_unreachable("Could not find unwind successor");
2655 }
2656
2657 NewTI->takeName(TI);
2658 NewTI->setDebugLoc(TI->getDebugLoc());
2659 UnwindDest->removePredecessor(BB);
2660 TI->replaceAllUsesWith(NewTI);
2661 TI->eraseFromParent();
2662 if (DTU)
2663 DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
2664 return NewTI;
2665}
2666
2667/// removeUnreachableBlocks - Remove blocks that are not reachable, even
2668/// if they are in a dead cycle. Return true if a change was made, false
2669/// otherwise.
2671 MemorySSAUpdater *MSSAU) {
2673 bool Changed = markAliveBlocks(F, Reachable, DTU);
2674
2675 // If there are unreachable blocks in the CFG...
2676 if (Reachable.size() == F.size())
2677 return Changed;
2678
2679 assert(Reachable.size() < F.size());
2680
2681 // Are there any blocks left to actually delete?
2682 SmallSetVector<BasicBlock *, 8> BlocksToRemove;
2683 for (BasicBlock &BB : F) {
2684 // Skip reachable basic blocks
2685 if (Reachable.count(&BB))
2686 continue;
2687 // Skip already-deleted blocks
2688 if (DTU && DTU->isBBPendingDeletion(&BB))
2689 continue;
2690 BlocksToRemove.insert(&BB);
2691 }
2692
2693 if (BlocksToRemove.empty())
2694 return Changed;
2695
2696 Changed = true;
2697 NumRemoved += BlocksToRemove.size();
2698
2699 if (MSSAU)
2700 MSSAU->removeBlocks(BlocksToRemove);
2701
2702 DeleteDeadBlocks(BlocksToRemove.takeVector(), DTU);
2703
2704 return Changed;
2705}
2706
2708 ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
2710 K->dropUnknownNonDebugMetadata(KnownIDs);
2711 K->getAllMetadataOtherThanDebugLoc(Metadata);
2712 for (const auto &MD : Metadata) {
2713 unsigned Kind = MD.first;
2714 MDNode *JMD = J->getMetadata(Kind);
2715 MDNode *KMD = MD.second;
2716
2717 switch (Kind) {
2718 default:
2719 K->setMetadata(Kind, nullptr); // Remove unknown metadata
2720 break;
2721 case LLVMContext::MD_dbg:
2722 llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
2723 case LLVMContext::MD_DIAssignID:
2724 K->mergeDIAssignID(J);
2725 break;
2726 case LLVMContext::MD_tbaa:
2727 K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
2728 break;
2729 case LLVMContext::MD_alias_scope:
2730 K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
2731 break;
2732 case LLVMContext::MD_noalias:
2733 case LLVMContext::MD_mem_parallel_loop_access:
2734 K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
2735 break;
2736 case LLVMContext::MD_access_group:
2737 K->setMetadata(LLVMContext::MD_access_group,
2738 intersectAccessGroups(K, J));
2739 break;
2740 case LLVMContext::MD_range:
2741 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
2742 K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
2743 break;
2744 case LLVMContext::MD_fpmath:
2745 K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
2746 break;
2747 case LLVMContext::MD_invariant_load:
2748 // If K moves, only set the !invariant.load if it is present in both
2749 // instructions.
2750 if (DoesKMove)
2751 K->setMetadata(Kind, JMD);
2752 break;
2753 case LLVMContext::MD_nonnull:
2754 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
2755 K->setMetadata(Kind, JMD);
2756 break;
2757 case LLVMContext::MD_invariant_group:
2758 // Preserve !invariant.group in K.
2759 break;
2760 case LLVMContext::MD_align:
2761 if (DoesKMove || !K->hasMetadata(LLVMContext::MD_noundef))
2762 K->setMetadata(
2764 break;
2765 case LLVMContext::MD_dereferenceable:
2766 case LLVMContext::MD_dereferenceable_or_null:
2767 if (DoesKMove)
2768 K->setMetadata(Kind,
2770 break;
2771 case LLVMContext::MD_preserve_access_index:
2772 // Preserve !preserve.access.index in K.
2773 break;
2774 case LLVMContext::MD_noundef:
2775 // If K does move, keep noundef if it is present in both instructions.
2776 if (DoesKMove)
2777 K->setMetadata(Kind, JMD);
2778 break;
2779 case LLVMContext::MD_nontemporal:
2780 // Preserve !nontemporal if it is present on both instructions.
2781 K->setMetadata(Kind, JMD);
2782 break;
2783 case LLVMContext::MD_prof:
2784 if (DoesKMove)
2785 K->setMetadata(Kind, MDNode::getMergedProfMetadata(KMD, JMD, K, J));
2786 break;
2787 }
2788 }
2789 // Set !invariant.group from J if J has it. If both instructions have it
2790 // then we will just pick it from J - even when they are different.
2791 // Also make sure that K is load or store - f.e. combining bitcast with load
2792 // could produce bitcast with invariant.group metadata, which is invalid.
2793 // FIXME: we should try to preserve both invariant.group md if they are
2794 // different, but right now instruction can only have one invariant.group.
2795 if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2796 if (isa<LoadInst>(K) || isa<StoreInst>(K))
2797 K->setMetadata(LLVMContext::MD_invariant_group, JMD);
2798}
2799
2801 bool KDominatesJ) {
2802 unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
2803 LLVMContext::MD_alias_scope,
2804 LLVMContext::MD_noalias,
2805 LLVMContext::MD_range,
2806 LLVMContext::MD_fpmath,
2807 LLVMContext::MD_invariant_load,
2808 LLVMContext::MD_nonnull,
2809 LLVMContext::MD_invariant_group,
2810 LLVMContext::MD_align,
2811 LLVMContext::MD_dereferenceable,
2812 LLVMContext::MD_dereferenceable_or_null,
2813 LLVMContext::MD_access_group,
2814 LLVMContext::MD_preserve_access_index,
2815 LLVMContext::MD_prof,
2816 LLVMContext::MD_nontemporal,
2817 LLVMContext::MD_noundef};
2818 combineMetadata(K, J, KnownIDs, KDominatesJ);
2819}
2820
2821void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) {
2823 Source.getAllMetadata(MD);
2824 MDBuilder MDB(Dest.getContext());
2825 Type *NewType = Dest.getType();
2826 const DataLayout &DL = Source.getModule()->getDataLayout();
2827 for (const auto &MDPair : MD) {
2828 unsigned ID = MDPair.first;
2829 MDNode *N = MDPair.second;
2830 // Note, essentially every kind of metadata should be preserved here! This
2831 // routine is supposed to clone a load instruction changing *only its type*.
2832 // The only metadata it makes sense to drop is metadata which is invalidated
2833 // when the pointer type changes. This should essentially never be the case
2834 // in LLVM, but we explicitly switch over only known metadata to be
2835 // conservatively correct. If you are adding metadata to LLVM which pertains
2836 // to loads, you almost certainly want to add it here.
2837 switch (ID) {
2838 case LLVMContext::MD_dbg:
2839 case LLVMContext::MD_tbaa:
2840 case LLVMContext::MD_prof:
2841 case LLVMContext::MD_fpmath:
2842 case LLVMContext::MD_tbaa_struct:
2843 case LLVMContext::MD_invariant_load:
2844 case LLVMContext::MD_alias_scope:
2845 case LLVMContext::MD_noalias:
2846 case LLVMContext::MD_nontemporal:
2847 case LLVMContext::MD_mem_parallel_loop_access:
2848 case LLVMContext::MD_access_group:
2849 case LLVMContext::MD_noundef:
2850 // All of these directly apply.
2851 Dest.setMetadata(ID, N);
2852 break;
2853
2854 case LLVMContext::MD_nonnull:
2855 copyNonnullMetadata(Source, N, Dest);
2856 break;
2857
2858 case LLVMContext::MD_align:
2859 case LLVMContext::MD_dereferenceable:
2860 case LLVMContext::MD_dereferenceable_or_null:
2861 // These only directly apply if the new type is also a pointer.
2862 if (NewType->isPointerTy())
2863 Dest.setMetadata(ID, N);
2864 break;
2865
2866 case LLVMContext::MD_range:
2867 copyRangeMetadata(DL, Source, N, Dest);
2868 break;
2869 }
2870 }
2871}
2872
2874 auto *ReplInst = dyn_cast<Instruction>(Repl);
2875 if (!ReplInst)
2876 return;
2877
2878 // Patch the replacement so that it is not more restrictive than the value
2879 // being replaced.
2880 // Note that if 'I' is a load being replaced by some operation,
2881 // for example, by an arithmetic operation, then andIRFlags()
2882 // would just erase all math flags from the original arithmetic
2883 // operation, which is clearly not wanted and not needed.
2884 if (!isa<LoadInst>(I))
2885 ReplInst->andIRFlags(I);
2886
2887 // FIXME: If both the original and replacement value are part of the
2888 // same control-flow region (meaning that the execution of one
2889 // guarantees the execution of the other), then we can combine the
2890 // noalias scopes here and do better than the general conservative
2891 // answer used in combineMetadata().
2892
2893 // In general, GVN unifies expressions over different control-flow
2894 // regions, and so we need a conservative combination of the noalias
2895 // scopes.
2896 combineMetadataForCSE(ReplInst, I, false);
2897}
2898
2899template <typename RootType, typename DominatesFn>
2901 const RootType &Root,
2902 const DominatesFn &Dominates) {
2903 assert(From->getType() == To->getType());
2904
2905 unsigned Count = 0;
2906 for (Use &U : llvm::make_early_inc_range(From->uses())) {
2907 if (!Dominates(Root, U))
2908 continue;
2909 LLVM_DEBUG(dbgs() << "Replace dominated use of '";
2910 From->printAsOperand(dbgs());
2911 dbgs() << "' with " << *To << " in " << *U.getUser() << "\n");
2912 U.set(To);
2913 ++Count;
2914 }
2915 return Count;
2916}
2917
2919 assert(From->getType() == To->getType());
2920 auto *BB = From->getParent();
2921 unsigned Count = 0;
2922
2923 for (Use &U : llvm::make_early_inc_range(From->uses())) {
2924 auto *I = cast<Instruction>(U.getUser());
2925 if (I->getParent() == BB)
2926 continue;
2927 U.set(To);
2928 ++Count;
2929 }
2930 return Count;
2931}
2932
2934 DominatorTree &DT,
2935 const BasicBlockEdge &Root) {
2936 auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2937 return DT.dominates(Root, U);
2938 };
2939 return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2940}
2941
2943 DominatorTree &DT,
2944 const BasicBlock *BB) {
2945 auto Dominates = [&DT](const BasicBlock *BB, const Use &U) {
2946 return DT.dominates(BB, U);
2947 };
2948 return ::replaceDominatedUsesWith(From, To, BB, Dominates);
2949}
2950
2952 const TargetLibraryInfo &TLI) {
2953 // Check if the function is specifically marked as a gc leaf function.
2954 if (Call->hasFnAttr("gc-leaf-function"))
2955 return true;
2956 if (const Function *F = Call->getCalledFunction()) {
2957 if (F->hasFnAttribute("gc-leaf-function"))
2958 return true;
2959
2960 if (auto IID = F->getIntrinsicID()) {
2961 // Most LLVM intrinsics do not take safepoints.
2962 return IID != Intrinsic::experimental_gc_statepoint &&
2963 IID != Intrinsic::experimental_deoptimize &&
2964 IID != Intrinsic::memcpy_element_unordered_atomic &&
2965 IID != Intrinsic::memmove_element_unordered_atomic;
2966 }
2967 }
2968
2969 // Lib calls can be materialized by some passes, and won't be
2970 // marked as 'gc-leaf-function.' All available Libcalls are
2971 // GC-leaf.
2972 LibFunc LF;
2973 if (TLI.getLibFunc(*Call, LF)) {
2974 return TLI.has(LF);
2975 }
2976
2977 return false;
2978}
2979
2981 LoadInst &NewLI) {
2982 auto *NewTy = NewLI.getType();
2983
2984 // This only directly applies if the new type is also a pointer.
2985 if (NewTy->isPointerTy()) {
2986 NewLI.setMetadata(LLVMContext::MD_nonnull, N);
2987 return;
2988 }
2989
2990 // The only other translation we can do is to integral loads with !range
2991 // metadata.
2992 if (!NewTy->isIntegerTy())
2993 return;
2994
2995 MDBuilder MDB(NewLI.getContext());
2996 const Value *Ptr = OldLI.getPointerOperand();
2997 auto *ITy = cast<IntegerType>(NewTy);
2998 auto *NullInt = ConstantExpr::getPtrToInt(
2999 ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
3000 auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
3001 NewLI.setMetadata(LLVMContext::MD_range,
3002 MDB.createRange(NonNullInt, NullInt));
3003}
3004
3006 MDNode *N, LoadInst &NewLI) {
3007 auto *NewTy = NewLI.getType();
3008 // Simply copy the metadata if the type did not change.
3009 if (NewTy == OldLI.getType()) {
3010 NewLI.setMetadata(LLVMContext::MD_range, N);
3011 return;
3012 }
3013
3014 // Give up unless it is converted to a pointer where there is a single very
3015 // valuable mapping we can do reliably.
3016 // FIXME: It would be nice to propagate this in more ways, but the type
3017 // conversions make it hard.
3018 if (!NewTy->isPointerTy())
3019 return;
3020
3021 unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
3022 if (BitWidth == OldLI.getType()->getScalarSizeInBits() &&
3024 MDNode *NN = MDNode::get(OldLI.getContext(), std::nullopt);
3025 NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
3026 }
3027}
3028
3031 findDbgUsers(DbgUsers, &I);
3032 for (auto *DII : DbgUsers)
3033 DII->eraseFromParent();
3034}
3035
3037 BasicBlock *BB) {
3038 // Since we are moving the instructions out of its basic block, we do not
3039 // retain their original debug locations (DILocations) and debug intrinsic
3040 // instructions.
3041 //
3042 // Doing so would degrade the debugging experience and adversely affect the
3043 // accuracy of profiling information.
3044 //
3045 // Currently, when hoisting the instructions, we take the following actions:
3046 // - Remove their debug intrinsic instructions.
3047 // - Set their debug locations to the values from the insertion point.
3048 //
3049 // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
3050 // need to be deleted, is because there will not be any instructions with a
3051 // DILocation in either branch left after performing the transformation. We
3052 // can only insert a dbg.value after the two branches are joined again.
3053 //
3054 // See PR38762, PR39243 for more details.
3055 //
3056 // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
3057 // encode predicated DIExpressions that yield different results on different
3058 // code paths.
3059
3060 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
3061 Instruction *I = &*II;
3062 I->dropUBImplyingAttrsAndMetadata();
3063 if (I->isUsedByMetadata())
3064 dropDebugUsers(*I);
3065 if (I->isDebugOrPseudoInst()) {
3066 // Remove DbgInfo and pseudo probe Intrinsics.
3067 II = I->eraseFromParent();
3068 continue;
3069 }
3070 I->setDebugLoc(InsertPt->getDebugLoc());
3071 ++II;
3072 }
3073 DomBlock->splice(InsertPt->getIterator(), BB, BB->begin(),
3074 BB->getTerminator()->getIterator());
3075}
3076
3077namespace {
3078
3079/// A potential constituent of a bitreverse or bswap expression. See
3080/// collectBitParts for a fuller explanation.
3081struct BitPart {
3082 BitPart(Value *P, unsigned BW) : Provider(P) {
3083 Provenance.resize(BW);
3084 }
3085
3086 /// The Value that this is a bitreverse/bswap of.
3087 Value *Provider;
3088
3089 /// The "provenance" of each bit. Provenance[A] = B means that bit A
3090 /// in Provider becomes bit B in the result of this expression.
3091 SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
3092
3093 enum { Unset = -1 };
3094};
3095
3096} // end anonymous namespace
3097
3098/// Analyze the specified subexpression and see if it is capable of providing
3099/// pieces of a bswap or bitreverse. The subexpression provides a potential
3100/// piece of a bswap or bitreverse if it can be proved that each non-zero bit in
3101/// the output of the expression came from a corresponding bit in some other
3102/// value. This function is recursive, and the end result is a mapping of
3103/// bitnumber to bitnumber. It is the caller's responsibility to validate that
3104/// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
3105///
3106/// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
3107/// that the expression deposits the low byte of %X into the high byte of the
3108/// result and that all other bits are zero. This expression is accepted and a
3109/// BitPart is returned with Provider set to %X and Provenance[24-31] set to
3110/// [0-7].
3111///
3112/// For vector types, all analysis is performed at the per-element level. No
3113/// cross-element analysis is supported (shuffle/insertion/reduction), and all
3114/// constant masks must be splatted across all elements.
3115///
3116/// To avoid revisiting values, the BitPart results are memoized into the
3117/// provided map. To avoid unnecessary copying of BitParts, BitParts are
3118/// constructed in-place in the \c BPS map. Because of this \c BPS needs to
3119/// store BitParts objects, not pointers. As we need the concept of a nullptr
3120/// BitParts (Value has been analyzed and the analysis failed), we an Optional
3121/// type instead to provide the same functionality.
3122///
3123/// Because we pass around references into \c BPS, we must use a container that
3124/// does not invalidate internal references (std::map instead of DenseMap).
3125static const std::optional<BitPart> &
3126collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
3127 std::map<Value *, std::optional<BitPart>> &BPS, int Depth,
3128 bool &FoundRoot) {
3129 auto I = BPS.find(V);
3130 if (I != BPS.end())
3131 return I->second;
3132
3133 auto &Result = BPS[V] = std::nullopt;
3134 auto BitWidth = V->getType()->getScalarSizeInBits();
3135
3136 // Can't do integer/elements > 128 bits.
3137 if (BitWidth > 128)
3138 return Result;
3139
3140 // Prevent stack overflow by limiting the recursion depth
3142 LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n");
3143 return Result;
3144 }
3145
3146 if (auto *I = dyn_cast<Instruction>(V)) {
3147 Value *X, *Y;
3148 const APInt *C;
3149
3150 // If this is an or instruction, it may be an inner node of the bswap.
3151 if (match(V, m_Or(m_Value(X), m_Value(Y)))) {
3152 // Check we have both sources and they are from the same provider.
3153 const auto &A = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3154 Depth + 1, FoundRoot);
3155 if (!A || !A->Provider)
3156 return Result;
3157
3158 const auto &B = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
3159 Depth + 1, FoundRoot);
3160 if (!B || A->Provider != B->Provider)
3161 return Result;
3162
3163 // Try and merge the two together.
3164 Result = BitPart(A->Provider, BitWidth);
3165 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) {
3166 if (A->Provenance[BitIdx] != BitPart::Unset &&
3167 B->Provenance[BitIdx] != BitPart::Unset &&
3168 A->Provenance[BitIdx] != B->Provenance[BitIdx])
3169 return Result = std::nullopt;
3170
3171 if (A->Provenance[BitIdx] == BitPart::Unset)
3172 Result->Provenance[BitIdx] = B->Provenance[BitIdx];
3173 else
3174 Result->Provenance[BitIdx] = A->Provenance[BitIdx];
3175 }
3176
3177 return Result;
3178 }
3179
3180 // If this is a logical shift by a constant, recurse then shift the result.
3181 if (match(V, m_LogicalShift(m_Value(X), m_APInt(C)))) {
3182 const APInt &BitShift = *C;
3183
3184 // Ensure the shift amount is defined.
3185 if (BitShift.uge(BitWidth))
3186 return Result;
3187
3188 // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3189 if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0)
3190 return Result;
3191
3192 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3193 Depth + 1, FoundRoot);
3194 if (!Res)
3195 return Result;
3196 Result = Res;
3197
3198 // Perform the "shift" on BitProvenance.
3199 auto &P = Result->Provenance;
3200 if (I->getOpcode() == Instruction::Shl) {
3201 P.erase(std::prev(P.end(), BitShift.getZExtValue()), P.end());
3202 P.insert(P.begin(), BitShift.getZExtValue(), BitPart::Unset);
3203 } else {
3204 P.erase(P.begin(), std::next(P.begin(), BitShift.getZExtValue()));
3205 P.insert(P.end(), BitShift.getZExtValue(), BitPart::Unset);
3206 }
3207
3208 return Result;
3209 }
3210
3211 // If this is a logical 'and' with a mask that clears bits, recurse then
3212 // unset the appropriate bits.
3213 if (match(V, m_And(m_Value(X), m_APInt(C)))) {
3214 const APInt &AndMask = *C;
3215
3216 // Check that the mask allows a multiple of 8 bits for a bswap, for an
3217 // early exit.
3218 unsigned NumMaskedBits = AndMask.popcount();
3219 if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3220 return Result;
3221
3222 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3223 Depth + 1, FoundRoot);
3224 if (!Res)
3225 return Result;
3226 Result = Res;
3227
3228 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3229 // If the AndMask is zero for this bit, clear the bit.
3230 if (AndMask[BitIdx] == 0)
3231 Result->Provenance[BitIdx] = BitPart::Unset;
3232 return Result;
3233 }
3234
3235 // If this is a zext instruction zero extend the result.
3236 if (match(V, m_ZExt(m_Value(X)))) {
3237 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3238 Depth + 1, FoundRoot);
3239 if (!Res)
3240 return Result;
3241
3242 Result = BitPart(Res->Provider, BitWidth);
3243 auto NarrowBitWidth = X->getType()->getScalarSizeInBits();
3244 for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3245 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3246 for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx)
3247 Result->Provenance[BitIdx] = BitPart::Unset;
3248 return Result;
3249 }
3250
3251 // If this is a truncate instruction, extract the lower bits.
3252 if (match(V, m_Trunc(m_Value(X)))) {
3253 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3254 Depth + 1, FoundRoot);
3255 if (!Res)
3256 return Result;
3257
3258 Result = BitPart(Res->Provider, BitWidth);
3259 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3260 Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3261 return Result;
3262 }
3263
3264 // BITREVERSE - most likely due to us previous matching a partial
3265 // bitreverse.
3266 if (match(V, m_BitReverse(m_Value(X)))) {
3267 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3268 Depth + 1, FoundRoot);
3269 if (!Res)
3270 return Result;
3271
3272 Result = BitPart(Res->Provider, BitWidth);
3273 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3274 Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3275 return Result;
3276 }
3277
3278 // BSWAP - most likely due to us previous matching a partial bswap.
3279 if (match(V, m_BSwap(m_Value(X)))) {
3280 const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3281 Depth + 1, FoundRoot);
3282 if (!Res)
3283 return Result;
3284
3285 unsigned ByteWidth = BitWidth / 8;
3286 Result = BitPart(Res->Provider, BitWidth);
3287 for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3288 unsigned ByteBitOfs = ByteIdx * 8;
3289 for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3290 Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] =
3291 Res->Provenance[ByteBitOfs + BitIdx];
3292 }
3293 return Result;
3294 }
3295
3296 // Funnel 'double' shifts take 3 operands, 2 inputs and the shift
3297 // amount (modulo).
3298 // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
3299 // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW))
3300 if (match(V, m_FShl(m_Value(X), m_Value(Y), m_APInt(C))) ||
3301 match(V, m_FShr(m_Value(X), m_Value(Y), m_APInt(C)))) {
3302 // We can treat fshr as a fshl by flipping the modulo amount.
3303 unsigned ModAmt = C->urem(BitWidth);
3304 if (cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fshr)
3305 ModAmt = BitWidth - ModAmt;
3306
3307 // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3308 if (!MatchBitReversals && (ModAmt % 8) != 0)
3309 return Result;
3310
3311 // Check we have both sources and they are from the same provider.
3312 const auto &LHS = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3313 Depth + 1, FoundRoot);
3314 if (!LHS || !LHS->Provider)
3315 return Result;
3316
3317 const auto &RHS = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
3318 Depth + 1, FoundRoot);
3319 if (!RHS || LHS->Provider != RHS->Provider)
3320 return Result;
3321
3322 unsigned StartBitRHS = BitWidth - ModAmt;
3323 Result = BitPart(LHS->Provider, BitWidth);
3324 for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3325 Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx];
3326 for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3327 Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS];
3328 return Result;
3329 }
3330 }
3331
3332 // If we've already found a root input value then we're never going to merge
3333 // these back together.
3334 if (FoundRoot)
3335 return Result;
3336
3337 // Okay, we got to something that isn't a shift, 'or', 'and', etc. This must
3338 // be the root input value to the bswap/bitreverse.
3339 FoundRoot = true;
3340 Result = BitPart(V, BitWidth);
3341 for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3342 Result->Provenance[BitIdx] = BitIdx;
3343 return Result;
3344}
3345
3346static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
3347 unsigned BitWidth) {
3348 if (From % 8 != To % 8)
3349 return false;
3350 // Convert from bit indices to byte indices and check for a byte reversal.
3351 From >>= 3;
3352 To >>= 3;
3353 BitWidth >>= 3;
3354 return From == BitWidth - To - 1;
3355}
3356
3357static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
3358 unsigned BitWidth) {
3359 return From == BitWidth - To - 1;
3360}
3361
3363 Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
3364 SmallVectorImpl<Instruction *> &InsertedInsts) {
3365 if (!match(I, m_Or(m_Value(), m_Value())) &&
3366 !match(I, m_FShl(m_Value(), m_Value(), m_Value())) &&
3367 !match(I, m_FShr(m_Value(), m_Value(), m_Value())))
3368 return false;
3369 if (!MatchBSwaps && !MatchBitReversals)
3370 return false;
3371 Type *ITy = I->getType();
3372 if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() > 128)
3373 return false; // Can't do integer/elements > 128 bits.
3374
3375 // Try to find all the pieces corresponding to the bswap.
3376 bool FoundRoot = false;
3377 std::map<Value *, std::optional<BitPart>> BPS;
3378 const auto &Res =
3379 collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0, FoundRoot);
3380 if (!Res)
3381 return false;
3382 ArrayRef<int8_t> BitProvenance = Res->Provenance;
3383 assert(all_of(BitProvenance,
3384 [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) &&
3385 "Illegal bit provenance index");
3386
3387 // If the upper bits are zero, then attempt to perform as a truncated op.
3388 Type *DemandedTy = ITy;
3389 if (BitProvenance.back() == BitPart::Unset) {
3390 while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset)
3391 BitProvenance = BitProvenance.drop_back();
3392 if (BitProvenance.empty())
3393 return false; // TODO - handle null value?
3394 DemandedTy = Type::getIntNTy(I->getContext(), BitProvenance.size());
3395 if (auto *IVecTy = dyn_cast<VectorType>(ITy))
3396 DemandedTy = VectorType::get(DemandedTy, IVecTy);
3397 }
3398
3399 // Check BitProvenance hasn't found a source larger than the result type.
3400 unsigned DemandedBW = DemandedTy->getScalarSizeInBits();
3401 if (DemandedBW > ITy->getScalarSizeInBits())
3402 return false;
3403
3404 // Now, is the bit permutation correct for a bswap or a bitreverse? We can
3405 // only byteswap values with an even number of bytes.
3406 APInt DemandedMask = APInt::getAllOnes(DemandedBW);
3407 bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
3408 bool OKForBitReverse = MatchBitReversals;
3409 for (unsigned BitIdx = 0;
3410 (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
3411 if (BitProvenance[BitIdx] == BitPart::Unset) {
3412 DemandedMask.clearBit(BitIdx);
3413 continue;
3414 }
3415 OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[BitIdx], BitIdx,
3416 DemandedBW);
3417 OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[BitIdx],
3418 BitIdx, DemandedBW);
3419 }
3420
3421 Intrinsic::ID Intrin;
3422 if (OKForBSwap)
3423 Intrin = Intrinsic::bswap;
3424 else if (OKForBitReverse)
3425 Intrin = Intrinsic::bitreverse;
3426 else
3427 return false;
3428
3429 Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
3430 Value *Provider = Res->Provider;
3431
3432 // We may need to truncate the provider.
3433 if (DemandedTy != Provider->getType()) {
3434 auto *Trunc =
3435 CastInst::CreateIntegerCast(Provider, DemandedTy, false, "trunc", I);
3436 InsertedInsts.push_back(Trunc);
3437 Provider = Trunc;
3438 }
3439
3440 Instruction *Result = CallInst::Create(F, Provider, "rev", I);
3441 InsertedInsts.push_back(Result);
3442
3443 if (!DemandedMask.isAllOnes()) {
3444 auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
3445 Result = BinaryOperator::Create(Instruction::And, Result, Mask, "mask", I);
3446 InsertedInsts.push_back(Result);
3447 }
3448
3449 // We may need to zeroextend back to the result type.
3450 if (ITy != Result->getType()) {
3451 auto *ExtInst = CastInst::CreateIntegerCast(Result, ITy, false, "zext", I);
3452 InsertedInsts.push_back(ExtInst);
3453 }
3454
3455 return true;
3456}
3457
3458// CodeGen has special handling for some string functions that may replace
3459// them with target-specific intrinsics. Since that'd skip our interceptors
3460// in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
3461// we mark affected calls as NoBuiltin, which will disable optimization
3462// in CodeGen.
3464 CallInst *CI, const TargetLibraryInfo *TLI) {
3465 Function *F = CI->getCalledFunction();
3466 LibFunc Func;
3467 if (F && !F->hasLocalLinkage() && F->hasName() &&
3468 TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
3469 !F->doesNotAccessMemory())
3470 CI->addFnAttr(Attribute::NoBuiltin);
3471}
3472
3474 // We can't have a PHI with a metadata type.
3475 if (I->getOperand(OpIdx)->getType()->isMetadataTy())
3476 return false;
3477
3478 // Early exit.
3479 if (!isa<Constant>(I->getOperand(OpIdx)))
3480 return true;
3481
3482 switch (I->getOpcode()) {
3483 default:
3484 return true;
3485 case Instruction::Call:
3486 case Instruction::Invoke: {
3487 const auto &CB = cast<CallBase>(*I);
3488
3489 // Can't handle inline asm. Skip it.
3490 if (CB.isInlineAsm())
3491 return false;
3492
3493 // Constant bundle operands may need to retain their constant-ness for
3494 // correctness.
3495 if (CB.isBundleOperand(OpIdx))
3496 return false;
3497
3498 if (OpIdx < CB.arg_size()) {
3499 // Some variadic intrinsics require constants in the variadic arguments,
3500 // which currently aren't markable as immarg.
3501 if (isa<IntrinsicInst>(CB) &&
3502 OpIdx >= CB.getFunctionType()->getNumParams()) {
3503 // This is known to be OK for stackmap.
3504 return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
3505 }
3506
3507 // gcroot is a special case, since it requires a constant argument which
3508 // isn't also required to be a simple ConstantInt.
3509 if (CB.getIntrinsicID() == Intrinsic::gcroot)
3510 return false;
3511
3512 // Some intrinsic operands are required to be immediates.
3513 return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
3514 }
3515
3516 // It is never allowed to replace the call argument to an intrinsic, but it
3517 // may be possible for a call.
3518 return !isa<IntrinsicInst>(CB);
3519 }
3520 case Instruction::ShuffleVector:
3521 // Shufflevector masks are constant.
3522 return OpIdx != 2;
3523 case Instruction::Switch:
3524 case Instruction::ExtractValue:
3525 // All operands apart from the first are constant.
3526 return OpIdx == 0;
3527 case Instruction::InsertValue:
3528 // All operands apart from the first and the second are constant.
3529 return OpIdx < 2;
3530 case Instruction::Alloca:
3531 // Static allocas (constant size in the entry block) are handled by
3532 // prologue/epilogue insertion so they're free anyway. We definitely don't
3533 // want to make them non-constant.
3534 return !cast<AllocaInst>(I)->isStaticAlloca();
3535 case Instruction::GetElementPtr:
3536 if (OpIdx == 0)
3537 return true;
3539 for (auto E = std::next(It, OpIdx); It != E; ++It)
3540 if (It.isStruct())
3541 return false;
3542 return true;
3543 }
3544}
3545
3547 // First: Check if it's a constant
3548 if (Constant *C = dyn_cast<Constant>(Condition))
3549 return ConstantExpr::getNot(C);
3550
3551 // Second: If the condition is already inverted, return the original value
3552 Value *NotCondition;
3553 if (match(Condition, m_Not(m_Value(NotCondition))))
3554 return NotCondition;
3555
3556 BasicBlock *Parent = nullptr;
3557 Instruction *Inst = dyn_cast<Instruction>(Condition);
3558 if (Inst)
3559 Parent = Inst->getParent();
3560 else if (Argument *Arg = dyn_cast<Argument>(Condition))
3561 Parent = &Arg->getParent()->getEntryBlock();
3562 assert(Parent && "Unsupported condition to invert");
3563
3564 // Third: Check all the users for an invert
3565 for (User *U : Condition->users())
3566 if (Instruction *I = dyn_cast<Instruction>(U))
3567 if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
3568 return I;
3569
3570 // Last option: Create a new instruction
3571 auto *Inverted =
3572 BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv");
3573 if (Inst && !isa<PHINode>(Inst))
3574 Inverted->insertAfter(Inst);
3575 else
3576 Inverted->insertBefore(&*Parent->getFirstInsertionPt());
3577 return Inverted;
3578}
3579
3581 // Note: We explicitly check for attributes rather than using cover functions
3582 // because some of the cover functions include the logic being implemented.
3583
3584 bool Changed = false;
3585 // readnone + not convergent implies nosync
3586 if (!F.hasFnAttribute(Attribute::NoSync) &&
3587 F.doesNotAccessMemory() && !F.isConvergent()) {
3588 F.setNoSync();
3589 Changed = true;
3590 }
3591
3592 // readonly implies nofree
3593 if (!F.hasFnAttribute(Attribute::NoFree) && F.onlyReadsMemory()) {
3594 F.setDoesNotFreeMemory();
3595 Changed = true;
3596 }
3597
3598 // willreturn implies mustprogress
3599 if (!F.hasFnAttribute(Attribute::MustProgress) && F.willReturn()) {
3600 F.setMustProgress();
3601 Changed = true;
3602 }
3603
3604 // TODO: There are a bunch of cases of restrictive memory effects we
3605 // can infer by inspecting arguments of argmemonly-ish functions.
3606
3607 return Changed;
3608}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static unsigned getIntrinsicID(const SDNode *N)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
ReachingDefAnalysis InstSet & ToRemove
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)
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.
bool End
Definition: ELF_riscv.cpp:469
static unsigned getHashValueImpl(SimpleValue Val)
Definition: EarlyCSE.cpp:235
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
Definition: EarlyCSE.cpp:357
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.
const SmallVectorImpl< MachineOperand > & Cond
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:2434
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:2209
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 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:850
static void gatherIncomingValuesToPhi(PHINode *PN, IncomingValueMap &IncomingValues)
Create a map from block to value for the operands of a given phi.
Definition: Local.cpp:947
static void handleSSAValueOperands(uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues, Instruction *I)
Definition: Local.cpp:1993
std::optional< DIExpression * > DbgValReplacement
A replacement for a dbg.value expression.
Definition: Local.cpp:2142
Value * getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:2005
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:963
Value * getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1937
Value * getSalvageOpsForIcmpOp(ICmpInst *Icmp, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:2064
static unsigned replaceDominatedUsesWith(Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates)
Definition: Local.cpp:2900
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:842
static bool simplifyAndDCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Local.cpp:659
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:618
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"))
uint64_t getDwarfOpForIcmpPred(CmpInst::Predicate Pred)
Definition: Local.cpp:2039
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:3346
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:3126
static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB, SmallPtrSetImpl< PHINode * > &ToRemove)
Definition: Local.cpp:1251
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 bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB, SmallPtrSetImpl< PHINode * > &ToRemove)
Definition: Local.cpp:1287
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:922
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:1007
static const unsigned BitPartRecursionMaxDepth
Definition: Local.cpp:113
static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:3357
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:2147
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:76
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:212
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1379
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1485
unsigned popcount() const
Count the number of bits set.
Definition: APInt.h:1614
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:349
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1507
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1193
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:174
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
ArrayRef< T > drop_back(size_t N=1) const
Drop the last N elements of the array.
Definition: ArrayRef.h:210
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
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:337
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:335
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:393
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:257
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:516
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:216
const Instruction & front() const
Definition: BasicBlock.h:347
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:408
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:140
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:296
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:227
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:345
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:489
const Instruction & back() const
Definition: BasicBlock.h:349
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:145
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:353
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:874
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1762
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:1190
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1474
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
Definition: InstrTypes.h:1521
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:1412
CallingConv::ID getCallingConv() const
Definition: InstrTypes.h:1470
Value * getCalledOperand() const
Definition: InstrTypes.h:1405
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1493
FunctionType * getFunctionType() const
Definition: InstrTypes.h:1270
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1348
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1489
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)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:711
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:740
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:741
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:735
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:734
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:738
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:736
@ ICMP_EQ
equal
Definition: InstrTypes.h:732
@ ICMP_NE
not equal
Definition: InstrTypes.h:733
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:739
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:737
bool isSigned() const
Definition: InstrTypes.h:961
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:801
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2199
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2582
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2185
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2588
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:1691
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:747
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
This instruction compares its operands according to the predicate given to the constructor.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2625
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:89
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:392
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:71
bool extractProfTotalWeight(uint64_t &TotalVal) const
Retrieve total raw weight values of a branch.
Definition: Metadata.cpp:1641
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:734
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:302
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:1521
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:83
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:389
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
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:950
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1034
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1416
static MDNode * getMergedProfMetadata(MDNode *A, MDNode *B, const Instruction *AInstr, const Instruction *BInstr)
Merge !prof metadata from two instructions.
Definition: Metadata.cpp:1116
static MDNode * getMostGenericFPMath(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1066
static MDNode * getMostGenericRange(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1178
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1021
static MDNode * getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1250
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
iterator end()
Definition: MapVector.h:71
iterator find(const KeyT &Key)
Definition: MapVector.h:146
bool empty() const
Definition: MapVector.h:79
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:117
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.h:254
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:1743
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:87
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:264
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
value_type pop_back_val()
Definition: SetVector.h:285
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:345
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
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:366
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:390
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
size_type size() const
Definition: SmallSet.h:161
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void reserve(size_type N)
Definition: SmallVector.h:667
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:809
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Provides information about what library functions are available for the current target.
bool hasOptimizedCodeGen(LibFunc F) const
Tests if the function is both available and a candidate for optimized code generation.
bool has(LibFunc F) const
Tests whether a library function is available.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
Definition: TypeSize.h:322
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:265
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:252
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:234
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
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:249
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
Definition: Type.h:243
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:228
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:225
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:1724
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:535
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:1069
static constexpr unsigned MaxAlignmentExponent
The maximum alignment for instructions.
Definition: Value.h:794
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:309
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:384
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:1422
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:780
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:545
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:440
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:1747
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:1727
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:529
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:2391
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:2282
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:2918
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:1394
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:2371
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:2821
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:2443
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:666
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:717
bool isAssumeWithEmptyBundle(const AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
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)
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
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:1734
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 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:1062
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: DebugInfo.cpp:103
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:3362
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:1985
CallInst * createCallMatchingInvoke(InvokeInst *II)
Create a call that matches the invoke II in terms of arguments, attributes, debug information,...
Definition: Local.cpp:2345
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:2632
bool wouldInstructionBeTriviallyDead(const 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
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition: Local.cpp:2873
DebugLoc getDebugValueLoc(DbgVariableIntrinsic *DII)
Produce a DebugLoc to use for each dbg.declare that is promoted to a dbg.value.
Definition: DebugInfo.cpp:114
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:99
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:2933
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:2707
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:2306
bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)
Point debug users of From to To or salvage them.
Definition: Local.cpp:2227
Value * salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Ops, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:2093
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2800
void dropDebugUsers(Instruction &I)
Remove the debug intrinsic instructions for the given instruction.
Definition: Local.cpp:3029
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
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:757
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in @llvm.dbg intrinsics with undef.
Definition: Local.cpp:606
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:3036
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:3005
void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a nonnull metadata node to a new load instruction.
Definition: Local.cpp:2980
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=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 canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
Definition: Local.cpp:3473
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
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 * 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:544
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:1926
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
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:1884
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:637
bool inferAttributesFromOthers(Function &F)
If we can infer one attribute from another on the declaration of a function, explicitly materialize t...
Definition: Local.cpp:3580
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3546
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:3463
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:2670
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
Definition: Local.cpp:1383
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
Definition: Local.cpp:2951
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:50
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