xref: /llvm-project/llvm/lib/Transforms/Utils/Local.cpp (revision 9ee942f4814dd5a12cc37eb0be9e1734c4f0cfe4)
1 //===- Local.cpp - Functions to perform local transformations -------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This family of functions perform various local transformations to the
11 // program.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/Transforms/Utils/Local.h"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/DenseMapInfo.h"
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/ADT/Hashing.h"
21 #include "llvm/ADT/None.h"
22 #include "llvm/ADT/Optional.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/ADT/SetVector.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/ADT/Statistic.h"
28 #include "llvm/ADT/TinyPtrVector.h"
29 #include "llvm/Analysis/ConstantFolding.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/TargetLibraryInfo.h"
35 #include "llvm/Analysis/ValueTracking.h"
36 #include "llvm/BinaryFormat/Dwarf.h"
37 #include "llvm/IR/Argument.h"
38 #include "llvm/IR/Attributes.h"
39 #include "llvm/IR/BasicBlock.h"
40 #include "llvm/IR/CFG.h"
41 #include "llvm/IR/CallSite.h"
42 #include "llvm/IR/Constant.h"
43 #include "llvm/IR/ConstantRange.h"
44 #include "llvm/IR/Constants.h"
45 #include "llvm/IR/DIBuilder.h"
46 #include "llvm/IR/DataLayout.h"
47 #include "llvm/IR/DebugInfoMetadata.h"
48 #include "llvm/IR/DebugLoc.h"
49 #include "llvm/IR/DerivedTypes.h"
50 #include "llvm/IR/Dominators.h"
51 #include "llvm/IR/Function.h"
52 #include "llvm/IR/GetElementPtrTypeIterator.h"
53 #include "llvm/IR/GlobalObject.h"
54 #include "llvm/IR/IRBuilder.h"
55 #include "llvm/IR/InstrTypes.h"
56 #include "llvm/IR/Instruction.h"
57 #include "llvm/IR/Instructions.h"
58 #include "llvm/IR/IntrinsicInst.h"
59 #include "llvm/IR/Intrinsics.h"
60 #include "llvm/IR/LLVMContext.h"
61 #include "llvm/IR/MDBuilder.h"
62 #include "llvm/IR/Metadata.h"
63 #include "llvm/IR/Module.h"
64 #include "llvm/IR/Operator.h"
65 #include "llvm/IR/PatternMatch.h"
66 #include "llvm/IR/Type.h"
67 #include "llvm/IR/Use.h"
68 #include "llvm/IR/User.h"
69 #include "llvm/IR/Value.h"
70 #include "llvm/IR/ValueHandle.h"
71 #include "llvm/Support/Casting.h"
72 #include "llvm/Support/Debug.h"
73 #include "llvm/Support/ErrorHandling.h"
74 #include "llvm/Support/KnownBits.h"
75 #include "llvm/Support/raw_ostream.h"
76 #include <algorithm>
77 #include <cassert>
78 #include <climits>
79 #include <cstdint>
80 #include <iterator>
81 #include <map>
82 #include <utility>
83 
84 using namespace llvm;
85 using namespace llvm::PatternMatch;
86 
87 #define DEBUG_TYPE "local"
88 
89 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
90 
91 //===----------------------------------------------------------------------===//
92 //  Local constant propagation.
93 //
94 
95 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
96 /// constant value, convert it into an unconditional branch to the constant
97 /// destination.  This is a nontrivial operation because the successors of this
98 /// basic block must have their PHI nodes updated.
99 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
100 /// conditions and indirectbr addresses this might make dead if
101 /// DeleteDeadConditions is true.
102 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
103                                   const TargetLibraryInfo *TLI) {
104   TerminatorInst *T = BB->getTerminator();
105   IRBuilder<> Builder(T);
106 
107   // Branch - See if we are conditional jumping on constant
108   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
109     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
110     BasicBlock *Dest1 = BI->getSuccessor(0);
111     BasicBlock *Dest2 = BI->getSuccessor(1);
112 
113     if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
114       // Are we branching on constant?
115       // YES.  Change to unconditional branch...
116       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
117       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
118 
119       //cerr << "Function: " << T->getParent()->getParent()
120       //     << "\nRemoving branch from " << T->getParent()
121       //     << "\n\nTo: " << OldDest << endl;
122 
123       // Let the basic block know that we are letting go of it.  Based on this,
124       // it will adjust it's PHI nodes.
125       OldDest->removePredecessor(BB);
126 
127       // Replace the conditional branch with an unconditional one.
128       Builder.CreateBr(Destination);
129       BI->eraseFromParent();
130       return true;
131     }
132 
133     if (Dest2 == Dest1) {       // Conditional branch to same location?
134       // This branch matches something like this:
135       //     br bool %cond, label %Dest, label %Dest
136       // and changes it into:  br label %Dest
137 
138       // Let the basic block know that we are letting go of one copy of it.
139       assert(BI->getParent() && "Terminator not inserted in block!");
140       Dest1->removePredecessor(BI->getParent());
141 
142       // Replace the conditional branch with an unconditional one.
143       Builder.CreateBr(Dest1);
144       Value *Cond = BI->getCondition();
145       BI->eraseFromParent();
146       if (DeleteDeadConditions)
147         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
148       return true;
149     }
150     return false;
151   }
152 
153   if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
154     // If we are switching on a constant, we can convert the switch to an
155     // unconditional branch.
156     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
157     BasicBlock *DefaultDest = SI->getDefaultDest();
158     BasicBlock *TheOnlyDest = DefaultDest;
159 
160     // If the default is unreachable, ignore it when searching for TheOnlyDest.
161     if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) &&
162         SI->getNumCases() > 0) {
163       TheOnlyDest = SI->case_begin()->getCaseSuccessor();
164     }
165 
166     // Figure out which case it goes to.
167     for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
168       // Found case matching a constant operand?
169       if (i->getCaseValue() == CI) {
170         TheOnlyDest = i->getCaseSuccessor();
171         break;
172       }
173 
174       // Check to see if this branch is going to the same place as the default
175       // dest.  If so, eliminate it as an explicit compare.
176       if (i->getCaseSuccessor() == DefaultDest) {
177         MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
178         unsigned NCases = SI->getNumCases();
179         // Fold the case metadata into the default if there will be any branches
180         // left, unless the metadata doesn't match the switch.
181         if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
182           // Collect branch weights into a vector.
183           SmallVector<uint32_t, 8> Weights;
184           for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
185                ++MD_i) {
186             auto *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i));
187             Weights.push_back(CI->getValue().getZExtValue());
188           }
189           // Merge weight of this case to the default weight.
190           unsigned idx = i->getCaseIndex();
191           Weights[0] += Weights[idx+1];
192           // Remove weight for this case.
193           std::swap(Weights[idx+1], Weights.back());
194           Weights.pop_back();
195           SI->setMetadata(LLVMContext::MD_prof,
196                           MDBuilder(BB->getContext()).
197                           createBranchWeights(Weights));
198         }
199         // Remove this entry.
200         DefaultDest->removePredecessor(SI->getParent());
201         i = SI->removeCase(i);
202         e = SI->case_end();
203         continue;
204       }
205 
206       // Otherwise, check to see if the switch only branches to one destination.
207       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
208       // destinations.
209       if (i->getCaseSuccessor() != TheOnlyDest)
210         TheOnlyDest = nullptr;
211 
212       // Increment this iterator as we haven't removed the case.
213       ++i;
214     }
215 
216     if (CI && !TheOnlyDest) {
217       // Branching on a constant, but not any of the cases, go to the default
218       // successor.
219       TheOnlyDest = SI->getDefaultDest();
220     }
221 
222     // If we found a single destination that we can fold the switch into, do so
223     // now.
224     if (TheOnlyDest) {
225       // Insert the new branch.
226       Builder.CreateBr(TheOnlyDest);
227       BasicBlock *BB = SI->getParent();
228 
229       // Remove entries from PHI nodes which we no longer branch to...
230       for (BasicBlock *Succ : SI->successors()) {
231         // Found case matching a constant operand?
232         if (Succ == TheOnlyDest)
233           TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
234         else
235           Succ->removePredecessor(BB);
236       }
237 
238       // Delete the old switch.
239       Value *Cond = SI->getCondition();
240       SI->eraseFromParent();
241       if (DeleteDeadConditions)
242         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
243       return true;
244     }
245 
246     if (SI->getNumCases() == 1) {
247       // Otherwise, we can fold this switch into a conditional branch
248       // instruction if it has only one non-default destination.
249       auto FirstCase = *SI->case_begin();
250       Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
251           FirstCase.getCaseValue(), "cond");
252 
253       // Insert the new branch.
254       BranchInst *NewBr = Builder.CreateCondBr(Cond,
255                                                FirstCase.getCaseSuccessor(),
256                                                SI->getDefaultDest());
257       MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
258       if (MD && MD->getNumOperands() == 3) {
259         ConstantInt *SICase =
260             mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
261         ConstantInt *SIDef =
262             mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
263         assert(SICase && SIDef);
264         // The TrueWeight should be the weight for the single case of SI.
265         NewBr->setMetadata(LLVMContext::MD_prof,
266                         MDBuilder(BB->getContext()).
267                         createBranchWeights(SICase->getValue().getZExtValue(),
268                                             SIDef->getValue().getZExtValue()));
269       }
270 
271       // Update make.implicit metadata to the newly-created conditional branch.
272       MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
273       if (MakeImplicitMD)
274         NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
275 
276       // Delete the old switch.
277       SI->eraseFromParent();
278       return true;
279     }
280     return false;
281   }
282 
283   if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
284     // indirectbr blockaddress(@F, @BB) -> br label @BB
285     if (BlockAddress *BA =
286           dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
287       BasicBlock *TheOnlyDest = BA->getBasicBlock();
288       // Insert the new branch.
289       Builder.CreateBr(TheOnlyDest);
290 
291       for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
292         if (IBI->getDestination(i) == TheOnlyDest)
293           TheOnlyDest = nullptr;
294         else
295           IBI->getDestination(i)->removePredecessor(IBI->getParent());
296       }
297       Value *Address = IBI->getAddress();
298       IBI->eraseFromParent();
299       if (DeleteDeadConditions)
300         RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
301 
302       // If we didn't find our destination in the IBI successor list, then we
303       // have undefined behavior.  Replace the unconditional branch with an
304       // 'unreachable' instruction.
305       if (TheOnlyDest) {
306         BB->getTerminator()->eraseFromParent();
307         new UnreachableInst(BB->getContext(), BB);
308       }
309 
310       return true;
311     }
312   }
313 
314   return false;
315 }
316 
317 //===----------------------------------------------------------------------===//
318 //  Local dead code elimination.
319 //
320 
321 /// isInstructionTriviallyDead - Return true if the result produced by the
322 /// instruction is not used, and the instruction has no side effects.
323 ///
324 bool llvm::isInstructionTriviallyDead(Instruction *I,
325                                       const TargetLibraryInfo *TLI) {
326   if (!I->use_empty())
327     return false;
328   return wouldInstructionBeTriviallyDead(I, TLI);
329 }
330 
331 bool llvm::wouldInstructionBeTriviallyDead(Instruction *I,
332                                            const TargetLibraryInfo *TLI) {
333   if (isa<TerminatorInst>(I))
334     return false;
335 
336   // We don't want the landingpad-like instructions removed by anything this
337   // general.
338   if (I->isEHPad())
339     return false;
340 
341   // We don't want debug info removed by anything this general, unless
342   // debug info is empty.
343   if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
344     if (DDI->getAddress())
345       return false;
346     return true;
347   }
348   if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
349     if (DVI->getValue())
350       return false;
351     return true;
352   }
353 
354   if (!I->mayHaveSideEffects())
355     return true;
356 
357   // Special case intrinsics that "may have side effects" but can be deleted
358   // when dead.
359   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
360     // Safe to delete llvm.stacksave if dead.
361     if (II->getIntrinsicID() == Intrinsic::stacksave)
362       return true;
363 
364     // Lifetime intrinsics are dead when their right-hand is undef.
365     if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
366         II->getIntrinsicID() == Intrinsic::lifetime_end)
367       return isa<UndefValue>(II->getArgOperand(1));
368 
369     // Assumptions are dead if their condition is trivially true.  Guards on
370     // true are operationally no-ops.  In the future we can consider more
371     // sophisticated tradeoffs for guards considering potential for check
372     // widening, but for now we keep things simple.
373     if (II->getIntrinsicID() == Intrinsic::assume ||
374         II->getIntrinsicID() == Intrinsic::experimental_guard) {
375       if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
376         return !Cond->isZero();
377 
378       return false;
379     }
380   }
381 
382   if (isAllocLikeFn(I, TLI))
383     return true;
384 
385   if (CallInst *CI = isFreeCall(I, TLI))
386     if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
387       return C->isNullValue() || isa<UndefValue>(C);
388 
389   if (CallSite CS = CallSite(I))
390     if (isMathLibCallNoop(CS, TLI))
391       return true;
392 
393   return false;
394 }
395 
396 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
397 /// trivially dead instruction, delete it.  If that makes any of its operands
398 /// trivially dead, delete them too, recursively.  Return true if any
399 /// instructions were deleted.
400 bool
401 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
402                                                  const TargetLibraryInfo *TLI) {
403   Instruction *I = dyn_cast<Instruction>(V);
404   if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI))
405     return false;
406 
407   SmallVector<Instruction*, 16> DeadInsts;
408   DeadInsts.push_back(I);
409 
410   do {
411     I = DeadInsts.pop_back_val();
412 
413     // Null out all of the instruction's operands to see if any operand becomes
414     // dead as we go.
415     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
416       Value *OpV = I->getOperand(i);
417       I->setOperand(i, nullptr);
418 
419       if (!OpV->use_empty()) continue;
420 
421       // If the operand is an instruction that became dead as we nulled out the
422       // operand, and if it is 'trivially' dead, delete it in a future loop
423       // iteration.
424       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
425         if (isInstructionTriviallyDead(OpI, TLI))
426           DeadInsts.push_back(OpI);
427     }
428 
429     I->eraseFromParent();
430   } while (!DeadInsts.empty());
431 
432   return true;
433 }
434 
435 /// areAllUsesEqual - Check whether the uses of a value are all the same.
436 /// This is similar to Instruction::hasOneUse() except this will also return
437 /// true when there are no uses or multiple uses that all refer to the same
438 /// value.
439 static bool areAllUsesEqual(Instruction *I) {
440   Value::user_iterator UI = I->user_begin();
441   Value::user_iterator UE = I->user_end();
442   if (UI == UE)
443     return true;
444 
445   User *TheUse = *UI;
446   for (++UI; UI != UE; ++UI) {
447     if (*UI != TheUse)
448       return false;
449   }
450   return true;
451 }
452 
453 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
454 /// dead PHI node, due to being a def-use chain of single-use nodes that
455 /// either forms a cycle or is terminated by a trivially dead instruction,
456 /// delete it.  If that makes any of its operands trivially dead, delete them
457 /// too, recursively.  Return true if a change was made.
458 bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN,
459                                         const TargetLibraryInfo *TLI) {
460   SmallPtrSet<Instruction*, 4> Visited;
461   for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
462        I = cast<Instruction>(*I->user_begin())) {
463     if (I->use_empty())
464       return RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
465 
466     // If we find an instruction more than once, we're on a cycle that
467     // won't prove fruitful.
468     if (!Visited.insert(I).second) {
469       // Break the cycle and delete the instruction and its operands.
470       I->replaceAllUsesWith(UndefValue::get(I->getType()));
471       (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
472       return true;
473     }
474   }
475   return false;
476 }
477 
478 static bool
479 simplifyAndDCEInstruction(Instruction *I,
480                           SmallSetVector<Instruction *, 16> &WorkList,
481                           const DataLayout &DL,
482                           const TargetLibraryInfo *TLI) {
483   if (isInstructionTriviallyDead(I, TLI)) {
484     // Null out all of the instruction's operands to see if any operand becomes
485     // dead as we go.
486     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
487       Value *OpV = I->getOperand(i);
488       I->setOperand(i, nullptr);
489 
490       if (!OpV->use_empty() || I == OpV)
491         continue;
492 
493       // If the operand is an instruction that became dead as we nulled out the
494       // operand, and if it is 'trivially' dead, delete it in a future loop
495       // iteration.
496       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
497         if (isInstructionTriviallyDead(OpI, TLI))
498           WorkList.insert(OpI);
499     }
500 
501     I->eraseFromParent();
502 
503     return true;
504   }
505 
506   if (Value *SimpleV = SimplifyInstruction(I, DL)) {
507     // Add the users to the worklist. CAREFUL: an instruction can use itself,
508     // in the case of a phi node.
509     for (User *U : I->users()) {
510       if (U != I) {
511         WorkList.insert(cast<Instruction>(U));
512       }
513     }
514 
515     // Replace the instruction with its simplified value.
516     bool Changed = false;
517     if (!I->use_empty()) {
518       I->replaceAllUsesWith(SimpleV);
519       Changed = true;
520     }
521     if (isInstructionTriviallyDead(I, TLI)) {
522       I->eraseFromParent();
523       Changed = true;
524     }
525     return Changed;
526   }
527   return false;
528 }
529 
530 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
531 /// simplify any instructions in it and recursively delete dead instructions.
532 ///
533 /// This returns true if it changed the code, note that it can delete
534 /// instructions in other blocks as well in this block.
535 bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB,
536                                        const TargetLibraryInfo *TLI) {
537   bool MadeChange = false;
538   const DataLayout &DL = BB->getModule()->getDataLayout();
539 
540 #ifndef NDEBUG
541   // In debug builds, ensure that the terminator of the block is never replaced
542   // or deleted by these simplifications. The idea of simplification is that it
543   // cannot introduce new instructions, and there is no way to replace the
544   // terminator of a block without introducing a new instruction.
545   AssertingVH<Instruction> TerminatorVH(&BB->back());
546 #endif
547 
548   SmallSetVector<Instruction *, 16> WorkList;
549   // Iterate over the original function, only adding insts to the worklist
550   // if they actually need to be revisited. This avoids having to pre-init
551   // the worklist with the entire function's worth of instructions.
552   for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end());
553        BI != E;) {
554     assert(!BI->isTerminator());
555     Instruction *I = &*BI;
556     ++BI;
557 
558     // We're visiting this instruction now, so make sure it's not in the
559     // worklist from an earlier visit.
560     if (!WorkList.count(I))
561       MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
562   }
563 
564   while (!WorkList.empty()) {
565     Instruction *I = WorkList.pop_back_val();
566     MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
567   }
568   return MadeChange;
569 }
570 
571 //===----------------------------------------------------------------------===//
572 //  Control Flow Graph Restructuring.
573 //
574 
575 /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this
576 /// method is called when we're about to delete Pred as a predecessor of BB.  If
577 /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred.
578 ///
579 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
580 /// nodes that collapse into identity values.  For example, if we have:
581 ///   x = phi(1, 0, 0, 0)
582 ///   y = and x, z
583 ///
584 /// .. and delete the predecessor corresponding to the '1', this will attempt to
585 /// recursively fold the and to 0.
586 void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) {
587   // This only adjusts blocks with PHI nodes.
588   if (!isa<PHINode>(BB->begin()))
589     return;
590 
591   // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
592   // them down.  This will leave us with single entry phi nodes and other phis
593   // that can be removed.
594   BB->removePredecessor(Pred, true);
595 
596   WeakTrackingVH PhiIt = &BB->front();
597   while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
598     PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
599     Value *OldPhiIt = PhiIt;
600 
601     if (!recursivelySimplifyInstruction(PN))
602       continue;
603 
604     // If recursive simplification ended up deleting the next PHI node we would
605     // iterate to, then our iterator is invalid, restart scanning from the top
606     // of the block.
607     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
608   }
609 }
610 
611 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
612 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
613 /// between them, moving the instructions in the predecessor into DestBB and
614 /// deleting the predecessor block.
615 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) {
616   // If BB has single-entry PHI nodes, fold them.
617   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
618     Value *NewVal = PN->getIncomingValue(0);
619     // Replace self referencing PHI with undef, it must be dead.
620     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
621     PN->replaceAllUsesWith(NewVal);
622     PN->eraseFromParent();
623   }
624 
625   BasicBlock *PredBB = DestBB->getSinglePredecessor();
626   assert(PredBB && "Block doesn't have a single predecessor!");
627 
628   // Zap anything that took the address of DestBB.  Not doing this will give the
629   // address an invalid value.
630   if (DestBB->hasAddressTaken()) {
631     BlockAddress *BA = BlockAddress::get(DestBB);
632     Constant *Replacement =
633       ConstantInt::get(Type::getInt32Ty(BA->getContext()), 1);
634     BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
635                                                      BA->getType()));
636     BA->destroyConstant();
637   }
638 
639   // Anything that branched to PredBB now branches to DestBB.
640   PredBB->replaceAllUsesWith(DestBB);
641 
642   // Splice all the instructions from PredBB to DestBB.
643   PredBB->getTerminator()->eraseFromParent();
644   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
645 
646   // If the PredBB is the entry block of the function, move DestBB up to
647   // become the entry block after we erase PredBB.
648   if (PredBB == &DestBB->getParent()->getEntryBlock())
649     DestBB->moveAfter(PredBB);
650 
651   if (DT) {
652     // For some irreducible CFG we end up having forward-unreachable blocks
653     // so check if getNode returns a valid node before updating the domtree.
654     if (DomTreeNode *DTN = DT->getNode(PredBB)) {
655       BasicBlock *PredBBIDom = DTN->getIDom()->getBlock();
656       DT->changeImmediateDominator(DestBB, PredBBIDom);
657       DT->eraseNode(PredBB);
658     }
659   }
660   // Nuke BB.
661   PredBB->eraseFromParent();
662 }
663 
664 /// CanMergeValues - Return true if we can choose one of these values to use
665 /// in place of the other. Note that we will always choose the non-undef
666 /// value to keep.
667 static bool CanMergeValues(Value *First, Value *Second) {
668   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
669 }
670 
671 /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an
672 /// almost-empty BB ending in an unconditional branch to Succ, into Succ.
673 ///
674 /// Assumption: Succ is the single successor for BB.
675 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
676   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
677 
678   DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
679         << Succ->getName() << "\n");
680   // Shortcut, if there is only a single predecessor it must be BB and merging
681   // is always safe
682   if (Succ->getSinglePredecessor()) return true;
683 
684   // Make a list of the predecessors of BB
685   SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
686 
687   // Look at all the phi nodes in Succ, to see if they present a conflict when
688   // merging these blocks
689   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
690     PHINode *PN = cast<PHINode>(I);
691 
692     // If the incoming value from BB is again a PHINode in
693     // BB which has the same incoming value for *PI as PN does, we can
694     // merge the phi nodes and then the blocks can still be merged
695     PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
696     if (BBPN && BBPN->getParent() == BB) {
697       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
698         BasicBlock *IBB = PN->getIncomingBlock(PI);
699         if (BBPreds.count(IBB) &&
700             !CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
701                             PN->getIncomingValue(PI))) {
702           DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
703                 << Succ->getName() << " is conflicting with "
704                 << BBPN->getName() << " with regard to common predecessor "
705                 << IBB->getName() << "\n");
706           return false;
707         }
708       }
709     } else {
710       Value* Val = PN->getIncomingValueForBlock(BB);
711       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
712         // See if the incoming value for the common predecessor is equal to the
713         // one for BB, in which case this phi node will not prevent the merging
714         // of the block.
715         BasicBlock *IBB = PN->getIncomingBlock(PI);
716         if (BBPreds.count(IBB) &&
717             !CanMergeValues(Val, PN->getIncomingValue(PI))) {
718           DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
719                 << Succ->getName() << " is conflicting with regard to common "
720                 << "predecessor " << IBB->getName() << "\n");
721           return false;
722         }
723       }
724     }
725   }
726 
727   return true;
728 }
729 
730 using PredBlockVector = SmallVector<BasicBlock *, 16>;
731 using IncomingValueMap = DenseMap<BasicBlock *, Value *>;
732 
733 /// \brief Determines the value to use as the phi node input for a block.
734 ///
735 /// Select between \p OldVal any value that we know flows from \p BB
736 /// to a particular phi on the basis of which one (if either) is not
737 /// undef. Update IncomingValues based on the selected value.
738 ///
739 /// \param OldVal The value we are considering selecting.
740 /// \param BB The block that the value flows in from.
741 /// \param IncomingValues A map from block-to-value for other phi inputs
742 /// that we have examined.
743 ///
744 /// \returns the selected value.
745 static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB,
746                                           IncomingValueMap &IncomingValues) {
747   if (!isa<UndefValue>(OldVal)) {
748     assert((!IncomingValues.count(BB) ||
749             IncomingValues.find(BB)->second == OldVal) &&
750            "Expected OldVal to match incoming value from BB!");
751 
752     IncomingValues.insert(std::make_pair(BB, OldVal));
753     return OldVal;
754   }
755 
756   IncomingValueMap::const_iterator It = IncomingValues.find(BB);
757   if (It != IncomingValues.end()) return It->second;
758 
759   return OldVal;
760 }
761 
762 /// \brief Create a map from block to value for the operands of a
763 /// given phi.
764 ///
765 /// Create a map from block to value for each non-undef value flowing
766 /// into \p PN.
767 ///
768 /// \param PN The phi we are collecting the map for.
769 /// \param IncomingValues [out] The map from block to value for this phi.
770 static void gatherIncomingValuesToPhi(PHINode *PN,
771                                       IncomingValueMap &IncomingValues) {
772   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
773     BasicBlock *BB = PN->getIncomingBlock(i);
774     Value *V = PN->getIncomingValue(i);
775 
776     if (!isa<UndefValue>(V))
777       IncomingValues.insert(std::make_pair(BB, V));
778   }
779 }
780 
781 /// \brief Replace the incoming undef values to a phi with the values
782 /// from a block-to-value map.
783 ///
784 /// \param PN The phi we are replacing the undefs in.
785 /// \param IncomingValues A map from block to value.
786 static void replaceUndefValuesInPhi(PHINode *PN,
787                                     const IncomingValueMap &IncomingValues) {
788   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
789     Value *V = PN->getIncomingValue(i);
790 
791     if (!isa<UndefValue>(V)) continue;
792 
793     BasicBlock *BB = PN->getIncomingBlock(i);
794     IncomingValueMap::const_iterator It = IncomingValues.find(BB);
795     if (It == IncomingValues.end()) continue;
796 
797     PN->setIncomingValue(i, It->second);
798   }
799 }
800 
801 /// \brief Replace a value flowing from a block to a phi with
802 /// potentially multiple instances of that value flowing from the
803 /// block's predecessors to the phi.
804 ///
805 /// \param BB The block with the value flowing into the phi.
806 /// \param BBPreds The predecessors of BB.
807 /// \param PN The phi that we are updating.
808 static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
809                                                 const PredBlockVector &BBPreds,
810                                                 PHINode *PN) {
811   Value *OldVal = PN->removeIncomingValue(BB, false);
812   assert(OldVal && "No entry in PHI for Pred BB!");
813 
814   IncomingValueMap IncomingValues;
815 
816   // We are merging two blocks - BB, and the block containing PN - and
817   // as a result we need to redirect edges from the predecessors of BB
818   // to go to the block containing PN, and update PN
819   // accordingly. Since we allow merging blocks in the case where the
820   // predecessor and successor blocks both share some predecessors,
821   // and where some of those common predecessors might have undef
822   // values flowing into PN, we want to rewrite those values to be
823   // consistent with the non-undef values.
824 
825   gatherIncomingValuesToPhi(PN, IncomingValues);
826 
827   // If this incoming value is one of the PHI nodes in BB, the new entries
828   // in the PHI node are the entries from the old PHI.
829   if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
830     PHINode *OldValPN = cast<PHINode>(OldVal);
831     for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
832       // Note that, since we are merging phi nodes and BB and Succ might
833       // have common predecessors, we could end up with a phi node with
834       // identical incoming branches. This will be cleaned up later (and
835       // will trigger asserts if we try to clean it up now, without also
836       // simplifying the corresponding conditional branch).
837       BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
838       Value *PredVal = OldValPN->getIncomingValue(i);
839       Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
840                                                     IncomingValues);
841 
842       // And add a new incoming value for this predecessor for the
843       // newly retargeted branch.
844       PN->addIncoming(Selected, PredBB);
845     }
846   } else {
847     for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
848       // Update existing incoming values in PN for this
849       // predecessor of BB.
850       BasicBlock *PredBB = BBPreds[i];
851       Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
852                                                     IncomingValues);
853 
854       // And add a new incoming value for this predecessor for the
855       // newly retargeted branch.
856       PN->addIncoming(Selected, PredBB);
857     }
858   }
859 
860   replaceUndefValuesInPhi(PN, IncomingValues);
861 }
862 
863 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
864 /// unconditional branch, and contains no instructions other than PHI nodes,
865 /// potential side-effect free intrinsics and the branch.  If possible,
866 /// eliminate BB by rewriting all the predecessors to branch to the successor
867 /// block and return true.  If we can't transform, return false.
868 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {
869   assert(BB != &BB->getParent()->getEntryBlock() &&
870          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
871 
872   // We can't eliminate infinite loops.
873   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
874   if (BB == Succ) return false;
875 
876   // Check to see if merging these blocks would cause conflicts for any of the
877   // phi nodes in BB or Succ. If not, we can safely merge.
878   if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
879 
880   // Check for cases where Succ has multiple predecessors and a PHI node in BB
881   // has uses which will not disappear when the PHI nodes are merged.  It is
882   // possible to handle such cases, but difficult: it requires checking whether
883   // BB dominates Succ, which is non-trivial to calculate in the case where
884   // Succ has multiple predecessors.  Also, it requires checking whether
885   // constructing the necessary self-referential PHI node doesn't introduce any
886   // conflicts; this isn't too difficult, but the previous code for doing this
887   // was incorrect.
888   //
889   // Note that if this check finds a live use, BB dominates Succ, so BB is
890   // something like a loop pre-header (or rarely, a part of an irreducible CFG);
891   // folding the branch isn't profitable in that case anyway.
892   if (!Succ->getSinglePredecessor()) {
893     BasicBlock::iterator BBI = BB->begin();
894     while (isa<PHINode>(*BBI)) {
895       for (Use &U : BBI->uses()) {
896         if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
897           if (PN->getIncomingBlock(U) != BB)
898             return false;
899         } else {
900           return false;
901         }
902       }
903       ++BBI;
904     }
905   }
906 
907   DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
908 
909   if (isa<PHINode>(Succ->begin())) {
910     // If there is more than one pred of succ, and there are PHI nodes in
911     // the successor, then we need to add incoming edges for the PHI nodes
912     //
913     const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
914 
915     // Loop over all of the PHI nodes in the successor of BB.
916     for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
917       PHINode *PN = cast<PHINode>(I);
918 
919       redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
920     }
921   }
922 
923   if (Succ->getSinglePredecessor()) {
924     // BB is the only predecessor of Succ, so Succ will end up with exactly
925     // the same predecessors BB had.
926 
927     // Copy over any phi, debug or lifetime instruction.
928     BB->getTerminator()->eraseFromParent();
929     Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
930                                BB->getInstList());
931   } else {
932     while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
933       // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
934       assert(PN->use_empty() && "There shouldn't be any uses here!");
935       PN->eraseFromParent();
936     }
937   }
938 
939   // If the unconditional branch we replaced contains llvm.loop metadata, we
940   // add the metadata to the branch instructions in the predecessors.
941   unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
942   Instruction *TI = BB->getTerminator();
943   if (TI)
944     if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
945       for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
946         BasicBlock *Pred = *PI;
947         Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
948       }
949 
950   // Everything that jumped to BB now goes to Succ.
951   BB->replaceAllUsesWith(Succ);
952   if (!Succ->hasName()) Succ->takeName(BB);
953   BB->eraseFromParent();              // Delete the old basic block.
954   return true;
955 }
956 
957 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
958 /// nodes in this block. This doesn't try to be clever about PHI nodes
959 /// which differ only in the order of the incoming values, but instcombine
960 /// orders them so it usually won't matter.
961 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
962   // This implementation doesn't currently consider undef operands
963   // specially. Theoretically, two phis which are identical except for
964   // one having an undef where the other doesn't could be collapsed.
965 
966   struct PHIDenseMapInfo {
967     static PHINode *getEmptyKey() {
968       return DenseMapInfo<PHINode *>::getEmptyKey();
969     }
970 
971     static PHINode *getTombstoneKey() {
972       return DenseMapInfo<PHINode *>::getTombstoneKey();
973     }
974 
975     static unsigned getHashValue(PHINode *PN) {
976       // Compute a hash value on the operands. Instcombine will likely have
977       // sorted them, which helps expose duplicates, but we have to check all
978       // the operands to be safe in case instcombine hasn't run.
979       return static_cast<unsigned>(hash_combine(
980           hash_combine_range(PN->value_op_begin(), PN->value_op_end()),
981           hash_combine_range(PN->block_begin(), PN->block_end())));
982     }
983 
984     static bool isEqual(PHINode *LHS, PHINode *RHS) {
985       if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
986           RHS == getEmptyKey() || RHS == getTombstoneKey())
987         return LHS == RHS;
988       return LHS->isIdenticalTo(RHS);
989     }
990   };
991 
992   // Set of unique PHINodes.
993   DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
994 
995   // Examine each PHI.
996   bool Changed = false;
997   for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
998     auto Inserted = PHISet.insert(PN);
999     if (!Inserted.second) {
1000       // A duplicate. Replace this PHI with its duplicate.
1001       PN->replaceAllUsesWith(*Inserted.first);
1002       PN->eraseFromParent();
1003       Changed = true;
1004 
1005       // The RAUW can change PHIs that we already visited. Start over from the
1006       // beginning.
1007       PHISet.clear();
1008       I = BB->begin();
1009     }
1010   }
1011 
1012   return Changed;
1013 }
1014 
1015 /// enforceKnownAlignment - If the specified pointer points to an object that
1016 /// we control, modify the object's alignment to PrefAlign. This isn't
1017 /// often possible though. If alignment is important, a more reliable approach
1018 /// is to simply align all global variables and allocation instructions to
1019 /// their preferred alignment from the beginning.
1020 static unsigned enforceKnownAlignment(Value *V, unsigned Align,
1021                                       unsigned PrefAlign,
1022                                       const DataLayout &DL) {
1023   assert(PrefAlign > Align);
1024 
1025   V = V->stripPointerCasts();
1026 
1027   if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1028     // TODO: ideally, computeKnownBits ought to have used
1029     // AllocaInst::getAlignment() in its computation already, making
1030     // the below max redundant. But, as it turns out,
1031     // stripPointerCasts recurses through infinite layers of bitcasts,
1032     // while computeKnownBits is not allowed to traverse more than 6
1033     // levels.
1034     Align = std::max(AI->getAlignment(), Align);
1035     if (PrefAlign <= Align)
1036       return Align;
1037 
1038     // If the preferred alignment is greater than the natural stack alignment
1039     // then don't round up. This avoids dynamic stack realignment.
1040     if (DL.exceedsNaturalStackAlignment(PrefAlign))
1041       return Align;
1042     AI->setAlignment(PrefAlign);
1043     return PrefAlign;
1044   }
1045 
1046   if (auto *GO = dyn_cast<GlobalObject>(V)) {
1047     // TODO: as above, this shouldn't be necessary.
1048     Align = std::max(GO->getAlignment(), Align);
1049     if (PrefAlign <= Align)
1050       return Align;
1051 
1052     // If there is a large requested alignment and we can, bump up the alignment
1053     // of the global.  If the memory we set aside for the global may not be the
1054     // memory used by the final program then it is impossible for us to reliably
1055     // enforce the preferred alignment.
1056     if (!GO->canIncreaseAlignment())
1057       return Align;
1058 
1059     GO->setAlignment(PrefAlign);
1060     return PrefAlign;
1061   }
1062 
1063   return Align;
1064 }
1065 
1066 unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
1067                                           const DataLayout &DL,
1068                                           const Instruction *CxtI,
1069                                           AssumptionCache *AC,
1070                                           const DominatorTree *DT) {
1071   assert(V->getType()->isPointerTy() &&
1072          "getOrEnforceKnownAlignment expects a pointer!");
1073 
1074   KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT);
1075   unsigned TrailZ = Known.countMinTrailingZeros();
1076 
1077   // Avoid trouble with ridiculously large TrailZ values, such as
1078   // those computed from a null pointer.
1079   TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1));
1080 
1081   unsigned Align = 1u << std::min(Known.getBitWidth() - 1, TrailZ);
1082 
1083   // LLVM doesn't support alignments larger than this currently.
1084   Align = std::min(Align, +Value::MaximumAlignment);
1085 
1086   if (PrefAlign > Align)
1087     Align = enforceKnownAlignment(V, Align, PrefAlign, DL);
1088 
1089   // We don't need to make any adjustment.
1090   return Align;
1091 }
1092 
1093 ///===---------------------------------------------------------------------===//
1094 ///  Dbg Intrinsic utilities
1095 ///
1096 
1097 /// See if there is a dbg.value intrinsic for DIVar before I.
1098 static bool LdStHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr,
1099                               Instruction *I) {
1100   // Since we can't guarantee that the original dbg.declare instrinsic
1101   // is removed by LowerDbgDeclare(), we need to make sure that we are
1102   // not inserting the same dbg.value intrinsic over and over.
1103   BasicBlock::InstListType::iterator PrevI(I);
1104   if (PrevI != I->getParent()->getInstList().begin()) {
1105     --PrevI;
1106     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
1107       if (DVI->getValue() == I->getOperand(0) &&
1108           DVI->getVariable() == DIVar &&
1109           DVI->getExpression() == DIExpr)
1110         return true;
1111   }
1112   return false;
1113 }
1114 
1115 /// See if there is a dbg.value intrinsic for DIVar for the PHI node.
1116 static bool PhiHasDebugValue(DILocalVariable *DIVar,
1117                              DIExpression *DIExpr,
1118                              PHINode *APN) {
1119   // Since we can't guarantee that the original dbg.declare instrinsic
1120   // is removed by LowerDbgDeclare(), we need to make sure that we are
1121   // not inserting the same dbg.value intrinsic over and over.
1122   SmallVector<DbgValueInst *, 1> DbgValues;
1123   findDbgValues(DbgValues, APN);
1124   for (auto *DVI : DbgValues) {
1125     assert(DVI->getValue() == APN);
1126     if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1127       return true;
1128   }
1129   return false;
1130 }
1131 
1132 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1133 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1134 void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII,
1135                                            StoreInst *SI, DIBuilder &Builder) {
1136   assert(DII->isAddressOfVariable());
1137   auto *DIVar = DII->getVariable();
1138   assert(DIVar && "Missing variable");
1139   auto *DIExpr = DII->getExpression();
1140   Value *DV = SI->getOperand(0);
1141 
1142   // If an argument is zero extended then use argument directly. The ZExt
1143   // may be zapped by an optimization pass in future.
1144   Argument *ExtendedArg = nullptr;
1145   if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
1146     ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0));
1147   if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
1148     ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0));
1149   if (ExtendedArg) {
1150     // If this DII was already describing only a fragment of a variable, ensure
1151     // that fragment is appropriately narrowed here.
1152     // But if a fragment wasn't used, describe the value as the original
1153     // argument (rather than the zext or sext) so that it remains described even
1154     // if the sext/zext is optimized away. This widens the variable description,
1155     // leaving it up to the consumer to know how the smaller value may be
1156     // represented in a larger register.
1157     if (auto Fragment = DIExpr->getFragmentInfo()) {
1158       unsigned FragmentOffset = Fragment->OffsetInBits;
1159       SmallVector<uint64_t, 3> Ops(DIExpr->elements_begin(),
1160                                    DIExpr->elements_end() - 3);
1161       Ops.push_back(dwarf::DW_OP_LLVM_fragment);
1162       Ops.push_back(FragmentOffset);
1163       const DataLayout &DL = DII->getModule()->getDataLayout();
1164       Ops.push_back(DL.getTypeSizeInBits(ExtendedArg->getType()));
1165       DIExpr = Builder.createExpression(Ops);
1166     }
1167     DV = ExtendedArg;
1168   }
1169   if (!LdStHasDebugValue(DIVar, DIExpr, SI))
1170     Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, DII->getDebugLoc(),
1171                                     SI);
1172 }
1173 
1174 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1175 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1176 void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII,
1177                                            LoadInst *LI, DIBuilder &Builder) {
1178   auto *DIVar = DII->getVariable();
1179   auto *DIExpr = DII->getExpression();
1180   assert(DIVar && "Missing variable");
1181 
1182   if (LdStHasDebugValue(DIVar, DIExpr, LI))
1183     return;
1184 
1185   // We are now tracking the loaded value instead of the address. In the
1186   // future if multi-location support is added to the IR, it might be
1187   // preferable to keep tracking both the loaded value and the original
1188   // address in case the alloca can not be elided.
1189   Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
1190       LI, DIVar, DIExpr, DII->getDebugLoc(), (Instruction *)nullptr);
1191   DbgValue->insertAfter(LI);
1192 }
1193 
1194 /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
1195 /// llvm.dbg.declare or llvm.dbg.addr intrinsic.
1196 void llvm::ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII,
1197                                            PHINode *APN, DIBuilder &Builder) {
1198   auto *DIVar = DII->getVariable();
1199   auto *DIExpr = DII->getExpression();
1200   assert(DIVar && "Missing variable");
1201 
1202   if (PhiHasDebugValue(DIVar, DIExpr, APN))
1203     return;
1204 
1205   BasicBlock *BB = APN->getParent();
1206   auto InsertionPt = BB->getFirstInsertionPt();
1207 
1208   // The block may be a catchswitch block, which does not have a valid
1209   // insertion point.
1210   // FIXME: Insert dbg.value markers in the successors when appropriate.
1211   if (InsertionPt != BB->end())
1212     Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, DII->getDebugLoc(),
1213                                     &*InsertionPt);
1214 }
1215 
1216 /// Determine whether this alloca is either a VLA or an array.
1217 static bool isArray(AllocaInst *AI) {
1218   return AI->isArrayAllocation() ||
1219     AI->getType()->getElementType()->isArrayTy();
1220 }
1221 
1222 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1223 /// of llvm.dbg.value intrinsics.
1224 bool llvm::LowerDbgDeclare(Function &F) {
1225   DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1226   SmallVector<DbgDeclareInst *, 4> Dbgs;
1227   for (auto &FI : F)
1228     for (Instruction &BI : FI)
1229       if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
1230         Dbgs.push_back(DDI);
1231 
1232   if (Dbgs.empty())
1233     return false;
1234 
1235   for (auto &I : Dbgs) {
1236     DbgDeclareInst *DDI = I;
1237     AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1238     // If this is an alloca for a scalar variable, insert a dbg.value
1239     // at each load and store to the alloca and erase the dbg.declare.
1240     // The dbg.values allow tracking a variable even if it is not
1241     // stored on the stack, while the dbg.declare can only describe
1242     // the stack slot (and at a lexical-scope granularity). Later
1243     // passes will attempt to elide the stack slot.
1244     if (AI && !isArray(AI)) {
1245       for (auto &AIUse : AI->uses()) {
1246         User *U = AIUse.getUser();
1247         if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1248           if (AIUse.getOperandNo() == 1)
1249             ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
1250         } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1251           ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1252         } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1253           // This is a call by-value or some other instruction that
1254           // takes a pointer to the variable. Insert a *value*
1255           // intrinsic that describes the alloca.
1256           DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(),
1257                                       DDI->getExpression(), DDI->getDebugLoc(),
1258                                       CI);
1259         }
1260       }
1261       DDI->eraseFromParent();
1262     }
1263   }
1264   return true;
1265 }
1266 
1267 /// Finds all intrinsics declaring local variables as living in the memory that
1268 /// 'V' points to. This may include a mix of dbg.declare and
1269 /// dbg.addr intrinsics.
1270 TinyPtrVector<DbgInfoIntrinsic *> llvm::FindDbgAddrUses(Value *V) {
1271   auto *L = LocalAsMetadata::getIfExists(V);
1272   if (!L)
1273     return {};
1274   auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L);
1275   if (!MDV)
1276     return {};
1277 
1278   TinyPtrVector<DbgInfoIntrinsic *> Declares;
1279   for (User *U : MDV->users()) {
1280     if (auto *DII = dyn_cast<DbgInfoIntrinsic>(U))
1281       if (DII->isAddressOfVariable())
1282         Declares.push_back(DII);
1283   }
1284 
1285   return Declares;
1286 }
1287 
1288 void llvm::findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V) {
1289   if (auto *L = LocalAsMetadata::getIfExists(V))
1290     if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1291       for (User *U : MDV->users())
1292         if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U))
1293           DbgValues.push_back(DVI);
1294 }
1295 
1296 bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress,
1297                              Instruction *InsertBefore, DIBuilder &Builder,
1298                              bool Deref, int Offset) {
1299   auto DbgAddrs = FindDbgAddrUses(Address);
1300   for (DbgInfoIntrinsic *DII : DbgAddrs) {
1301     DebugLoc Loc = DII->getDebugLoc();
1302     auto *DIVar = DII->getVariable();
1303     auto *DIExpr = DII->getExpression();
1304     assert(DIVar && "Missing variable");
1305     DIExpr = DIExpression::prepend(DIExpr, Deref, Offset);
1306     // Insert llvm.dbg.declare immediately after InsertBefore, and remove old
1307     // llvm.dbg.declare.
1308     Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore);
1309     if (DII == InsertBefore)
1310       InsertBefore = &*std::next(InsertBefore->getIterator());
1311     DII->eraseFromParent();
1312   }
1313   return !DbgAddrs.empty();
1314 }
1315 
1316 bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
1317                                       DIBuilder &Builder, bool Deref, int Offset) {
1318   return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder,
1319                            Deref, Offset);
1320 }
1321 
1322 static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
1323                                         DIBuilder &Builder, int Offset) {
1324   DebugLoc Loc = DVI->getDebugLoc();
1325   auto *DIVar = DVI->getVariable();
1326   auto *DIExpr = DVI->getExpression();
1327   assert(DIVar && "Missing variable");
1328 
1329   // This is an alloca-based llvm.dbg.value. The first thing it should do with
1330   // the alloca pointer is dereference it. Otherwise we don't know how to handle
1331   // it and give up.
1332   if (!DIExpr || DIExpr->getNumElements() < 1 ||
1333       DIExpr->getElement(0) != dwarf::DW_OP_deref)
1334     return;
1335 
1336   // Insert the offset immediately after the first deref.
1337   // We could just change the offset argument of dbg.value, but it's unsigned...
1338   if (Offset) {
1339     SmallVector<uint64_t, 4> Ops;
1340     Ops.push_back(dwarf::DW_OP_deref);
1341     DIExpression::appendOffset(Ops, Offset);
1342     Ops.append(DIExpr->elements_begin() + 1, DIExpr->elements_end());
1343     DIExpr = Builder.createExpression(Ops);
1344   }
1345 
1346   Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI);
1347   DVI->eraseFromParent();
1348 }
1349 
1350 void llvm::replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
1351                                     DIBuilder &Builder, int Offset) {
1352   if (auto *L = LocalAsMetadata::getIfExists(AI))
1353     if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
1354       for (auto UI = MDV->use_begin(), UE = MDV->use_end(); UI != UE;) {
1355         Use &U = *UI++;
1356         if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
1357           replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1358       }
1359 }
1360 
1361 void llvm::salvageDebugInfo(Instruction &I) {
1362   SmallVector<DbgValueInst *, 1> DbgValues;
1363   auto &M = *I.getModule();
1364 
1365   auto MDWrap = [&](Value *V) {
1366     return MetadataAsValue::get(I.getContext(), ValueAsMetadata::get(V));
1367   };
1368 
1369   if (isa<BitCastInst>(&I)) {
1370     findDbgValues(DbgValues, &I);
1371     for (auto *DVI : DbgValues) {
1372       // Bitcasts are entirely irrelevant for debug info. Rewrite the dbg.value
1373       // to use the cast's source.
1374       DVI->setOperand(0, MDWrap(I.getOperand(0)));
1375       DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n');
1376     }
1377   } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1378     findDbgValues(DbgValues, &I);
1379     for (auto *DVI : DbgValues) {
1380       unsigned BitWidth =
1381           M.getDataLayout().getPointerSizeInBits(GEP->getPointerAddressSpace());
1382       APInt Offset(BitWidth, 0);
1383       // Rewrite a constant GEP into a DIExpression.  Since we are performing
1384       // arithmetic to compute the variable's *value* in the DIExpression, we
1385       // need to mark the expression with a DW_OP_stack_value.
1386       if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) {
1387         auto *DIExpr = DVI->getExpression();
1388         // GEP offsets are i32 and thus always fit into an int64_t.
1389         DIExpr = DIExpression::prepend(DIExpr, DIExpression::NoDeref,
1390                                        Offset.getSExtValue(),
1391                                        DIExpression::WithStackValue);
1392         DVI->setOperand(0, MDWrap(I.getOperand(0)));
1393         DVI->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr));
1394         DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n');
1395       }
1396     }
1397   } else if (isa<LoadInst>(&I)) {
1398     findDbgValues(DbgValues, &I);
1399     for (auto *DVI : DbgValues) {
1400       // Rewrite the load into DW_OP_deref.
1401       auto *DIExpr = DVI->getExpression();
1402       DIExpr = DIExpression::prepend(DIExpr, DIExpression::WithDeref);
1403       DVI->setOperand(0, MDWrap(I.getOperand(0)));
1404       DVI->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr));
1405       DEBUG(dbgs() << "SALVAGE:  " << *DVI << '\n');
1406     }
1407   }
1408 }
1409 
1410 unsigned llvm::removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB) {
1411   unsigned NumDeadInst = 0;
1412   // Delete the instructions backwards, as it has a reduced likelihood of
1413   // having to update as many def-use and use-def chains.
1414   Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
1415   while (EndInst != &BB->front()) {
1416     // Delete the next to last instruction.
1417     Instruction *Inst = &*--EndInst->getIterator();
1418     if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
1419       Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
1420     if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
1421       EndInst = Inst;
1422       continue;
1423     }
1424     if (!isa<DbgInfoIntrinsic>(Inst))
1425       ++NumDeadInst;
1426     Inst->eraseFromParent();
1427   }
1428   return NumDeadInst;
1429 }
1430 
1431 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
1432                                    bool PreserveLCSSA) {
1433   BasicBlock *BB = I->getParent();
1434   // Loop over all of the successors, removing BB's entry from any PHI
1435   // nodes.
1436   for (BasicBlock *Successor : successors(BB))
1437     Successor->removePredecessor(BB, PreserveLCSSA);
1438 
1439   // Insert a call to llvm.trap right before this.  This turns the undefined
1440   // behavior into a hard fail instead of falling through into random code.
1441   if (UseLLVMTrap) {
1442     Function *TrapFn =
1443       Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
1444     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
1445     CallTrap->setDebugLoc(I->getDebugLoc());
1446   }
1447   new UnreachableInst(I->getContext(), I);
1448 
1449   // All instructions after this are dead.
1450   unsigned NumInstrsRemoved = 0;
1451   BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
1452   while (BBI != BBE) {
1453     if (!BBI->use_empty())
1454       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
1455     BB->getInstList().erase(BBI++);
1456     ++NumInstrsRemoved;
1457   }
1458   return NumInstrsRemoved;
1459 }
1460 
1461 /// changeToCall - Convert the specified invoke into a normal call.
1462 static void changeToCall(InvokeInst *II) {
1463   SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
1464   SmallVector<OperandBundleDef, 1> OpBundles;
1465   II->getOperandBundlesAsDefs(OpBundles);
1466   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
1467                                        "", II);
1468   NewCall->takeName(II);
1469   NewCall->setCallingConv(II->getCallingConv());
1470   NewCall->setAttributes(II->getAttributes());
1471   NewCall->setDebugLoc(II->getDebugLoc());
1472   II->replaceAllUsesWith(NewCall);
1473 
1474   // Follow the call by a branch to the normal destination.
1475   BranchInst::Create(II->getNormalDest(), II);
1476 
1477   // Update PHI nodes in the unwind destination
1478   II->getUnwindDest()->removePredecessor(II->getParent());
1479   II->eraseFromParent();
1480 }
1481 
1482 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
1483                                                    BasicBlock *UnwindEdge) {
1484   BasicBlock *BB = CI->getParent();
1485 
1486   // Convert this function call into an invoke instruction.  First, split the
1487   // basic block.
1488   BasicBlock *Split =
1489       BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc");
1490 
1491   // Delete the unconditional branch inserted by splitBasicBlock
1492   BB->getInstList().pop_back();
1493 
1494   // Create the new invoke instruction.
1495   SmallVector<Value *, 8> InvokeArgs(CI->arg_begin(), CI->arg_end());
1496   SmallVector<OperandBundleDef, 1> OpBundles;
1497 
1498   CI->getOperandBundlesAsDefs(OpBundles);
1499 
1500   // Note: we're round tripping operand bundles through memory here, and that
1501   // can potentially be avoided with a cleverer API design that we do not have
1502   // as of this time.
1503 
1504   InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, UnwindEdge,
1505                                       InvokeArgs, OpBundles, CI->getName(), BB);
1506   II->setDebugLoc(CI->getDebugLoc());
1507   II->setCallingConv(CI->getCallingConv());
1508   II->setAttributes(CI->getAttributes());
1509 
1510   // Make sure that anything using the call now uses the invoke!  This also
1511   // updates the CallGraph if present, because it uses a WeakTrackingVH.
1512   CI->replaceAllUsesWith(II);
1513 
1514   // Delete the original call
1515   Split->getInstList().pop_front();
1516   return Split;
1517 }
1518 
1519 static bool markAliveBlocks(Function &F,
1520                             SmallPtrSetImpl<BasicBlock*> &Reachable) {
1521   SmallVector<BasicBlock*, 128> Worklist;
1522   BasicBlock *BB = &F.front();
1523   Worklist.push_back(BB);
1524   Reachable.insert(BB);
1525   bool Changed = false;
1526   do {
1527     BB = Worklist.pop_back_val();
1528 
1529     // Do a quick scan of the basic block, turning any obviously unreachable
1530     // instructions into LLVM unreachable insts.  The instruction combining pass
1531     // canonicalizes unreachable insts into stores to null or undef.
1532     for (Instruction &I : *BB) {
1533       // Assumptions that are known to be false are equivalent to unreachable.
1534       // Also, if the condition is undefined, then we make the choice most
1535       // beneficial to the optimizer, and choose that to also be unreachable.
1536       if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
1537         if (II->getIntrinsicID() == Intrinsic::assume) {
1538           if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
1539             // Don't insert a call to llvm.trap right before the unreachable.
1540             changeToUnreachable(II, false);
1541             Changed = true;
1542             break;
1543           }
1544         }
1545 
1546         if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
1547           // A call to the guard intrinsic bails out of the current compilation
1548           // unit if the predicate passed to it is false.  If the predicate is a
1549           // constant false, then we know the guard will bail out of the current
1550           // compile unconditionally, so all code following it is dead.
1551           //
1552           // Note: unlike in llvm.assume, it is not "obviously profitable" for
1553           // guards to treat `undef` as `false` since a guard on `undef` can
1554           // still be useful for widening.
1555           if (match(II->getArgOperand(0), m_Zero()))
1556             if (!isa<UnreachableInst>(II->getNextNode())) {
1557               changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false);
1558               Changed = true;
1559               break;
1560             }
1561         }
1562       }
1563 
1564       if (auto *CI = dyn_cast<CallInst>(&I)) {
1565         Value *Callee = CI->getCalledValue();
1566         if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1567           changeToUnreachable(CI, /*UseLLVMTrap=*/false);
1568           Changed = true;
1569           break;
1570         }
1571         if (CI->doesNotReturn()) {
1572           // If we found a call to a no-return function, insert an unreachable
1573           // instruction after it.  Make sure there isn't *already* one there
1574           // though.
1575           if (!isa<UnreachableInst>(CI->getNextNode())) {
1576             // Don't insert a call to llvm.trap right before the unreachable.
1577             changeToUnreachable(CI->getNextNode(), false);
1578             Changed = true;
1579           }
1580           break;
1581         }
1582       }
1583 
1584       // Store to undef and store to null are undefined and used to signal that
1585       // they should be changed to unreachable by passes that can't modify the
1586       // CFG.
1587       if (auto *SI = dyn_cast<StoreInst>(&I)) {
1588         // Don't touch volatile stores.
1589         if (SI->isVolatile()) continue;
1590 
1591         Value *Ptr = SI->getOperand(1);
1592 
1593         if (isa<UndefValue>(Ptr) ||
1594             (isa<ConstantPointerNull>(Ptr) &&
1595              SI->getPointerAddressSpace() == 0)) {
1596           changeToUnreachable(SI, true);
1597           Changed = true;
1598           break;
1599         }
1600       }
1601     }
1602 
1603     TerminatorInst *Terminator = BB->getTerminator();
1604     if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
1605       // Turn invokes that call 'nounwind' functions into ordinary calls.
1606       Value *Callee = II->getCalledValue();
1607       if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1608         changeToUnreachable(II, true);
1609         Changed = true;
1610       } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
1611         if (II->use_empty() && II->onlyReadsMemory()) {
1612           // jump to the normal destination branch.
1613           BranchInst::Create(II->getNormalDest(), II);
1614           II->getUnwindDest()->removePredecessor(II->getParent());
1615           II->eraseFromParent();
1616         } else
1617           changeToCall(II);
1618         Changed = true;
1619       }
1620     } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
1621       // Remove catchpads which cannot be reached.
1622       struct CatchPadDenseMapInfo {
1623         static CatchPadInst *getEmptyKey() {
1624           return DenseMapInfo<CatchPadInst *>::getEmptyKey();
1625         }
1626 
1627         static CatchPadInst *getTombstoneKey() {
1628           return DenseMapInfo<CatchPadInst *>::getTombstoneKey();
1629         }
1630 
1631         static unsigned getHashValue(CatchPadInst *CatchPad) {
1632           return static_cast<unsigned>(hash_combine_range(
1633               CatchPad->value_op_begin(), CatchPad->value_op_end()));
1634         }
1635 
1636         static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
1637           if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
1638               RHS == getEmptyKey() || RHS == getTombstoneKey())
1639             return LHS == RHS;
1640           return LHS->isIdenticalTo(RHS);
1641         }
1642       };
1643 
1644       // Set of unique CatchPads.
1645       SmallDenseMap<CatchPadInst *, detail::DenseSetEmpty, 4,
1646                     CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
1647           HandlerSet;
1648       detail::DenseSetEmpty Empty;
1649       for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
1650                                              E = CatchSwitch->handler_end();
1651            I != E; ++I) {
1652         BasicBlock *HandlerBB = *I;
1653         auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
1654         if (!HandlerSet.insert({CatchPad, Empty}).second) {
1655           CatchSwitch->removeHandler(I);
1656           --I;
1657           --E;
1658           Changed = true;
1659         }
1660       }
1661     }
1662 
1663     Changed |= ConstantFoldTerminator(BB, true);
1664     for (BasicBlock *Successor : successors(BB))
1665       if (Reachable.insert(Successor).second)
1666         Worklist.push_back(Successor);
1667   } while (!Worklist.empty());
1668   return Changed;
1669 }
1670 
1671 void llvm::removeUnwindEdge(BasicBlock *BB) {
1672   TerminatorInst *TI = BB->getTerminator();
1673 
1674   if (auto *II = dyn_cast<InvokeInst>(TI)) {
1675     changeToCall(II);
1676     return;
1677   }
1678 
1679   TerminatorInst *NewTI;
1680   BasicBlock *UnwindDest;
1681 
1682   if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
1683     NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
1684     UnwindDest = CRI->getUnwindDest();
1685   } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
1686     auto *NewCatchSwitch = CatchSwitchInst::Create(
1687         CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
1688         CatchSwitch->getName(), CatchSwitch);
1689     for (BasicBlock *PadBB : CatchSwitch->handlers())
1690       NewCatchSwitch->addHandler(PadBB);
1691 
1692     NewTI = NewCatchSwitch;
1693     UnwindDest = CatchSwitch->getUnwindDest();
1694   } else {
1695     llvm_unreachable("Could not find unwind successor");
1696   }
1697 
1698   NewTI->takeName(TI);
1699   NewTI->setDebugLoc(TI->getDebugLoc());
1700   UnwindDest->removePredecessor(BB);
1701   TI->replaceAllUsesWith(NewTI);
1702   TI->eraseFromParent();
1703 }
1704 
1705 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
1706 /// if they are in a dead cycle.  Return true if a change was made, false
1707 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
1708 /// after modifying the CFG.
1709 bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) {
1710   SmallPtrSet<BasicBlock*, 16> Reachable;
1711   bool Changed = markAliveBlocks(F, Reachable);
1712 
1713   // If there are unreachable blocks in the CFG...
1714   if (Reachable.size() == F.size())
1715     return Changed;
1716 
1717   assert(Reachable.size() < F.size());
1718   NumRemoved += F.size()-Reachable.size();
1719 
1720   // Loop over all of the basic blocks that are not reachable, dropping all of
1721   // their internal references...
1722   for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
1723     if (Reachable.count(&*BB))
1724       continue;
1725 
1726     for (BasicBlock *Successor : successors(&*BB))
1727       if (Reachable.count(Successor))
1728         Successor->removePredecessor(&*BB);
1729     if (LVI)
1730       LVI->eraseBlock(&*BB);
1731     BB->dropAllReferences();
1732   }
1733 
1734   for (Function::iterator I = ++F.begin(); I != F.end();)
1735     if (!Reachable.count(&*I))
1736       I = F.getBasicBlockList().erase(I);
1737     else
1738       ++I;
1739 
1740   return true;
1741 }
1742 
1743 void llvm::combineMetadata(Instruction *K, const Instruction *J,
1744                            ArrayRef<unsigned> KnownIDs) {
1745   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
1746   K->dropUnknownNonDebugMetadata(KnownIDs);
1747   K->getAllMetadataOtherThanDebugLoc(Metadata);
1748   for (const auto &MD : Metadata) {
1749     unsigned Kind = MD.first;
1750     MDNode *JMD = J->getMetadata(Kind);
1751     MDNode *KMD = MD.second;
1752 
1753     switch (Kind) {
1754       default:
1755         K->setMetadata(Kind, nullptr); // Remove unknown metadata
1756         break;
1757       case LLVMContext::MD_dbg:
1758         llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
1759       case LLVMContext::MD_tbaa:
1760         K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
1761         break;
1762       case LLVMContext::MD_alias_scope:
1763         K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
1764         break;
1765       case LLVMContext::MD_noalias:
1766       case LLVMContext::MD_mem_parallel_loop_access:
1767         K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
1768         break;
1769       case LLVMContext::MD_range:
1770         K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
1771         break;
1772       case LLVMContext::MD_fpmath:
1773         K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
1774         break;
1775       case LLVMContext::MD_invariant_load:
1776         // Only set the !invariant.load if it is present in both instructions.
1777         K->setMetadata(Kind, JMD);
1778         break;
1779       case LLVMContext::MD_nonnull:
1780         // Only set the !nonnull if it is present in both instructions.
1781         K->setMetadata(Kind, JMD);
1782         break;
1783       case LLVMContext::MD_invariant_group:
1784         // Preserve !invariant.group in K.
1785         break;
1786       case LLVMContext::MD_align:
1787         K->setMetadata(Kind,
1788           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
1789         break;
1790       case LLVMContext::MD_dereferenceable:
1791       case LLVMContext::MD_dereferenceable_or_null:
1792         K->setMetadata(Kind,
1793           MDNode::getMostGenericAlignmentOrDereferenceable(JMD, KMD));
1794         break;
1795     }
1796   }
1797   // Set !invariant.group from J if J has it. If both instructions have it
1798   // then we will just pick it from J - even when they are different.
1799   // Also make sure that K is load or store - f.e. combining bitcast with load
1800   // could produce bitcast with invariant.group metadata, which is invalid.
1801   // FIXME: we should try to preserve both invariant.group md if they are
1802   // different, but right now instruction can only have one invariant.group.
1803   if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
1804     if (isa<LoadInst>(K) || isa<StoreInst>(K))
1805       K->setMetadata(LLVMContext::MD_invariant_group, JMD);
1806 }
1807 
1808 void llvm::combineMetadataForCSE(Instruction *K, const Instruction *J) {
1809   unsigned KnownIDs[] = {
1810       LLVMContext::MD_tbaa,            LLVMContext::MD_alias_scope,
1811       LLVMContext::MD_noalias,         LLVMContext::MD_range,
1812       LLVMContext::MD_invariant_load,  LLVMContext::MD_nonnull,
1813       LLVMContext::MD_invariant_group, LLVMContext::MD_align,
1814       LLVMContext::MD_dereferenceable,
1815       LLVMContext::MD_dereferenceable_or_null};
1816   combineMetadata(K, J, KnownIDs);
1817 }
1818 
1819 template <typename RootType, typename DominatesFn>
1820 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
1821                                          const RootType &Root,
1822                                          const DominatesFn &Dominates) {
1823   assert(From->getType() == To->getType());
1824 
1825   unsigned Count = 0;
1826   for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
1827        UI != UE;) {
1828     Use &U = *UI++;
1829     if (!Dominates(Root, U))
1830       continue;
1831     U.set(To);
1832     DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as "
1833                  << *To << " in " << *U << "\n");
1834     ++Count;
1835   }
1836   return Count;
1837 }
1838 
1839 unsigned llvm::replaceNonLocalUsesWith(Instruction *From, Value *To) {
1840    assert(From->getType() == To->getType());
1841    auto *BB = From->getParent();
1842    unsigned Count = 0;
1843 
1844   for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
1845        UI != UE;) {
1846     Use &U = *UI++;
1847     auto *I = cast<Instruction>(U.getUser());
1848     if (I->getParent() == BB)
1849       continue;
1850     U.set(To);
1851     ++Count;
1852   }
1853   return Count;
1854 }
1855 
1856 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
1857                                         DominatorTree &DT,
1858                                         const BasicBlockEdge &Root) {
1859   auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
1860     return DT.dominates(Root, U);
1861   };
1862   return ::replaceDominatedUsesWith(From, To, Root, Dominates);
1863 }
1864 
1865 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
1866                                         DominatorTree &DT,
1867                                         const BasicBlock *BB) {
1868   auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
1869     auto *I = cast<Instruction>(U.getUser())->getParent();
1870     return DT.properlyDominates(BB, I);
1871   };
1872   return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
1873 }
1874 
1875 bool llvm::callsGCLeafFunction(ImmutableCallSite CS,
1876                                const TargetLibraryInfo &TLI) {
1877   // Check if the function is specifically marked as a gc leaf function.
1878   if (CS.hasFnAttr("gc-leaf-function"))
1879     return true;
1880   if (const Function *F = CS.getCalledFunction()) {
1881     if (F->hasFnAttribute("gc-leaf-function"))
1882       return true;
1883 
1884     if (auto IID = F->getIntrinsicID())
1885       // Most LLVM intrinsics do not take safepoints.
1886       return IID != Intrinsic::experimental_gc_statepoint &&
1887              IID != Intrinsic::experimental_deoptimize;
1888   }
1889 
1890   // Lib calls can be materialized by some passes, and won't be
1891   // marked as 'gc-leaf-function.' All available Libcalls are
1892   // GC-leaf.
1893   LibFunc LF;
1894   if (TLI.getLibFunc(CS, LF)) {
1895     return TLI.has(LF);
1896   }
1897 
1898   return false;
1899 }
1900 
1901 void llvm::copyNonnullMetadata(const LoadInst &OldLI, MDNode *N,
1902                                LoadInst &NewLI) {
1903   auto *NewTy = NewLI.getType();
1904 
1905   // This only directly applies if the new type is also a pointer.
1906   if (NewTy->isPointerTy()) {
1907     NewLI.setMetadata(LLVMContext::MD_nonnull, N);
1908     return;
1909   }
1910 
1911   // The only other translation we can do is to integral loads with !range
1912   // metadata.
1913   if (!NewTy->isIntegerTy())
1914     return;
1915 
1916   MDBuilder MDB(NewLI.getContext());
1917   const Value *Ptr = OldLI.getPointerOperand();
1918   auto *ITy = cast<IntegerType>(NewTy);
1919   auto *NullInt = ConstantExpr::getPtrToInt(
1920       ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
1921   auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
1922   NewLI.setMetadata(LLVMContext::MD_range,
1923                     MDB.createRange(NonNullInt, NullInt));
1924 }
1925 
1926 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
1927                              MDNode *N, LoadInst &NewLI) {
1928   auto *NewTy = NewLI.getType();
1929 
1930   // Give up unless it is converted to a pointer where there is a single very
1931   // valuable mapping we can do reliably.
1932   // FIXME: It would be nice to propagate this in more ways, but the type
1933   // conversions make it hard.
1934   if (!NewTy->isPointerTy())
1935     return;
1936 
1937   unsigned BitWidth = DL.getTypeSizeInBits(NewTy);
1938   if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
1939     MDNode *NN = MDNode::get(OldLI.getContext(), None);
1940     NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
1941   }
1942 }
1943 
1944 namespace {
1945 
1946 /// A potential constituent of a bitreverse or bswap expression. See
1947 /// collectBitParts for a fuller explanation.
1948 struct BitPart {
1949   BitPart(Value *P, unsigned BW) : Provider(P) {
1950     Provenance.resize(BW);
1951   }
1952 
1953   /// The Value that this is a bitreverse/bswap of.
1954   Value *Provider;
1955 
1956   /// The "provenance" of each bit. Provenance[A] = B means that bit A
1957   /// in Provider becomes bit B in the result of this expression.
1958   SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
1959 
1960   enum { Unset = -1 };
1961 };
1962 
1963 } // end anonymous namespace
1964 
1965 /// Analyze the specified subexpression and see if it is capable of providing
1966 /// pieces of a bswap or bitreverse. The subexpression provides a potential
1967 /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in
1968 /// the output of the expression came from a corresponding bit in some other
1969 /// value. This function is recursive, and the end result is a mapping of
1970 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
1971 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
1972 ///
1973 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
1974 /// that the expression deposits the low byte of %X into the high byte of the
1975 /// result and that all other bits are zero. This expression is accepted and a
1976 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
1977 /// [0-7].
1978 ///
1979 /// To avoid revisiting values, the BitPart results are memoized into the
1980 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
1981 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
1982 /// store BitParts objects, not pointers. As we need the concept of a nullptr
1983 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
1984 /// type instead to provide the same functionality.
1985 ///
1986 /// Because we pass around references into \c BPS, we must use a container that
1987 /// does not invalidate internal references (std::map instead of DenseMap).
1988 static const Optional<BitPart> &
1989 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
1990                 std::map<Value *, Optional<BitPart>> &BPS) {
1991   auto I = BPS.find(V);
1992   if (I != BPS.end())
1993     return I->second;
1994 
1995   auto &Result = BPS[V] = None;
1996   auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
1997 
1998   if (Instruction *I = dyn_cast<Instruction>(V)) {
1999     // If this is an or instruction, it may be an inner node of the bswap.
2000     if (I->getOpcode() == Instruction::Or) {
2001       auto &A = collectBitParts(I->getOperand(0), MatchBSwaps,
2002                                 MatchBitReversals, BPS);
2003       auto &B = collectBitParts(I->getOperand(1), MatchBSwaps,
2004                                 MatchBitReversals, BPS);
2005       if (!A || !B)
2006         return Result;
2007 
2008       // Try and merge the two together.
2009       if (!A->Provider || A->Provider != B->Provider)
2010         return Result;
2011 
2012       Result = BitPart(A->Provider, BitWidth);
2013       for (unsigned i = 0; i < A->Provenance.size(); ++i) {
2014         if (A->Provenance[i] != BitPart::Unset &&
2015             B->Provenance[i] != BitPart::Unset &&
2016             A->Provenance[i] != B->Provenance[i])
2017           return Result = None;
2018 
2019         if (A->Provenance[i] == BitPart::Unset)
2020           Result->Provenance[i] = B->Provenance[i];
2021         else
2022           Result->Provenance[i] = A->Provenance[i];
2023       }
2024 
2025       return Result;
2026     }
2027 
2028     // If this is a logical shift by a constant, recurse then shift the result.
2029     if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
2030       unsigned BitShift =
2031           cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
2032       // Ensure the shift amount is defined.
2033       if (BitShift > BitWidth)
2034         return Result;
2035 
2036       auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2037                                   MatchBitReversals, BPS);
2038       if (!Res)
2039         return Result;
2040       Result = Res;
2041 
2042       // Perform the "shift" on BitProvenance.
2043       auto &P = Result->Provenance;
2044       if (I->getOpcode() == Instruction::Shl) {
2045         P.erase(std::prev(P.end(), BitShift), P.end());
2046         P.insert(P.begin(), BitShift, BitPart::Unset);
2047       } else {
2048         P.erase(P.begin(), std::next(P.begin(), BitShift));
2049         P.insert(P.end(), BitShift, BitPart::Unset);
2050       }
2051 
2052       return Result;
2053     }
2054 
2055     // If this is a logical 'and' with a mask that clears bits, recurse then
2056     // unset the appropriate bits.
2057     if (I->getOpcode() == Instruction::And &&
2058         isa<ConstantInt>(I->getOperand(1))) {
2059       APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1);
2060       const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
2061 
2062       // Check that the mask allows a multiple of 8 bits for a bswap, for an
2063       // early exit.
2064       unsigned NumMaskedBits = AndMask.countPopulation();
2065       if (!MatchBitReversals && NumMaskedBits % 8 != 0)
2066         return Result;
2067 
2068       auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2069                                   MatchBitReversals, BPS);
2070       if (!Res)
2071         return Result;
2072       Result = Res;
2073 
2074       for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1)
2075         // If the AndMask is zero for this bit, clear the bit.
2076         if ((AndMask & Bit) == 0)
2077           Result->Provenance[i] = BitPart::Unset;
2078       return Result;
2079     }
2080 
2081     // If this is a zext instruction zero extend the result.
2082     if (I->getOpcode() == Instruction::ZExt) {
2083       auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2084                                   MatchBitReversals, BPS);
2085       if (!Res)
2086         return Result;
2087 
2088       Result = BitPart(Res->Provider, BitWidth);
2089       auto NarrowBitWidth =
2090           cast<IntegerType>(cast<ZExtInst>(I)->getSrcTy())->getBitWidth();
2091       for (unsigned i = 0; i < NarrowBitWidth; ++i)
2092         Result->Provenance[i] = Res->Provenance[i];
2093       for (unsigned i = NarrowBitWidth; i < BitWidth; ++i)
2094         Result->Provenance[i] = BitPart::Unset;
2095       return Result;
2096     }
2097   }
2098 
2099   // Okay, we got to something that isn't a shift, 'or' or 'and'.  This must be
2100   // the input value to the bswap/bitreverse.
2101   Result = BitPart(V, BitWidth);
2102   for (unsigned i = 0; i < BitWidth; ++i)
2103     Result->Provenance[i] = i;
2104   return Result;
2105 }
2106 
2107 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
2108                                           unsigned BitWidth) {
2109   if (From % 8 != To % 8)
2110     return false;
2111   // Convert from bit indices to byte indices and check for a byte reversal.
2112   From >>= 3;
2113   To >>= 3;
2114   BitWidth >>= 3;
2115   return From == BitWidth - To - 1;
2116 }
2117 
2118 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
2119                                                unsigned BitWidth) {
2120   return From == BitWidth - To - 1;
2121 }
2122 
2123 /// Given an OR instruction, check to see if this is a bitreverse
2124 /// idiom. If so, insert the new intrinsic and return true.
2125 bool llvm::recognizeBSwapOrBitReverseIdiom(
2126     Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
2127     SmallVectorImpl<Instruction *> &InsertedInsts) {
2128   if (Operator::getOpcode(I) != Instruction::Or)
2129     return false;
2130   if (!MatchBSwaps && !MatchBitReversals)
2131     return false;
2132   IntegerType *ITy = dyn_cast<IntegerType>(I->getType());
2133   if (!ITy || ITy->getBitWidth() > 128)
2134     return false;   // Can't do vectors or integers > 128 bits.
2135   unsigned BW = ITy->getBitWidth();
2136 
2137   unsigned DemandedBW = BW;
2138   IntegerType *DemandedTy = ITy;
2139   if (I->hasOneUse()) {
2140     if (TruncInst *Trunc = dyn_cast<TruncInst>(I->user_back())) {
2141       DemandedTy = cast<IntegerType>(Trunc->getType());
2142       DemandedBW = DemandedTy->getBitWidth();
2143     }
2144   }
2145 
2146   // Try to find all the pieces corresponding to the bswap.
2147   std::map<Value *, Optional<BitPart>> BPS;
2148   auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS);
2149   if (!Res)
2150     return false;
2151   auto &BitProvenance = Res->Provenance;
2152 
2153   // Now, is the bit permutation correct for a bswap or a bitreverse? We can
2154   // only byteswap values with an even number of bytes.
2155   bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true;
2156   for (unsigned i = 0; i < DemandedBW; ++i) {
2157     OKForBSwap &=
2158         bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW);
2159     OKForBitReverse &=
2160         bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW);
2161   }
2162 
2163   Intrinsic::ID Intrin;
2164   if (OKForBSwap && MatchBSwaps)
2165     Intrin = Intrinsic::bswap;
2166   else if (OKForBitReverse && MatchBitReversals)
2167     Intrin = Intrinsic::bitreverse;
2168   else
2169     return false;
2170 
2171   if (ITy != DemandedTy) {
2172     Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
2173     Value *Provider = Res->Provider;
2174     IntegerType *ProviderTy = cast<IntegerType>(Provider->getType());
2175     // We may need to truncate the provider.
2176     if (DemandedTy != ProviderTy) {
2177       auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy,
2178                                      "trunc", I);
2179       InsertedInsts.push_back(Trunc);
2180       Provider = Trunc;
2181     }
2182     auto *CI = CallInst::Create(F, Provider, "rev", I);
2183     InsertedInsts.push_back(CI);
2184     auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I);
2185     InsertedInsts.push_back(ExtInst);
2186     return true;
2187   }
2188 
2189   Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy);
2190   InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I));
2191   return true;
2192 }
2193 
2194 // CodeGen has special handling for some string functions that may replace
2195 // them with target-specific intrinsics.  Since that'd skip our interceptors
2196 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
2197 // we mark affected calls as NoBuiltin, which will disable optimization
2198 // in CodeGen.
2199 void llvm::maybeMarkSanitizerLibraryCallNoBuiltin(
2200     CallInst *CI, const TargetLibraryInfo *TLI) {
2201   Function *F = CI->getCalledFunction();
2202   LibFunc Func;
2203   if (F && !F->hasLocalLinkage() && F->hasName() &&
2204       TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
2205       !F->doesNotAccessMemory())
2206     CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin);
2207 }
2208 
2209 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
2210   // We can't have a PHI with a metadata type.
2211   if (I->getOperand(OpIdx)->getType()->isMetadataTy())
2212     return false;
2213 
2214   // Early exit.
2215   if (!isa<Constant>(I->getOperand(OpIdx)))
2216     return true;
2217 
2218   switch (I->getOpcode()) {
2219   default:
2220     return true;
2221   case Instruction::Call:
2222   case Instruction::Invoke:
2223     // Can't handle inline asm. Skip it.
2224     if (isa<InlineAsm>(ImmutableCallSite(I).getCalledValue()))
2225       return false;
2226     // Many arithmetic intrinsics have no issue taking a
2227     // variable, however it's hard to distingish these from
2228     // specials such as @llvm.frameaddress that require a constant.
2229     if (isa<IntrinsicInst>(I))
2230       return false;
2231 
2232     // Constant bundle operands may need to retain their constant-ness for
2233     // correctness.
2234     if (ImmutableCallSite(I).isBundleOperand(OpIdx))
2235       return false;
2236     return true;
2237   case Instruction::ShuffleVector:
2238     // Shufflevector masks are constant.
2239     return OpIdx != 2;
2240   case Instruction::Switch:
2241   case Instruction::ExtractValue:
2242     // All operands apart from the first are constant.
2243     return OpIdx == 0;
2244   case Instruction::InsertValue:
2245     // All operands apart from the first and the second are constant.
2246     return OpIdx < 2;
2247   case Instruction::Alloca:
2248     // Static allocas (constant size in the entry block) are handled by
2249     // prologue/epilogue insertion so they're free anyway. We definitely don't
2250     // want to make them non-constant.
2251     return !dyn_cast<AllocaInst>(I)->isStaticAlloca();
2252   case Instruction::GetElementPtr:
2253     if (OpIdx == 0)
2254       return true;
2255     gep_type_iterator It = gep_type_begin(I);
2256     for (auto E = std::next(It, OpIdx); It != E; ++It)
2257       if (It.isStruct())
2258         return false;
2259     return true;
2260   }
2261 }
2262