1 //===- Local.cpp - Functions to perform local transformations -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This family of functions perform various local transformations to the
10 // program.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Transforms/Utils/Local.h"
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseMapInfo.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/Hashing.h"
20 #include "llvm/ADT/None.h"
21 #include "llvm/ADT/Optional.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/ADT/TinyPtrVector.h"
28 #include "llvm/Analysis/ConstantFolding.h"
29 #include "llvm/Analysis/DomTreeUpdater.h"
30 #include "llvm/Analysis/EHPersonalities.h"
31 #include "llvm/Analysis/InstructionSimplify.h"
32 #include "llvm/Analysis/LazyValueInfo.h"
33 #include "llvm/Analysis/MemoryBuiltins.h"
34 #include "llvm/Analysis/MemorySSAUpdater.h"
35 #include "llvm/Analysis/TargetLibraryInfo.h"
36 #include "llvm/Analysis/ValueTracking.h"
37 #include "llvm/Analysis/VectorUtils.h"
38 #include "llvm/BinaryFormat/Dwarf.h"
39 #include "llvm/IR/Argument.h"
40 #include "llvm/IR/Attributes.h"
41 #include "llvm/IR/BasicBlock.h"
42 #include "llvm/IR/CFG.h"
43 #include "llvm/IR/CallSite.h"
44 #include "llvm/IR/Constant.h"
45 #include "llvm/IR/ConstantRange.h"
46 #include "llvm/IR/Constants.h"
47 #include "llvm/IR/DIBuilder.h"
48 #include "llvm/IR/DataLayout.h"
49 #include "llvm/IR/DebugInfoMetadata.h"
50 #include "llvm/IR/DebugLoc.h"
51 #include "llvm/IR/DerivedTypes.h"
52 #include "llvm/IR/Dominators.h"
53 #include "llvm/IR/Function.h"
54 #include "llvm/IR/GetElementPtrTypeIterator.h"
55 #include "llvm/IR/GlobalObject.h"
56 #include "llvm/IR/IRBuilder.h"
57 #include "llvm/IR/InstrTypes.h"
58 #include "llvm/IR/Instruction.h"
59 #include "llvm/IR/Instructions.h"
60 #include "llvm/IR/IntrinsicInst.h"
61 #include "llvm/IR/Intrinsics.h"
62 #include "llvm/IR/LLVMContext.h"
63 #include "llvm/IR/MDBuilder.h"
64 #include "llvm/IR/Metadata.h"
65 #include "llvm/IR/Module.h"
66 #include "llvm/IR/Operator.h"
67 #include "llvm/IR/PatternMatch.h"
68 #include "llvm/IR/Type.h"
69 #include "llvm/IR/Use.h"
70 #include "llvm/IR/User.h"
71 #include "llvm/IR/Value.h"
72 #include "llvm/IR/ValueHandle.h"
73 #include "llvm/Support/Casting.h"
74 #include "llvm/Support/Debug.h"
75 #include "llvm/Support/ErrorHandling.h"
76 #include "llvm/Support/KnownBits.h"
77 #include "llvm/Support/raw_ostream.h"
78 #include "llvm/Transforms/Utils/ValueMapper.h"
79 #include <algorithm>
80 #include <cassert>
81 #include <climits>
82 #include <cstdint>
83 #include <iterator>
84 #include <map>
85 #include <utility>
86 
87 using namespace llvm;
88 using namespace llvm::PatternMatch;
89 
90 #define DEBUG_TYPE "local"
91 
92 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
93 
94 // Max recursion depth for collectBitParts used when detecting bswap and
95 // bitreverse idioms
96 static const unsigned BitPartRecursionMaxDepth = 64;
97 
98 //===----------------------------------------------------------------------===//
99 //  Local constant propagation.
100 //
101 
102 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
103 /// constant value, convert it into an unconditional branch to the constant
104 /// destination.  This is a nontrivial operation because the successors of this
105 /// basic block must have their PHI nodes updated.
106 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
107 /// conditions and indirectbr addresses this might make dead if
108 /// DeleteDeadConditions is true.
ConstantFoldTerminator(BasicBlock * BB,bool DeleteDeadConditions,const TargetLibraryInfo * TLI,DomTreeUpdater * DTU)109 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
110                                   const TargetLibraryInfo *TLI,
111                                   DomTreeUpdater *DTU) {
112   Instruction *T = BB->getTerminator();
113   IRBuilder<> Builder(T);
114 
115   // Branch - See if we are conditional jumping on constant
116   if (auto *BI = dyn_cast<BranchInst>(T)) {
117     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
118     BasicBlock *Dest1 = BI->getSuccessor(0);
119     BasicBlock *Dest2 = BI->getSuccessor(1);
120 
121     if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
122       // Are we branching on constant?
123       // YES.  Change to unconditional branch...
124       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
125       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
126 
127       // Let the basic block know that we are letting go of it.  Based on this,
128       // it will adjust it's PHI nodes.
129       OldDest->removePredecessor(BB);
130 
131       // Replace the conditional branch with an unconditional one.
132       Builder.CreateBr(Destination);
133       BI->eraseFromParent();
134       if (DTU)
135         DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, OldDest}});
136       return true;
137     }
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       Builder.CreateBr(Dest1);
150       Value *Cond = BI->getCondition();
151       BI->eraseFromParent();
152       if (DeleteDeadConditions)
153         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
154       return true;
155     }
156     return false;
157   }
158 
159   if (auto *SI = dyn_cast<SwitchInst>(T)) {
160     // If we are switching on a constant, we can convert the switch to an
161     // unconditional branch.
162     auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
163     BasicBlock *DefaultDest = SI->getDefaultDest();
164     BasicBlock *TheOnlyDest = DefaultDest;
165 
166     // If the default is unreachable, ignore it when searching for TheOnlyDest.
167     if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) &&
168         SI->getNumCases() > 0) {
169       TheOnlyDest = SI->case_begin()->getCaseSuccessor();
170     }
171 
172     // Figure out which case it goes to.
173     for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
174       // Found case matching a constant operand?
175       if (i->getCaseValue() == CI) {
176         TheOnlyDest = i->getCaseSuccessor();
177         break;
178       }
179 
180       // Check to see if this branch is going to the same place as the default
181       // dest.  If so, eliminate it as an explicit compare.
182       if (i->getCaseSuccessor() == DefaultDest) {
183         MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
184         unsigned NCases = SI->getNumCases();
185         // Fold the case metadata into the default if there will be any branches
186         // left, unless the metadata doesn't match the switch.
187         if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
188           // Collect branch weights into a vector.
189           SmallVector<uint32_t, 8> Weights;
190           for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
191                ++MD_i) {
192             auto *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i));
193             Weights.push_back(CI->getValue().getZExtValue());
194           }
195           // Merge weight of this case to the default weight.
196           unsigned idx = i->getCaseIndex();
197           Weights[0] += Weights[idx+1];
198           // Remove weight for this case.
199           std::swap(Weights[idx+1], Weights.back());
200           Weights.pop_back();
201           SI->setMetadata(LLVMContext::MD_prof,
202                           MDBuilder(BB->getContext()).
203                           createBranchWeights(Weights));
204         }
205         // Remove this entry.
206         BasicBlock *ParentBB = SI->getParent();
207         DefaultDest->removePredecessor(ParentBB);
208         i = SI->removeCase(i);
209         e = SI->case_end();
210         if (DTU)
211           DTU->applyUpdatesPermissive(
212               {{DominatorTree::Delete, ParentBB, DefaultDest}});
213         continue;
214       }
215 
216       // Otherwise, check to see if the switch only branches to one destination.
217       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
218       // destinations.
219       if (i->getCaseSuccessor() != TheOnlyDest)
220         TheOnlyDest = nullptr;
221 
222       // Increment this iterator as we haven't removed the case.
223       ++i;
224     }
225 
226     if (CI && !TheOnlyDest) {
227       // Branching on a constant, but not any of the cases, go to the default
228       // successor.
229       TheOnlyDest = SI->getDefaultDest();
230     }
231 
232     // If we found a single destination that we can fold the switch into, do so
233     // now.
234     if (TheOnlyDest) {
235       // Insert the new branch.
236       Builder.CreateBr(TheOnlyDest);
237       BasicBlock *BB = SI->getParent();
238       std::vector <DominatorTree::UpdateType> Updates;
239       if (DTU)
240         Updates.reserve(SI->getNumSuccessors() - 1);
241 
242       // Remove entries from PHI nodes which we no longer branch to...
243       for (BasicBlock *Succ : successors(SI)) {
244         // Found case matching a constant operand?
245         if (Succ == TheOnlyDest) {
246           TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
247         } else {
248           Succ->removePredecessor(BB);
249           if (DTU)
250             Updates.push_back({DominatorTree::Delete, BB, Succ});
251         }
252       }
253 
254       // Delete the old switch.
255       Value *Cond = SI->getCondition();
256       SI->eraseFromParent();
257       if (DeleteDeadConditions)
258         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
259       if (DTU)
260         DTU->applyUpdatesPermissive(Updates);
261       return true;
262     }
263 
264     if (SI->getNumCases() == 1) {
265       // Otherwise, we can fold this switch into a conditional branch
266       // instruction if it has only one non-default destination.
267       auto FirstCase = *SI->case_begin();
268       Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
269           FirstCase.getCaseValue(), "cond");
270 
271       // Insert the new branch.
272       BranchInst *NewBr = Builder.CreateCondBr(Cond,
273                                                FirstCase.getCaseSuccessor(),
274                                                SI->getDefaultDest());
275       MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
276       if (MD && MD->getNumOperands() == 3) {
277         ConstantInt *SICase =
278             mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
279         ConstantInt *SIDef =
280             mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
281         assert(SICase && SIDef);
282         // The TrueWeight should be the weight for the single case of SI.
283         NewBr->setMetadata(LLVMContext::MD_prof,
284                         MDBuilder(BB->getContext()).
285                         createBranchWeights(SICase->getValue().getZExtValue(),
286                                             SIDef->getValue().getZExtValue()));
287       }
288 
289       // Update make.implicit metadata to the newly-created conditional branch.
290       MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
291       if (MakeImplicitMD)
292         NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
293 
294       // Delete the old switch.
295       SI->eraseFromParent();
296       return true;
297     }
298     return false;
299   }
300 
301   if (auto *IBI = dyn_cast<IndirectBrInst>(T)) {
302     // indirectbr blockaddress(@F, @BB) -> br label @BB
303     if (auto *BA =
304           dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
305       BasicBlock *TheOnlyDest = BA->getBasicBlock();
306       std::vector <DominatorTree::UpdateType> Updates;
307       if (DTU)
308         Updates.reserve(IBI->getNumDestinations() - 1);
309 
310       // Insert the new branch.
311       Builder.CreateBr(TheOnlyDest);
312 
313       for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
314         if (IBI->getDestination(i) == TheOnlyDest) {
315           TheOnlyDest = nullptr;
316         } else {
317           BasicBlock *ParentBB = IBI->getParent();
318           BasicBlock *DestBB = IBI->getDestination(i);
319           DestBB->removePredecessor(ParentBB);
320           if (DTU)
321             Updates.push_back({DominatorTree::Delete, ParentBB, DestBB});
322         }
323       }
324       Value *Address = IBI->getAddress();
325       IBI->eraseFromParent();
326       if (DeleteDeadConditions)
327         // Delete pointer cast instructions.
328         RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
329 
330       // Also zap the blockaddress constant if there are no users remaining,
331       // otherwise the destination is still marked as having its address taken.
332       if (BA->use_empty())
333         BA->destroyConstant();
334 
335       // If we didn't find our destination in the IBI successor list, then we
336       // have undefined behavior.  Replace the unconditional branch with an
337       // 'unreachable' instruction.
338       if (TheOnlyDest) {
339         BB->getTerminator()->eraseFromParent();
340         new UnreachableInst(BB->getContext(), BB);
341       }
342 
343       if (DTU)
344         DTU->applyUpdatesPermissive(Updates);
345       return true;
346     }
347   }
348 
349   return false;
350 }
351 
352 //===----------------------------------------------------------------------===//
353 //  Local dead code elimination.
354 //
355 
356 /// isInstructionTriviallyDead - Return true if the result produced by the
357 /// instruction is not used, and the instruction has no side effects.
358 ///
isInstructionTriviallyDead(Instruction * I,const TargetLibraryInfo * TLI)359 bool llvm::isInstructionTriviallyDead(Instruction *I,
360                                       const TargetLibraryInfo *TLI) {
361   if (!I->use_empty())
362     return false;
363   return wouldInstructionBeTriviallyDead(I, TLI);
364 }
365 
wouldInstructionBeTriviallyDead(Instruction * I,const TargetLibraryInfo * TLI)366 bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
367                                            const TargetLibraryInfo *TLI) {
368   if (I->isTerminator())
369     return false;
370 
371   // We don't want the landingpad-like instructions removed by anything this
372   // general.
373   if (I->isEHPad())
374     return false;
375 
376   // We don't want debug info removed by anything this general, unless
377   // debug info is empty.
378   if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
379     if (DDI->getAddress())
380       return false;
381     return true;
382   }
383   if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
384     if (DVI->getValue())
385       return false;
386     return true;
387   }
388   if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) {
389     if (DLI->getLabel())
390       return false;
391     return true;
392   }
393 
394   if (!I->mayHaveSideEffects())
395     return true;
396 
397   // Special case intrinsics that "may have side effects" but can be deleted
398   // when dead.
399   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
400     // Safe to delete llvm.stacksave and launder.invariant.group if dead.
401     if (II->getIntrinsicID() == Intrinsic::stacksave ||
402         II->getIntrinsicID() == Intrinsic::launder_invariant_group)
403       return true;
404 
405     // Lifetime intrinsics are dead when their right-hand is undef.
406     if (II->isLifetimeStartOrEnd())
407       return isa<UndefValue>(II->getArgOperand(1));
408 
409     // Assumptions are dead if their condition is trivially true.  Guards on
410     // true are operationally no-ops.  In the future we can consider more
411     // sophisticated tradeoffs for guards considering potential for check
412     // widening, but for now we keep things simple.
413     if (II->getIntrinsicID() == Intrinsic::assume ||
414         II->getIntrinsicID() == Intrinsic::experimental_guard) {
415       if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
416         return !Cond->isZero();
417 
418       return false;
419     }
420   }
421 
422   if (isAllocLikeFn(I, TLI))
423     return true;
424 
425   if (CallInst *CI = isFreeCall(I, TLI))
426     if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
427       return C->isNullValue() || isa<UndefValue>(C);
428 
429   if (auto *Call = dyn_cast<CallBase>(I))
430     if (isMathLibCallNoop(Call, TLI))
431       return true;
432 
433   return false;
434 }
435 
436 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
437 /// trivially dead instruction, delete it.  If that makes any of its operands
438 /// trivially dead, delete them too, recursively.  Return true if any
439 /// instructions were deleted.
RecursivelyDeleteTriviallyDeadInstructions(Value * V,const TargetLibraryInfo * TLI,MemorySSAUpdater * MSSAU)440 bool llvm::RecursivelyDeleteTriviallyDeadInstructions(
441     Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU) {
442   Instruction *I = dyn_cast<Instruction>(V);
443   if (!I || !isInstructionTriviallyDead(I, TLI))
444     return false;
445 
446   SmallVector<Instruction*, 16> DeadInsts;
447   DeadInsts.push_back(I);
448   RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU);
449 
450   return true;
451 }
452 
RecursivelyDeleteTriviallyDeadInstructions(SmallVectorImpl<Instruction * > & DeadInsts,const TargetLibraryInfo * TLI,MemorySSAUpdater * MSSAU)453 void llvm::RecursivelyDeleteTriviallyDeadInstructions(
454     SmallVectorImpl<Instruction *> &DeadInsts, const TargetLibraryInfo *TLI,
455     MemorySSAUpdater *MSSAU) {
456   // Process the dead instruction list until empty.
457   while (!DeadInsts.empty()) {
458     Instruction &I = *DeadInsts.pop_back_val();
459     assert(I.use_empty() && "Instructions with uses are not dead.");
460     assert(isInstructionTriviallyDead(&I, TLI) &&
461            "Live instruction found in dead worklist!");
462 
463     // Don't lose the debug info while deleting the instructions.
464     salvageDebugInfo(I);
465 
466     // Null out all of the instruction's operands to see if any operand becomes
467     // dead as we go.
468     for (Use &OpU : I.operands()) {
469       Value *OpV = OpU.get();
470       OpU.set(nullptr);
471 
472       if (!OpV->use_empty())
473         continue;
474 
475       // If the operand is an instruction that became dead as we nulled out the
476       // operand, and if it is 'trivially' dead, delete it in a future loop
477       // iteration.
478       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
479         if (isInstructionTriviallyDead(OpI, TLI))
480           DeadInsts.push_back(OpI);
481     }
482     if (MSSAU)
483       MSSAU->removeMemoryAccess(&I);
484 
485     I.eraseFromParent();
486   }
487 }
488 
replaceDbgUsesWithUndef(Instruction * I)489 bool llvm::replaceDbgUsesWithUndef(Instruction *I) {
490   SmallVector<DbgVariableIntrinsic *, 1> DbgUsers;
491   findDbgUsers(DbgUsers, I);
492   for (auto *DII : DbgUsers) {
493     Value *Undef = UndefValue::get(I->getType());
494     DII->setOperand(0, MetadataAsValue::get(DII->getContext(),
495                                             ValueAsMetadata::get(Undef)));
496   }
497   return !DbgUsers.empty();
498 }
499 
500 /// areAllUsesEqual - Check whether the uses of a value are all the same.
501 /// This is similar to Instruction::hasOneUse() except this will also return
502 /// true when there are no uses or multiple uses that all refer to the same
503 /// value.
areAllUsesEqual(Instruction * I)504 static bool areAllUsesEqual(Instruction *I) {
505   Value::user_iterator UI = I->user_begin();
506   Value::user_iterator UE = I->user_end();
507   if (UI == UE)
508     return true;
509 
510   User *TheUse = *UI;
511   for (++UI; UI != UE; ++UI) {
512     if (*UI != TheUse)
513       return false;
514   }
515   return true;
516 }
517 
518 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
519 /// dead PHI node, due to being a def-use chain of single-use nodes that
520 /// either forms a cycle or is terminated by a trivially dead instruction,
521 /// delete it.  If that makes any of its operands trivially dead, delete them
522 /// too, recursively.  Return true if a change was made.
RecursivelyDeleteDeadPHINode(PHINode * PN,const TargetLibraryInfo * TLI)523 bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN,
524                                         const TargetLibraryInfo *TLI) {
525   SmallPtrSet<Instruction*, 4> Visited;
526   for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
527        I = cast<Instruction>(*I->user_begin())) {
528     if (I->use_empty())
529       return RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
530 
531     // If we find an instruction more than once, we're on a cycle that
532     // won't prove fruitful.
533     if (!Visited.insert(I).second) {
534       // Break the cycle and delete the instruction and its operands.
535       I->replaceAllUsesWith(UndefValue::get(I->getType()));
536       (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
537       return true;
538     }
539   }
540   return false;
541 }
542 
543 static bool
simplifyAndDCEInstruction(Instruction * I,SmallSetVector<Instruction *,16> & WorkList,const DataLayout & DL,const TargetLibraryInfo * TLI)544 simplifyAndDCEInstruction(Instruction *I,
545                           SmallSetVector<Instruction *, 16> &WorkList,
546                           const DataLayout &DL,
547                           const TargetLibraryInfo *TLI) {
548   if (isInstructionTriviallyDead(I, TLI)) {
549     salvageDebugInfo(*I);
550 
551     // Null out all of the instruction's operands to see if any operand becomes
552     // dead as we go.
553     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
554       Value *OpV = I->getOperand(i);
555       I->setOperand(i, nullptr);
556 
557       if (!OpV->use_empty() || I == OpV)
558         continue;
559 
560       // If the operand is an instruction that became dead as we nulled out the
561       // operand, and if it is 'trivially' dead, delete it in a future loop
562       // iteration.
563       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
564         if (isInstructionTriviallyDead(OpI, TLI))
565           WorkList.insert(OpI);
566     }
567 
568     I->eraseFromParent();
569 
570     return true;
571   }
572 
573   if (Value *SimpleV = SimplifyInstruction(I, DL)) {
574     // Add the users to the worklist. CAREFUL: an instruction can use itself,
575     // in the case of a phi node.
576     for (User *U : I->users()) {
577       if (U != I) {
578         WorkList.insert(cast<Instruction>(U));
579       }
580     }
581 
582     // Replace the instruction with its simplified value.
583     bool Changed = false;
584     if (!I->use_empty()) {
585       I->replaceAllUsesWith(SimpleV);
586       Changed = true;
587     }
588     if (isInstructionTriviallyDead(I, TLI)) {
589       I->eraseFromParent();
590       Changed = true;
591     }
592     return Changed;
593   }
594   return false;
595 }
596 
597 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
598 /// simplify any instructions in it and recursively delete dead instructions.
599 ///
600 /// This returns true if it changed the code, note that it can delete
601 /// instructions in other blocks as well in this block.
SimplifyInstructionsInBlock(BasicBlock * BB,const TargetLibraryInfo * TLI)602 bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB,
603                                        const TargetLibraryInfo *TLI) {
604   bool MadeChange = false;
605   const DataLayout &DL = BB->getModule()->getDataLayout();
606 
607 #ifndef NDEBUG
608   // In debug builds, ensure that the terminator of the block is never replaced
609   // or deleted by these simplifications. The idea of simplification is that it
610   // cannot introduce new instructions, and there is no way to replace the
611   // terminator of a block without introducing a new instruction.
612   AssertingVH<Instruction> TerminatorVH(&BB->back());
613 #endif
614 
615   SmallSetVector<Instruction *, 16> WorkList;
616   // Iterate over the original function, only adding insts to the worklist
617   // if they actually need to be revisited. This avoids having to pre-init
618   // the worklist with the entire function's worth of instructions.
619   for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end());
620        BI != E;) {
621     assert(!BI->isTerminator());
622     Instruction *I = &*BI;
623     ++BI;
624 
625     // We're visiting this instruction now, so make sure it's not in the
626     // worklist from an earlier visit.
627     if (!WorkList.count(I))
628       MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
629   }
630 
631   while (!WorkList.empty()) {
632     Instruction *I = WorkList.pop_back_val();
633     MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
634   }
635   return MadeChange;
636 }
637 
638 //===----------------------------------------------------------------------===//
639 //  Control Flow Graph Restructuring.
640 //
641 
RemovePredecessorAndSimplify(BasicBlock * BB,BasicBlock * Pred,DomTreeUpdater * DTU)642 void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
643                                         DomTreeUpdater *DTU) {
644   // This only adjusts blocks with PHI nodes.
645   if (!isa<PHINode>(BB->begin()))
646     return;
647 
648   // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
649   // them down.  This will leave us with single entry phi nodes and other phis
650   // that can be removed.
651   BB->removePredecessor(Pred, true);
652 
653   WeakTrackingVH PhiIt = &BB->front();
654   while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
655     PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
656     Value *OldPhiIt = PhiIt;
657 
658     if (!recursivelySimplifyInstruction(PN))
659       continue;
660 
661     // If recursive simplification ended up deleting the next PHI node we would
662     // iterate to, then our iterator is invalid, restart scanning from the top
663     // of the block.
664     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
665   }
666   if (DTU)
667     DTU->applyUpdatesPermissive({{DominatorTree::Delete, Pred, BB}});
668 }
669 
MergeBasicBlockIntoOnlyPred(BasicBlock * DestBB,DomTreeUpdater * DTU)670 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB,
671                                        DomTreeUpdater *DTU) {
672 
673   // If BB has single-entry PHI nodes, fold them.
674   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
675     Value *NewVal = PN->getIncomingValue(0);
676     // Replace self referencing PHI with undef, it must be dead.
677     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
678     PN->replaceAllUsesWith(NewVal);
679     PN->eraseFromParent();
680   }
681 
682   BasicBlock *PredBB = DestBB->getSinglePredecessor();
683   assert(PredBB && "Block doesn't have a single predecessor!");
684 
685   bool ReplaceEntryBB = false;
686   if (PredBB == &DestBB->getParent()->getEntryBlock())
687     ReplaceEntryBB = true;
688 
689   // DTU updates: Collect all the edges that enter
690   // PredBB. These dominator edges will be redirected to DestBB.
691   SmallVector<DominatorTree::UpdateType, 32> Updates;
692 
693   if (DTU) {
694     Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
695     for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) {
696       Updates.push_back({DominatorTree::Delete, *I, PredBB});
697       // This predecessor of PredBB may already have DestBB as a successor.
698       if (llvm::find(successors(*I), DestBB) == succ_end(*I))
699         Updates.push_back({DominatorTree::Insert, *I, DestBB});
700     }
701   }
702 
703   // Zap anything that took the address of DestBB.  Not doing this will give the
704   // address an invalid value.
705   if (DestBB->hasAddressTaken()) {
706     BlockAddress *BA = BlockAddress::get(DestBB);
707     Constant *Replacement =
708       ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1);
709     BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
710                                                      BA->getType()));
711     BA->destroyConstant();
712   }
713 
714   // Anything that branched to PredBB now branches to DestBB.
715   PredBB->replaceAllUsesWith(DestBB);
716 
717   // Splice all the instructions from PredBB to DestBB.
718   PredBB->getTerminator()->eraseFromParent();
719   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
720   new UnreachableInst(PredBB->getContext(), PredBB);
721 
722   // If the PredBB is the entry block of the function, move DestBB up to
723   // become the entry block after we erase PredBB.
724   if (ReplaceEntryBB)
725     DestBB->moveAfter(PredBB);
726 
727   if (DTU) {
728     assert(PredBB->getInstList().size() == 1 &&
729            isa<UnreachableInst>(PredBB->getTerminator()) &&
730            "The successor list of PredBB isn't empty before "
731            "applying corresponding DTU updates.");
732     DTU->applyUpdatesPermissive(Updates);
733     DTU->deleteBB(PredBB);
734     // Recalculation of DomTree is needed when updating a forward DomTree and
735     // the Entry BB is replaced.
736     if (ReplaceEntryBB && DTU->hasDomTree()) {
737       // The entry block was removed and there is no external interface for
738       // the dominator tree to be notified of this change. In this corner-case
739       // we recalculate the entire tree.
740       DTU->recalculate(*(DestBB->getParent()));
741     }
742   }
743 
744   else {
745     PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr.
746   }
747 }
748 
749 /// Return true if we can choose one of these values to use in place of the
750 /// other. Note that we will always choose the non-undef value to keep.
CanMergeValues(Value * First,Value * Second)751 static bool CanMergeValues(Value *First, Value *Second) {
752   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
753 }
754 
755 /// Return true if we can fold BB, an almost-empty BB ending in an unconditional
756 /// branch to Succ, into Succ.
757 ///
758 /// Assumption: Succ is the single successor for BB.
CanPropagatePredecessorsForPHIs(BasicBlock * BB,BasicBlock * Succ)759 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
760   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
761 
762   LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
763                     << Succ->getName() << "\n");
764   // Shortcut, if there is only a single predecessor it must be BB and merging
765   // is always safe
766   if (Succ->getSinglePredecessor()) return true;
767 
768   // Make a list of the predecessors of BB
769   SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
770 
771   // Look at all the phi nodes in Succ, to see if they present a conflict when
772   // merging these blocks
773   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
774     PHINode *PN = cast<PHINode>(I);
775 
776     // If the incoming value from BB is again a PHINode in
777     // BB which has the same incoming value for *PI as PN does, we can
778     // merge the phi nodes and then the blocks can still be merged
779     PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
780     if (BBPN && BBPN->getParent() == BB) {
781       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
782         BasicBlock *IBB = PN->getIncomingBlock(PI);
783         if (BBPreds.count(IBB) &&
784             !CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
785                             PN->getIncomingValue(PI))) {
786           LLVM_DEBUG(dbgs()
787                      << "Can't fold, phi node " << PN->getName() << " in "
788                      << Succ->getName() << " is conflicting with "
789                      << BBPN->getName() << " with regard to common predecessor "
790                      << IBB->getName() << "\n");
791           return false;
792         }
793       }
794     } else {
795       Value* Val = PN->getIncomingValueForBlock(BB);
796       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
797         // See if the incoming value for the common predecessor is equal to the
798         // one for BB, in which case this phi node will not prevent the merging
799         // of the block.
800         BasicBlock *IBB = PN->getIncomingBlock(PI);
801         if (BBPreds.count(IBB) &&
802             !CanMergeValues(Val, PN->getIncomingValue(PI))) {
803           LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()
804                             << " in " << Succ->getName()
805                             << " is conflicting with regard to common "
806                             << "predecessor " << IBB->getName() << "\n");
807           return false;
808         }
809       }
810     }
811   }
812 
813   return true;
814 }
815 
816 using PredBlockVector = SmallVector<BasicBlock *, 16>;
817 using IncomingValueMap = DenseMap<BasicBlock *, Value *>;
818 
819 /// Determines the value to use as the phi node input for a block.
820 ///
821 /// Select between \p OldVal any value that we know flows from \p BB
822 /// to a particular phi on the basis of which one (if either) is not
823 /// undef. Update IncomingValues based on the selected value.
824 ///
825 /// \param OldVal The value we are considering selecting.
826 /// \param BB The block that the value flows in from.
827 /// \param IncomingValues A map from block-to-value for other phi inputs
828 /// that we have examined.
829 ///
830 /// \returns the selected value.
selectIncomingValueForBlock(Value * OldVal,BasicBlock * BB,IncomingValueMap & IncomingValues)831 static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB,
832                                           IncomingValueMap &IncomingValues) {
833   if (!isa<UndefValue>(OldVal)) {
834     assert((!IncomingValues.count(BB) ||
835             IncomingValues.find(BB)->second == OldVal) &&
836            "Expected OldVal to match incoming value from BB!");
837 
838     IncomingValues.insert(std::make_pair(BB, OldVal));
839     return OldVal;
840   }
841 
842   IncomingValueMap::const_iterator It = IncomingValues.find(BB);
843   if (It != IncomingValues.end()) return It->second;
844 
845   return OldVal;
846 }
847 
848 /// Create a map from block to value for the operands of a
849 /// given phi.
850 ///
851 /// Create a map from block to value for each non-undef value flowing
852 /// into \p PN.
853 ///
854 /// \param PN The phi we are collecting the map for.
855 /// \param IncomingValues [out] The map from block to value for this phi.
gatherIncomingValuesToPhi(PHINode * PN,IncomingValueMap & IncomingValues)856 static void gatherIncomingValuesToPhi(PHINode *PN,
857                                       IncomingValueMap &IncomingValues) {
858   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
859     BasicBlock *BB = PN->getIncomingBlock(i);
860     Value *V = PN->getIncomingValue(i);
861 
862     if (!isa<UndefValue>(V))
863       IncomingValues.insert(std::make_pair(BB, V));
864   }
865 }
866 
867 /// Replace the incoming undef values to a phi with the values
868 /// from a block-to-value map.
869 ///
870 /// \param PN The phi we are replacing the undefs in.
871 /// \param IncomingValues A map from block to value.
replaceUndefValuesInPhi(PHINode * PN,const IncomingValueMap & IncomingValues)872 static void replaceUndefValuesInPhi(PHINode *PN,
873                                     const IncomingValueMap &IncomingValues) {
874   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
875     Value *V = PN->getIncomingValue(i);
876 
877     if (!isa<UndefValue>(V)) continue;
878 
879     BasicBlock *BB = PN->getIncomingBlock(i);
880     IncomingValueMap::const_iterator It = IncomingValues.find(BB);
881     if (It == IncomingValues.end()) continue;
882 
883     PN->setIncomingValue(i, It->second);
884   }
885 }
886 
887 /// Replace a value flowing from a block to a phi with
888 /// potentially multiple instances of that value flowing from the
889 /// block's predecessors to the phi.
890 ///
891 /// \param BB The block with the value flowing into the phi.
892 /// \param BBPreds The predecessors of BB.
893 /// \param PN The phi that we are updating.
redirectValuesFromPredecessorsToPhi(BasicBlock * BB,const PredBlockVector & BBPreds,PHINode * PN)894 static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
895                                                 const PredBlockVector &BBPreds,
896                                                 PHINode *PN) {
897   Value *OldVal = PN->removeIncomingValue(BB, false);
898   assert(OldVal && "No entry in PHI for Pred BB!");
899 
900   IncomingValueMap IncomingValues;
901 
902   // We are merging two blocks - BB, and the block containing PN - and
903   // as a result we need to redirect edges from the predecessors of BB
904   // to go to the block containing PN, and update PN
905   // accordingly. Since we allow merging blocks in the case where the
906   // predecessor and successor blocks both share some predecessors,
907   // and where some of those common predecessors might have undef
908   // values flowing into PN, we want to rewrite those values to be
909   // consistent with the non-undef values.
910 
911   gatherIncomingValuesToPhi(PN, IncomingValues);
912 
913   // If this incoming value is one of the PHI nodes in BB, the new entries
914   // in the PHI node are the entries from the old PHI.
915   if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
916     PHINode *OldValPN = cast<PHINode>(OldVal);
917     for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
918       // Note that, since we are merging phi nodes and BB and Succ might
919       // have common predecessors, we could end up with a phi node with
920       // identical incoming branches. This will be cleaned up later (and
921       // will trigger asserts if we try to clean it up now, without also
922       // simplifying the corresponding conditional branch).
923       BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
924       Value *PredVal = OldValPN->getIncomingValue(i);
925       Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
926                                                     IncomingValues);
927 
928       // And add a new incoming value for this predecessor for the
929       // newly retargeted branch.
930       PN->addIncoming(Selected, PredBB);
931     }
932   } else {
933     for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
934       // Update existing incoming values in PN for this
935       // predecessor of BB.
936       BasicBlock *PredBB = BBPreds[i];
937       Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
938                                                     IncomingValues);
939 
940       // And add a new incoming value for this predecessor for the
941       // newly retargeted branch.
942       PN->addIncoming(Selected, PredBB);
943     }
944   }
945 
946   replaceUndefValuesInPhi(PN, IncomingValues);
947 }
948 
TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock * BB,DomTreeUpdater * DTU)949 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
950                                                    DomTreeUpdater *DTU) {
951   assert(BB != &BB->getParent()->getEntryBlock() &&
952          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
953 
954   // We can't eliminate infinite loops.
955   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
956   if (BB == Succ) return false;
957 
958   // Check to see if merging these blocks would cause conflicts for any of the
959   // phi nodes in BB or Succ. If not, we can safely merge.
960   if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
961 
962   // Check for cases where Succ has multiple predecessors and a PHI node in BB
963   // has uses which will not disappear when the PHI nodes are merged.  It is
964   // possible to handle such cases, but difficult: it requires checking whether
965   // BB dominates Succ, which is non-trivial to calculate in the case where
966   // Succ has multiple predecessors.  Also, it requires checking whether
967   // constructing the necessary self-referential PHI node doesn't introduce any
968   // conflicts; this isn't too difficult, but the previous code for doing this
969   // was incorrect.
970   //
971   // Note that if this check finds a live use, BB dominates Succ, so BB is
972   // something like a loop pre-header (or rarely, a part of an irreducible CFG);
973   // folding the branch isn't profitable in that case anyway.
974   if (!Succ->getSinglePredecessor()) {
975     BasicBlock::iterator BBI = BB->begin();
976     while (isa<PHINode>(*BBI)) {
977       for (Use &U : BBI->uses()) {
978         if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
979           if (PN->getIncomingBlock(U) != BB)
980             return false;
981         } else {
982           return false;
983         }
984       }
985       ++BBI;
986     }
987   }
988 
989   // We cannot fold the block if it's a branch to an already present callbr
990   // successor because that creates duplicate successors.
991   for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
992     if (auto *CBI = dyn_cast<CallBrInst>((*I)->getTerminator())) {
993       if (Succ == CBI->getDefaultDest())
994         return false;
995       for (unsigned i = 0, e = CBI->getNumIndirectDests(); i != e; ++i)
996         if (Succ == CBI->getIndirectDest(i))
997           return false;
998     }
999   }
1000 
1001   LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
1002 
1003   SmallVector<DominatorTree::UpdateType, 32> Updates;
1004   if (DTU) {
1005     Updates.push_back({DominatorTree::Delete, BB, Succ});
1006     // All predecessors of BB will be moved to Succ.
1007     for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
1008       Updates.push_back({DominatorTree::Delete, *I, BB});
1009       // This predecessor of BB may already have Succ as a successor.
1010       if (llvm::find(successors(*I), Succ) == succ_end(*I))
1011         Updates.push_back({DominatorTree::Insert, *I, Succ});
1012     }
1013   }
1014 
1015   if (isa<PHINode>(Succ->begin())) {
1016     // If there is more than one pred of succ, and there are PHI nodes in
1017     // the successor, then we need to add incoming edges for the PHI nodes
1018     //
1019     const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
1020 
1021     // Loop over all of the PHI nodes in the successor of BB.
1022     for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
1023       PHINode *PN = cast<PHINode>(I);
1024 
1025       redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
1026     }
1027   }
1028 
1029   if (Succ->getSinglePredecessor()) {
1030     // BB is the only predecessor of Succ, so Succ will end up with exactly
1031     // the same predecessors BB had.
1032 
1033     // Copy over any phi, debug or lifetime instruction.
1034     BB->getTerminator()->eraseFromParent();
1035     Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
1036                                BB->getInstList());
1037   } else {
1038     while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
1039       // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
1040       assert(PN->use_empty() && "There shouldn't be any uses here!");
1041       PN->eraseFromParent();
1042     }
1043   }
1044 
1045   // If the unconditional branch we replaced contains llvm.loop metadata, we
1046   // add the metadata to the branch instructions in the predecessors.
1047   unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
1048   Instruction *TI = BB->getTerminator();
1049   if (TI)
1050     if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
1051       for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
1052         BasicBlock *Pred = *PI;
1053         Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
1054       }
1055 
1056   // Everything that jumped to BB now goes to Succ.
1057   BB->replaceAllUsesWith(Succ);
1058   if (!Succ->hasName()) Succ->takeName(BB);
1059 
1060   // Clear the successor list of BB to match updates applying to DTU later.
1061   if (BB->getTerminator())
1062     BB->getInstList().pop_back();
1063   new UnreachableInst(BB->getContext(), BB);
1064   assert(succ_empty(BB) && "The successor list of BB isn't empty before "
1065                            "applying corresponding DTU updates.");
1066 
1067   if (DTU) {
1068     DTU->applyUpdatesPermissive(Updates);
1069     DTU->deleteBB(BB);
1070   } else {
1071     BB->eraseFromParent(); // Delete the old basic block.
1072   }
1073   return true;
1074 }
1075 
EliminateDuplicatePHINodes(BasicBlock * BB)1076 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
1077   // This implementation doesn't currently consider undef operands
1078   // specially. Theoretically, two phis which are identical except for
1079   // one having an undef where the other doesn't could be collapsed.
1080 
1081   struct PHIDenseMapInfo {
1082     static PHINode *getEmptyKey() {
1083       return DenseMapInfo<PHINode *>::getEmptyKey();
1084     }
1085 
1086     static PHINode *getTombstoneKey() {
1087       return DenseMapInfo<PHINode *>::getTombstoneKey();
1088     }
1089 
1090     static unsigned getHashValue(PHINode *PN) {
1091       // Compute a hash value on the operands. Instcombine will likely have
1092       // sorted them, which helps expose duplicates, but we have to check all
1093       // the operands to be safe in case instcombine hasn't run.
1094       return static_cast<unsigned>(hash_combine(
1095           hash_combine_range(PN->value_op_begin(), PN->value_op_end()),
1096           hash_combine_range(PN->block_begin(), PN->block_end())));
1097     }
1098 
1099     static bool isEqual(PHINode *LHS, PHINode *RHS) {
1100       if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
1101           RHS == getEmptyKey() || RHS == getTombstoneKey())
1102         return LHS == RHS;
1103       return LHS->isIdenticalTo(RHS);
1104     }
1105   };
1106 
1107   // Set of unique PHINodes.
1108   DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
1109 
1110   // Examine each PHI.
1111   bool Changed = false;
1112   for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
1113     auto Inserted = PHISet.insert(PN);
1114     if (!Inserted.second) {
1115       // A duplicate. Replace this PHI with its duplicate.
1116       PN->replaceAllUsesWith(*Inserted.first);
1117       PN->eraseFromParent();
1118       Changed = true;
1119 
1120       // The RAUW can change PHIs that we already visited. Start over from the
1121       // beginning.
1122       PHISet.clear();
1123       I = BB->begin();
1124     }
1125   }
1126 
1127   return Changed;
1128 }
1129 
1130 /// enforceKnownAlignment - If the specified pointer points to an object that
1131 /// we control, modify the object's alignment to PrefAlign. This isn't
1132 /// often possible though. If alignment is important, a more reliable approach
1133 /// is to simply align all global variables and allocation instructions to
1134 /// their preferred alignment from the beginning.
enforceKnownAlignment(Value * V,unsigned Alignment,unsigned PrefAlign,const DataLayout & DL)1135 static unsigned enforceKnownAlignment(Value *V, unsigned Alignment,
1136                                       unsigned PrefAlign,
1137                                       const DataLayout &DL) {
1138   assert(PrefAlign > Alignment);
1139 
1140   V = V->stripPointerCasts();
1141 
1142   if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1143     // TODO: ideally, computeKnownBits ought to have used
1144     // AllocaInst::getAlignment() in its computation already, making
1145     // the below max redundant. But, as it turns out,
1146     // stripPointerCasts recurses through infinite layers of bitcasts,
1147     // while computeKnownBits is not allowed to traverse more than 6
1148     // levels.
1149     Alignment = std::max(AI->getAlignment(), Alignment);
1150     if (PrefAlign <= Alignment)
1151       return Alignment;
1152 
1153     // If the preferred alignment is greater than the natural stack alignment
1154     // then don't round up. This avoids dynamic stack realignment.
1155     if (DL.exceedsNaturalStackAlignment(Align(PrefAlign)))
1156       return Alignment;
1157     AI->setAlignment(MaybeAlign(PrefAlign));
1158     return PrefAlign;
1159   }
1160 
1161   if (auto *GO = dyn_cast<GlobalObject>(V)) {
1162     // TODO: as above, this shouldn't be necessary.
1163     Alignment = std::max(GO->getAlignment(), Alignment);
1164     if (PrefAlign <= Alignment)
1165       return Alignment;
1166 
1167     // If there is a large requested alignment and we can, bump up the alignment
1168     // of the global.  If the memory we set aside for the global may not be the
1169     // memory used by the final program then it is impossible for us to reliably
1170     // enforce the preferred alignment.
1171     if (!GO->canIncreaseAlignment())
1172       return Alignment;
1173 
1174     GO->setAlignment(MaybeAlign(PrefAlign));
1175     return PrefAlign;
1176   }
1177 
1178   return Alignment;
1179 }
1180 
getOrEnforceKnownAlignment(Value * V,unsigned PrefAlign,const DataLayout & DL,const Instruction * CxtI,AssumptionCache * AC,const DominatorTree * DT)1181 unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
1182                                           const DataLayout &DL,
1183                                           const Instruction *CxtI,
1184                                           AssumptionCache *AC,
1185                                           const DominatorTree *DT) {
1186   assert(V->getType()->isPointerTy() &&
1187          "getOrEnforceKnownAlignment expects a pointer!");
1188 
1189   KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT);
1190   unsigned TrailZ = Known.countMinTrailingZeros();
1191 
1192   // Avoid trouble with ridiculously large TrailZ values, such as
1193   // those computed from a null pointer.
1194   TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1));
1195 
1196   unsigned Align = 1u << std::min(Known.getBitWidth() - 1, TrailZ);
1197 
1198   // LLVM doesn't support alignments larger than this currently.
1199   Align = std::min(Align, +Value::MaximumAlignment);
1200 
1201   if (PrefAlign > Align)
1202     Align = enforceKnownAlignment(V, Align, PrefAlign, DL);
1203 
1204   // We don't need to make any adjustment.
1205   return Align;
1206 }
1207 
1208 ///===---------------------------------------------------------------------===//
1209 ///  Dbg Intrinsic utilities
1210 ///
1211 
1212 /// See if there is a dbg.value intrinsic for DIVar before I.
LdStHasDebugValue(DILocalVariable * DIVar,DIExpression * DIExpr,Instruction * I)1213 static bool LdStHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr,
1214                               Instruction *I) {
1215   // Since we can't guarantee that the original dbg.declare instrinsic
1216   // is removed by LowerDbgDeclare(), we need to make sure that we are
1217   // not inserting the same dbg.value intrinsic over and over.
1218   BasicBlock::InstListType::iterator PrevI(I);
1219   if (PrevI != I->getParent()->getInstList().begin()) {
1220     --PrevI;
1221     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
1222       if (DVI->getValue() == I->getOperand(0) &&
1223           DVI->getVariable() == DIVar &&
1224           DVI->getExpression() == DIExpr)
1225         return true;
1226   }
1227   return false;
1228 }
1229 
1230 /// See if there is a dbg.value intrinsic for DIVar for the PHI node.
PhiHasDebugValue(DILocalVariable * DIVar,DIExpression * DIExpr,PHINode * APN)1231 static bool PhiHasDebugValue(DILocalVariable *DIVar,
1232                              DIExpression *DIExpr,
1233                              PHINode *APN) {
1234   // Since we can't guarantee that the original dbg.declare instrinsic
1235   // is removed by LowerDbgDeclare(), we need to make sure that we are
1236   // not inserting the same dbg.value intrinsic over and over.
1237   SmallVector<DbgValueInst *, 1> DbgValues;
1238   findDbgValues(DbgValues, APN);
1239   for (auto *DVI : DbgValues) {
1240     assert(DVI->getValue() == APN);
1241     if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1242       return true;
1243   }
1244   return false;
1245 }
1246 
1247 /// Check if the alloc size of \p ValTy is large enough to cover the variable
1248 /// (or fragment of the variable) described by \p DII.
1249 ///
1250 /// This is primarily intended as a helper for the different
1251 /// ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is
1252 /// converted describes an alloca'd variable, so we need to use the
1253 /// alloc size of the value when doing the comparison. E.g. an i1 value will be
1254 /// identified as covering an n-bit fragment, if the store size of i1 is at
1255 /// least n bits.
valueCoversEntireFragment(Type * ValTy,DbgVariableIntrinsic * DII)1256 static bool valueCoversEntireFragment(Type *ValTy, DbgVariableIntrinsic *DII) {
1257   const DataLayout &DL = DII->getModule()->getDataLayout();
1258   uint64_t ValueSize = DL.getTypeAllocSizeInBits(ValTy);
1259   if (auto FragmentSize = DII->getFragmentSizeInBits())
1260     return ValueSize >= *FragmentSize;
1261   // We can't always calculate the size of the DI variable (e.g. if it is a
1262   // VLA). Try to use the size of the alloca that the dbg intrinsic describes
1263   // intead.
1264   if (DII->isAddressOfVariable())
1265     if (auto *AI = dyn_cast_or_null<AllocaInst>(DII->getVariableLocation()))
1266       if (auto FragmentSize = AI->getAllocationSizeInBits(DL))
1267         return ValueSize >= *FragmentSize;
1268   // Could not determine size of variable. Conservatively return false.
1269   return false;
1270 }
1271 
1272 /// Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted
1273 /// to a dbg.value. Because no machine insts can come from debug intrinsics,
1274 /// only the scope and inlinedAt is significant. Zero line numbers are used in
1275 /// case this DebugLoc leaks into any adjacent instructions.
getDebugValueLoc(DbgVariableIntrinsic * DII,Instruction * Src)1276 static DebugLoc getDebugValueLoc(DbgVariableIntrinsic *DII, Instruction *Src) {
1277   // Original dbg.declare must have a location.
1278   DebugLoc DeclareLoc = DII->getDebugLoc();
1279   MDNode *Scope = DeclareLoc.getScope();
1280   DILocation *InlinedAt = DeclareLoc.getInlinedAt();
1281   // Produce an unknown location with the correct scope / inlinedAt fields.
1282   return DebugLoc::get(0, 0, Scope, InlinedAt);
1283 }
1284 
1285 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1286 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic * DII,StoreInst * SI,DIBuilder & Builder)1287 void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII,
1288                                            StoreInst *SI, DIBuilder &Builder) {
1289   assert(DII->isAddressOfVariable());
1290   auto *DIVar = DII->getVariable();
1291   assert(DIVar && "Missing variable");
1292   auto *DIExpr = DII->getExpression();
1293   Value *DV = SI->getValueOperand();
1294 
1295   DebugLoc NewLoc = getDebugValueLoc(DII, SI);
1296 
1297   if (!valueCoversEntireFragment(DV->getType(), DII)) {
1298     // FIXME: If storing to a part of the variable described by the dbg.declare,
1299     // then we want to insert a dbg.value for the corresponding fragment.
1300     LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1301                       << *DII << '\n');
1302     // For now, when there is a store to parts of the variable (but we do not
1303     // know which part) we insert an dbg.value instrinsic to indicate that we
1304     // know nothing about the variable's content.
1305     DV = UndefValue::get(DV->getType());
1306     if (!LdStHasDebugValue(DIVar, DIExpr, SI))
1307       Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1308     return;
1309   }
1310 
1311   if (!LdStHasDebugValue(DIVar, DIExpr, SI))
1312     Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1313 }
1314 
1315 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1316 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic * DII,LoadInst * LI,DIBuilder & Builder)1317 void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII,
1318                                            LoadInst *LI, DIBuilder &Builder) {
1319   auto *DIVar = DII->getVariable();
1320   auto *DIExpr = DII->getExpression();
1321   assert(DIVar && "Missing variable");
1322 
1323   if (LdStHasDebugValue(DIVar, DIExpr, LI))
1324     return;
1325 
1326   if (!valueCoversEntireFragment(LI->getType(), DII)) {
1327     // FIXME: If only referring to a part of the variable described by the
1328     // dbg.declare, then we want to insert a dbg.value for the corresponding
1329     // fragment.
1330     LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1331                       << *DII << '\n');
1332     return;
1333   }
1334 
1335   DebugLoc NewLoc = getDebugValueLoc(DII, nullptr);
1336 
1337   // We are now tracking the loaded value instead of the address. In the
1338   // future if multi-location support is added to the IR, it might be
1339   // preferable to keep tracking both the loaded value and the original
1340   // address in case the alloca can not be elided.
1341   Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
1342       LI, DIVar, DIExpr, NewLoc, (Instruction *)nullptr);
1343   DbgValue->insertAfter(LI);
1344 }
1345 
1346 /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
1347 /// llvm.dbg.declare or llvm.dbg.addr intrinsic.
ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic * DII,PHINode * APN,DIBuilder & Builder)1348 void llvm::ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII,
1349                                            PHINode *APN, DIBuilder &Builder) {
1350   auto *DIVar = DII->getVariable();
1351   auto *DIExpr = DII->getExpression();
1352   assert(DIVar && "Missing variable");
1353 
1354   if (PhiHasDebugValue(DIVar, DIExpr, APN))
1355     return;
1356 
1357   if (!valueCoversEntireFragment(APN->getType(), DII)) {
1358     // FIXME: If only referring to a part of the variable described by the
1359     // dbg.declare, then we want to insert a dbg.value for the corresponding
1360     // fragment.
1361     LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1362                       << *DII << '\n');
1363     return;
1364   }
1365 
1366   BasicBlock *BB = APN->getParent();
1367   auto InsertionPt = BB->getFirstInsertionPt();
1368 
1369   DebugLoc NewLoc = getDebugValueLoc(DII, nullptr);
1370 
1371   // The block may be a catchswitch block, which does not have a valid
1372   // insertion point.
1373   // FIXME: Insert dbg.value markers in the successors when appropriate.
1374   if (InsertionPt != BB->end())
1375     Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, NewLoc, &*InsertionPt);
1376 }
1377 
1378 /// Determine whether this alloca is either a VLA or an array.
isArray(AllocaInst * AI)1379 static bool isArray(AllocaInst *AI) {
1380   return AI->isArrayAllocation() ||
1381          (AI->getAllocatedType() && AI->getAllocatedType()->isArrayTy());
1382 }
1383 
1384 /// Determine whether this alloca is a structure.
isStructure(AllocaInst * AI)1385 static bool isStructure(AllocaInst *AI) {
1386   return AI->getAllocatedType() && AI->getAllocatedType()->isStructTy();
1387 }
1388 
1389 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1390 /// of llvm.dbg.value intrinsics.
LowerDbgDeclare(Function & F)1391 bool llvm::LowerDbgDeclare(Function &F) {
1392   DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1393   SmallVector<DbgDeclareInst *, 4> Dbgs;
1394   for (auto &FI : F)
1395     for (Instruction &BI : FI)
1396       if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
1397         Dbgs.push_back(DDI);
1398 
1399   if (Dbgs.empty())
1400     return false;
1401 
1402   for (auto &I : Dbgs) {
1403     DbgDeclareInst *DDI = I;
1404     AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1405     // If this is an alloca for a scalar variable, insert a dbg.value
1406     // at each load and store to the alloca and erase the dbg.declare.
1407     // The dbg.values allow tracking a variable even if it is not
1408     // stored on the stack, while the dbg.declare can only describe
1409     // the stack slot (and at a lexical-scope granularity). Later
1410     // passes will attempt to elide the stack slot.
1411     if (!AI || isArray(AI) || isStructure(AI))
1412       continue;
1413 
1414     // A volatile load/store means that the alloca can't be elided anyway.
1415     if (llvm::any_of(AI->users(), [](User *U) -> bool {
1416           if (LoadInst *LI = dyn_cast<LoadInst>(U))
1417             return LI->isVolatile();
1418           if (StoreInst *SI = dyn_cast<StoreInst>(U))
1419             return SI->isVolatile();
1420           return false;
1421         }))
1422       continue;
1423 
1424     SmallVector<const Value *, 8> WorkList;
1425     WorkList.push_back(AI);
1426     while (!WorkList.empty()) {
1427       const Value *V = WorkList.pop_back_val();
1428       for (auto &AIUse : V->uses()) {
1429         User *U = AIUse.getUser();
1430         if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1431           if (AIUse.getOperandNo() == 1)
1432             ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
1433         } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1434           ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1435         } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1436           // This is a call by-value or some other instruction that takes a
1437           // pointer to the variable. Insert a *value* intrinsic that describes
1438           // the variable by dereferencing the alloca.
1439           if (!CI->isLifetimeStartOrEnd()) {
1440             DebugLoc NewLoc = getDebugValueLoc(DDI, nullptr);
1441             auto *DerefExpr =
1442                 DIExpression::append(DDI->getExpression(), dwarf::DW_OP_deref);
1443             DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DerefExpr,
1444                                         NewLoc, CI);
1445           }
1446         } else if (BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
1447           if (BI->getType()->isPointerTy())
1448             WorkList.push_back(BI);
1449         }
1450       }
1451     }
1452     DDI->eraseFromParent();
1453   }
1454   return true;
1455 }
1456 
1457 /// Propagate dbg.value intrinsics through the newly inserted PHIs.
insertDebugValuesForPHIs(BasicBlock * BB,SmallVectorImpl<PHINode * > & InsertedPHIs)1458 void llvm::insertDebugValuesForPHIs(BasicBlock *BB,
1459                                     SmallVectorImpl<PHINode *> &InsertedPHIs) {
1460   assert(BB && "No BasicBlock to clone dbg.value(s) from.");
1461   if (InsertedPHIs.size() == 0)
1462     return;
1463 
1464   // Map existing PHI nodes to their dbg.values.
1465   ValueToValueMapTy DbgValueMap;
1466   for (auto &I : *BB) {
1467     if (auto DbgII = dyn_cast<DbgVariableIntrinsic>(&I)) {
1468       if (auto *Loc = dyn_cast_or_null<PHINode>(DbgII->getVariableLocation()))
1469         DbgValueMap.insert({Loc, DbgII});
1470     }
1471   }
1472   if (DbgValueMap.size() == 0)
1473     return;
1474 
1475   // Then iterate through the new PHIs and look to see if they use one of the
1476   // previously mapped PHIs. If so, insert a new dbg.value intrinsic that will
1477   // propagate the info through the new PHI.
1478   LLVMContext &C = BB->getContext();
1479   for (auto PHI : InsertedPHIs) {
1480     BasicBlock *Parent = PHI->getParent();
1481     // Avoid inserting an intrinsic into an EH block.
1482     if (Parent->getFirstNonPHI()->isEHPad())
1483       continue;
1484     auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI));
1485     for (auto VI : PHI->operand_values()) {
1486       auto V = DbgValueMap.find(VI);
1487       if (V != DbgValueMap.end()) {
1488         auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
1489         Instruction *NewDbgII = DbgII->clone();
1490         NewDbgII->setOperand(0, PhiMAV);
1491         auto InsertionPt = Parent->getFirstInsertionPt();
1492         assert(InsertionPt != Parent->end() && "Ill-formed basic block");
1493         NewDbgII->insertBefore(&*InsertionPt);
1494       }
1495     }
1496   }
1497 }
1498 
1499 /// Finds all intrinsics declaring local variables as living in the memory that
1500 /// 'V' points to. This may include a mix of dbg.declare and
1501 /// dbg.addr intrinsics.
FindDbgAddrUses(Value * V)1502 TinyPtrVector<DbgVariableIntrinsic *> llvm::FindDbgAddrUses(Value *V) {
1503   // This function is hot. Check whether the value has any metadata to avoid a
1504   // DenseMap lookup.
1505   if (!V->isUsedByMetadata())
1506     return {};
1507   auto *L = LocalAsMetadata::getIfExists(V);
1508   if (!L)
1509     return {};
1510   auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L);
1511   if (!MDV)
1512     return {};
1513 
1514   TinyPtrVector<DbgVariableIntrinsic *> Declares;
1515   for (User *U : MDV->users()) {
1516     if (auto *DII = dyn_cast<DbgVariableIntrinsic>(U))
1517       if (DII->isAddressOfVariable())
1518         Declares.push_back(DII);
1519   }
1520 
1521   return Declares;
1522 }
1523 
findDbgValues(SmallVectorImpl<DbgValueInst * > & DbgValues,Value * V)1524 void llvm::findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V) {
1525   // This function is hot. Check whether the value has any metadata to avoid a
1526   // DenseMap lookup.
1527   if (!V->isUsedByMetadata())
1528     return;
1529   if (auto *L = LocalAsMetadata::getIfExists(V))
1530     if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1531       for (User *U : MDV->users())
1532         if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U))
1533           DbgValues.push_back(DVI);
1534 }
1535 
findDbgUsers(SmallVectorImpl<DbgVariableIntrinsic * > & DbgUsers,Value * V)1536 void llvm::findDbgUsers(SmallVectorImpl<DbgVariableIntrinsic *> &DbgUsers,
1537                         Value *V) {
1538   // This function is hot. Check whether the value has any metadata to avoid a
1539   // DenseMap lookup.
1540   if (!V->isUsedByMetadata())
1541     return;
1542   if (auto *L = LocalAsMetadata::getIfExists(V))
1543     if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1544       for (User *U : MDV->users())
1545         if (DbgVariableIntrinsic *DII = dyn_cast<DbgVariableIntrinsic>(U))
1546           DbgUsers.push_back(DII);
1547 }
1548 
replaceDbgDeclare(Value * Address,Value * NewAddress,Instruction * InsertBefore,DIBuilder & Builder,uint8_t DIExprFlags,int Offset)1549 bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress,
1550                              Instruction *InsertBefore, DIBuilder &Builder,
1551                              uint8_t DIExprFlags, int Offset) {
1552   auto DbgAddrs = FindDbgAddrUses(Address);
1553   for (DbgVariableIntrinsic *DII : DbgAddrs) {
1554     DebugLoc Loc = DII->getDebugLoc();
1555     auto *DIVar = DII->getVariable();
1556     auto *DIExpr = DII->getExpression();
1557     assert(DIVar && "Missing variable");
1558     DIExpr = DIExpression::prepend(DIExpr, DIExprFlags, Offset);
1559     // Insert llvm.dbg.declare immediately before InsertBefore, and remove old
1560     // llvm.dbg.declare.
1561     Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore);
1562     if (DII == InsertBefore)
1563       InsertBefore = InsertBefore->getNextNode();
1564     DII->eraseFromParent();
1565   }
1566   return !DbgAddrs.empty();
1567 }
1568 
replaceDbgDeclareForAlloca(AllocaInst * AI,Value * NewAllocaAddress,DIBuilder & Builder,uint8_t DIExprFlags,int Offset)1569 bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
1570                                       DIBuilder &Builder, uint8_t DIExprFlags,
1571                                       int Offset) {
1572   return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder,
1573                            DIExprFlags, Offset);
1574 }
1575 
replaceOneDbgValueForAlloca(DbgValueInst * DVI,Value * NewAddress,DIBuilder & Builder,int Offset)1576 static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
1577                                         DIBuilder &Builder, int Offset) {
1578   DebugLoc Loc = DVI->getDebugLoc();
1579   auto *DIVar = DVI->getVariable();
1580   auto *DIExpr = DVI->getExpression();
1581   assert(DIVar && "Missing variable");
1582 
1583   // This is an alloca-based llvm.dbg.value. The first thing it should do with
1584   // the alloca pointer is dereference it. Otherwise we don't know how to handle
1585   // it and give up.
1586   if (!DIExpr || DIExpr->getNumElements() < 1 ||
1587       DIExpr->getElement(0) != dwarf::DW_OP_deref)
1588     return;
1589 
1590   // Insert the offset before the first deref.
1591   // We could just change the offset argument of dbg.value, but it's unsigned...
1592   if (Offset)
1593     DIExpr = DIExpression::prepend(DIExpr, 0, Offset);
1594 
1595   Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI);
1596   DVI->eraseFromParent();
1597 }
1598 
replaceDbgValueForAlloca(AllocaInst * AI,Value * NewAllocaAddress,DIBuilder & Builder,int Offset)1599 void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
1600                                     DIBuilder &Builder, int Offset) {
1601   if (auto *L = LocalAsMetadata::getIfExists(AI))
1602     if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
1603       for (auto UI = MDV->use_begin(), UE = MDV->use_end(); UI != UE;) {
1604         Use &U = *UI++;
1605         if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
1606           replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1607       }
1608 }
1609 
1610 /// Wrap \p V in a ValueAsMetadata instance.
wrapValueInMetadata(LLVMContext & C,Value * V)1611 static MetadataAsValue *wrapValueInMetadata(LLVMContext &C, Value *V) {
1612   return MetadataAsValue::get(C, ValueAsMetadata::get(V));
1613 }
1614 
salvageDebugInfo(Instruction & I)1615 bool llvm::salvageDebugInfo(Instruction &I) {
1616   SmallVector<DbgVariableIntrinsic *, 1> DbgUsers;
1617   findDbgUsers(DbgUsers, &I);
1618   if (DbgUsers.empty())
1619     return false;
1620 
1621   return salvageDebugInfoForDbgValues(I, DbgUsers);
1622 }
1623 
salvageDebugInfoOrMarkUndef(Instruction & I)1624 void llvm::salvageDebugInfoOrMarkUndef(Instruction &I) {
1625   if (!salvageDebugInfo(I))
1626     replaceDbgUsesWithUndef(&I);
1627 }
1628 
salvageDebugInfoForDbgValues(Instruction & I,ArrayRef<DbgVariableIntrinsic * > DbgUsers)1629 bool llvm::salvageDebugInfoForDbgValues(
1630     Instruction &I, ArrayRef<DbgVariableIntrinsic *> DbgUsers) {
1631   auto &Ctx = I.getContext();
1632   auto wrapMD = [&](Value *V) { return wrapValueInMetadata(Ctx, V); };
1633 
1634   for (auto *DII : DbgUsers) {
1635     // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they
1636     // are implicitly pointing out the value as a DWARF memory location
1637     // description.
1638     bool StackValue = isa<DbgValueInst>(DII);
1639 
1640     DIExpression *DIExpr =
1641         salvageDebugInfoImpl(I, DII->getExpression(), StackValue);
1642 
1643     // salvageDebugInfoImpl should fail on examining the first element of
1644     // DbgUsers, or none of them.
1645     if (!DIExpr)
1646       return false;
1647 
1648     DII->setOperand(0, wrapMD(I.getOperand(0)));
1649     DII->setOperand(2, MetadataAsValue::get(Ctx, DIExpr));
1650     LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
1651   }
1652 
1653   return true;
1654 }
1655 
salvageDebugInfoImpl(Instruction & I,DIExpression * SrcDIExpr,bool WithStackValue)1656 DIExpression *llvm::salvageDebugInfoImpl(Instruction &I,
1657                                          DIExpression *SrcDIExpr,
1658                                          bool WithStackValue) {
1659   auto &M = *I.getModule();
1660   auto &DL = M.getDataLayout();
1661 
1662   // Apply a vector of opcodes to the source DIExpression.
1663   auto doSalvage = [&](SmallVectorImpl<uint64_t> &Ops) -> DIExpression * {
1664     DIExpression *DIExpr = SrcDIExpr;
1665     if (!Ops.empty()) {
1666       DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue);
1667     }
1668     return DIExpr;
1669   };
1670 
1671   // Apply the given offset to the source DIExpression.
1672   auto applyOffset = [&](uint64_t Offset) -> DIExpression * {
1673     SmallVector<uint64_t, 8> Ops;
1674     DIExpression::appendOffset(Ops, Offset);
1675     return doSalvage(Ops);
1676   };
1677 
1678   // initializer-list helper for applying operators to the source DIExpression.
1679   auto applyOps = [&](ArrayRef<uint64_t> Opcodes) -> DIExpression * {
1680     SmallVector<uint64_t, 8> Ops(Opcodes.begin(), Opcodes.end());
1681     return doSalvage(Ops);
1682   };
1683 
1684   if (auto *CI = dyn_cast<CastInst>(&I)) {
1685     // No-op casts and zexts are irrelevant for debug info.
1686     if (CI->isNoopCast(DL) || isa<ZExtInst>(&I))
1687       return SrcDIExpr;
1688 
1689     Type *Type = CI->getType();
1690     // Casts other than Trunc or SExt to scalar types cannot be salvaged.
1691     if (Type->isVectorTy() || (!isa<TruncInst>(&I) && !isa<SExtInst>(&I)))
1692       return nullptr;
1693 
1694     Value *FromValue = CI->getOperand(0);
1695     unsigned FromTypeBitSize = FromValue->getType()->getScalarSizeInBits();
1696     unsigned ToTypeBitSize = Type->getScalarSizeInBits();
1697 
1698     return applyOps(DIExpression::getExtOps(FromTypeBitSize, ToTypeBitSize,
1699                                             isa<SExtInst>(&I)));
1700   }
1701 
1702   if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1703     unsigned BitWidth =
1704         M.getDataLayout().getIndexSizeInBits(GEP->getPointerAddressSpace());
1705     // Rewrite a constant GEP into a DIExpression.
1706     APInt Offset(BitWidth, 0);
1707     if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) {
1708       return applyOffset(Offset.getSExtValue());
1709     } else {
1710       return nullptr;
1711     }
1712   } else if (auto *BI = dyn_cast<BinaryOperator>(&I)) {
1713     // Rewrite binary operations with constant integer operands.
1714     auto *ConstInt = dyn_cast<ConstantInt>(I.getOperand(1));
1715     if (!ConstInt || ConstInt->getBitWidth() > 64)
1716       return nullptr;
1717 
1718     uint64_t Val = ConstInt->getSExtValue();
1719     switch (BI->getOpcode()) {
1720     case Instruction::Add:
1721       return applyOffset(Val);
1722     case Instruction::Sub:
1723       return applyOffset(-int64_t(Val));
1724     case Instruction::Mul:
1725       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_mul});
1726     case Instruction::SDiv:
1727       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_div});
1728     case Instruction::SRem:
1729       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_mod});
1730     case Instruction::Or:
1731       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_or});
1732     case Instruction::And:
1733       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_and});
1734     case Instruction::Xor:
1735       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_xor});
1736     case Instruction::Shl:
1737       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_shl});
1738     case Instruction::LShr:
1739       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_shr});
1740     case Instruction::AShr:
1741       return applyOps({dwarf::DW_OP_constu, Val, dwarf::DW_OP_shra});
1742     default:
1743       // TODO: Salvage constants from each kind of binop we know about.
1744       return nullptr;
1745     }
1746     // *Not* to do: we should not attempt to salvage load instructions,
1747     // because the validity and lifetime of a dbg.value containing
1748     // DW_OP_deref becomes difficult to analyze. See PR40628 for examples.
1749   }
1750   return nullptr;
1751 }
1752 
1753 /// A replacement for a dbg.value expression.
1754 using DbgValReplacement = Optional<DIExpression *>;
1755 
1756 /// Point debug users of \p From to \p To using exprs given by \p RewriteExpr,
1757 /// possibly moving/undefing users to prevent use-before-def. Returns true if
1758 /// changes are made.
rewriteDebugUsers(Instruction & From,Value & To,Instruction & DomPoint,DominatorTree & DT,function_ref<DbgValReplacement (DbgVariableIntrinsic & DII)> RewriteExpr)1759 static bool rewriteDebugUsers(
1760     Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT,
1761     function_ref<DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr) {
1762   // Find debug users of From.
1763   SmallVector<DbgVariableIntrinsic *, 1> Users;
1764   findDbgUsers(Users, &From);
1765   if (Users.empty())
1766     return false;
1767 
1768   // Prevent use-before-def of To.
1769   bool Changed = false;
1770   SmallPtrSet<DbgVariableIntrinsic *, 1> UndefOrSalvage;
1771   if (isa<Instruction>(&To)) {
1772     bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint;
1773 
1774     for (auto *DII : Users) {
1775       // It's common to see a debug user between From and DomPoint. Move it
1776       // after DomPoint to preserve the variable update without any reordering.
1777       if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) {
1778         LLVM_DEBUG(dbgs() << "MOVE:  " << *DII << '\n');
1779         DII->moveAfter(&DomPoint);
1780         Changed = true;
1781 
1782       // Users which otherwise aren't dominated by the replacement value must
1783       // be salvaged or deleted.
1784       } else if (!DT.dominates(&DomPoint, DII)) {
1785         UndefOrSalvage.insert(DII);
1786       }
1787     }
1788   }
1789 
1790   // Update debug users without use-before-def risk.
1791   for (auto *DII : Users) {
1792     if (UndefOrSalvage.count(DII))
1793       continue;
1794 
1795     LLVMContext &Ctx = DII->getContext();
1796     DbgValReplacement DVR = RewriteExpr(*DII);
1797     if (!DVR)
1798       continue;
1799 
1800     DII->setOperand(0, wrapValueInMetadata(Ctx, &To));
1801     DII->setOperand(2, MetadataAsValue::get(Ctx, *DVR));
1802     LLVM_DEBUG(dbgs() << "REWRITE:  " << *DII << '\n');
1803     Changed = true;
1804   }
1805 
1806   if (!UndefOrSalvage.empty()) {
1807     // Try to salvage the remaining debug users.
1808     salvageDebugInfoOrMarkUndef(From);
1809     Changed = true;
1810   }
1811 
1812   return Changed;
1813 }
1814 
1815 /// Check if a bitcast between a value of type \p FromTy to type \p ToTy would
1816 /// losslessly preserve the bits and semantics of the value. This predicate is
1817 /// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result.
1818 ///
1819 /// Note that Type::canLosslesslyBitCastTo is not suitable here because it
1820 /// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>,
1821 /// and also does not allow lossless pointer <-> integer conversions.
isBitCastSemanticsPreserving(const DataLayout & DL,Type * FromTy,Type * ToTy)1822 static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy,
1823                                          Type *ToTy) {
1824   // Trivially compatible types.
1825   if (FromTy == ToTy)
1826     return true;
1827 
1828   // Handle compatible pointer <-> integer conversions.
1829   if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) {
1830     bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy);
1831     bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) &&
1832                               !DL.isNonIntegralPointerType(ToTy);
1833     return SameSize && LosslessConversion;
1834   }
1835 
1836   // TODO: This is not exhaustive.
1837   return false;
1838 }
1839 
replaceAllDbgUsesWith(Instruction & From,Value & To,Instruction & DomPoint,DominatorTree & DT)1840 bool llvm::replaceAllDbgUsesWith(Instruction &From, Value &To,
1841                                  Instruction &DomPoint, DominatorTree &DT) {
1842   // Exit early if From has no debug users.
1843   if (!From.isUsedByMetadata())
1844     return false;
1845 
1846   assert(&From != &To && "Can't replace something with itself");
1847 
1848   Type *FromTy = From.getType();
1849   Type *ToTy = To.getType();
1850 
1851   auto Identity = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
1852     return DII.getExpression();
1853   };
1854 
1855   // Handle no-op conversions.
1856   Module &M = *From.getModule();
1857   const DataLayout &DL = M.getDataLayout();
1858   if (isBitCastSemanticsPreserving(DL, FromTy, ToTy))
1859     return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
1860 
1861   // Handle integer-to-integer widening and narrowing.
1862   // FIXME: Use DW_OP_convert when it's available everywhere.
1863   if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) {
1864     uint64_t FromBits = FromTy->getPrimitiveSizeInBits();
1865     uint64_t ToBits = ToTy->getPrimitiveSizeInBits();
1866     assert(FromBits != ToBits && "Unexpected no-op conversion");
1867 
1868     // When the width of the result grows, assume that a debugger will only
1869     // access the low `FromBits` bits when inspecting the source variable.
1870     if (FromBits < ToBits)
1871       return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
1872 
1873     // The width of the result has shrunk. Use sign/zero extension to describe
1874     // the source variable's high bits.
1875     auto SignOrZeroExt = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
1876       DILocalVariable *Var = DII.getVariable();
1877 
1878       // Without knowing signedness, sign/zero extension isn't possible.
1879       auto Signedness = Var->getSignedness();
1880       if (!Signedness)
1881         return None;
1882 
1883       bool Signed = *Signedness == DIBasicType::Signedness::Signed;
1884       return DIExpression::appendExt(DII.getExpression(), ToBits, FromBits,
1885                                      Signed);
1886     };
1887     return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt);
1888   }
1889 
1890   // TODO: Floating-point conversions, vectors.
1891   return false;
1892 }
1893 
removeAllNonTerminatorAndEHPadInstructions(BasicBlock * BB)1894 unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) {
1895   unsigned NumDeadInst = 0;
1896   // Delete the instructions backwards, as it has a reduced likelihood of
1897   // having to update as many def-use and use-def chains.
1898   Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
1899   while (EndInst != &BB->front()) {
1900     // Delete the next to last instruction.
1901     Instruction *Inst = &*--EndInst->getIterator();
1902     if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
1903       Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
1904     if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
1905       EndInst = Inst;
1906       continue;
1907     }
1908     if (!isa<DbgInfoIntrinsic>(Inst))
1909       ++NumDeadInst;
1910     Inst->eraseFromParent();
1911   }
1912   return NumDeadInst;
1913 }
1914 
changeToUnreachable(Instruction * I,bool UseLLVMTrap,bool PreserveLCSSA,DomTreeUpdater * DTU,MemorySSAUpdater * MSSAU)1915 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
1916                                    bool PreserveLCSSA, DomTreeUpdater *DTU,
1917                                    MemorySSAUpdater *MSSAU) {
1918   BasicBlock *BB = I->getParent();
1919   std::vector <DominatorTree::UpdateType> Updates;
1920 
1921   if (MSSAU)
1922     MSSAU->changeToUnreachable(I);
1923 
1924   // Loop over all of the successors, removing BB's entry from any PHI
1925   // nodes.
1926   if (DTU)
1927     Updates.reserve(BB->getTerminator()->getNumSuccessors());
1928   for (BasicBlock *Successor : successors(BB)) {
1929     Successor->removePredecessor(BB, PreserveLCSSA);
1930     if (DTU)
1931       Updates.push_back({DominatorTree::Delete, BB, Successor});
1932   }
1933   // Insert a call to llvm.trap right before this.  This turns the undefined
1934   // behavior into a hard fail instead of falling through into random code.
1935   if (UseLLVMTrap) {
1936     Function *TrapFn =
1937       Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
1938     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
1939     CallTrap->setDebugLoc(I->getDebugLoc());
1940   }
1941   auto *UI = new UnreachableInst(I->getContext(), I);
1942   UI->setDebugLoc(I->getDebugLoc());
1943 
1944   // All instructions after this are dead.
1945   unsigned NumInstrsRemoved = 0;
1946   BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
1947   while (BBI != BBE) {
1948     if (!BBI->use_empty())
1949       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
1950     BB->getInstList().erase(BBI++);
1951     ++NumInstrsRemoved;
1952   }
1953   if (DTU)
1954     DTU->applyUpdatesPermissive(Updates);
1955   return NumInstrsRemoved;
1956 }
1957 
createCallMatchingInvoke(InvokeInst * II)1958 CallInst *llvm::createCallMatchingInvoke(InvokeInst *II) {
1959   SmallVector<Value *, 8> Args(II->arg_begin(), II->arg_end());
1960   SmallVector<OperandBundleDef, 1> OpBundles;
1961   II->getOperandBundlesAsDefs(OpBundles);
1962   CallInst *NewCall = CallInst::Create(II->getFunctionType(),
1963                                        II->getCalledValue(), Args, OpBundles);
1964   NewCall->setCallingConv(II->getCallingConv());
1965   NewCall->setAttributes(II->getAttributes());
1966   NewCall->setDebugLoc(II->getDebugLoc());
1967   NewCall->copyMetadata(*II);
1968   return NewCall;
1969 }
1970 
1971 /// changeToCall - Convert the specified invoke into a normal call.
changeToCall(InvokeInst * II,DomTreeUpdater * DTU)1972 void llvm::changeToCall(InvokeInst *II, DomTreeUpdater *DTU) {
1973   CallInst *NewCall = createCallMatchingInvoke(II);
1974   NewCall->takeName(II);
1975   NewCall->insertBefore(II);
1976   II->replaceAllUsesWith(NewCall);
1977 
1978   // Follow the call by a branch to the normal destination.
1979   BasicBlock *NormalDestBB = II->getNormalDest();
1980   BranchInst::Create(NormalDestBB, II);
1981 
1982   // Update PHI nodes in the unwind destination
1983   BasicBlock *BB = II->getParent();
1984   BasicBlock *UnwindDestBB = II->getUnwindDest();
1985   UnwindDestBB->removePredecessor(BB);
1986   II->eraseFromParent();
1987   if (DTU)
1988     DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDestBB}});
1989 }
1990 
changeToInvokeAndSplitBasicBlock(CallInst * CI,BasicBlock * UnwindEdge)1991 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
1992                                                    BasicBlock *UnwindEdge) {
1993   BasicBlock *BB = CI->getParent();
1994 
1995   // Convert this function call into an invoke instruction.  First, split the
1996   // basic block.
1997   BasicBlock *Split =
1998       BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc");
1999 
2000   // Delete the unconditional branch inserted by splitBasicBlock
2001   BB->getInstList().pop_back();
2002 
2003   // Create the new invoke instruction.
2004   SmallVector<Value *, 8> InvokeArgs(CI->arg_begin(), CI->arg_end());
2005   SmallVector<OperandBundleDef, 1> OpBundles;
2006 
2007   CI->getOperandBundlesAsDefs(OpBundles);
2008 
2009   // Note: we're round tripping operand bundles through memory here, and that
2010   // can potentially be avoided with a cleverer API design that we do not have
2011   // as of this time.
2012 
2013   InvokeInst *II =
2014       InvokeInst::Create(CI->getFunctionType(), CI->getCalledValue(), Split,
2015                          UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB);
2016   II->setDebugLoc(CI->getDebugLoc());
2017   II->setCallingConv(CI->getCallingConv());
2018   II->setAttributes(CI->getAttributes());
2019 
2020   // Make sure that anything using the call now uses the invoke!  This also
2021   // updates the CallGraph if present, because it uses a WeakTrackingVH.
2022   CI->replaceAllUsesWith(II);
2023 
2024   // Delete the original call
2025   Split->getInstList().pop_front();
2026   return Split;
2027 }
2028 
markAliveBlocks(Function & F,SmallPtrSetImpl<BasicBlock * > & Reachable,DomTreeUpdater * DTU=nullptr)2029 static bool markAliveBlocks(Function &F,
2030                             SmallPtrSetImpl<BasicBlock *> &Reachable,
2031                             DomTreeUpdater *DTU = nullptr) {
2032   SmallVector<BasicBlock*, 128> Worklist;
2033   BasicBlock *BB = &F.front();
2034   Worklist.push_back(BB);
2035   Reachable.insert(BB);
2036   bool Changed = false;
2037   do {
2038     BB = Worklist.pop_back_val();
2039 
2040     // Do a quick scan of the basic block, turning any obviously unreachable
2041     // instructions into LLVM unreachable insts.  The instruction combining pass
2042     // canonicalizes unreachable insts into stores to null or undef.
2043     for (Instruction &I : *BB) {
2044       if (auto *CI = dyn_cast<CallInst>(&I)) {
2045         Value *Callee = CI->getCalledValue();
2046         // Handle intrinsic calls.
2047         if (Function *F = dyn_cast<Function>(Callee)) {
2048           auto IntrinsicID = F->getIntrinsicID();
2049           // Assumptions that are known to be false are equivalent to
2050           // unreachable. Also, if the condition is undefined, then we make the
2051           // choice most beneficial to the optimizer, and choose that to also be
2052           // unreachable.
2053           if (IntrinsicID == Intrinsic::assume) {
2054             if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
2055               // Don't insert a call to llvm.trap right before the unreachable.
2056               changeToUnreachable(CI, false, false, DTU);
2057               Changed = true;
2058               break;
2059             }
2060           } else if (IntrinsicID == Intrinsic::experimental_guard) {
2061             // A call to the guard intrinsic bails out of the current
2062             // compilation unit if the predicate passed to it is false. If the
2063             // predicate is a constant false, then we know the guard will bail
2064             // out of the current compile unconditionally, so all code following
2065             // it is dead.
2066             //
2067             // Note: unlike in llvm.assume, it is not "obviously profitable" for
2068             // guards to treat `undef` as `false` since a guard on `undef` can
2069             // still be useful for widening.
2070             if (match(CI->getArgOperand(0), m_Zero()))
2071               if (!isa<UnreachableInst>(CI->getNextNode())) {
2072                 changeToUnreachable(CI->getNextNode(), /*UseLLVMTrap=*/false,
2073                                     false, DTU);
2074                 Changed = true;
2075                 break;
2076               }
2077           }
2078         } else if ((isa<ConstantPointerNull>(Callee) &&
2079                     !NullPointerIsDefined(CI->getFunction())) ||
2080                    isa<UndefValue>(Callee)) {
2081           changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DTU);
2082           Changed = true;
2083           break;
2084         }
2085         if (CI->doesNotReturn() && !CI->isMustTailCall()) {
2086           // If we found a call to a no-return function, insert an unreachable
2087           // instruction after it.  Make sure there isn't *already* one there
2088           // though.
2089           if (!isa<UnreachableInst>(CI->getNextNode())) {
2090             // Don't insert a call to llvm.trap right before the unreachable.
2091             changeToUnreachable(CI->getNextNode(), false, false, DTU);
2092             Changed = true;
2093           }
2094           break;
2095         }
2096       } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
2097         // Store to undef and store to null are undefined and used to signal
2098         // that they should be changed to unreachable by passes that can't
2099         // modify the CFG.
2100 
2101         // Don't touch volatile stores.
2102         if (SI->isVolatile()) continue;
2103 
2104         Value *Ptr = SI->getOperand(1);
2105 
2106         if (isa<UndefValue>(Ptr) ||
2107             (isa<ConstantPointerNull>(Ptr) &&
2108              !NullPointerIsDefined(SI->getFunction(),
2109                                    SI->getPointerAddressSpace()))) {
2110           changeToUnreachable(SI, true, false, DTU);
2111           Changed = true;
2112           break;
2113         }
2114       }
2115     }
2116 
2117     Instruction *Terminator = BB->getTerminator();
2118     if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
2119       // Turn invokes that call 'nounwind' functions into ordinary calls.
2120       Value *Callee = II->getCalledValue();
2121       if ((isa<ConstantPointerNull>(Callee) &&
2122            !NullPointerIsDefined(BB->getParent())) ||
2123           isa<UndefValue>(Callee)) {
2124         changeToUnreachable(II, true, false, DTU);
2125         Changed = true;
2126       } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
2127         if (II->use_empty() && II->onlyReadsMemory()) {
2128           // jump to the normal destination branch.
2129           BasicBlock *NormalDestBB = II->getNormalDest();
2130           BasicBlock *UnwindDestBB = II->getUnwindDest();
2131           BranchInst::Create(NormalDestBB, II);
2132           UnwindDestBB->removePredecessor(II->getParent());
2133           II->eraseFromParent();
2134           if (DTU)
2135             DTU->applyUpdatesPermissive(
2136                 {{DominatorTree::Delete, BB, UnwindDestBB}});
2137         } else
2138           changeToCall(II, DTU);
2139         Changed = true;
2140       }
2141     } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
2142       // Remove catchpads which cannot be reached.
2143       struct CatchPadDenseMapInfo {
2144         static CatchPadInst *getEmptyKey() {
2145           return DenseMapInfo<CatchPadInst *>::getEmptyKey();
2146         }
2147 
2148         static CatchPadInst *getTombstoneKey() {
2149           return DenseMapInfo<CatchPadInst *>::getTombstoneKey();
2150         }
2151 
2152         static unsigned getHashValue(CatchPadInst *CatchPad) {
2153           return static_cast<unsigned>(hash_combine_range(
2154               CatchPad->value_op_begin(), CatchPad->value_op_end()));
2155         }
2156 
2157         static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
2158           if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
2159               RHS == getEmptyKey() || RHS == getTombstoneKey())
2160             return LHS == RHS;
2161           return LHS->isIdenticalTo(RHS);
2162         }
2163       };
2164 
2165       // Set of unique CatchPads.
2166       SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4,
2167                     CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
2168           HandlerSet;
2169       detail::DenseSetEmpty Empty;
2170       for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
2171                                              E = CatchSwitch->handler_end();
2172            I != E; ++I) {
2173         BasicBlock *HandlerBB = *I;
2174         auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
2175         if (!HandlerSet.insert({CatchPad, Empty}).second) {
2176           CatchSwitch->removeHandler(I);
2177           --I;
2178           --E;
2179           Changed = true;
2180         }
2181       }
2182     }
2183 
2184     Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
2185     for (BasicBlock *Successor : successors(BB))
2186       if (Reachable.insert(Successor).second)
2187         Worklist.push_back(Successor);
2188   } while (!Worklist.empty());
2189   return Changed;
2190 }
2191 
removeUnwindEdge(BasicBlock * BB,DomTreeUpdater * DTU)2192 void llvm::removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU) {
2193   Instruction *TI = BB->getTerminator();
2194 
2195   if (auto *II = dyn_cast<InvokeInst>(TI)) {
2196     changeToCall(II, DTU);
2197     return;
2198   }
2199 
2200   Instruction *NewTI;
2201   BasicBlock *UnwindDest;
2202 
2203   if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
2204     NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
2205     UnwindDest = CRI->getUnwindDest();
2206   } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
2207     auto *NewCatchSwitch = CatchSwitchInst::Create(
2208         CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
2209         CatchSwitch->getName(), CatchSwitch);
2210     for (BasicBlock *PadBB : CatchSwitch->handlers())
2211       NewCatchSwitch->addHandler(PadBB);
2212 
2213     NewTI = NewCatchSwitch;
2214     UnwindDest = CatchSwitch->getUnwindDest();
2215   } else {
2216     llvm_unreachable("Could not find unwind successor");
2217   }
2218 
2219   NewTI->takeName(TI);
2220   NewTI->setDebugLoc(TI->getDebugLoc());
2221   UnwindDest->removePredecessor(BB);
2222   TI->replaceAllUsesWith(NewTI);
2223   TI->eraseFromParent();
2224   if (DTU)
2225     DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDest}});
2226 }
2227 
2228 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
2229 /// if they are in a dead cycle.  Return true if a change was made, false
2230 /// otherwise.
removeUnreachableBlocks(Function & F,DomTreeUpdater * DTU,MemorySSAUpdater * MSSAU)2231 bool llvm::removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
2232                                    MemorySSAUpdater *MSSAU) {
2233   SmallPtrSet<BasicBlock *, 16> Reachable;
2234   bool Changed = markAliveBlocks(F, Reachable, DTU);
2235 
2236   // If there are unreachable blocks in the CFG...
2237   if (Reachable.size() == F.size())
2238     return Changed;
2239 
2240   assert(Reachable.size() < F.size());
2241   NumRemoved += F.size() - Reachable.size();
2242 
2243   SmallSetVector<BasicBlock *, 8> DeadBlockSet;
2244   for (BasicBlock &BB : F) {
2245     // Skip reachable basic blocks
2246     if (Reachable.find(&BB) != Reachable.end())
2247       continue;
2248     DeadBlockSet.insert(&BB);
2249   }
2250 
2251   if (MSSAU)
2252     MSSAU->removeBlocks(DeadBlockSet);
2253 
2254   // Loop over all of the basic blocks that are not reachable, dropping all of
2255   // their internal references. Update DTU if available.
2256   std::vector<DominatorTree::UpdateType> Updates;
2257   for (auto *BB : DeadBlockSet) {
2258     for (BasicBlock *Successor : successors(BB)) {
2259       if (!DeadBlockSet.count(Successor))
2260         Successor->removePredecessor(BB);
2261       if (DTU)
2262         Updates.push_back({DominatorTree::Delete, BB, Successor});
2263     }
2264     BB->dropAllReferences();
2265     if (DTU) {
2266       Instruction *TI = BB->getTerminator();
2267       assert(TI && "Basic block should have a terminator");
2268       // Terminators like invoke can have users. We have to replace their users,
2269       // before removing them.
2270       if (!TI->use_empty())
2271         TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
2272       TI->eraseFromParent();
2273       new UnreachableInst(BB->getContext(), BB);
2274       assert(succ_empty(BB) && "The successor list of BB isn't empty before "
2275                                "applying corresponding DTU updates.");
2276     }
2277   }
2278 
2279   if (DTU) {
2280     DTU->applyUpdatesPermissive(Updates);
2281     bool Deleted = false;
2282     for (auto *BB : DeadBlockSet) {
2283       if (DTU->isBBPendingDeletion(BB))
2284         --NumRemoved;
2285       else
2286         Deleted = true;
2287       DTU->deleteBB(BB);
2288     }
2289     if (!Deleted)
2290       return false;
2291   } else {
2292     for (auto *BB : DeadBlockSet)
2293       BB->eraseFromParent();
2294   }
2295 
2296   return true;
2297 }
2298 
combineMetadata(Instruction * K,const Instruction * J,ArrayRef<unsigned> KnownIDs,bool DoesKMove)2299 void llvm::combineMetadata(Instruction *K, const Instruction *J,
2300                            ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
2301   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
2302   K->dropUnknownNonDebugMetadata(KnownIDs);
2303   K->getAllMetadataOtherThanDebugLoc(Metadata);
2304   for (const auto &MD : Metadata) {
2305     unsigned Kind = MD.first;
2306     MDNode *JMD = J->getMetadata(Kind);
2307     MDNode *KMD = MD.second;
2308 
2309     switch (Kind) {
2310       default:
2311         K->setMetadata(Kind, nullptr); // Remove unknown metadata
2312         break;
2313       case LLVMContext::MD_dbg:
2314         llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
2315       case LLVMContext::MD_tbaa:
2316         K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
2317         break;
2318       case LLVMContext::MD_alias_scope:
2319         K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
2320         break;
2321       case LLVMContext::MD_noalias:
2322       case LLVMContext::MD_mem_parallel_loop_access:
2323         K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
2324         break;
2325       case LLVMContext::MD_access_group:
2326         K->setMetadata(LLVMContext::MD_access_group,
2327                        intersectAccessGroups(K, J));
2328         break;
2329       case LLVMContext::MD_range:
2330 
2331         // If K does move, use most generic range. Otherwise keep the range of
2332         // K.
2333         if (DoesKMove)
2334           // FIXME: If K does move, we should drop the range info and nonnull.
2335           //        Currently this function is used with DoesKMove in passes
2336           //        doing hoisting/sinking and the current behavior of using the
2337           //        most generic range is correct in those cases.
2338           K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
2339         break;
2340       case LLVMContext::MD_fpmath:
2341         K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
2342         break;
2343       case LLVMContext::MD_invariant_load:
2344         // Only set the !invariant.load if it is present in both instructions.
2345         K->setMetadata(Kind, JMD);
2346         break;
2347       case LLVMContext::MD_nonnull:
2348         // If K does move, keep nonull if it is present in both instructions.
2349         if (DoesKMove)
2350           K->setMetadata(Kind, JMD);
2351         break;
2352       case LLVMContext::MD_invariant_group:
2353         // Preserve !invariant.group in K.
2354         break;
2355       case LLVMContext::MD_align:
2356         K->setMetadata(Kind,
2357           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
2358         break;
2359       case LLVMContext::MD_dereferenceable:
2360       case LLVMContext::MD_dereferenceable_or_null:
2361         K->setMetadata(Kind,
2362           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
2363         break;
2364       case LLVMContext::MD_preserve_access_index:
2365         // Preserve !preserve.access.index in K.
2366         break;
2367     }
2368   }
2369   // Set !invariant.group from J if J has it. If both instructions have it
2370   // then we will just pick it from J - even when they are different.
2371   // Also make sure that K is load or store - f.e. combining bitcast with load
2372   // could produce bitcast with invariant.group metadata, which is invalid.
2373   // FIXME: we should try to preserve both invariant.group md if they are
2374   // different, but right now instruction can only have one invariant.group.
2375   if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2376     if (isa<LoadInst>(K) || isa<StoreInst>(K))
2377       K->setMetadata(LLVMContext::MD_invariant_group, JMD);
2378 }
2379 
combineMetadataForCSE(Instruction * K,const Instruction * J,bool KDominatesJ)2380 void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J,
2381                                  bool KDominatesJ) {
2382   unsigned KnownIDs[] = {
2383       LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
2384       LLVMContext::MD_noalias,         LLVMContext::MD_range,
2385       LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
2386       LLVMContext::MD_invariant_group, LLVMContext::MD_align,
2387       LLVMContext::MD_dereferenceable,
2388       LLVMContext::MD_dereferenceable_or_null,
2389       LLVMContext::MD_access_group,    LLVMContext::MD_preserve_access_index};
2390   combineMetadata(K, J, KnownIDs, KDominatesJ);
2391 }
2392 
copyMetadataForLoad(LoadInst & Dest,const LoadInst & Source)2393 void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) {
2394   SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
2395   Source.getAllMetadata(MD);
2396   MDBuilder MDB(Dest.getContext());
2397   Type *NewType = Dest.getType();
2398   const DataLayout &DL = Source.getModule()->getDataLayout();
2399   for (const auto &MDPair : MD) {
2400     unsigned ID = MDPair.first;
2401     MDNode *N = MDPair.second;
2402     // Note, essentially every kind of metadata should be preserved here! This
2403     // routine is supposed to clone a load instruction changing *only its type*.
2404     // The only metadata it makes sense to drop is metadata which is invalidated
2405     // when the pointer type changes. This should essentially never be the case
2406     // in LLVM, but we explicitly switch over only known metadata to be
2407     // conservatively correct. If you are adding metadata to LLVM which pertains
2408     // to loads, you almost certainly want to add it here.
2409     switch (ID) {
2410     case LLVMContext::MD_dbg:
2411     case LLVMContext::MD_tbaa:
2412     case LLVMContext::MD_prof:
2413     case LLVMContext::MD_fpmath:
2414     case LLVMContext::MD_tbaa_struct:
2415     case LLVMContext::MD_invariant_load:
2416     case LLVMContext::MD_alias_scope:
2417     case LLVMContext::MD_noalias:
2418     case LLVMContext::MD_nontemporal:
2419     case LLVMContext::MD_mem_parallel_loop_access:
2420     case LLVMContext::MD_access_group:
2421       // All of these directly apply.
2422       Dest.setMetadata(ID, N);
2423       break;
2424 
2425     case LLVMContext::MD_nonnull:
2426       copyNonnullMetadata(Source, N, Dest);
2427       break;
2428 
2429     case LLVMContext::MD_align:
2430     case LLVMContext::MD_dereferenceable:
2431     case LLVMContext::MD_dereferenceable_or_null:
2432       // These only directly apply if the new type is also a pointer.
2433       if (NewType->isPointerTy())
2434         Dest.setMetadata(ID, N);
2435       break;
2436 
2437     case LLVMContext::MD_range:
2438       copyRangeMetadata(DL, Source, N, Dest);
2439       break;
2440     }
2441   }
2442 }
2443 
patchReplacementInstruction(Instruction * I,Value * Repl)2444 void llvm::patchReplacementInstruction(Instruction *I, Value *Repl) {
2445   auto *ReplInst = dyn_cast<Instruction>(Repl);
2446   if (!ReplInst)
2447     return;
2448 
2449   // Patch the replacement so that it is not more restrictive than the value
2450   // being replaced.
2451   // Note that if 'I' is a load being replaced by some operation,
2452   // for example, by an arithmetic operation, then andIRFlags()
2453   // would just erase all math flags from the original arithmetic
2454   // operation, which is clearly not wanted and not needed.
2455   if (!isa<LoadInst>(I))
2456     ReplInst->andIRFlags(I);
2457 
2458   // FIXME: If both the original and replacement value are part of the
2459   // same control-flow region (meaning that the execution of one
2460   // guarantees the execution of the other), then we can combine the
2461   // noalias scopes here and do better than the general conservative
2462   // answer used in combineMetadata().
2463 
2464   // In general, GVN unifies expressions over different control-flow
2465   // regions, and so we need a conservative combination of the noalias
2466   // scopes.
2467   static const unsigned KnownIDs[] = {
2468       LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
2469       LLVMContext::MD_noalias,         LLVMContext::MD_range,
2470       LLVMContext::MD_fpmath,          LLVMContext::MD_invariant_load,
2471       LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull,
2472       LLVMContext::MD_access_group,    LLVMContext::MD_preserve_access_index};
2473   combineMetadata(ReplInst, I, KnownIDs, false);
2474 }
2475 
2476 template <typename RootType, typename DominatesFn>
replaceDominatedUsesWith(Value * From,Value * To,const RootType & Root,const DominatesFn & Dominates)2477 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
2478                                          const RootType &Root,
2479                                          const DominatesFn &Dominates) {
2480   assert(From->getType() == To->getType());
2481 
2482   unsigned Count = 0;
2483   for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2484        UI != UE;) {
2485     Use &U = *UI++;
2486     if (!Dominates(Root, U))
2487       continue;
2488     U.set(To);
2489     LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()
2490                       << "' as " << *To << " in " << *U << "\n");
2491     ++Count;
2492   }
2493   return Count;
2494 }
2495 
replaceNonLocalUsesWith(Instruction * From,Value * To)2496 unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) {
2497    assert(From->getType() == To->getType());
2498    auto *BB = From->getParent();
2499    unsigned Count = 0;
2500 
2501   for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2502        UI != UE;) {
2503     Use &U = *UI++;
2504     auto *I = cast<Instruction>(U.getUser());
2505     if (I->getParent() == BB)
2506       continue;
2507     U.set(To);
2508     ++Count;
2509   }
2510   return Count;
2511 }
2512 
replaceDominatedUsesWith(Value * From,Value * To,DominatorTree & DT,const BasicBlockEdge & Root)2513 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
2514                                         DominatorTree &DT,
2515                                         const BasicBlockEdge &Root) {
2516   auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2517     return DT.dominates(Root, U);
2518   };
2519   return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2520 }
2521 
replaceDominatedUsesWith(Value * From,Value * To,DominatorTree & DT,const BasicBlock * BB)2522 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
2523                                         DominatorTree &DT,
2524                                         const BasicBlock *BB) {
2525   auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
2526     auto *I = cast<Instruction>(U.getUser())->getParent();
2527     return DT.properlyDominates(BB, I);
2528   };
2529   return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
2530 }
2531 
callsGCLeafFunction(const CallBase * Call,const TargetLibraryInfo & TLI)2532 bool llvm::callsGCLeafFunction(const CallBase *Call,
2533                                const TargetLibraryInfo &TLI) {
2534   // Check if the function is specifically marked as a gc leaf function.
2535   if (Call->hasFnAttr("gc-leaf-function"))
2536     return true;
2537   if (const Function *F = Call->getCalledFunction()) {
2538     if (F->hasFnAttribute("gc-leaf-function"))
2539       return true;
2540 
2541     if (auto IID = F->getIntrinsicID())
2542       // Most LLVM intrinsics do not take safepoints.
2543       return IID != Intrinsic::experimental_gc_statepoint &&
2544              IID != Intrinsic::experimental_deoptimize;
2545   }
2546 
2547   // Lib calls can be materialized by some passes, and won't be
2548   // marked as 'gc-leaf-function.' All available Libcalls are
2549   // GC-leaf.
2550   LibFunc LF;
2551   if (TLI.getLibFunc(ImmutableCallSite(Call), LF)) {
2552     return TLI.has(LF);
2553   }
2554 
2555   return false;
2556 }
2557 
copyNonnullMetadata(const LoadInst & OldLI,MDNode * N,LoadInst & NewLI)2558 void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N,
2559                                LoadInst &NewLI) {
2560   auto *NewTy = NewLI.getType();
2561 
2562   // This only directly applies if the new type is also a pointer.
2563   if (NewTy->isPointerTy()) {
2564     NewLI.setMetadata(LLVMContext::MD_nonnull, N);
2565     return;
2566   }
2567 
2568   // The only other translation we can do is to integral loads with !range
2569   // metadata.
2570   if (!NewTy->isIntegerTy())
2571     return;
2572 
2573   MDBuilder MDB(NewLI.getContext());
2574   const Value *Ptr = OldLI.getPointerOperand();
2575   auto *ITy = cast<IntegerType>(NewTy);
2576   auto *NullInt = ConstantExpr::getPtrToInt(
2577       ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
2578   auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
2579   NewLI.setMetadata(LLVMContext::MD_range,
2580                     MDB.createRange(NonNullInt, NullInt));
2581 }
2582 
copyRangeMetadata(const DataLayout & DL,const LoadInst & OldLI,MDNode * N,LoadInst & NewLI)2583 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
2584                              MDNode *N, LoadInst &NewLI) {
2585   auto *NewTy = NewLI.getType();
2586 
2587   // Give up unless it is converted to a pointer where there is a single very
2588   // valuable mapping we can do reliably.
2589   // FIXME: It would be nice to propagate this in more ways, but the type
2590   // conversions make it hard.
2591   if (!NewTy->isPointerTy())
2592     return;
2593 
2594   unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
2595   if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
2596     MDNode *NN = MDNode::get(OldLI.getContext(), None);
2597     NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
2598   }
2599 }
2600 
dropDebugUsers(Instruction & I)2601 void llvm::dropDebugUsers(Instruction &I) {
2602   SmallVector<DbgVariableIntrinsic *, 1> DbgUsers;
2603   findDbgUsers(DbgUsers, &I);
2604   for (auto *DII : DbgUsers)
2605     DII->eraseFromParent();
2606 }
2607 
hoistAllInstructionsInto(BasicBlock * DomBlock,Instruction * InsertPt,BasicBlock * BB)2608 void llvm::hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt,
2609                                     BasicBlock *BB) {
2610   // Since we are moving the instructions out of its basic block, we do not
2611   // retain their original debug locations (DILocations) and debug intrinsic
2612   // instructions.
2613   //
2614   // Doing so would degrade the debugging experience and adversely affect the
2615   // accuracy of profiling information.
2616   //
2617   // Currently, when hoisting the instructions, we take the following actions:
2618   // - Remove their debug intrinsic instructions.
2619   // - Set their debug locations to the values from the insertion point.
2620   //
2621   // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
2622   // need to be deleted, is because there will not be any instructions with a
2623   // DILocation in either branch left after performing the transformation. We
2624   // can only insert a dbg.value after the two branches are joined again.
2625   //
2626   // See PR38762, PR39243 for more details.
2627   //
2628   // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
2629   // encode predicated DIExpressions that yield different results on different
2630   // code paths.
2631   for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
2632     Instruction *I = &*II;
2633     I->dropUnknownNonDebugMetadata();
2634     if (I->isUsedByMetadata())
2635       dropDebugUsers(*I);
2636     if (isa<DbgInfoIntrinsic>(I)) {
2637       // Remove DbgInfo Intrinsics.
2638       II = I->eraseFromParent();
2639       continue;
2640     }
2641     I->setDebugLoc(InsertPt->getDebugLoc());
2642     ++II;
2643   }
2644   DomBlock->getInstList().splice(InsertPt->getIterator(), BB->getInstList(),
2645                                  BB->begin(),
2646                                  BB->getTerminator()->getIterator());
2647 }
2648 
2649 namespace {
2650 
2651 /// A potential constituent of a bitreverse or bswap expression. See
2652 /// collectBitParts for a fuller explanation.
2653 struct BitPart {
BitPart__anonf947a8e20a11::BitPart2654   BitPart(Value *P, unsigned BW) : Provider(P) {
2655     Provenance.resize(BW);
2656   }
2657 
2658   /// The Value that this is a bitreverse/bswap of.
2659   Value *Provider;
2660 
2661   /// The "provenance" of each bit. Provenance[A] = B means that bit A
2662   /// in Provider becomes bit B in the result of this expression.
2663   SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
2664 
2665   enum { Unset = -1 };
2666 };
2667 
2668 } // end anonymous namespace
2669 
2670 /// Analyze the specified subexpression and see if it is capable of providing
2671 /// pieces of a bswap or bitreverse. The subexpression provides a potential
2672 /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in
2673 /// the output of the expression came from a corresponding bit in some other
2674 /// value. This function is recursive, and the end result is a mapping of
2675 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
2676 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
2677 ///
2678 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
2679 /// that the expression deposits the low byte of %X into the high byte of the
2680 /// result and that all other bits are zero. This expression is accepted and a
2681 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
2682 /// [0-7].
2683 ///
2684 /// To avoid revisiting values, the BitPart results are memoized into the
2685 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
2686 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
2687 /// store BitParts objects, not pointers. As we need the concept of a nullptr
2688 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
2689 /// type instead to provide the same functionality.
2690 ///
2691 /// Because we pass around references into \c BPS, we must use a container that
2692 /// does not invalidate internal references (std::map instead of DenseMap).
2693 static const Optional<BitPart> &
collectBitParts(Value * V,bool MatchBSwaps,bool MatchBitReversals,std::map<Value *,Optional<BitPart>> & BPS,int Depth)2694 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
2695                 std::map<Value *, Optional<BitPart>> &BPS, int Depth) {
2696   auto I = BPS.find(V);
2697   if (I != BPS.end())
2698     return I->second;
2699 
2700   auto &Result = BPS[V] = None;
2701   auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
2702 
2703   // Prevent stack overflow by limiting the recursion depth
2704   if (Depth == BitPartRecursionMaxDepth) {
2705     LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n");
2706     return Result;
2707   }
2708 
2709   if (Instruction *I = dyn_cast<Instruction>(V)) {
2710     // If this is an or instruction, it may be an inner node of the bswap.
2711     if (I->getOpcode() == Instruction::Or) {
2712       auto &A = collectBitParts(I->getOperand(0), MatchBSwaps,
2713                                 MatchBitReversals, BPS, Depth + 1);
2714       auto &B = collectBitParts(I->getOperand(1), MatchBSwaps,
2715                                 MatchBitReversals, BPS, Depth + 1);
2716       if (!A || !B)
2717         return Result;
2718 
2719       // Try and merge the two together.
2720       if (!A->Provider || A->Provider != B->Provider)
2721         return Result;
2722 
2723       Result = BitPart(A->Provider, BitWidth);
2724       for (unsigned i = 0; i < A->Provenance.size(); ++i) {
2725         if (A->Provenance[i] != BitPart::Unset &&
2726             B->Provenance[i] != BitPart::Unset &&
2727             A->Provenance[i] != B->Provenance[i])
2728           return Result = None;
2729 
2730         if (A->Provenance[i] == BitPart::Unset)
2731           Result->Provenance[i] = B->Provenance[i];
2732         else
2733           Result->Provenance[i] = A->Provenance[i];
2734       }
2735 
2736       return Result;
2737     }
2738 
2739     // If this is a logical shift by a constant, recurse then shift the result.
2740     if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
2741       unsigned BitShift =
2742           cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
2743       // Ensure the shift amount is defined.
2744       if (BitShift > BitWidth)
2745         return Result;
2746 
2747       auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2748                                   MatchBitReversals, BPS, Depth + 1);
2749       if (!Res)
2750         return Result;
2751       Result = Res;
2752 
2753       // Perform the "shift" on BitProvenance.
2754       auto &P = Result->Provenance;
2755       if (I->getOpcode() == Instruction::Shl) {
2756         P.erase(std::prev(P.end(), BitShift), P.end());
2757         P.insert(P.begin(), BitShift, BitPart::Unset);
2758       } else {
2759         P.erase(P.begin(), std::next(P.begin(), BitShift));
2760         P.insert(P.end(), BitShift, BitPart::Unset);
2761       }
2762 
2763       return Result;
2764     }
2765 
2766     // If this is a logical 'and' with a mask that clears bits, recurse then
2767     // unset the appropriate bits.
2768     if (I->getOpcode() == Instruction::And &&
2769         isa<ConstantInt>(I->getOperand(1))) {
2770       APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1);
2771       const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
2772 
2773       // Check that the mask allows a multiple of 8 bits for a bswap, for an
2774       // early exit.
2775       unsigned NumMaskedBits = AndMask.countPopulation();
2776       if (!MatchBitReversals && NumMaskedBits % 8 != 0)
2777         return Result;
2778 
2779       auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2780                                   MatchBitReversals, BPS, Depth + 1);
2781       if (!Res)
2782         return Result;
2783       Result = Res;
2784 
2785       for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1)
2786         // If the AndMask is zero for this bit, clear the bit.
2787         if ((AndMask & Bit) == 0)
2788           Result->Provenance[i] = BitPart::Unset;
2789       return Result;
2790     }
2791 
2792     // If this is a zext instruction zero extend the result.
2793     if (I->getOpcode() == Instruction::ZExt) {
2794       auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2795                                   MatchBitReversals, BPS, Depth + 1);
2796       if (!Res)
2797         return Result;
2798 
2799       Result = BitPart(Res->Provider, BitWidth);
2800       auto NarrowBitWidth =
2801           cast<IntegerType>(cast<ZExtInst>(I)->getSrcTy())->getBitWidth();
2802       for (unsigned i = 0; i < NarrowBitWidth; ++i)
2803         Result->Provenance[i] = Res->Provenance[i];
2804       for (unsigned i = NarrowBitWidth; i < BitWidth; ++i)
2805         Result->Provenance[i] = BitPart::Unset;
2806       return Result;
2807     }
2808   }
2809 
2810   // Okay, we got to something that isn't a shift, 'or' or 'and'.  This must be
2811   // the input value to the bswap/bitreverse.
2812   Result = BitPart(V, BitWidth);
2813   for (unsigned i = 0; i < BitWidth; ++i)
2814     Result->Provenance[i] = i;
2815   return Result;
2816 }
2817 
bitTransformIsCorrectForBSwap(unsigned From,unsigned To,unsigned BitWidth)2818 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
2819                                           unsigned BitWidth) {
2820   if (From % 8 != To % 8)
2821     return false;
2822   // Convert from bit indices to byte indices and check for a byte reversal.
2823   From >>= 3;
2824   To >>= 3;
2825   BitWidth >>= 3;
2826   return From == BitWidth - To - 1;
2827 }
2828 
bitTransformIsCorrectForBitReverse(unsigned From,unsigned To,unsigned BitWidth)2829 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
2830                                                unsigned BitWidth) {
2831   return From == BitWidth - To - 1;
2832 }
2833 
recognizeBSwapOrBitReverseIdiom(Instruction * I,bool MatchBSwaps,bool MatchBitReversals,SmallVectorImpl<Instruction * > & InsertedInsts)2834 bool llvm::recognizeBSwapOrBitReverseIdiom(
2835     Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
2836     SmallVectorImpl<Instruction *> &InsertedInsts) {
2837   if (Operator::getOpcode(I) != Instruction::Or)
2838     return false;
2839   if (!MatchBSwaps && !MatchBitReversals)
2840     return false;
2841   IntegerType *ITy = dyn_cast<IntegerType>(I->getType());
2842   if (!ITy || ITy->getBitWidth() > 128)
2843     return false;   // Can't do vectors or integers > 128 bits.
2844   unsigned BW = ITy->getBitWidth();
2845 
2846   unsigned DemandedBW = BW;
2847   IntegerType *DemandedTy = ITy;
2848   if (I->hasOneUse()) {
2849     if (TruncInst *Trunc = dyn_cast<TruncInst>(I->user_back())) {
2850       DemandedTy = cast<IntegerType>(Trunc->getType());
2851       DemandedBW = DemandedTy->getBitWidth();
2852     }
2853   }
2854 
2855   // Try to find all the pieces corresponding to the bswap.
2856   std::map<Value *, Optional<BitPart>> BPS;
2857   auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0);
2858   if (!Res)
2859     return false;
2860   auto &BitProvenance = Res->Provenance;
2861 
2862   // Now, is the bit permutation correct for a bswap or a bitreverse? We can
2863   // only byteswap values with an even number of bytes.
2864   bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true;
2865   for (unsigned i = 0; i < DemandedBW; ++i) {
2866     OKForBSwap &=
2867         bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW);
2868     OKForBitReverse &=
2869         bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW);
2870   }
2871 
2872   Intrinsic::ID Intrin;
2873   if (OKForBSwap && MatchBSwaps)
2874     Intrin = Intrinsic::bswap;
2875   else if (OKForBitReverse && MatchBitReversals)
2876     Intrin = Intrinsic::bitreverse;
2877   else
2878     return false;
2879 
2880   if (ITy != DemandedTy) {
2881     Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
2882     Value *Provider = Res->Provider;
2883     IntegerType *ProviderTy = cast<IntegerType>(Provider->getType());
2884     // We may need to truncate the provider.
2885     if (DemandedTy != ProviderTy) {
2886       auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy,
2887                                      "trunc", I);
2888       InsertedInsts.push_back(Trunc);
2889       Provider = Trunc;
2890     }
2891     auto *CI = CallInst::Create(F, Provider, "rev", I);
2892     InsertedInsts.push_back(CI);
2893     auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I);
2894     InsertedInsts.push_back(ExtInst);
2895     return true;
2896   }
2897 
2898   Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy);
2899   InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I));
2900   return true;
2901 }
2902 
2903 // CodeGen has special handling for some string functions that may replace
2904 // them with target-specific intrinsics.  Since that'd skip our interceptors
2905 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
2906 // we mark affected calls as NoBuiltin, which will disable optimization
2907 // in CodeGen.
maybeMarkSanitizerLibraryCallNoBuiltin(CallInst * CI,const TargetLibraryInfo * TLI)2908 void llvm::maybeMarkSanitizerLibraryCallNoBuiltin(
2909     CallInst *CI, const TargetLibraryInfo *TLI) {
2910   Function *F = CI->getCalledFunction();
2911   LibFunc Func;
2912   if (F && !F->hasLocalLinkage() && F->hasName() &&
2913       TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
2914       !F->doesNotAccessMemory())
2915     CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin);
2916 }
2917 
canReplaceOperandWithVariable(const Instruction * I,unsigned OpIdx)2918 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
2919   // We can't have a PHI with a metadata type.
2920   if (I->getOperand(OpIdx)->getType()->isMetadataTy())
2921     return false;
2922 
2923   // Early exit.
2924   if (!isa<Constant>(I->getOperand(OpIdx)))
2925     return true;
2926 
2927   switch (I->getOpcode()) {
2928   default:
2929     return true;
2930   case Instruction::Call:
2931   case Instruction::Invoke:
2932     // Can't handle inline asm. Skip it.
2933     if (isa<InlineAsm>(ImmutableCallSite(I).getCalledValue()))
2934       return false;
2935     // Many arithmetic intrinsics have no issue taking a
2936     // variable, however it's hard to distingish these from
2937     // specials such as @llvm.frameaddress that require a constant.
2938     if (isa<IntrinsicInst>(I))
2939       return false;
2940 
2941     // Constant bundle operands may need to retain their constant-ness for
2942     // correctness.
2943     if (ImmutableCallSite(I).isBundleOperand(OpIdx))
2944       return false;
2945     return true;
2946   case Instruction::ShuffleVector:
2947     // Shufflevector masks are constant.
2948     return OpIdx != 2;
2949   case Instruction::Switch:
2950   case Instruction::ExtractValue:
2951     // All operands apart from the first are constant.
2952     return OpIdx == 0;
2953   case Instruction::InsertValue:
2954     // All operands apart from the first and the second are constant.
2955     return OpIdx < 2;
2956   case Instruction::Alloca:
2957     // Static allocas (constant size in the entry block) are handled by
2958     // prologue/epilogue insertion so they're free anyway. We definitely don't
2959     // want to make them non-constant.
2960     return !cast<AllocaInst>(I)->isStaticAlloca();
2961   case Instruction::GetElementPtr:
2962     if (OpIdx == 0)
2963       return true;
2964     gep_type_iterator It = gep_type_begin(I);
2965     for (auto E = std::next(It, OpIdx); It != E; ++It)
2966       if (It.isStruct())
2967         return false;
2968     return true;
2969   }
2970 }
2971 
2972 using AllocaForValueMapTy = DenseMap<Value *, AllocaInst *>;
findAllocaForValue(Value * V,AllocaForValueMapTy & AllocaForValue)2973 AllocaInst *llvm::findAllocaForValue(Value *V,
2974                                      AllocaForValueMapTy &AllocaForValue) {
2975   if (AllocaInst *AI = dyn_cast<AllocaInst>(V))
2976     return AI;
2977   // See if we've already calculated (or started to calculate) alloca for a
2978   // given value.
2979   AllocaForValueMapTy::iterator I = AllocaForValue.find(V);
2980   if (I != AllocaForValue.end())
2981     return I->second;
2982   // Store 0 while we're calculating alloca for value V to avoid
2983   // infinite recursion if the value references itself.
2984   AllocaForValue[V] = nullptr;
2985   AllocaInst *Res = nullptr;
2986   if (CastInst *CI = dyn_cast<CastInst>(V))
2987     Res = findAllocaForValue(CI->getOperand(0), AllocaForValue);
2988   else if (PHINode *PN = dyn_cast<PHINode>(V)) {
2989     for (Value *IncValue : PN->incoming_values()) {
2990       // Allow self-referencing phi-nodes.
2991       if (IncValue == PN)
2992         continue;
2993       AllocaInst *IncValueAI = findAllocaForValue(IncValue, AllocaForValue);
2994       // AI for incoming values should exist and should all be equal.
2995       if (IncValueAI == nullptr || (Res != nullptr && IncValueAI != Res))
2996         return nullptr;
2997       Res = IncValueAI;
2998     }
2999   } else if (GetElementPtrInst *EP = dyn_cast<GetElementPtrInst>(V)) {
3000     Res = findAllocaForValue(EP->getPointerOperand(), AllocaForValue);
3001   } else {
3002     LLVM_DEBUG(dbgs() << "Alloca search cancelled on unknown instruction: "
3003                       << *V << "\n");
3004   }
3005   if (Res)
3006     AllocaForValue[V] = Res;
3007   return Res;
3008 }
3009