1 //===-- Local.cpp - Functions to perform local transformations ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This family of functions perform various local transformations to the
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Utils/Local.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseSet.h"
18 #include "llvm/ADT/Hashing.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/EHPersonalities.h"
24 #include "llvm/Analysis/InstructionSimplify.h"
25 #include "llvm/Analysis/MemoryBuiltins.h"
26 #include "llvm/Analysis/LazyValueInfo.h"
27 #include "llvm/Analysis/ValueTracking.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DIBuilder.h"
31 #include "llvm/IR/DataLayout.h"
32 #include "llvm/IR/DebugInfo.h"
33 #include "llvm/IR/DerivedTypes.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/GetElementPtrTypeIterator.h"
36 #include "llvm/IR/GlobalAlias.h"
37 #include "llvm/IR/GlobalVariable.h"
38 #include "llvm/IR/IRBuilder.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/Intrinsics.h"
42 #include "llvm/IR/MDBuilder.h"
43 #include "llvm/IR/Metadata.h"
44 #include "llvm/IR/Operator.h"
45 #include "llvm/IR/PatternMatch.h"
46 #include "llvm/IR/ValueHandle.h"
47 #include "llvm/Support/Debug.h"
48 #include "llvm/Support/KnownBits.h"
49 #include "llvm/Support/MathExtras.h"
50 #include "llvm/Support/raw_ostream.h"
52 using namespace llvm::PatternMatch;
54 #define DEBUG_TYPE "local"
56 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
58 //===----------------------------------------------------------------------===//
59 // Local constant propagation.
62 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
63 /// constant value, convert it into an unconditional branch to the constant
64 /// destination. This is a nontrivial operation because the successors of this
65 /// basic block must have their PHI nodes updated.
66 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
67 /// conditions and indirectbr addresses this might make dead if
68 /// DeleteDeadConditions is true.
69 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
70 const TargetLibraryInfo *TLI) {
71 TerminatorInst *T = BB->getTerminator();
72 IRBuilder<> Builder(T);
74 // Branch - See if we are conditional jumping on constant
75 if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
76 if (BI->isUnconditional()) return false; // Can't optimize uncond branch
77 BasicBlock *Dest1 = BI->getSuccessor(0);
78 BasicBlock *Dest2 = BI->getSuccessor(1);
80 if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
81 // Are we branching on constant?
82 // YES. Change to unconditional branch...
83 BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
84 BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;
86 //cerr << "Function: " << T->getParent()->getParent()
87 // << "\nRemoving branch from " << T->getParent()
88 // << "\n\nTo: " << OldDest << endl;
90 // Let the basic block know that we are letting go of it. Based on this,
91 // it will adjust it's PHI nodes.
92 OldDest->removePredecessor(BB);
94 // Replace the conditional branch with an unconditional one.
95 Builder.CreateBr(Destination);
96 BI->eraseFromParent();
100 if (Dest2 == Dest1) { // Conditional branch to same location?
101 // This branch matches something like this:
102 // br bool %cond, label %Dest, label %Dest
103 // and changes it into: br label %Dest
105 // Let the basic block know that we are letting go of one copy of it.
106 assert(BI->getParent() && "Terminator not inserted in block!");
107 Dest1->removePredecessor(BI->getParent());
109 // Replace the conditional branch with an unconditional one.
110 Builder.CreateBr(Dest1);
111 Value *Cond = BI->getCondition();
112 BI->eraseFromParent();
113 if (DeleteDeadConditions)
114 RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
120 if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
121 // If we are switching on a constant, we can convert the switch to an
122 // unconditional branch.
123 ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
124 BasicBlock *DefaultDest = SI->getDefaultDest();
125 BasicBlock *TheOnlyDest = DefaultDest;
127 // If the default is unreachable, ignore it when searching for TheOnlyDest.
128 if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) &&
129 SI->getNumCases() > 0) {
130 TheOnlyDest = SI->case_begin()->getCaseSuccessor();
133 // Figure out which case it goes to.
134 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
135 // Found case matching a constant operand?
136 if (i->getCaseValue() == CI) {
137 TheOnlyDest = i->getCaseSuccessor();
141 // Check to see if this branch is going to the same place as the default
142 // dest. If so, eliminate it as an explicit compare.
143 if (i->getCaseSuccessor() == DefaultDest) {
144 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
145 unsigned NCases = SI->getNumCases();
146 // Fold the case metadata into the default if there will be any branches
147 // left, unless the metadata doesn't match the switch.
148 if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
149 // Collect branch weights into a vector.
150 SmallVector<uint32_t, 8> Weights;
151 for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
153 auto *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i));
154 Weights.push_back(CI->getValue().getZExtValue());
156 // Merge weight of this case to the default weight.
157 unsigned idx = i->getCaseIndex();
158 Weights[0] += Weights[idx+1];
159 // Remove weight for this case.
160 std::swap(Weights[idx+1], Weights.back());
162 SI->setMetadata(LLVMContext::MD_prof,
163 MDBuilder(BB->getContext()).
164 createBranchWeights(Weights));
166 // Remove this entry.
167 DefaultDest->removePredecessor(SI->getParent());
168 i = SI->removeCase(i);
173 // Otherwise, check to see if the switch only branches to one destination.
174 // We do this by reseting "TheOnlyDest" to null when we find two non-equal
176 if (i->getCaseSuccessor() != TheOnlyDest)
177 TheOnlyDest = nullptr;
179 // Increment this iterator as we haven't removed the case.
183 if (CI && !TheOnlyDest) {
184 // Branching on a constant, but not any of the cases, go to the default
186 TheOnlyDest = SI->getDefaultDest();
189 // If we found a single destination that we can fold the switch into, do so
192 // Insert the new branch.
193 Builder.CreateBr(TheOnlyDest);
194 BasicBlock *BB = SI->getParent();
196 // Remove entries from PHI nodes which we no longer branch to...
197 for (BasicBlock *Succ : SI->successors()) {
198 // Found case matching a constant operand?
199 if (Succ == TheOnlyDest)
200 TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
202 Succ->removePredecessor(BB);
205 // Delete the old switch.
206 Value *Cond = SI->getCondition();
207 SI->eraseFromParent();
208 if (DeleteDeadConditions)
209 RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
213 if (SI->getNumCases() == 1) {
214 // Otherwise, we can fold this switch into a conditional branch
215 // instruction if it has only one non-default destination.
216 auto FirstCase = *SI->case_begin();
217 Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
218 FirstCase.getCaseValue(), "cond");
220 // Insert the new branch.
221 BranchInst *NewBr = Builder.CreateCondBr(Cond,
222 FirstCase.getCaseSuccessor(),
223 SI->getDefaultDest());
224 MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
225 if (MD && MD->getNumOperands() == 3) {
226 ConstantInt *SICase =
227 mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
229 mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
230 assert(SICase && SIDef);
231 // The TrueWeight should be the weight for the single case of SI.
232 NewBr->setMetadata(LLVMContext::MD_prof,
233 MDBuilder(BB->getContext()).
234 createBranchWeights(SICase->getValue().getZExtValue(),
235 SIDef->getValue().getZExtValue()));
238 // Update make.implicit metadata to the newly-created conditional branch.
239 MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
241 NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
243 // Delete the old switch.
244 SI->eraseFromParent();
250 if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
251 // indirectbr blockaddress(@F, @BB) -> br label @BB
252 if (BlockAddress *BA =
253 dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
254 BasicBlock *TheOnlyDest = BA->getBasicBlock();
255 // Insert the new branch.
256 Builder.CreateBr(TheOnlyDest);
258 for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
259 if (IBI->getDestination(i) == TheOnlyDest)
260 TheOnlyDest = nullptr;
262 IBI->getDestination(i)->removePredecessor(IBI->getParent());
264 Value *Address = IBI->getAddress();
265 IBI->eraseFromParent();
266 if (DeleteDeadConditions)
267 RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
269 // If we didn't find our destination in the IBI successor list, then we
270 // have undefined behavior. Replace the unconditional branch with an
271 // 'unreachable' instruction.
273 BB->getTerminator()->eraseFromParent();
274 new UnreachableInst(BB->getContext(), BB);
285 //===----------------------------------------------------------------------===//
286 // Local dead code elimination.
289 /// isInstructionTriviallyDead - Return true if the result produced by the
290 /// instruction is not used, and the instruction has no side effects.
292 bool llvm::isInstructionTriviallyDead(Instruction *I,
293 const TargetLibraryInfo *TLI) {
296 return wouldInstructionBeTriviallyDead(I, TLI);
299 bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
300 const TargetLibraryInfo *TLI) {
301 if (isa<TerminatorInst>(I))
304 // We don't want the landingpad-like instructions removed by anything this
309 // We don't want debug info removed by anything this general, unless
310 // debug info is empty.
311 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
312 if (DDI->getAddress())
316 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
322 if (!I->mayHaveSideEffects())
325 // Special case intrinsics that "may have side effects" but can be deleted
327 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
328 // Safe to delete llvm.stacksave if dead.
329 if (II->getIntrinsicID() == Intrinsic::stacksave)
332 // Lifetime intrinsics are dead when their right-hand is undef.
333 if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
334 II->getIntrinsicID() == Intrinsic::lifetime_end)
335 return isa<UndefValue>(II->getArgOperand(1));
337 // Assumptions are dead if their condition is trivially true. Guards on
338 // true are operationally no-ops. In the future we can consider more
339 // sophisticated tradeoffs for guards considering potential for check
340 // widening, but for now we keep things simple.
341 if (II->getIntrinsicID() == Intrinsic::assume ||
342 II->getIntrinsicID() == Intrinsic::experimental_guard) {
343 if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
344 return !Cond->isZero();
350 if (isAllocLikeFn(I, TLI))
353 if (CallInst *CI = isFreeCall(I, TLI))
354 if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
355 return C->isNullValue() || isa<UndefValue>(C);
357 if (CallSite CS = CallSite(I))
358 if (isMathLibCallNoop(CS, TLI))
364 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
365 /// trivially dead instruction, delete it. If that makes any of its operands
366 /// trivially dead, delete them too, recursively. Return true if any
367 /// instructions were deleted.
369 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
370 const TargetLibraryInfo *TLI) {
371 Instruction *I = dyn_cast<Instruction>(V);
372 if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI))
375 SmallVector<Instruction*, 16> DeadInsts;
376 DeadInsts.push_back(I);
379 I = DeadInsts.pop_back_val();
381 // Null out all of the instruction's operands to see if any operand becomes
383 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
384 Value *OpV = I->getOperand(i);
385 I->setOperand(i, nullptr);
387 if (!OpV->use_empty()) continue;
389 // If the operand is an instruction that became dead as we nulled out the
390 // operand, and if it is 'trivially' dead, delete it in a future loop
392 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
393 if (isInstructionTriviallyDead(OpI, TLI))
394 DeadInsts.push_back(OpI);
397 I->eraseFromParent();
398 } while (!DeadInsts.empty());
403 /// areAllUsesEqual - Check whether the uses of a value are all the same.
404 /// This is similar to Instruction::hasOneUse() except this will also return
405 /// true when there are no uses or multiple uses that all refer to the same
407 static bool areAllUsesEqual(Instruction *I) {
408 Value::user_iterator UI = I->user_begin();
409 Value::user_iterator UE = I->user_end();
414 for (++UI; UI != UE; ++UI) {
421 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
422 /// dead PHI node, due to being a def-use chain of single-use nodes that
423 /// either forms a cycle or is terminated by a trivially dead instruction,
424 /// delete it. If that makes any of its operands trivially dead, delete them
425 /// too, recursively. Return true if a change was made.
426 bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN,
427 const TargetLibraryInfo *TLI) {
428 SmallPtrSet<Instruction*, 4> Visited;
429 for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
430 I = cast<Instruction>(*I->user_begin())) {
432 return RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
434 // If we find an instruction more than once, we're on a cycle that
435 // won't prove fruitful.
436 if (!Visited.insert(I).second) {
437 // Break the cycle and delete the instruction and its operands.
438 I->replaceAllUsesWith(UndefValue::get(I->getType()));
439 (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
447 simplifyAndDCEInstruction(Instruction *I,
448 SmallSetVector<Instruction *, 16> &WorkList,
449 const DataLayout &DL,
450 const TargetLibraryInfo *TLI) {
451 if (isInstructionTriviallyDead(I, TLI)) {
452 // Null out all of the instruction's operands to see if any operand becomes
454 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
455 Value *OpV = I->getOperand(i);
456 I->setOperand(i, nullptr);
458 if (!OpV->use_empty() || I == OpV)
461 // If the operand is an instruction that became dead as we nulled out the
462 // operand, and if it is 'trivially' dead, delete it in a future loop
464 if (Instruction *OpI = dyn_cast<Instruction>(OpV))
465 if (isInstructionTriviallyDead(OpI, TLI))
466 WorkList.insert(OpI);
469 I->eraseFromParent();
474 if (Value *SimpleV = SimplifyInstruction(I, DL)) {
475 // Add the users to the worklist. CAREFUL: an instruction can use itself,
476 // in the case of a phi node.
477 for (User *U : I->users()) {
479 WorkList.insert(cast<Instruction>(U));
483 // Replace the instruction with its simplified value.
484 bool Changed = false;
485 if (!I->use_empty()) {
486 I->replaceAllUsesWith(SimpleV);
489 if (isInstructionTriviallyDead(I, TLI)) {
490 I->eraseFromParent();
498 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
499 /// simplify any instructions in it and recursively delete dead instructions.
501 /// This returns true if it changed the code, note that it can delete
502 /// instructions in other blocks as well in this block.
503 bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB,
504 const TargetLibraryInfo *TLI) {
505 bool MadeChange = false;
506 const DataLayout &DL = BB->getModule()->getDataLayout();
509 // In debug builds, ensure that the terminator of the block is never replaced
510 // or deleted by these simplifications. The idea of simplification is that it
511 // cannot introduce new instructions, and there is no way to replace the
512 // terminator of a block without introducing a new instruction.
513 AssertingVH<Instruction> TerminatorVH(&BB->back());
516 SmallSetVector<Instruction *, 16> WorkList;
517 // Iterate over the original function, only adding insts to the worklist
518 // if they actually need to be revisited. This avoids having to pre-init
519 // the worklist with the entire function's worth of instructions.
520 for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end());
522 assert(!BI->isTerminator());
523 Instruction *I = &*BI;
526 // We're visiting this instruction now, so make sure it's not in the
527 // worklist from an earlier visit.
528 if (!WorkList.count(I))
529 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
532 while (!WorkList.empty()) {
533 Instruction *I = WorkList.pop_back_val();
534 MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
539 //===----------------------------------------------------------------------===//
540 // Control Flow Graph Restructuring.
544 /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this
545 /// method is called when we're about to delete Pred as a predecessor of BB. If
546 /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred.
548 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
549 /// nodes that collapse into identity values. For example, if we have:
550 /// x = phi(1, 0, 0, 0)
553 /// .. and delete the predecessor corresponding to the '1', this will attempt to
554 /// recursively fold the and to 0.
555 void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) {
556 // This only adjusts blocks with PHI nodes.
557 if (!isa<PHINode>(BB->begin()))
560 // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
561 // them down. This will leave us with single entry phi nodes and other phis
562 // that can be removed.
563 BB->removePredecessor(Pred, true);
565 WeakTrackingVH PhiIt = &BB->front();
566 while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
567 PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
568 Value *OldPhiIt = PhiIt;
570 if (!recursivelySimplifyInstruction(PN))
573 // If recursive simplification ended up deleting the next PHI node we would
574 // iterate to, then our iterator is invalid, restart scanning from the top
576 if (PhiIt != OldPhiIt) PhiIt = &BB->front();
581 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
582 /// predecessor is known to have one successor (DestBB!). Eliminate the edge
583 /// between them, moving the instructions in the predecessor into DestBB and
584 /// deleting the predecessor block.
586 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) {
587 // If BB has single-entry PHI nodes, fold them.
588 while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
589 Value *NewVal = PN->getIncomingValue(0);
590 // Replace self referencing PHI with undef, it must be dead.
591 if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
592 PN->replaceAllUsesWith(NewVal);
593 PN->eraseFromParent();
596 BasicBlock *PredBB = DestBB->getSinglePredecessor();
597 assert(PredBB && "Block doesn't have a single predecessor!");
599 // Zap anything that took the address of DestBB. Not doing this will give the
600 // address an invalid value.
601 if (DestBB->hasAddressTaken()) {
602 BlockAddress *BA = BlockAddress::get(DestBB);
603 Constant *Replacement =
604 ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1);
605 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
607 BA->destroyConstant();
610 // Anything that branched to PredBB now branches to DestBB.
611 PredBB->replaceAllUsesWith(DestBB);
613 // Splice all the instructions from PredBB to DestBB.
614 PredBB->getTerminator()->eraseFromParent();
615 DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
617 // If the PredBB is the entry block of the function, move DestBB up to
618 // become the entry block after we erase PredBB.
619 if (PredBB == &DestBB->getParent()->getEntryBlock())
620 DestBB->moveAfter(PredBB);
623 BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock();
624 DT->changeImmediateDominator(DestBB, PredBBIDom);
625 DT->eraseNode(PredBB);
628 PredBB->eraseFromParent();
631 /// CanMergeValues - Return true if we can choose one of these values to use
632 /// in place of the other. Note that we will always choose the non-undef
634 static bool CanMergeValues(Value *First, Value *Second) {
635 return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
638 /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an
639 /// almost-empty BB ending in an unconditional branch to Succ, into Succ.
641 /// Assumption: Succ is the single successor for BB.
643 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
644 assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
646 DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
647 << Succ->getName() << "\n");
648 // Shortcut, if there is only a single predecessor it must be BB and merging
650 if (Succ->getSinglePredecessor()) return true;
652 // Make a list of the predecessors of BB
653 SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
655 // Look at all the phi nodes in Succ, to see if they present a conflict when
656 // merging these blocks
657 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
658 PHINode *PN = cast<PHINode>(I);
660 // If the incoming value from BB is again a PHINode in
661 // BB which has the same incoming value for *PI as PN does, we can
662 // merge the phi nodes and then the blocks can still be merged
663 PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
664 if (BBPN && BBPN->getParent() == BB) {
665 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
666 BasicBlock *IBB = PN->getIncomingBlock(PI);
667 if (BBPreds.count(IBB) &&
668 !CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
669 PN->getIncomingValue(PI))) {
670 DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
671 << Succ->getName() << " is conflicting with "
672 << BBPN->getName() << " with regard to common predecessor "
673 << IBB->getName() << "\n");
678 Value* Val = PN->getIncomingValueForBlock(BB);
679 for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
680 // See if the incoming value for the common predecessor is equal to the
681 // one for BB, in which case this phi node will not prevent the merging
683 BasicBlock *IBB = PN->getIncomingBlock(PI);
684 if (BBPreds.count(IBB) &&
685 !CanMergeValues(Val, PN->getIncomingValue(PI))) {
686 DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
687 << Succ->getName() << " is conflicting with regard to common "
688 << "predecessor " << IBB->getName() << "\n");
698 typedef SmallVector<BasicBlock *, 16> PredBlockVector;
699 typedef DenseMap<BasicBlock *, Value *> IncomingValueMap;
701 /// \brief Determines the value to use as the phi node input for a block.
703 /// Select between \p OldVal any value that we know flows from \p BB
704 /// to a particular phi on the basis of which one (if either) is not
705 /// undef. Update IncomingValues based on the selected value.
707 /// \param OldVal The value we are considering selecting.
708 /// \param BB The block that the value flows in from.
709 /// \param IncomingValues A map from block-to-value for other phi inputs
710 /// that we have examined.
712 /// \returns the selected value.
713 static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB,
714 IncomingValueMap &IncomingValues) {
715 if (!isa<UndefValue>(OldVal)) {
716 assert((!IncomingValues.count(BB) ||
717 IncomingValues.find(BB)->second == OldVal) &&
718 "Expected OldVal to match incoming value from BB!");
720 IncomingValues.insert(std::make_pair(BB, OldVal));
724 IncomingValueMap::const_iterator It = IncomingValues.find(BB);
725 if (It != IncomingValues.end()) return It->second;
730 /// \brief Create a map from block to value for the operands of a
733 /// Create a map from block to value for each non-undef value flowing
736 /// \param PN The phi we are collecting the map for.
737 /// \param IncomingValues [out] The map from block to value for this phi.
738 static void gatherIncomingValuesToPhi(PHINode *PN,
739 IncomingValueMap &IncomingValues) {
740 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
741 BasicBlock *BB = PN->getIncomingBlock(i);
742 Value *V = PN->getIncomingValue(i);
744 if (!isa<UndefValue>(V))
745 IncomingValues.insert(std::make_pair(BB, V));
749 /// \brief Replace the incoming undef values to a phi with the values
750 /// from a block-to-value map.
752 /// \param PN The phi we are replacing the undefs in.
753 /// \param IncomingValues A map from block to value.
754 static void replaceUndefValuesInPhi(PHINode *PN,
755 const IncomingValueMap &IncomingValues) {
756 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
757 Value *V = PN->getIncomingValue(i);
759 if (!isa<UndefValue>(V)) continue;
761 BasicBlock *BB = PN->getIncomingBlock(i);
762 IncomingValueMap::const_iterator It = IncomingValues.find(BB);
763 if (It == IncomingValues.end()) continue;
765 PN->setIncomingValue(i, It->second);
769 /// \brief Replace a value flowing from a block to a phi with
770 /// potentially multiple instances of that value flowing from the
771 /// block's predecessors to the phi.
773 /// \param BB The block with the value flowing into the phi.
774 /// \param BBPreds The predecessors of BB.
775 /// \param PN The phi that we are updating.
776 static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
777 const PredBlockVector &BBPreds,
779 Value *OldVal = PN->removeIncomingValue(BB, false);
780 assert(OldVal && "No entry in PHI for Pred BB!");
782 IncomingValueMap IncomingValues;
784 // We are merging two blocks - BB, and the block containing PN - and
785 // as a result we need to redirect edges from the predecessors of BB
786 // to go to the block containing PN, and update PN
787 // accordingly. Since we allow merging blocks in the case where the
788 // predecessor and successor blocks both share some predecessors,
789 // and where some of those common predecessors might have undef
790 // values flowing into PN, we want to rewrite those values to be
791 // consistent with the non-undef values.
793 gatherIncomingValuesToPhi(PN, IncomingValues);
795 // If this incoming value is one of the PHI nodes in BB, the new entries
796 // in the PHI node are the entries from the old PHI.
797 if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
798 PHINode *OldValPN = cast<PHINode>(OldVal);
799 for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
800 // Note that, since we are merging phi nodes and BB and Succ might
801 // have common predecessors, we could end up with a phi node with
802 // identical incoming branches. This will be cleaned up later (and
803 // will trigger asserts if we try to clean it up now, without also
804 // simplifying the corresponding conditional branch).
805 BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
806 Value *PredVal = OldValPN->getIncomingValue(i);
807 Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
810 // And add a new incoming value for this predecessor for the
811 // newly retargeted branch.
812 PN->addIncoming(Selected, PredBB);
815 for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
816 // Update existing incoming values in PN for this
817 // predecessor of BB.
818 BasicBlock *PredBB = BBPreds[i];
819 Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
822 // And add a new incoming value for this predecessor for the
823 // newly retargeted branch.
824 PN->addIncoming(Selected, PredBB);
828 replaceUndefValuesInPhi(PN, IncomingValues);
831 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
832 /// unconditional branch, and contains no instructions other than PHI nodes,
833 /// potential side-effect free intrinsics and the branch. If possible,
834 /// eliminate BB by rewriting all the predecessors to branch to the successor
835 /// block and return true. If we can't transform, return false.
836 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {
837 assert(BB != &BB->getParent()->getEntryBlock() &&
838 "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
840 // We can't eliminate infinite loops.
841 BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
842 if (BB == Succ) return false;
844 // Check to see if merging these blocks would cause conflicts for any of the
845 // phi nodes in BB or Succ. If not, we can safely merge.
846 if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
848 // Check for cases where Succ has multiple predecessors and a PHI node in BB
849 // has uses which will not disappear when the PHI nodes are merged. It is
850 // possible to handle such cases, but difficult: it requires checking whether
851 // BB dominates Succ, which is non-trivial to calculate in the case where
852 // Succ has multiple predecessors. Also, it requires checking whether
853 // constructing the necessary self-referential PHI node doesn't introduce any
854 // conflicts; this isn't too difficult, but the previous code for doing this
857 // Note that if this check finds a live use, BB dominates Succ, so BB is
858 // something like a loop pre-header (or rarely, a part of an irreducible CFG);
859 // folding the branch isn't profitable in that case anyway.
860 if (!Succ->getSinglePredecessor()) {
861 BasicBlock::iterator BBI = BB->begin();
862 while (isa<PHINode>(*BBI)) {
863 for (Use &U : BBI->uses()) {
864 if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
865 if (PN->getIncomingBlock(U) != BB)
875 DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
877 if (isa<PHINode>(Succ->begin())) {
878 // If there is more than one pred of succ, and there are PHI nodes in
879 // the successor, then we need to add incoming edges for the PHI nodes
881 const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
883 // Loop over all of the PHI nodes in the successor of BB.
884 for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
885 PHINode *PN = cast<PHINode>(I);
887 redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
891 if (Succ->getSinglePredecessor()) {
892 // BB is the only predecessor of Succ, so Succ will end up with exactly
893 // the same predecessors BB had.
895 // Copy over any phi, debug or lifetime instruction.
896 BB->getTerminator()->eraseFromParent();
897 Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
900 while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
901 // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
902 assert(PN->use_empty() && "There shouldn't be any uses here!");
903 PN->eraseFromParent();
907 // If the unconditional branch we replaced contains llvm.loop metadata, we
908 // add the metadata to the branch instructions in the predecessors.
909 unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
910 Instruction *TI = BB->getTerminator();
912 if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
913 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
914 BasicBlock *Pred = *PI;
915 Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
918 // Everything that jumped to BB now goes to Succ.
919 BB->replaceAllUsesWith(Succ);
920 if (!Succ->hasName()) Succ->takeName(BB);
921 BB->eraseFromParent(); // Delete the old basic block.
925 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
926 /// nodes in this block. This doesn't try to be clever about PHI nodes
927 /// which differ only in the order of the incoming values, but instcombine
928 /// orders them so it usually won't matter.
930 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
931 // This implementation doesn't currently consider undef operands
932 // specially. Theoretically, two phis which are identical except for
933 // one having an undef where the other doesn't could be collapsed.
935 struct PHIDenseMapInfo {
936 static PHINode *getEmptyKey() {
937 return DenseMapInfo<PHINode *>::getEmptyKey();
939 static PHINode *getTombstoneKey() {
940 return DenseMapInfo<PHINode *>::getTombstoneKey();
942 static unsigned getHashValue(PHINode *PN) {
943 // Compute a hash value on the operands. Instcombine will likely have
944 // sorted them, which helps expose duplicates, but we have to check all
945 // the operands to be safe in case instcombine hasn't run.
946 return static_cast<unsigned>(hash_combine(
947 hash_combine_range(PN->value_op_begin(), PN->value_op_end()),
948 hash_combine_range(PN->block_begin(), PN->block_end())));
950 static bool isEqual(PHINode *LHS, PHINode *RHS) {
951 if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
952 RHS == getEmptyKey() || RHS == getTombstoneKey())
954 return LHS->isIdenticalTo(RHS);
958 // Set of unique PHINodes.
959 DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
962 bool Changed = false;
963 for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
964 auto Inserted = PHISet.insert(PN);
965 if (!Inserted.second) {
966 // A duplicate. Replace this PHI with its duplicate.
967 PN->replaceAllUsesWith(*Inserted.first);
968 PN->eraseFromParent();
971 // The RAUW can change PHIs that we already visited. Start over from the
981 /// enforceKnownAlignment - If the specified pointer points to an object that
982 /// we control, modify the object's alignment to PrefAlign. This isn't
983 /// often possible though. If alignment is important, a more reliable approach
984 /// is to simply align all global variables and allocation instructions to
985 /// their preferred alignment from the beginning.
987 static unsigned enforceKnownAlignment(Value *V, unsigned Align,
989 const DataLayout &DL) {
990 assert(PrefAlign > Align);
992 V = V->stripPointerCasts();
994 if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
995 // TODO: ideally, computeKnownBits ought to have used
996 // AllocaInst::getAlignment() in its computation already, making
997 // the below max redundant. But, as it turns out,
998 // stripPointerCasts recurses through infinite layers of bitcasts,
999 // while computeKnownBits is not allowed to traverse more than 6
1001 Align = std::max(AI->getAlignment(), Align);
1002 if (PrefAlign <= Align)
1005 // If the preferred alignment is greater than the natural stack alignment
1006 // then don't round up. This avoids dynamic stack realignment.
1007 if (DL.exceedsNaturalStackAlignment(PrefAlign))
1009 AI->setAlignment(PrefAlign);
1013 if (auto *GO = dyn_cast<GlobalObject>(V)) {
1014 // TODO: as above, this shouldn't be necessary.
1015 Align = std::max(GO->getAlignment(), Align);
1016 if (PrefAlign <= Align)
1019 // If there is a large requested alignment and we can, bump up the alignment
1020 // of the global. If the memory we set aside for the global may not be the
1021 // memory used by the final program then it is impossible for us to reliably
1022 // enforce the preferred alignment.
1023 if (!GO->canIncreaseAlignment())
1026 GO->setAlignment(PrefAlign);
1033 unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
1034 const DataLayout &DL,
1035 const Instruction *CxtI,
1036 AssumptionCache *AC,
1037 const DominatorTree *DT) {
1038 assert(V->getType()->isPointerTy() &&
1039 "getOrEnforceKnownAlignment expects a pointer!");
1041 KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT);
1042 unsigned TrailZ = Known.countMinTrailingZeros();
1044 // Avoid trouble with ridiculously large TrailZ values, such as
1045 // those computed from a null pointer.
1046 TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1));
1048 unsigned Align = 1u << std::min(Known.getBitWidth() - 1, TrailZ);
1050 // LLVM doesn't support alignments larger than this currently.
1051 Align = std::min(Align, +Value::MaximumAlignment);
1053 if (PrefAlign > Align)
1054 Align = enforceKnownAlignment(V, Align, PrefAlign, DL);
1056 // We don't need to make any adjustment.
1060 ///===---------------------------------------------------------------------===//
1061 /// Dbg Intrinsic utilities
1064 /// See if there is a dbg.value intrinsic for DIVar before I.
1065 static bool LdStHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr,
1067 // Since we can't guarantee that the original dbg.declare instrinsic
1068 // is removed by LowerDbgDeclare(), we need to make sure that we are
1069 // not inserting the same dbg.value intrinsic over and over.
1070 llvm::BasicBlock::InstListType::iterator PrevI(I);
1071 if (PrevI != I->getParent()->getInstList().begin()) {
1073 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
1074 if (DVI->getValue() == I->getOperand(0) &&
1075 DVI->getOffset() == 0 &&
1076 DVI->getVariable() == DIVar &&
1077 DVI->getExpression() == DIExpr)
1083 /// See if there is a dbg.value intrinsic for DIVar for the PHI node.
1084 static bool PhiHasDebugValue(DILocalVariable *DIVar,
1085 DIExpression *DIExpr,
1087 // Since we can't guarantee that the original dbg.declare instrinsic
1088 // is removed by LowerDbgDeclare(), we need to make sure that we are
1089 // not inserting the same dbg.value intrinsic over and over.
1090 SmallVector<DbgValueInst *, 1> DbgValues;
1091 findDbgValues(DbgValues, APN);
1092 for (auto *DVI : DbgValues) {
1093 assert(DVI->getValue() == APN);
1094 assert(DVI->getOffset() == 0);
1095 if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1101 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1102 /// that has an associated llvm.dbg.decl intrinsic.
1103 void llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
1104 StoreInst *SI, DIBuilder &Builder) {
1105 auto *DIVar = DDI->getVariable();
1106 assert(DIVar && "Missing variable");
1107 auto *DIExpr = DDI->getExpression();
1108 Value *DV = SI->getOperand(0);
1110 // If an argument is zero extended then use argument directly. The ZExt
1111 // may be zapped by an optimization pass in future.
1112 Argument *ExtendedArg = nullptr;
1113 if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
1114 ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0));
1115 if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
1116 ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0));
1118 // If this DDI was already describing only a fragment of a variable, ensure
1119 // that fragment is appropriately narrowed here.
1120 // But if a fragment wasn't used, describe the value as the original
1121 // argument (rather than the zext or sext) so that it remains described even
1122 // if the sext/zext is optimized away. This widens the variable description,
1123 // leaving it up to the consumer to know how the smaller value may be
1124 // represented in a larger register.
1125 if (auto Fragment = DIExpr->getFragmentInfo()) {
1126 unsigned FragmentOffset = Fragment->OffsetInBits;
1127 SmallVector<uint64_t, 3> Ops(DIExpr->elements_begin(),
1128 DIExpr->elements_end() - 3);
1129 Ops.push_back(dwarf::DW_OP_LLVM_fragment);
1130 Ops.push_back(FragmentOffset);
1131 const DataLayout &DL = DDI->getModule()->getDataLayout();
1132 Ops.push_back(DL.getTypeSizeInBits(ExtendedArg->getType()));
1133 DIExpr = Builder.createExpression(Ops);
1137 if (!LdStHasDebugValue(DIVar, DIExpr, SI))
1138 Builder.insertDbgValueIntrinsic(DV, 0, DIVar, DIExpr, DDI->getDebugLoc(),
1142 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1143 /// that has an associated llvm.dbg.decl intrinsic.
1144 void llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
1145 LoadInst *LI, DIBuilder &Builder) {
1146 auto *DIVar = DDI->getVariable();
1147 auto *DIExpr = DDI->getExpression();
1148 assert(DIVar && "Missing variable");
1150 if (LdStHasDebugValue(DIVar, DIExpr, LI))
1153 // We are now tracking the loaded value instead of the address. In the
1154 // future if multi-location support is added to the IR, it might be
1155 // preferable to keep tracking both the loaded value and the original
1156 // address in case the alloca can not be elided.
1157 Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
1158 LI, 0, DIVar, DIExpr, DDI->getDebugLoc(), (Instruction *)nullptr);
1159 DbgValue->insertAfter(LI);
1162 /// Inserts a llvm.dbg.value intrinsic after a phi
1163 /// that has an associated llvm.dbg.decl intrinsic.
1164 void llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
1165 PHINode *APN, DIBuilder &Builder) {
1166 auto *DIVar = DDI->getVariable();
1167 auto *DIExpr = DDI->getExpression();
1168 assert(DIVar && "Missing variable");
1170 if (PhiHasDebugValue(DIVar, DIExpr, APN))
1173 BasicBlock *BB = APN->getParent();
1174 auto InsertionPt = BB->getFirstInsertionPt();
1176 // The block may be a catchswitch block, which does not have a valid
1178 // FIXME: Insert dbg.value markers in the successors when appropriate.
1179 if (InsertionPt != BB->end())
1180 Builder.insertDbgValueIntrinsic(APN, 0, DIVar, DIExpr, DDI->getDebugLoc(),
1184 /// Determine whether this alloca is either a VLA or an array.
1185 static bool isArray(AllocaInst *AI) {
1186 return AI->isArrayAllocation() ||
1187 AI->getType()->getElementType()->isArrayTy();
1190 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1191 /// of llvm.dbg.value intrinsics.
1192 bool llvm::LowerDbgDeclare(Function &F) {
1193 DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1194 SmallVector<DbgDeclareInst *, 4> Dbgs;
1196 for (Instruction &BI : FI)
1197 if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
1198 Dbgs.push_back(DDI);
1203 for (auto &I : Dbgs) {
1204 DbgDeclareInst *DDI = I;
1205 AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1206 // If this is an alloca for a scalar variable, insert a dbg.value
1207 // at each load and store to the alloca and erase the dbg.declare.
1208 // The dbg.values allow tracking a variable even if it is not
1209 // stored on the stack, while the dbg.declare can only describe
1210 // the stack slot (and at a lexical-scope granularity). Later
1211 // passes will attempt to elide the stack slot.
1212 if (AI && !isArray(AI)) {
1213 for (auto &AIUse : AI->uses()) {
1214 User *U = AIUse.getUser();
1215 if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1216 if (AIUse.getOperandNo() == 1)
1217 ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
1218 } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1219 ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1220 } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1221 // This is a call by-value or some other instruction that
1222 // takes a pointer to the variable. Insert a *value*
1223 // intrinsic that describes the alloca.
1224 DIB.insertDbgValueIntrinsic(AI, 0, DDI->getVariable(),
1225 DDI->getExpression(), DDI->getDebugLoc(),
1229 DDI->eraseFromParent();
1235 /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the
1236 /// alloca 'V', if any.
1237 DbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) {
1238 if (auto *L = LocalAsMetadata::getIfExists(V))
1239 if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1240 for (User *U : MDV->users())
1241 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
1247 void llvm::findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V) {
1248 if (auto *L = LocalAsMetadata::getIfExists(V))
1249 if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1250 for (User *U : MDV->users())
1251 if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U))
1252 DbgValues.push_back(DVI);
1256 bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress,
1257 Instruction *InsertBefore, DIBuilder &Builder,
1258 bool Deref, int Offset) {
1259 DbgDeclareInst *DDI = FindAllocaDbgDeclare(Address);
1262 DebugLoc Loc = DDI->getDebugLoc();
1263 auto *DIVar = DDI->getVariable();
1264 auto *DIExpr = DDI->getExpression();
1265 assert(DIVar && "Missing variable");
1266 DIExpr = DIExpression::prepend(DIExpr, Deref, Offset);
1267 // Insert llvm.dbg.declare immediately after the original alloca, and remove
1268 // old llvm.dbg.declare.
1269 Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore);
1270 DDI->eraseFromParent();
1274 bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
1275 DIBuilder &Builder, bool Deref, int Offset) {
1276 return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder,
1280 static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
1281 DIBuilder &Builder, int Offset) {
1282 DebugLoc Loc = DVI->getDebugLoc();
1283 auto *DIVar = DVI->getVariable();
1284 auto *DIExpr = DVI->getExpression();
1285 assert(DIVar && "Missing variable");
1287 // This is an alloca-based llvm.dbg.value. The first thing it should do with
1288 // the alloca pointer is dereference it. Otherwise we don't know how to handle
1290 if (!DIExpr || DIExpr->getNumElements() < 1 ||
1291 DIExpr->getElement(0) != dwarf::DW_OP_deref)
1294 // Insert the offset immediately after the first deref.
1295 // We could just change the offset argument of dbg.value, but it's unsigned...
1297 SmallVector<uint64_t, 4> Ops;
1298 Ops.push_back(dwarf::DW_OP_deref);
1299 DIExpression::appendOffset(Ops, Offset);
1300 Ops.append(DIExpr->elements_begin() + 1, DIExpr->elements_end());
1301 DIExpr = Builder.createExpression(Ops);
1304 Builder.insertDbgValueIntrinsic(NewAddress, DVI->getOffset(), DIVar, DIExpr,
1306 DVI->eraseFromParent();
1309 void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
1310 DIBuilder &Builder, int Offset) {
1311 if (auto *L = LocalAsMetadata::getIfExists(AI))
1312 if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
1313 for (auto UI = MDV->use_begin(), UE = MDV->use_end(); UI != UE;) {
1315 if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
1316 replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1320 void llvm::salvageDebugInfo(Instruction &I) {
1321 SmallVector<DbgValueInst *, 1> DbgValues;
1322 auto &M = *I.getModule();
1324 auto MDWrap = [&](Value *V) {
1325 return MetadataAsValue::get(I.getContext(), ValueAsMetadata::get(V));
1328 if (isa<BitCastInst>(&I)) {
1329 findDbgValues(DbgValues, &I);
1330 for (auto *DVI : DbgValues) {
1331 // Bitcasts are entirely irrelevant for debug info. Rewrite the dbg.value
1332 // to use the cast's source.
1333 DVI->setOperand(0, MDWrap(I.getOperand(0)));
1334 DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n');
1336 } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1337 findDbgValues(DbgValues, &I);
1338 for (auto *DVI : DbgValues) {
1340 M.getDataLayout().getPointerSizeInBits(GEP->getPointerAddressSpace());
1341 APInt Offset(BitWidth, 0);
1342 // Rewrite a constant GEP into a DIExpression. Since we are performing
1343 // arithmetic to compute the variable's *value* in the DIExpression, we
1344 // need to mark the expression with a DW_OP_stack_value.
1345 if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) {
1346 auto *DIExpr = DVI->getExpression();
1347 DIBuilder DIB(M, /*AllowUnresolved*/ false);
1348 // GEP offsets are i32 and thus always fit into an int64_t.
1349 DIExpr = DIExpression::prepend(DIExpr, DIExpression::NoDeref,
1350 Offset.getSExtValue(),
1351 DIExpression::WithStackValue);
1352 DVI->setOperand(0, MDWrap(I.getOperand(0)));
1353 DVI->setOperand(3, MetadataAsValue::get(I.getContext(), DIExpr));
1354 DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n');
1357 } else if (isa<LoadInst>(&I)) {
1358 findDbgValues(DbgValues, &I);
1359 for (auto *DVI : DbgValues) {
1360 // Rewrite the load into DW_OP_deref.
1361 auto *DIExpr = DVI->getExpression();
1362 DIBuilder DIB(M, /*AllowUnresolved*/ false);
1363 DIExpr = DIExpression::prepend(DIExpr, DIExpression::WithDeref);
1364 DVI->setOperand(0, MDWrap(I.getOperand(0)));
1365 DVI->setOperand(3, MetadataAsValue::get(I.getContext(), DIExpr));
1366 DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n');
1371 unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) {
1372 unsigned NumDeadInst = 0;
1373 // Delete the instructions backwards, as it has a reduced likelihood of
1374 // having to update as many def-use and use-def chains.
1375 Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
1376 while (EndInst != &BB->front()) {
1377 // Delete the next to last instruction.
1378 Instruction *Inst = &*--EndInst->getIterator();
1379 if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
1380 Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
1381 if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
1385 if (!isa<DbgInfoIntrinsic>(Inst))
1387 Inst->eraseFromParent();
1392 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
1393 bool PreserveLCSSA) {
1394 BasicBlock *BB = I->getParent();
1395 // Loop over all of the successors, removing BB's entry from any PHI
1397 for (BasicBlock *Successor : successors(BB))
1398 Successor->removePredecessor(BB, PreserveLCSSA);
1400 // Insert a call to llvm.trap right before this. This turns the undefined
1401 // behavior into a hard fail instead of falling through into random code.
1404 Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
1405 CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
1406 CallTrap->setDebugLoc(I->getDebugLoc());
1408 new UnreachableInst(I->getContext(), I);
1410 // All instructions after this are dead.
1411 unsigned NumInstrsRemoved = 0;
1412 BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
1413 while (BBI != BBE) {
1414 if (!BBI->use_empty())
1415 BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
1416 BB->getInstList().erase(BBI++);
1419 return NumInstrsRemoved;
1422 /// changeToCall - Convert the specified invoke into a normal call.
1423 static void changeToCall(InvokeInst *II) {
1424 SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
1425 SmallVector<OperandBundleDef, 1> OpBundles;
1426 II->getOperandBundlesAsDefs(OpBundles);
1427 CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
1429 NewCall->takeName(II);
1430 NewCall->setCallingConv(II->getCallingConv());
1431 NewCall->setAttributes(II->getAttributes());
1432 NewCall->setDebugLoc(II->getDebugLoc());
1433 II->replaceAllUsesWith(NewCall);
1435 // Follow the call by a branch to the normal destination.
1436 BranchInst::Create(II->getNormalDest(), II);
1438 // Update PHI nodes in the unwind destination
1439 II->getUnwindDest()->removePredecessor(II->getParent());
1440 II->eraseFromParent();
1443 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
1444 BasicBlock *UnwindEdge) {
1445 BasicBlock *BB = CI->getParent();
1447 // Convert this function call into an invoke instruction. First, split the
1450 BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc");
1452 // Delete the unconditional branch inserted by splitBasicBlock
1453 BB->getInstList().pop_back();
1455 // Create the new invoke instruction.
1456 SmallVector<Value *, 8> InvokeArgs(CI->arg_begin(), CI->arg_end());
1457 SmallVector<OperandBundleDef, 1> OpBundles;
1459 CI->getOperandBundlesAsDefs(OpBundles);
1461 // Note: we're round tripping operand bundles through memory here, and that
1462 // can potentially be avoided with a cleverer API design that we do not have
1465 InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, UnwindEdge,
1466 InvokeArgs, OpBundles, CI->getName(), BB);
1467 II->setDebugLoc(CI->getDebugLoc());
1468 II->setCallingConv(CI->getCallingConv());
1469 II->setAttributes(CI->getAttributes());
1471 // Make sure that anything using the call now uses the invoke! This also
1472 // updates the CallGraph if present, because it uses a WeakTrackingVH.
1473 CI->replaceAllUsesWith(II);
1475 // Delete the original call
1476 Split->getInstList().pop_front();
1480 static bool markAliveBlocks(Function &F,
1481 SmallPtrSetImpl<BasicBlock*> &Reachable) {
1483 SmallVector<BasicBlock*, 128> Worklist;
1484 BasicBlock *BB = &F.front();
1485 Worklist.push_back(BB);
1486 Reachable.insert(BB);
1487 bool Changed = false;
1489 BB = Worklist.pop_back_val();
1491 // Do a quick scan of the basic block, turning any obviously unreachable
1492 // instructions into LLVM unreachable insts. The instruction combining pass
1493 // canonicalizes unreachable insts into stores to null or undef.
1494 for (Instruction &I : *BB) {
1495 // Assumptions that are known to be false are equivalent to unreachable.
1496 // Also, if the condition is undefined, then we make the choice most
1497 // beneficial to the optimizer, and choose that to also be unreachable.
1498 if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
1499 if (II->getIntrinsicID() == Intrinsic::assume) {
1500 if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
1501 // Don't insert a call to llvm.trap right before the unreachable.
1502 changeToUnreachable(II, false);
1508 if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
1509 // A call to the guard intrinsic bails out of the current compilation
1510 // unit if the predicate passed to it is false. If the predicate is a
1511 // constant false, then we know the guard will bail out of the current
1512 // compile unconditionally, so all code following it is dead.
1514 // Note: unlike in llvm.assume, it is not "obviously profitable" for
1515 // guards to treat `undef` as `false` since a guard on `undef` can
1516 // still be useful for widening.
1517 if (match(II->getArgOperand(0), m_Zero()))
1518 if (!isa<UnreachableInst>(II->getNextNode())) {
1519 changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false);
1526 if (auto *CI = dyn_cast<CallInst>(&I)) {
1527 Value *Callee = CI->getCalledValue();
1528 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1529 changeToUnreachable(CI, /*UseLLVMTrap=*/false);
1533 if (CI->doesNotReturn()) {
1534 // If we found a call to a no-return function, insert an unreachable
1535 // instruction after it. Make sure there isn't *already* one there
1537 if (!isa<UnreachableInst>(CI->getNextNode())) {
1538 // Don't insert a call to llvm.trap right before the unreachable.
1539 changeToUnreachable(CI->getNextNode(), false);
1546 // Store to undef and store to null are undefined and used to signal that
1547 // they should be changed to unreachable by passes that can't modify the
1549 if (auto *SI = dyn_cast<StoreInst>(&I)) {
1550 // Don't touch volatile stores.
1551 if (SI->isVolatile()) continue;
1553 Value *Ptr = SI->getOperand(1);
1555 if (isa<UndefValue>(Ptr) ||
1556 (isa<ConstantPointerNull>(Ptr) &&
1557 SI->getPointerAddressSpace() == 0)) {
1558 changeToUnreachable(SI, true);
1565 TerminatorInst *Terminator = BB->getTerminator();
1566 if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
1567 // Turn invokes that call 'nounwind' functions into ordinary calls.
1568 Value *Callee = II->getCalledValue();
1569 if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1570 changeToUnreachable(II, true);
1572 } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
1573 if (II->use_empty() && II->onlyReadsMemory()) {
1574 // jump to the normal destination branch.
1575 BranchInst::Create(II->getNormalDest(), II);
1576 II->getUnwindDest()->removePredecessor(II->getParent());
1577 II->eraseFromParent();
1582 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
1583 // Remove catchpads which cannot be reached.
1584 struct CatchPadDenseMapInfo {
1585 static CatchPadInst *getEmptyKey() {
1586 return DenseMapInfo<CatchPadInst *>::getEmptyKey();
1588 static CatchPadInst *getTombstoneKey() {
1589 return DenseMapInfo<CatchPadInst *>::getTombstoneKey();
1591 static unsigned getHashValue(CatchPadInst *CatchPad) {
1592 return static_cast<unsigned>(hash_combine_range(
1593 CatchPad->value_op_begin(), CatchPad->value_op_end()));
1595 static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
1596 if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
1597 RHS == getEmptyKey() || RHS == getTombstoneKey())
1599 return LHS->isIdenticalTo(RHS);
1603 // Set of unique CatchPads.
1604 SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4,
1605 CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
1607 detail::DenseSetEmpty Empty;
1608 for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
1609 E = CatchSwitch->handler_end();
1611 BasicBlock *HandlerBB = *I;
1612 auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
1613 if (!HandlerSet.insert({CatchPad, Empty}).second) {
1614 CatchSwitch->removeHandler(I);
1622 Changed |= ConstantFoldTerminator(BB, true);
1623 for (BasicBlock *Successor : successors(BB))
1624 if (Reachable.insert(Successor).second)
1625 Worklist.push_back(Successor);
1626 } while (!Worklist.empty());
1630 void llvm::removeUnwindEdge(BasicBlock *BB) {
1631 TerminatorInst *TI = BB->getTerminator();
1633 if (auto *II = dyn_cast<InvokeInst>(TI)) {
1638 TerminatorInst *NewTI;
1639 BasicBlock *UnwindDest;
1641 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
1642 NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
1643 UnwindDest = CRI->getUnwindDest();
1644 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
1645 auto *NewCatchSwitch = CatchSwitchInst::Create(
1646 CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
1647 CatchSwitch->getName(), CatchSwitch);
1648 for (BasicBlock *PadBB : CatchSwitch->handlers())
1649 NewCatchSwitch->addHandler(PadBB);
1651 NewTI = NewCatchSwitch;
1652 UnwindDest = CatchSwitch->getUnwindDest();
1654 llvm_unreachable("Could not find unwind successor");
1657 NewTI->takeName(TI);
1658 NewTI->setDebugLoc(TI->getDebugLoc());
1659 UnwindDest->removePredecessor(BB);
1660 TI->replaceAllUsesWith(NewTI);
1661 TI->eraseFromParent();
1664 /// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even
1665 /// if they are in a dead cycle. Return true if a change was made, false
1667 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) {
1668 SmallPtrSet<BasicBlock*, 16> Reachable;
1669 bool Changed = markAliveBlocks(F, Reachable);
1671 // If there are unreachable blocks in the CFG...
1672 if (Reachable.size() == F.size())
1675 assert(Reachable.size() < F.size());
1676 NumRemoved += F.size()-Reachable.size();
1678 // Loop over all of the basic blocks that are not reachable, dropping all of
1679 // their internal references...
1680 for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
1681 if (Reachable.count(&*BB))
1684 for (BasicBlock *Successor : successors(&*BB))
1685 if (Reachable.count(Successor))
1686 Successor->removePredecessor(&*BB);
1688 LVI->eraseBlock(&*BB);
1689 BB->dropAllReferences();
1692 for (Function::iterator I = ++F.begin(); I != F.end();)
1693 if (!Reachable.count(&*I))
1694 I = F.getBasicBlockList().erase(I);
1701 void llvm::combineMetadata(Instruction *K, const Instruction *J,
1702 ArrayRef<unsigned> KnownIDs) {
1703 SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
1704 K->dropUnknownNonDebugMetadata(KnownIDs);
1705 K->getAllMetadataOtherThanDebugLoc(Metadata);
1706 for (const auto &MD : Metadata) {
1707 unsigned Kind = MD.first;
1708 MDNode *JMD = J->getMetadata(Kind);
1709 MDNode *KMD = MD.second;
1713 K->setMetadata(Kind, nullptr); // Remove unknown metadata
1715 case LLVMContext::MD_dbg:
1716 llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
1717 case LLVMContext::MD_tbaa:
1718 K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
1720 case LLVMContext::MD_alias_scope:
1721 K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
1723 case LLVMContext::MD_noalias:
1724 case LLVMContext::MD_mem_parallel_loop_access:
1725 K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
1727 case LLVMContext::MD_range:
1728 K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
1730 case LLVMContext::MD_fpmath:
1731 K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
1733 case LLVMContext::MD_invariant_load:
1734 // Only set the !invariant.load if it is present in both instructions.
1735 K->setMetadata(Kind, JMD);
1737 case LLVMContext::MD_nonnull:
1738 // Only set the !nonnull if it is present in both instructions.
1739 K->setMetadata(Kind, JMD);
1741 case LLVMContext::MD_invariant_group:
1742 // Preserve !invariant.group in K.
1744 case LLVMContext::MD_align:
1745 K->setMetadata(Kind,
1746 MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
1748 case LLVMContext::MD_dereferenceable:
1749 case LLVMContext::MD_dereferenceable_or_null:
1750 K->setMetadata(Kind,
1751 MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
1755 // Set !invariant.group from J if J has it. If both instructions have it
1756 // then we will just pick it from J - even when they are different.
1757 // Also make sure that K is load or store - f.e. combining bitcast with load
1758 // could produce bitcast with invariant.group metadata, which is invalid.
1759 // FIXME: we should try to preserve both invariant.group md if they are
1760 // different, but right now instruction can only have one invariant.group.
1761 if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
1762 if (isa<LoadInst>(K) || isa<StoreInst>(K))
1763 K->setMetadata(LLVMContext::MD_invariant_group, JMD);
1766 void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J) {
1767 unsigned KnownIDs[] = {
1768 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
1769 LLVMContext::MD_noalias, LLVMContext::MD_range,
1770 LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull,
1771 LLVMContext::MD_invariant_group, LLVMContext::MD_align,
1772 LLVMContext::MD_dereferenceable,
1773 LLVMContext::MD_dereferenceable_or_null};
1774 combineMetadata(K, J, KnownIDs);
1777 template <typename RootType, typename DominatesFn>
1778 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
1779 const RootType &Root,
1780 const DominatesFn &Dominates) {
1781 assert(From->getType() == To->getType());
1784 for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
1787 if (!Dominates(Root, U))
1790 DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as "
1791 << *To << " in " << *U << "\n");
1797 unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) {
1798 assert(From->getType() == To->getType());
1799 auto *BB = From->getParent();
1802 for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
1805 auto *I = cast<Instruction>(U.getUser());
1806 if (I->getParent() == BB)
1814 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
1816 const BasicBlockEdge &Root) {
1817 auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
1818 return DT.dominates(Root, U);
1820 return ::replaceDominatedUsesWith(From, To, Root, Dominates);
1823 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
1825 const BasicBlock *BB) {
1826 auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
1827 auto *I = cast<Instruction>(U.getUser())->getParent();
1828 return DT.properlyDominates(BB, I);
1830 return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
1833 bool llvm::callsGCLeafFunction(ImmutableCallSite CS) {
1834 // Check if the function is specifically marked as a gc leaf function.
1835 if (CS.hasFnAttr("gc-leaf-function"))
1837 if (const Function *F = CS.getCalledFunction()) {
1838 if (F->hasFnAttribute("gc-leaf-function"))
1841 if (auto IID = F->getIntrinsicID())
1842 // Most LLVM intrinsics do not take safepoints.
1843 return IID != Intrinsic::experimental_gc_statepoint &&
1844 IID != Intrinsic::experimental_deoptimize;
1851 /// A potential constituent of a bitreverse or bswap expression. See
1852 /// collectBitParts for a fuller explanation.
1854 BitPart(Value *P, unsigned BW) : Provider(P) {
1855 Provenance.resize(BW);
1858 /// The Value that this is a bitreverse/bswap of.
1860 /// The "provenance" of each bit. Provenance[A] = B means that bit A
1861 /// in Provider becomes bit B in the result of this expression.
1862 SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
1864 enum { Unset = -1 };
1866 } // end anonymous namespace
1868 /// Analyze the specified subexpression and see if it is capable of providing
1869 /// pieces of a bswap or bitreverse. The subexpression provides a potential
1870 /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in
1871 /// the output of the expression came from a corresponding bit in some other
1872 /// value. This function is recursive, and the end result is a mapping of
1873 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
1874 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
1876 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
1877 /// that the expression deposits the low byte of %X into the high byte of the
1878 /// result and that all other bits are zero. This expression is accepted and a
1879 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
1882 /// To avoid revisiting values, the BitPart results are memoized into the
1883 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
1884 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
1885 /// store BitParts objects, not pointers. As we need the concept of a nullptr
1886 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
1887 /// type instead to provide the same functionality.
1889 /// Because we pass around references into \c BPS, we must use a container that
1890 /// does not invalidate internal references (std::map instead of DenseMap).
1892 static const Optional<BitPart> &
1893 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
1894 std::map<Value *, Optional<BitPart>> &BPS) {
1895 auto I = BPS.find(V);
1899 auto &Result = BPS[V] = None;
1900 auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
1902 if (Instruction *I = dyn_cast<Instruction>(V)) {
1903 // If this is an or instruction, it may be an inner node of the bswap.
1904 if (I->getOpcode() == Instruction::Or) {
1905 auto &A = collectBitParts(I->getOperand(0), MatchBSwaps,
1906 MatchBitReversals, BPS);
1907 auto &B = collectBitParts(I->getOperand(1), MatchBSwaps,
1908 MatchBitReversals, BPS);
1912 // Try and merge the two together.
1913 if (!A->Provider || A->Provider != B->Provider)
1916 Result = BitPart(A->Provider, BitWidth);
1917 for (unsigned i = 0; i < A->Provenance.size(); ++i) {
1918 if (A->Provenance[i] != BitPart::Unset &&
1919 B->Provenance[i] != BitPart::Unset &&
1920 A->Provenance[i] != B->Provenance[i])
1921 return Result = None;
1923 if (A->Provenance[i] == BitPart::Unset)
1924 Result->Provenance[i] = B->Provenance[i];
1926 Result->Provenance[i] = A->Provenance[i];
1932 // If this is a logical shift by a constant, recurse then shift the result.
1933 if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
1935 cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
1936 // Ensure the shift amount is defined.
1937 if (BitShift > BitWidth)
1940 auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
1941 MatchBitReversals, BPS);
1946 // Perform the "shift" on BitProvenance.
1947 auto &P = Result->Provenance;
1948 if (I->getOpcode() == Instruction::Shl) {
1949 P.erase(std::prev(P.end(), BitShift), P.end());
1950 P.insert(P.begin(), BitShift, BitPart::Unset);
1952 P.erase(P.begin(), std::next(P.begin(), BitShift));
1953 P.insert(P.end(), BitShift, BitPart::Unset);
1959 // If this is a logical 'and' with a mask that clears bits, recurse then
1960 // unset the appropriate bits.
1961 if (I->getOpcode() == Instruction::And &&
1962 isa<ConstantInt>(I->getOperand(1))) {
1963 APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1);
1964 const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
1966 // Check that the mask allows a multiple of 8 bits for a bswap, for an
1968 unsigned NumMaskedBits = AndMask.countPopulation();
1969 if (!MatchBitReversals && NumMaskedBits % 8 != 0)
1972 auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
1973 MatchBitReversals, BPS);
1978 for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1)
1979 // If the AndMask is zero for this bit, clear the bit.
1980 if ((AndMask & Bit) == 0)
1981 Result->Provenance[i] = BitPart::Unset;
1985 // If this is a zext instruction zero extend the result.
1986 if (I->getOpcode() == Instruction::ZExt) {
1987 auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
1988 MatchBitReversals, BPS);
1992 Result = BitPart(Res->Provider, BitWidth);
1993 auto NarrowBitWidth =
1994 cast<IntegerType>(cast<ZExtInst>(I)->getSrcTy())->getBitWidth();
1995 for (unsigned i = 0; i < NarrowBitWidth; ++i)
1996 Result->Provenance[i] = Res->Provenance[i];
1997 for (unsigned i = NarrowBitWidth; i < BitWidth; ++i)
1998 Result->Provenance[i] = BitPart::Unset;
2003 // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be
2004 // the input value to the bswap/bitreverse.
2005 Result = BitPart(V, BitWidth);
2006 for (unsigned i = 0; i < BitWidth; ++i)
2007 Result->Provenance[i] = i;
2011 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
2012 unsigned BitWidth) {
2013 if (From % 8 != To % 8)
2015 // Convert from bit indices to byte indices and check for a byte reversal.
2019 return From == BitWidth - To - 1;
2022 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
2023 unsigned BitWidth) {
2024 return From == BitWidth - To - 1;
2027 /// Given an OR instruction, check to see if this is a bitreverse
2028 /// idiom. If so, insert the new intrinsic and return true.
2029 bool llvm::recognizeBSwapOrBitReverseIdiom(
2030 Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
2031 SmallVectorImpl<Instruction *> &InsertedInsts) {
2032 if (Operator::getOpcode(I) != Instruction::Or)
2034 if (!MatchBSwaps && !MatchBitReversals)
2036 IntegerType *ITy = dyn_cast<IntegerType>(I->getType());
2037 if (!ITy || ITy->getBitWidth() > 128)
2038 return false; // Can't do vectors or integers > 128 bits.
2039 unsigned BW = ITy->getBitWidth();
2041 unsigned DemandedBW = BW;
2042 IntegerType *DemandedTy = ITy;
2043 if (I->hasOneUse()) {
2044 if (TruncInst *Trunc = dyn_cast<TruncInst>(I->user_back())) {
2045 DemandedTy = cast<IntegerType>(Trunc->getType());
2046 DemandedBW = DemandedTy->getBitWidth();
2050 // Try to find all the pieces corresponding to the bswap.
2051 std::map<Value *, Optional<BitPart>> BPS;
2052 auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS);
2055 auto &BitProvenance = Res->Provenance;
2057 // Now, is the bit permutation correct for a bswap or a bitreverse? We can
2058 // only byteswap values with an even number of bytes.
2059 bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true;
2060 for (unsigned i = 0; i < DemandedBW; ++i) {
2062 bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW);
2064 bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW);
2067 Intrinsic::ID Intrin;
2068 if (OKForBSwap && MatchBSwaps)
2069 Intrin = Intrinsic::bswap;
2070 else if (OKForBitReverse && MatchBitReversals)
2071 Intrin = Intrinsic::bitreverse;
2075 if (ITy != DemandedTy) {
2076 Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
2077 Value *Provider = Res->Provider;
2078 IntegerType *ProviderTy = cast<IntegerType>(Provider->getType());
2079 // We may need to truncate the provider.
2080 if (DemandedTy != ProviderTy) {
2081 auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy,
2083 InsertedInsts.push_back(Trunc);
2086 auto *CI = CallInst::Create(F, Provider, "rev", I);
2087 InsertedInsts.push_back(CI);
2088 auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I);
2089 InsertedInsts.push_back(ExtInst);
2093 Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy);
2094 InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I));
2098 // CodeGen has special handling for some string functions that may replace
2099 // them with target-specific intrinsics. Since that'd skip our interceptors
2100 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
2101 // we mark affected calls as NoBuiltin, which will disable optimization
2103 void llvm::maybeMarkSanitizerLibraryCallNoBuiltin(
2104 CallInst *CI, const TargetLibraryInfo *TLI) {
2105 Function *F = CI->getCalledFunction();
2107 if (F && !F->hasLocalLinkage() && F->hasName() &&
2108 TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
2109 !F->doesNotAccessMemory())
2110 CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin);
2113 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
2114 // We can't have a PHI with a metadata type.
2115 if (I->getOperand(OpIdx)->getType()->isMetadataTy())
2119 if (!isa<Constant>(I->getOperand(OpIdx)))
2122 switch (I->getOpcode()) {
2125 case Instruction::Call:
2126 case Instruction::Invoke:
2127 // Many arithmetic intrinsics have no issue taking a
2128 // variable, however it's hard to distingish these from
2129 // specials such as @llvm.frameaddress that require a constant.
2130 if (isa<IntrinsicInst>(I))
2133 // Constant bundle operands may need to retain their constant-ness for
2135 if (ImmutableCallSite(I).isBundleOperand(OpIdx))
2138 case Instruction::ShuffleVector:
2139 // Shufflevector masks are constant.
2141 case Instruction::ExtractValue:
2142 case Instruction::InsertValue:
2143 // All operands apart from the first are constant.
2145 case Instruction::Alloca:
2147 case Instruction::GetElementPtr:
2150 gep_type_iterator It = gep_type_begin(I);
2151 for (auto E = std::next(It, OpIdx); It != E; ++It)