LLVM  7.0.0svn
Local.cpp
Go to the documentation of this file.
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 
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"
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"
48 #include "llvm/IR/DebugLoc.h"
49 #include "llvm/IR/DerivedTypes.h"
50 #include "llvm/IR/Dominators.h"
51 #include "llvm/IR/Function.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"
74 #include "llvm/Support/KnownBits.h"
77 #include <algorithm>
78 #include <cassert>
79 #include <climits>
80 #include <cstdint>
81 #include <iterator>
82 #include <map>
83 #include <utility>
84 
85 using namespace llvm;
86 using namespace llvm::PatternMatch;
87 
88 #define DEBUG_TYPE "local"
89 
90 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
91 
92 //===----------------------------------------------------------------------===//
93 // Local constant propagation.
94 //
95 
96 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
97 /// constant value, convert it into an unconditional branch to the constant
98 /// destination. This is a nontrivial operation because the successors of this
99 /// basic block must have their PHI nodes updated.
100 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
101 /// conditions and indirectbr addresses this might make dead if
102 /// DeleteDeadConditions is true.
103 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
104  const TargetLibraryInfo *TLI,
105  DeferredDominance *DDT) {
106  TerminatorInst *T = BB->getTerminator();
107  IRBuilder<> Builder(T);
108 
109  // Branch - See if we are conditional jumping on constant
110  if (auto *BI = dyn_cast<BranchInst>(T)) {
111  if (BI->isUnconditional()) return false; // Can't optimize uncond branch
112  BasicBlock *Dest1 = BI->getSuccessor(0);
113  BasicBlock *Dest2 = BI->getSuccessor(1);
114 
115  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
116  // Are we branching on constant?
117  // YES. Change to unconditional branch...
118  BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
119  BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;
120 
121  // Let the basic block know that we are letting go of it. Based on this,
122  // it will adjust it's PHI nodes.
123  OldDest->removePredecessor(BB);
124 
125  // Replace the conditional branch with an unconditional one.
126  Builder.CreateBr(Destination);
127  BI->eraseFromParent();
128  if (DDT)
129  DDT->deleteEdge(BB, OldDest);
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)
148  return true;
149  }
150  return false;
151  }
152 
153  if (auto *SI = dyn_cast<SwitchInst>(T)) {
154  // If we are switching on a constant, we can convert the switch to an
155  // unconditional branch.
156  auto *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  BasicBlock *ParentBB = SI->getParent();
201  DefaultDest->removePredecessor(ParentBB);
202  i = SI->removeCase(i);
203  e = SI->case_end();
204  if (DDT)
205  DDT->deleteEdge(ParentBB, DefaultDest);
206  continue;
207  }
208 
209  // Otherwise, check to see if the switch only branches to one destination.
210  // We do this by reseting "TheOnlyDest" to null when we find two non-equal
211  // destinations.
212  if (i->getCaseSuccessor() != TheOnlyDest)
213  TheOnlyDest = nullptr;
214 
215  // Increment this iterator as we haven't removed the case.
216  ++i;
217  }
218 
219  if (CI && !TheOnlyDest) {
220  // Branching on a constant, but not any of the cases, go to the default
221  // successor.
222  TheOnlyDest = SI->getDefaultDest();
223  }
224 
225  // If we found a single destination that we can fold the switch into, do so
226  // now.
227  if (TheOnlyDest) {
228  // Insert the new branch.
229  Builder.CreateBr(TheOnlyDest);
230  BasicBlock *BB = SI->getParent();
231  std::vector <DominatorTree::UpdateType> Updates;
232  if (DDT)
233  Updates.reserve(SI->getNumSuccessors() - 1);
234 
235  // Remove entries from PHI nodes which we no longer branch to...
236  for (BasicBlock *Succ : SI->successors()) {
237  // Found case matching a constant operand?
238  if (Succ == TheOnlyDest) {
239  TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
240  } else {
241  Succ->removePredecessor(BB);
242  if (DDT)
243  Updates.push_back({DominatorTree::Delete, BB, Succ});
244  }
245  }
246 
247  // Delete the old switch.
248  Value *Cond = SI->getCondition();
249  SI->eraseFromParent();
250  if (DeleteDeadConditions)
252  if (DDT)
253  DDT->applyUpdates(Updates);
254  return true;
255  }
256 
257  if (SI->getNumCases() == 1) {
258  // Otherwise, we can fold this switch into a conditional branch
259  // instruction if it has only one non-default destination.
260  auto FirstCase = *SI->case_begin();
261  Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
262  FirstCase.getCaseValue(), "cond");
263 
264  // Insert the new branch.
265  BranchInst *NewBr = Builder.CreateCondBr(Cond,
266  FirstCase.getCaseSuccessor(),
267  SI->getDefaultDest());
268  MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
269  if (MD && MD->getNumOperands() == 3) {
270  ConstantInt *SICase =
271  mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
272  ConstantInt *SIDef =
273  mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
274  assert(SICase && SIDef);
275  // The TrueWeight should be the weight for the single case of SI.
277  MDBuilder(BB->getContext()).
278  createBranchWeights(SICase->getValue().getZExtValue(),
279  SIDef->getValue().getZExtValue()));
280  }
281 
282  // Update make.implicit metadata to the newly-created conditional branch.
283  MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
284  if (MakeImplicitMD)
285  NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
286 
287  // Delete the old switch.
288  SI->eraseFromParent();
289  return true;
290  }
291  return false;
292  }
293 
294  if (auto *IBI = dyn_cast<IndirectBrInst>(T)) {
295  // indirectbr blockaddress(@F, @BB) -> br label @BB
296  if (auto *BA =
297  dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
298  BasicBlock *TheOnlyDest = BA->getBasicBlock();
299  std::vector <DominatorTree::UpdateType> Updates;
300  if (DDT)
301  Updates.reserve(IBI->getNumDestinations() - 1);
302 
303  // Insert the new branch.
304  Builder.CreateBr(TheOnlyDest);
305 
306  for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
307  if (IBI->getDestination(i) == TheOnlyDest) {
308  TheOnlyDest = nullptr;
309  } else {
310  BasicBlock *ParentBB = IBI->getParent();
311  BasicBlock *DestBB = IBI->getDestination(i);
312  DestBB->removePredecessor(ParentBB);
313  if (DDT)
314  Updates.push_back({DominatorTree::Delete, ParentBB, DestBB});
315  }
316  }
317  Value *Address = IBI->getAddress();
318  IBI->eraseFromParent();
319  if (DeleteDeadConditions)
321 
322  // If we didn't find our destination in the IBI successor list, then we
323  // have undefined behavior. Replace the unconditional branch with an
324  // 'unreachable' instruction.
325  if (TheOnlyDest) {
327  new UnreachableInst(BB->getContext(), BB);
328  }
329 
330  if (DDT)
331  DDT->applyUpdates(Updates);
332  return true;
333  }
334  }
335 
336  return false;
337 }
338 
339 //===----------------------------------------------------------------------===//
340 // Local dead code elimination.
341 //
342 
343 /// isInstructionTriviallyDead - Return true if the result produced by the
344 /// instruction is not used, and the instruction has no side effects.
345 ///
347  const TargetLibraryInfo *TLI) {
348  if (!I->use_empty())
349  return false;
350  return wouldInstructionBeTriviallyDead(I, TLI);
351 }
352 
354  const TargetLibraryInfo *TLI) {
355  if (isa<TerminatorInst>(I))
356  return false;
357 
358  // We don't want the landingpad-like instructions removed by anything this
359  // general.
360  if (I->isEHPad())
361  return false;
362 
363  // We don't want debug info removed by anything this general, unless
364  // debug info is empty.
365  if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
366  if (DDI->getAddress())
367  return false;
368  return true;
369  }
370  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
371  if (DVI->getValue())
372  return false;
373  return true;
374  }
375 
376  if (!I->mayHaveSideEffects())
377  return true;
378 
379  // Special case intrinsics that "may have side effects" but can be deleted
380  // when dead.
381  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
382  // Safe to delete llvm.stacksave if dead.
383  if (II->getIntrinsicID() == Intrinsic::stacksave)
384  return true;
385 
386  // Lifetime intrinsics are dead when their right-hand is undef.
387  if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
388  II->getIntrinsicID() == Intrinsic::lifetime_end)
389  return isa<UndefValue>(II->getArgOperand(1));
390 
391  // Assumptions are dead if their condition is trivially true. Guards on
392  // true are operationally no-ops. In the future we can consider more
393  // sophisticated tradeoffs for guards considering potential for check
394  // widening, but for now we keep things simple.
395  if (II->getIntrinsicID() == Intrinsic::assume ||
396  II->getIntrinsicID() == Intrinsic::experimental_guard) {
397  if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
398  return !Cond->isZero();
399 
400  return false;
401  }
402  }
403 
404  if (isAllocLikeFn(I, TLI))
405  return true;
406 
407  if (CallInst *CI = isFreeCall(I, TLI))
408  if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
409  return C->isNullValue() || isa<UndefValue>(C);
410 
411  if (CallSite CS = CallSite(I))
412  if (isMathLibCallNoop(CS, TLI))
413  return true;
414 
415  return false;
416 }
417 
418 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
419 /// trivially dead instruction, delete it. If that makes any of its operands
420 /// trivially dead, delete them too, recursively. Return true if any
421 /// instructions were deleted.
422 bool
424  const TargetLibraryInfo *TLI) {
426  if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI))
427  return false;
428 
430  DeadInsts.push_back(I);
431 
432  do {
433  I = DeadInsts.pop_back_val();
434 
435  // Null out all of the instruction's operands to see if any operand becomes
436  // dead as we go.
437  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
438  Value *OpV = I->getOperand(i);
439  I->setOperand(i, nullptr);
440 
441  if (!OpV->use_empty()) continue;
442 
443  // If the operand is an instruction that became dead as we nulled out the
444  // operand, and if it is 'trivially' dead, delete it in a future loop
445  // iteration.
446  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
447  if (isInstructionTriviallyDead(OpI, TLI))
448  DeadInsts.push_back(OpI);
449  }
450 
451  I->eraseFromParent();
452  } while (!DeadInsts.empty());
453 
454  return true;
455 }
456 
457 /// areAllUsesEqual - Check whether the uses of a value are all the same.
458 /// This is similar to Instruction::hasOneUse() except this will also return
459 /// true when there are no uses or multiple uses that all refer to the same
460 /// value.
463  Value::user_iterator UE = I->user_end();
464  if (UI == UE)
465  return true;
466 
467  User *TheUse = *UI;
468  for (++UI; UI != UE; ++UI) {
469  if (*UI != TheUse)
470  return false;
471  }
472  return true;
473 }
474 
475 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
476 /// dead PHI node, due to being a def-use chain of single-use nodes that
477 /// either forms a cycle or is terminated by a trivially dead instruction,
478 /// delete it. If that makes any of its operands trivially dead, delete them
479 /// too, recursively. Return true if a change was made.
481  const TargetLibraryInfo *TLI) {
483  for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
484  I = cast<Instruction>(*I->user_begin())) {
485  if (I->use_empty())
487 
488  // If we find an instruction more than once, we're on a cycle that
489  // won't prove fruitful.
490  if (!Visited.insert(I).second) {
491  // Break the cycle and delete the instruction and its operands.
492  I->replaceAllUsesWith(UndefValue::get(I->getType()));
494  return true;
495  }
496  }
497  return false;
498 }
499 
500 static bool
503  const DataLayout &DL,
504  const TargetLibraryInfo *TLI) {
505  if (isInstructionTriviallyDead(I, TLI)) {
506  // Null out all of the instruction's operands to see if any operand becomes
507  // dead as we go.
508  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
509  Value *OpV = I->getOperand(i);
510  I->setOperand(i, nullptr);
511 
512  if (!OpV->use_empty() || I == OpV)
513  continue;
514 
515  // If the operand is an instruction that became dead as we nulled out the
516  // operand, and if it is 'trivially' dead, delete it in a future loop
517  // iteration.
518  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
519  if (isInstructionTriviallyDead(OpI, TLI))
520  WorkList.insert(OpI);
521  }
522 
523  I->eraseFromParent();
524 
525  return true;
526  }
527 
528  if (Value *SimpleV = SimplifyInstruction(I, DL)) {
529  // Add the users to the worklist. CAREFUL: an instruction can use itself,
530  // in the case of a phi node.
531  for (User *U : I->users()) {
532  if (U != I) {
533  WorkList.insert(cast<Instruction>(U));
534  }
535  }
536 
537  // Replace the instruction with its simplified value.
538  bool Changed = false;
539  if (!I->use_empty()) {
540  I->replaceAllUsesWith(SimpleV);
541  Changed = true;
542  }
543  if (isInstructionTriviallyDead(I, TLI)) {
544  I->eraseFromParent();
545  Changed = true;
546  }
547  return Changed;
548  }
549  return false;
550 }
551 
552 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
553 /// simplify any instructions in it and recursively delete dead instructions.
554 ///
555 /// This returns true if it changed the code, note that it can delete
556 /// instructions in other blocks as well in this block.
558  const TargetLibraryInfo *TLI) {
559  bool MadeChange = false;
560  const DataLayout &DL = BB->getModule()->getDataLayout();
561 
562 #ifndef NDEBUG
563  // In debug builds, ensure that the terminator of the block is never replaced
564  // or deleted by these simplifications. The idea of simplification is that it
565  // cannot introduce new instructions, and there is no way to replace the
566  // terminator of a block without introducing a new instruction.
567  AssertingVH<Instruction> TerminatorVH(&BB->back());
568 #endif
569 
571  // Iterate over the original function, only adding insts to the worklist
572  // if they actually need to be revisited. This avoids having to pre-init
573  // the worklist with the entire function's worth of instructions.
574  for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end());
575  BI != E;) {
576  assert(!BI->isTerminator());
577  Instruction *I = &*BI;
578  ++BI;
579 
580  // We're visiting this instruction now, so make sure it's not in the
581  // worklist from an earlier visit.
582  if (!WorkList.count(I))
583  MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
584  }
585 
586  while (!WorkList.empty()) {
587  Instruction *I = WorkList.pop_back_val();
588  MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
589  }
590  return MadeChange;
591 }
592 
593 //===----------------------------------------------------------------------===//
594 // Control Flow Graph Restructuring.
595 //
596 
597 /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this
598 /// method is called when we're about to delete Pred as a predecessor of BB. If
599 /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred.
600 ///
601 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
602 /// nodes that collapse into identity values. For example, if we have:
603 /// x = phi(1, 0, 0, 0)
604 /// y = and x, z
605 ///
606 /// .. and delete the predecessor corresponding to the '1', this will attempt to
607 /// recursively fold the and to 0.
609  DeferredDominance *DDT) {
610  // This only adjusts blocks with PHI nodes.
611  if (!isa<PHINode>(BB->begin()))
612  return;
613 
614  // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
615  // them down. This will leave us with single entry phi nodes and other phis
616  // that can be removed.
617  BB->removePredecessor(Pred, true);
618 
619  WeakTrackingVH PhiIt = &BB->front();
620  while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
621  PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
622  Value *OldPhiIt = PhiIt;
623 
625  continue;
626 
627  // If recursive simplification ended up deleting the next PHI node we would
628  // iterate to, then our iterator is invalid, restart scanning from the top
629  // of the block.
630  if (PhiIt != OldPhiIt) PhiIt = &BB->front();
631  }
632  if (DDT)
633  DDT->deleteEdge(Pred, BB);
634 }
635 
636 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
637 /// predecessor is known to have one successor (DestBB!). Eliminate the edge
638 /// between them, moving the instructions in the predecessor into DestBB and
639 /// deleting the predecessor block.
641  DeferredDominance *DDT) {
642  assert(!(DT && DDT) && "Cannot call with both DT and DDT.");
643 
644  // If BB has single-entry PHI nodes, fold them.
645  while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
646  Value *NewVal = PN->getIncomingValue(0);
647  // Replace self referencing PHI with undef, it must be dead.
648  if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
649  PN->replaceAllUsesWith(NewVal);
650  PN->eraseFromParent();
651  }
652 
653  BasicBlock *PredBB = DestBB->getSinglePredecessor();
654  assert(PredBB && "Block doesn't have a single predecessor!");
655 
656  bool ReplaceEntryBB = false;
657  if (PredBB == &DestBB->getParent()->getEntryBlock())
658  ReplaceEntryBB = true;
659 
660  // Deferred DT update: Collect all the edges that enter PredBB. These
661  // dominator edges will be redirected to DestBB.
662  std::vector <DominatorTree::UpdateType> Updates;
663  if (DDT && !ReplaceEntryBB) {
664  Updates.reserve(1 +
665  (2 * std::distance(pred_begin(PredBB), pred_end(PredBB))));
666  Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
667  for (auto I = pred_begin(PredBB), E = pred_end(PredBB); I != E; ++I) {
668  Updates.push_back({DominatorTree::Delete, *I, PredBB});
669  // This predecessor of PredBB may already have DestBB as a successor.
670  if (llvm::find(successors(*I), DestBB) == succ_end(*I))
671  Updates.push_back({DominatorTree::Insert, *I, DestBB});
672  }
673  }
674 
675  // Zap anything that took the address of DestBB. Not doing this will give the
676  // address an invalid value.
677  if (DestBB->hasAddressTaken()) {
678  BlockAddress *BA = BlockAddress::get(DestBB);
679  Constant *Replacement =
682  BA->getType()));
683  BA->destroyConstant();
684  }
685 
686  // Anything that branched to PredBB now branches to DestBB.
687  PredBB->replaceAllUsesWith(DestBB);
688 
689  // Splice all the instructions from PredBB to DestBB.
690  PredBB->getTerminator()->eraseFromParent();
691  DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
692 
693  // If the PredBB is the entry block of the function, move DestBB up to
694  // become the entry block after we erase PredBB.
695  if (ReplaceEntryBB)
696  DestBB->moveAfter(PredBB);
697 
698  if (DT) {
699  // For some irreducible CFG we end up having forward-unreachable blocks
700  // so check if getNode returns a valid node before updating the domtree.
701  if (DomTreeNode *DTN = DT->getNode(PredBB)) {
702  BasicBlock *PredBBIDom = DTN->getIDom()->getBlock();
703  DT->changeImmediateDominator(DestBB, PredBBIDom);
704  DT->eraseNode(PredBB);
705  }
706  }
707 
708  if (DDT) {
709  DDT->deleteBB(PredBB); // Deferred deletion of BB.
710  if (ReplaceEntryBB)
711  // The entry block was removed and there is no external interface for the
712  // dominator tree to be notified of this change. In this corner-case we
713  // recalculate the entire tree.
714  DDT->recalculate(*(DestBB->getParent()));
715  else
716  DDT->applyUpdates(Updates);
717  } else {
718  PredBB->eraseFromParent(); // Nuke BB.
719  }
720 }
721 
722 /// CanMergeValues - Return true if we can choose one of these values to use
723 /// in place of the other. Note that we will always choose the non-undef
724 /// value to keep.
725 static bool CanMergeValues(Value *First, Value *Second) {
726  return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
727 }
728 
729 /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an
730 /// almost-empty BB ending in an unconditional branch to Succ, into Succ.
731 ///
732 /// Assumption: Succ is the single successor for BB.
734  assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
735 
736  DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
737  << Succ->getName() << "\n");
738  // Shortcut, if there is only a single predecessor it must be BB and merging
739  // is always safe
740  if (Succ->getSinglePredecessor()) return true;
741 
742  // Make a list of the predecessors of BB
744 
745  // Look at all the phi nodes in Succ, to see if they present a conflict when
746  // merging these blocks
747  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
748  PHINode *PN = cast<PHINode>(I);
749 
750  // If the incoming value from BB is again a PHINode in
751  // BB which has the same incoming value for *PI as PN does, we can
752  // merge the phi nodes and then the blocks can still be merged
754  if (BBPN && BBPN->getParent() == BB) {
755  for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
756  BasicBlock *IBB = PN->getIncomingBlock(PI);
757  if (BBPreds.count(IBB) &&
758  !CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
759  PN->getIncomingValue(PI))) {
760  DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
761  << Succ->getName() << " is conflicting with "
762  << BBPN->getName() << " with regard to common predecessor "
763  << IBB->getName() << "\n");
764  return false;
765  }
766  }
767  } else {
768  Value* Val = PN->getIncomingValueForBlock(BB);
769  for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
770  // See if the incoming value for the common predecessor is equal to the
771  // one for BB, in which case this phi node will not prevent the merging
772  // of the block.
773  BasicBlock *IBB = PN->getIncomingBlock(PI);
774  if (BBPreds.count(IBB) &&
775  !CanMergeValues(Val, PN->getIncomingValue(PI))) {
776  DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
777  << Succ->getName() << " is conflicting with regard to common "
778  << "predecessor " << IBB->getName() << "\n");
779  return false;
780  }
781  }
782  }
783  }
784 
785  return true;
786 }
787 
790 
791 /// \brief Determines the value to use as the phi node input for a block.
792 ///
793 /// Select between \p OldVal any value that we know flows from \p BB
794 /// to a particular phi on the basis of which one (if either) is not
795 /// undef. Update IncomingValues based on the selected value.
796 ///
797 /// \param OldVal The value we are considering selecting.
798 /// \param BB The block that the value flows in from.
799 /// \param IncomingValues A map from block-to-value for other phi inputs
800 /// that we have examined.
801 ///
802 /// \returns the selected value.
804  IncomingValueMap &IncomingValues) {
805  if (!isa<UndefValue>(OldVal)) {
806  assert((!IncomingValues.count(BB) ||
807  IncomingValues.find(BB)->second == OldVal) &&
808  "Expected OldVal to match incoming value from BB!");
809 
810  IncomingValues.insert(std::make_pair(BB, OldVal));
811  return OldVal;
812  }
813 
814  IncomingValueMap::const_iterator It = IncomingValues.find(BB);
815  if (It != IncomingValues.end()) return It->second;
816 
817  return OldVal;
818 }
819 
820 /// \brief Create a map from block to value for the operands of a
821 /// given phi.
822 ///
823 /// Create a map from block to value for each non-undef value flowing
824 /// into \p PN.
825 ///
826 /// \param PN The phi we are collecting the map for.
827 /// \param IncomingValues [out] The map from block to value for this phi.
829  IncomingValueMap &IncomingValues) {
830  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
831  BasicBlock *BB = PN->getIncomingBlock(i);
832  Value *V = PN->getIncomingValue(i);
833 
834  if (!isa<UndefValue>(V))
835  IncomingValues.insert(std::make_pair(BB, V));
836  }
837 }
838 
839 /// \brief Replace the incoming undef values to a phi with the values
840 /// from a block-to-value map.
841 ///
842 /// \param PN The phi we are replacing the undefs in.
843 /// \param IncomingValues A map from block to value.
845  const IncomingValueMap &IncomingValues) {
846  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
847  Value *V = PN->getIncomingValue(i);
848 
849  if (!isa<UndefValue>(V)) continue;
850 
851  BasicBlock *BB = PN->getIncomingBlock(i);
852  IncomingValueMap::const_iterator It = IncomingValues.find(BB);
853  if (It == IncomingValues.end()) continue;
854 
855  PN->setIncomingValue(i, It->second);
856  }
857 }
858 
859 /// \brief Replace a value flowing from a block to a phi with
860 /// potentially multiple instances of that value flowing from the
861 /// block's predecessors to the phi.
862 ///
863 /// \param BB The block with the value flowing into the phi.
864 /// \param BBPreds The predecessors of BB.
865 /// \param PN The phi that we are updating.
867  const PredBlockVector &BBPreds,
868  PHINode *PN) {
869  Value *OldVal = PN->removeIncomingValue(BB, false);
870  assert(OldVal && "No entry in PHI for Pred BB!");
871 
872  IncomingValueMap IncomingValues;
873 
874  // We are merging two blocks - BB, and the block containing PN - and
875  // as a result we need to redirect edges from the predecessors of BB
876  // to go to the block containing PN, and update PN
877  // accordingly. Since we allow merging blocks in the case where the
878  // predecessor and successor blocks both share some predecessors,
879  // and where some of those common predecessors might have undef
880  // values flowing into PN, we want to rewrite those values to be
881  // consistent with the non-undef values.
882 
883  gatherIncomingValuesToPhi(PN, IncomingValues);
884 
885  // If this incoming value is one of the PHI nodes in BB, the new entries
886  // in the PHI node are the entries from the old PHI.
887  if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
888  PHINode *OldValPN = cast<PHINode>(OldVal);
889  for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
890  // Note that, since we are merging phi nodes and BB and Succ might
891  // have common predecessors, we could end up with a phi node with
892  // identical incoming branches. This will be cleaned up later (and
893  // will trigger asserts if we try to clean it up now, without also
894  // simplifying the corresponding conditional branch).
895  BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
896  Value *PredVal = OldValPN->getIncomingValue(i);
897  Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
898  IncomingValues);
899 
900  // And add a new incoming value for this predecessor for the
901  // newly retargeted branch.
902  PN->addIncoming(Selected, PredBB);
903  }
904  } else {
905  for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
906  // Update existing incoming values in PN for this
907  // predecessor of BB.
908  BasicBlock *PredBB = BBPreds[i];
909  Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
910  IncomingValues);
911 
912  // And add a new incoming value for this predecessor for the
913  // newly retargeted branch.
914  PN->addIncoming(Selected, PredBB);
915  }
916  }
917 
918  replaceUndefValuesInPhi(PN, IncomingValues);
919 }
920 
921 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
922 /// unconditional branch, and contains no instructions other than PHI nodes,
923 /// potential side-effect free intrinsics and the branch. If possible,
924 /// eliminate BB by rewriting all the predecessors to branch to the successor
925 /// block and return true. If we can't transform, return false.
927  DeferredDominance *DDT) {
928  assert(BB != &BB->getParent()->getEntryBlock() &&
929  "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
930 
931  // We can't eliminate infinite loops.
932  BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
933  if (BB == Succ) return false;
934 
935  // Check to see if merging these blocks would cause conflicts for any of the
936  // phi nodes in BB or Succ. If not, we can safely merge.
937  if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
938 
939  // Check for cases where Succ has multiple predecessors and a PHI node in BB
940  // has uses which will not disappear when the PHI nodes are merged. It is
941  // possible to handle such cases, but difficult: it requires checking whether
942  // BB dominates Succ, which is non-trivial to calculate in the case where
943  // Succ has multiple predecessors. Also, it requires checking whether
944  // constructing the necessary self-referential PHI node doesn't introduce any
945  // conflicts; this isn't too difficult, but the previous code for doing this
946  // was incorrect.
947  //
948  // Note that if this check finds a live use, BB dominates Succ, so BB is
949  // something like a loop pre-header (or rarely, a part of an irreducible CFG);
950  // folding the branch isn't profitable in that case anyway.
951  if (!Succ->getSinglePredecessor()) {
952  BasicBlock::iterator BBI = BB->begin();
953  while (isa<PHINode>(*BBI)) {
954  for (Use &U : BBI->uses()) {
955  if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
956  if (PN->getIncomingBlock(U) != BB)
957  return false;
958  } else {
959  return false;
960  }
961  }
962  ++BBI;
963  }
964  }
965 
966  DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
967 
968  std::vector<DominatorTree::UpdateType> Updates;
969  if (DDT) {
970  Updates.reserve(1 + (2 * std::distance(pred_begin(BB), pred_end(BB))));
971  Updates.push_back({DominatorTree::Delete, BB, Succ});
972  // All predecessors of BB will be moved to Succ.
973  for (auto I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
974  Updates.push_back({DominatorTree::Delete, *I, BB});
975  // This predecessor of BB may already have Succ as a successor.
976  if (llvm::find(successors(*I), Succ) == succ_end(*I))
977  Updates.push_back({DominatorTree::Insert, *I, Succ});
978  }
979  }
980 
981  if (isa<PHINode>(Succ->begin())) {
982  // If there is more than one pred of succ, and there are PHI nodes in
983  // the successor, then we need to add incoming edges for the PHI nodes
984  //
985  const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
986 
987  // Loop over all of the PHI nodes in the successor of BB.
988  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
989  PHINode *PN = cast<PHINode>(I);
990 
991  redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
992  }
993  }
994 
995  if (Succ->getSinglePredecessor()) {
996  // BB is the only predecessor of Succ, so Succ will end up with exactly
997  // the same predecessors BB had.
998 
999  // Copy over any phi, debug or lifetime instruction.
1000  BB->getTerminator()->eraseFromParent();
1001  Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
1002  BB->getInstList());
1003  } else {
1004  while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
1005  // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
1006  assert(PN->use_empty() && "There shouldn't be any uses here!");
1007  PN->eraseFromParent();
1008  }
1009  }
1010 
1011  // If the unconditional branch we replaced contains llvm.loop metadata, we
1012  // add the metadata to the branch instructions in the predecessors.
1013  unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
1014  Instruction *TI = BB->getTerminator();
1015  if (TI)
1016  if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
1017  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
1018  BasicBlock *Pred = *PI;
1019  Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
1020  }
1021 
1022  // Everything that jumped to BB now goes to Succ.
1023  BB->replaceAllUsesWith(Succ);
1024  if (!Succ->hasName()) Succ->takeName(BB);
1025 
1026  if (DDT) {
1027  DDT->deleteBB(BB); // Deferred deletion of the old basic block.
1028  DDT->applyUpdates(Updates);
1029  } else {
1030  BB->eraseFromParent(); // Delete the old basic block.
1031  }
1032  return true;
1033 }
1034 
1035 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
1036 /// nodes in this block. This doesn't try to be clever about PHI nodes
1037 /// which differ only in the order of the incoming values, but instcombine
1038 /// orders them so it usually won't matter.
1040  // This implementation doesn't currently consider undef operands
1041  // specially. Theoretically, two phis which are identical except for
1042  // one having an undef where the other doesn't could be collapsed.
1043 
1044  struct PHIDenseMapInfo {
1045  static PHINode *getEmptyKey() {
1047  }
1048 
1049  static PHINode *getTombstoneKey() {
1051  }
1052 
1053  static unsigned getHashValue(PHINode *PN) {
1054  // Compute a hash value on the operands. Instcombine will likely have
1055  // sorted them, which helps expose duplicates, but we have to check all
1056  // the operands to be safe in case instcombine hasn't run.
1057  return static_cast<unsigned>(hash_combine(
1059  hash_combine_range(PN->block_begin(), PN->block_end())));
1060  }
1061 
1062  static bool isEqual(PHINode *LHS, PHINode *RHS) {
1063  if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
1064  RHS == getEmptyKey() || RHS == getTombstoneKey())
1065  return LHS == RHS;
1066  return LHS->isIdenticalTo(RHS);
1067  }
1068  };
1069 
1070  // Set of unique PHINodes.
1072 
1073  // Examine each PHI.
1074  bool Changed = false;
1075  for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
1076  auto Inserted = PHISet.insert(PN);
1077  if (!Inserted.second) {
1078  // A duplicate. Replace this PHI with its duplicate.
1079  PN->replaceAllUsesWith(*Inserted.first);
1080  PN->eraseFromParent();
1081  Changed = true;
1082 
1083  // The RAUW can change PHIs that we already visited. Start over from the
1084  // beginning.
1085  PHISet.clear();
1086  I = BB->begin();
1087  }
1088  }
1089 
1090  return Changed;
1091 }
1092 
1093 /// enforceKnownAlignment - If the specified pointer points to an object that
1094 /// we control, modify the object's alignment to PrefAlign. This isn't
1095 /// often possible though. If alignment is important, a more reliable approach
1096 /// is to simply align all global variables and allocation instructions to
1097 /// their preferred alignment from the beginning.
1098 static unsigned enforceKnownAlignment(Value *V, unsigned Align,
1099  unsigned PrefAlign,
1100  const DataLayout &DL) {
1101  assert(PrefAlign > Align);
1102 
1103  V = V->stripPointerCasts();
1104 
1105  if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1106  // TODO: ideally, computeKnownBits ought to have used
1107  // AllocaInst::getAlignment() in its computation already, making
1108  // the below max redundant. But, as it turns out,
1109  // stripPointerCasts recurses through infinite layers of bitcasts,
1110  // while computeKnownBits is not allowed to traverse more than 6
1111  // levels.
1112  Align = std::max(AI->getAlignment(), Align);
1113  if (PrefAlign <= Align)
1114  return Align;
1115 
1116  // If the preferred alignment is greater than the natural stack alignment
1117  // then don't round up. This avoids dynamic stack realignment.
1118  if (DL.exceedsNaturalStackAlignment(PrefAlign))
1119  return Align;
1120  AI->setAlignment(PrefAlign);
1121  return PrefAlign;
1122  }
1123 
1124  if (auto *GO = dyn_cast<GlobalObject>(V)) {
1125  // TODO: as above, this shouldn't be necessary.
1126  Align = std::max(GO->getAlignment(), Align);
1127  if (PrefAlign <= Align)
1128  return Align;
1129 
1130  // If there is a large requested alignment and we can, bump up the alignment
1131  // of the global. If the memory we set aside for the global may not be the
1132  // memory used by the final program then it is impossible for us to reliably
1133  // enforce the preferred alignment.
1134  if (!GO->canIncreaseAlignment())
1135  return Align;
1136 
1137  GO->setAlignment(PrefAlign);
1138  return PrefAlign;
1139  }
1140 
1141  return Align;
1142 }
1143 
1144 unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
1145  const DataLayout &DL,
1146  const Instruction *CxtI,
1147  AssumptionCache *AC,
1148  const DominatorTree *DT) {
1149  assert(V->getType()->isPointerTy() &&
1150  "getOrEnforceKnownAlignment expects a pointer!");
1151 
1152  KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT);
1153  unsigned TrailZ = Known.countMinTrailingZeros();
1154 
1155  // Avoid trouble with ridiculously large TrailZ values, such as
1156  // those computed from a null pointer.
1157  TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1));
1158 
1159  unsigned Align = 1u << std::min(Known.getBitWidth() - 1, TrailZ);
1160 
1161  // LLVM doesn't support alignments larger than this currently.
1162  Align = std::min(Align, +Value::MaximumAlignment);
1163 
1164  if (PrefAlign > Align)
1165  Align = enforceKnownAlignment(V, Align, PrefAlign, DL);
1166 
1167  // We don't need to make any adjustment.
1168  return Align;
1169 }
1170 
1171 ///===---------------------------------------------------------------------===//
1172 /// Dbg Intrinsic utilities
1173 ///
1174 
1175 /// See if there is a dbg.value intrinsic for DIVar before I.
1176 static bool LdStHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr,
1177  Instruction *I) {
1178  // Since we can't guarantee that the original dbg.declare instrinsic
1179  // is removed by LowerDbgDeclare(), we need to make sure that we are
1180  // not inserting the same dbg.value intrinsic over and over.
1182  if (PrevI != I->getParent()->getInstList().begin()) {
1183  --PrevI;
1184  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
1185  if (DVI->getValue() == I->getOperand(0) &&
1186  DVI->getVariable() == DIVar &&
1187  DVI->getExpression() == DIExpr)
1188  return true;
1189  }
1190  return false;
1191 }
1192 
1193 /// See if there is a dbg.value intrinsic for DIVar for the PHI node.
1195  DIExpression *DIExpr,
1196  PHINode *APN) {
1197  // Since we can't guarantee that the original dbg.declare instrinsic
1198  // is removed by LowerDbgDeclare(), we need to make sure that we are
1199  // not inserting the same dbg.value intrinsic over and over.
1201  findDbgValues(DbgValues, APN);
1202  for (auto *DVI : DbgValues) {
1203  assert(DVI->getValue() == APN);
1204  if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1205  return true;
1206  }
1207  return false;
1208 }
1209 
1210 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1211 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1213  StoreInst *SI, DIBuilder &Builder) {
1214  assert(DII->isAddressOfVariable());
1215  auto *DIVar = DII->getVariable();
1216  assert(DIVar && "Missing variable");
1217  auto *DIExpr = DII->getExpression();
1218  Value *DV = SI->getOperand(0);
1219 
1220  // If an argument is zero extended then use argument directly. The ZExt
1221  // may be zapped by an optimization pass in future.
1222  Argument *ExtendedArg = nullptr;
1223  if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
1224  ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0));
1225  if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
1226  ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0));
1227  if (ExtendedArg) {
1228  // If this DII was already describing only a fragment of a variable, ensure
1229  // that fragment is appropriately narrowed here.
1230  // But if a fragment wasn't used, describe the value as the original
1231  // argument (rather than the zext or sext) so that it remains described even
1232  // if the sext/zext is optimized away. This widens the variable description,
1233  // leaving it up to the consumer to know how the smaller value may be
1234  // represented in a larger register.
1235  if (auto Fragment = DIExpr->getFragmentInfo()) {
1236  unsigned FragmentOffset = Fragment->OffsetInBits;
1237  SmallVector<uint64_t, 3> Ops(DIExpr->elements_begin(),
1238  DIExpr->elements_end() - 3);
1240  Ops.push_back(FragmentOffset);
1241  const DataLayout &DL = DII->getModule()->getDataLayout();
1242  Ops.push_back(DL.getTypeSizeInBits(ExtendedArg->getType()));
1243  DIExpr = Builder.createExpression(Ops);
1244  }
1245  DV = ExtendedArg;
1246  }
1247  if (!LdStHasDebugValue(DIVar, DIExpr, SI))
1248  Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, DII->getDebugLoc(),
1249  SI);
1250 }
1251 
1252 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1253 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1255  LoadInst *LI, DIBuilder &Builder) {
1256  auto *DIVar = DII->getVariable();
1257  auto *DIExpr = DII->getExpression();
1258  assert(DIVar && "Missing variable");
1259 
1260  if (LdStHasDebugValue(DIVar, DIExpr, LI))
1261  return;
1262 
1263  // We are now tracking the loaded value instead of the address. In the
1264  // future if multi-location support is added to the IR, it might be
1265  // preferable to keep tracking both the loaded value and the original
1266  // address in case the alloca can not be elided.
1267  Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
1268  LI, DIVar, DIExpr, DII->getDebugLoc(), (Instruction *)nullptr);
1269  DbgValue->insertAfter(LI);
1270 }
1271 
1272 /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
1273 /// llvm.dbg.declare or llvm.dbg.addr intrinsic.
1275  PHINode *APN, DIBuilder &Builder) {
1276  auto *DIVar = DII->getVariable();
1277  auto *DIExpr = DII->getExpression();
1278  assert(DIVar && "Missing variable");
1279 
1280  if (PhiHasDebugValue(DIVar, DIExpr, APN))
1281  return;
1282 
1283  BasicBlock *BB = APN->getParent();
1284  auto InsertionPt = BB->getFirstInsertionPt();
1285 
1286  // The block may be a catchswitch block, which does not have a valid
1287  // insertion point.
1288  // FIXME: Insert dbg.value markers in the successors when appropriate.
1289  if (InsertionPt != BB->end())
1290  Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, DII->getDebugLoc(),
1291  &*InsertionPt);
1292 }
1293 
1294 /// Determine whether this alloca is either a VLA or an array.
1295 static bool isArray(AllocaInst *AI) {
1296  return AI->isArrayAllocation() ||
1297  AI->getType()->getElementType()->isArrayTy();
1298 }
1299 
1300 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1301 /// of llvm.dbg.value intrinsics.
1303  DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1305  for (auto &FI : F)
1306  for (Instruction &BI : FI)
1307  if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
1308  Dbgs.push_back(DDI);
1309 
1310  if (Dbgs.empty())
1311  return false;
1312 
1313  for (auto &I : Dbgs) {
1314  DbgDeclareInst *DDI = I;
1315  AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1316  // If this is an alloca for a scalar variable, insert a dbg.value
1317  // at each load and store to the alloca and erase the dbg.declare.
1318  // The dbg.values allow tracking a variable even if it is not
1319  // stored on the stack, while the dbg.declare can only describe
1320  // the stack slot (and at a lexical-scope granularity). Later
1321  // passes will attempt to elide the stack slot.
1322  if (AI && !isArray(AI)) {
1323  for (auto &AIUse : AI->uses()) {
1324  User *U = AIUse.getUser();
1325  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1326  if (AIUse.getOperandNo() == 1)
1328  } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1329  ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1330  } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1331  // This is a call by-value or some other instruction that
1332  // takes a pointer to the variable. Insert a *value*
1333  // intrinsic that describes the alloca.
1334  DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(),
1335  DDI->getExpression(), DDI->getDebugLoc(),
1336  CI);
1337  }
1338  }
1339  DDI->eraseFromParent();
1340  }
1341  }
1342  return true;
1343 }
1344 
1345 /// Propagate dbg.value intrinsics through the newly inserted PHIs.
1347  SmallVectorImpl<PHINode *> &InsertedPHIs) {
1348  assert(BB && "No BasicBlock to clone dbg.value(s) from.");
1349  if (InsertedPHIs.size() == 0)
1350  return;
1351 
1352  // Map existing PHI nodes to their dbg.values.
1353  ValueToValueMapTy DbgValueMap;
1354  for (auto &I : *BB) {
1355  if (auto DbgII = dyn_cast<DbgInfoIntrinsic>(&I)) {
1356  if (auto *Loc = dyn_cast_or_null<PHINode>(DbgII->getVariableLocation()))
1357  DbgValueMap.insert({Loc, DbgII});
1358  }
1359  }
1360  if (DbgValueMap.size() == 0)
1361  return;
1362 
1363  // Then iterate through the new PHIs and look to see if they use one of the
1364  // previously mapped PHIs. If so, insert a new dbg.value intrinsic that will
1365  // propagate the info through the new PHI.
1366  LLVMContext &C = BB->getContext();
1367  for (auto PHI : InsertedPHIs) {
1368  BasicBlock *Parent = PHI->getParent();
1369  // Avoid inserting an intrinsic into an EH block.
1370  if (Parent->getFirstNonPHI()->isEHPad())
1371  continue;
1372  auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI));
1373  for (auto VI : PHI->operand_values()) {
1374  auto V = DbgValueMap.find(VI);
1375  if (V != DbgValueMap.end()) {
1376  auto *DbgII = cast<DbgInfoIntrinsic>(V->second);
1377  Instruction *NewDbgII = DbgII->clone();
1378  NewDbgII->setOperand(0, PhiMAV);
1379  auto InsertionPt = Parent->getFirstInsertionPt();
1380  assert(InsertionPt != Parent->end() && "Ill-formed basic block");
1381  NewDbgII->insertBefore(&*InsertionPt);
1382  }
1383  }
1384  }
1385 }
1386 
1387 /// Finds all intrinsics declaring local variables as living in the memory that
1388 /// 'V' points to. This may include a mix of dbg.declare and
1389 /// dbg.addr intrinsics.
1391  auto *L = LocalAsMetadata::getIfExists(V);
1392  if (!L)
1393  return {};
1394  auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L);
1395  if (!MDV)
1396  return {};
1397 
1399  for (User *U : MDV->users()) {
1400  if (auto *DII = dyn_cast<DbgInfoIntrinsic>(U))
1401  if (DII->isAddressOfVariable())
1402  Declares.push_back(DII);
1403  }
1404 
1405  return Declares;
1406 }
1407 
1409  if (auto *L = LocalAsMetadata::getIfExists(V))
1410  if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1411  for (User *U : MDV->users())
1412  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U))
1413  DbgValues.push_back(DVI);
1414 }
1415 
1417  Value *V) {
1418  if (auto *L = LocalAsMetadata::getIfExists(V))
1419  if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1420  for (User *U : MDV->users())
1421  if (DbgInfoIntrinsic *DII = dyn_cast<DbgInfoIntrinsic>(U))
1422  DbgUsers.push_back(DII);
1423 }
1424 
1426  Instruction *InsertBefore, DIBuilder &Builder,
1427  bool DerefBefore, int Offset, bool DerefAfter) {
1428  auto DbgAddrs = FindDbgAddrUses(Address);
1429  for (DbgInfoIntrinsic *DII : DbgAddrs) {
1430  DebugLoc Loc = DII->getDebugLoc();
1431  auto *DIVar = DII->getVariable();
1432  auto *DIExpr = DII->getExpression();
1433  assert(DIVar && "Missing variable");
1434  DIExpr = DIExpression::prepend(DIExpr, DerefBefore, Offset, DerefAfter);
1435  // Insert llvm.dbg.declare immediately after InsertBefore, and remove old
1436  // llvm.dbg.declare.
1437  Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore);
1438  if (DII == InsertBefore)
1439  InsertBefore = &*std::next(InsertBefore->getIterator());
1440  DII->eraseFromParent();
1441  }
1442  return !DbgAddrs.empty();
1443 }
1444 
1446  DIBuilder &Builder, bool DerefBefore,
1447  int Offset, bool DerefAfter) {
1448  return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder,
1449  DerefBefore, Offset, DerefAfter);
1450 }
1451 
1452 static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
1453  DIBuilder &Builder, int Offset) {
1454  DebugLoc Loc = DVI->getDebugLoc();
1455  auto *DIVar = DVI->getVariable();
1456  auto *DIExpr = DVI->getExpression();
1457  assert(DIVar && "Missing variable");
1458 
1459  // This is an alloca-based llvm.dbg.value. The first thing it should do with
1460  // the alloca pointer is dereference it. Otherwise we don't know how to handle
1461  // it and give up.
1462  if (!DIExpr || DIExpr->getNumElements() < 1 ||
1463  DIExpr->getElement(0) != dwarf::DW_OP_deref)
1464  return;
1465 
1466  // Insert the offset immediately after the first deref.
1467  // We could just change the offset argument of dbg.value, but it's unsigned...
1468  if (Offset) {
1470  Ops.push_back(dwarf::DW_OP_deref);
1471  DIExpression::appendOffset(Ops, Offset);
1472  Ops.append(DIExpr->elements_begin() + 1, DIExpr->elements_end());
1473  DIExpr = Builder.createExpression(Ops);
1474  }
1475 
1476  Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI);
1477  DVI->eraseFromParent();
1478 }
1479 
1481  DIBuilder &Builder, int Offset) {
1482  if (auto *L = LocalAsMetadata::getIfExists(AI))
1483  if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
1484  for (auto UI = MDV->use_begin(), UE = MDV->use_end(); UI != UE;) {
1485  Use &U = *UI++;
1486  if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
1487  replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1488  }
1489 }
1490 
1492  // This function is hot. An early check to determine whether the instruction
1493  // has any metadata to save allows it to return earlier on average.
1494  if (!I.isUsedByMetadata())
1495  return;
1496 
1498  findDbgUsers(DbgUsers, &I);
1499  if (DbgUsers.empty())
1500  return;
1501 
1502  auto &M = *I.getModule();
1503  auto &DL = M.getDataLayout();
1504 
1505  auto wrapMD = [&](Value *V) {
1507  };
1508 
1509  auto doSalvage = [&](DbgInfoIntrinsic *DII, SmallVectorImpl<uint64_t> &Ops) {
1510  auto *DIExpr = DII->getExpression();
1511  DIExpr = DIExpression::doPrepend(DIExpr, Ops,
1513  DII->setOperand(0, wrapMD(I.getOperand(0)));
1514  DII->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr));
1515  DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
1516  };
1517 
1518  auto applyOffset = [&](DbgInfoIntrinsic *DII, uint64_t Offset) {
1521  doSalvage(DII, Ops);
1522  };
1523 
1524  auto applyOps = [&](DbgInfoIntrinsic *DII,
1525  std::initializer_list<uint64_t> Opcodes) {
1526  SmallVector<uint64_t, 8> Ops(Opcodes);
1527  doSalvage(DII, Ops);
1528  };
1529 
1530  if (auto *CI = dyn_cast<CastInst>(&I)) {
1531  if (!CI->isNoopCast(DL))
1532  return;
1533 
1534  // No-op casts are irrelevant for debug info.
1535  MetadataAsValue *CastSrc = wrapMD(I.getOperand(0));
1536  for (auto *DII : DbgUsers) {
1537  DII->setOperand(0, CastSrc);
1538  DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
1539  }
1540  } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1541  unsigned BitWidth =
1542  M.getDataLayout().getIndexSizeInBits(GEP->getPointerAddressSpace());
1543  // Rewrite a constant GEP into a DIExpression. Since we are performing
1544  // arithmetic to compute the variable's *value* in the DIExpression, we
1545  // need to mark the expression with a DW_OP_stack_value.
1546  APInt Offset(BitWidth, 0);
1547  if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset))
1548  for (auto *DII : DbgUsers)
1549  applyOffset(DII, Offset.getSExtValue());
1550  } else if (auto *BI = dyn_cast<BinaryOperator>(&I)) {
1551  // Rewrite binary operations with constant integer operands.
1552  auto *ConstInt = dyn_cast<ConstantInt>(I.getOperand(1));
1553  if (!ConstInt || ConstInt->getBitWidth() > 64)
1554  return;
1555 
1556  uint64_t Val = ConstInt->getSExtValue();
1557  for (auto *DII : DbgUsers) {
1558  switch (BI->getOpcode()) {
1559  case Instruction::Add:
1560  applyOffset(DII, Val);
1561  break;
1562  case Instruction::Sub:
1563  applyOffset(DII, -int64_t(Val));
1564  break;
1565  case Instruction::Mul:
1566  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_mul});
1567  break;
1568  case Instruction::SDiv:
1569  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_div});
1570  break;
1571  case Instruction::SRem:
1572  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_mod});
1573  break;
1574  case Instruction::Or:
1575  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_or});
1576  break;
1577  case Instruction::And:
1578  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_and});
1579  break;
1580  case Instruction::Xor:
1581  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_xor});
1582  break;
1583  case Instruction::Shl:
1584  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shl});
1585  break;
1586  case Instruction::LShr:
1587  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shr});
1588  break;
1589  case Instruction::AShr:
1590  applyOps(DII, {dwarf::DW_OP_constu, Val, dwarf::DW_OP_shra});
1591  break;
1592  default:
1593  // TODO: Salvage constants from each kind of binop we know about.
1594  continue;
1595  }
1596  }
1597  } else if (isa<LoadInst>(&I)) {
1598  MetadataAsValue *AddrMD = wrapMD(I.getOperand(0));
1599  for (auto *DII : DbgUsers) {
1600  // Rewrite the load into DW_OP_deref.
1601  auto *DIExpr = DII->getExpression();
1603  DII->setOperand(0, AddrMD);
1604  DII->setOperand(2, MetadataAsValue::get(I.getContext(), DIExpr));
1605  DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
1606  }
1607  }
1608 }
1609 
1611  unsigned NumDeadInst = 0;
1612  // Delete the instructions backwards, as it has a reduced likelihood of
1613  // having to update as many def-use and use-def chains.
1614  Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
1615  while (EndInst != &BB->front()) {
1616  // Delete the next to last instruction.
1617  Instruction *Inst = &*--EndInst->getIterator();
1618  if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
1619  Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
1620  if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
1621  EndInst = Inst;
1622  continue;
1623  }
1624  if (!isa<DbgInfoIntrinsic>(Inst))
1625  ++NumDeadInst;
1626  Inst->eraseFromParent();
1627  }
1628  return NumDeadInst;
1629 }
1630 
1631 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
1632  bool PreserveLCSSA, DeferredDominance *DDT) {
1633  BasicBlock *BB = I->getParent();
1634  std::vector <DominatorTree::UpdateType> Updates;
1635 
1636  // Loop over all of the successors, removing BB's entry from any PHI
1637  // nodes.
1638  if (DDT)
1639  Updates.reserve(BB->getTerminator()->getNumSuccessors());
1640  for (BasicBlock *Successor : successors(BB)) {
1641  Successor->removePredecessor(BB, PreserveLCSSA);
1642  if (DDT)
1643  Updates.push_back({DominatorTree::Delete, BB, Successor});
1644  }
1645  // Insert a call to llvm.trap right before this. This turns the undefined
1646  // behavior into a hard fail instead of falling through into random code.
1647  if (UseLLVMTrap) {
1648  Function *TrapFn =
1649  Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
1650  CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
1651  CallTrap->setDebugLoc(I->getDebugLoc());
1652  }
1653  new UnreachableInst(I->getContext(), I);
1654 
1655  // All instructions after this are dead.
1656  unsigned NumInstrsRemoved = 0;
1657  BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
1658  while (BBI != BBE) {
1659  if (!BBI->use_empty())
1660  BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
1661  BB->getInstList().erase(BBI++);
1662  ++NumInstrsRemoved;
1663  }
1664  if (DDT)
1665  DDT->applyUpdates(Updates);
1666  return NumInstrsRemoved;
1667 }
1668 
1669 /// changeToCall - Convert the specified invoke into a normal call.
1670 static void changeToCall(InvokeInst *II, DeferredDominance *DDT = nullptr) {
1673  II->getOperandBundlesAsDefs(OpBundles);
1674  CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
1675  "", II);
1676  NewCall->takeName(II);
1677  NewCall->setCallingConv(II->getCallingConv());
1678  NewCall->setAttributes(II->getAttributes());
1679  NewCall->setDebugLoc(II->getDebugLoc());
1680  II->replaceAllUsesWith(NewCall);
1681 
1682  // Follow the call by a branch to the normal destination.
1683  BasicBlock *NormalDestBB = II->getNormalDest();
1684  BranchInst::Create(NormalDestBB, II);
1685 
1686  // Update PHI nodes in the unwind destination
1687  BasicBlock *BB = II->getParent();
1688  BasicBlock *UnwindDestBB = II->getUnwindDest();
1689  UnwindDestBB->removePredecessor(BB);
1690  II->eraseFromParent();
1691  if (DDT)
1692  DDT->deleteEdge(BB, UnwindDestBB);
1693 }
1694 
1696  BasicBlock *UnwindEdge) {
1697  BasicBlock *BB = CI->getParent();
1698 
1699  // Convert this function call into an invoke instruction. First, split the
1700  // basic block.
1701  BasicBlock *Split =
1702  BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc");
1703 
1704  // Delete the unconditional branch inserted by splitBasicBlock
1705  BB->getInstList().pop_back();
1706 
1707  // Create the new invoke instruction.
1708  SmallVector<Value *, 8> InvokeArgs(CI->arg_begin(), CI->arg_end());
1710 
1711  CI->getOperandBundlesAsDefs(OpBundles);
1712 
1713  // Note: we're round tripping operand bundles through memory here, and that
1714  // can potentially be avoided with a cleverer API design that we do not have
1715  // as of this time.
1716 
1717  InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, UnwindEdge,
1718  InvokeArgs, OpBundles, CI->getName(), BB);
1719  II->setDebugLoc(CI->getDebugLoc());
1720  II->setCallingConv(CI->getCallingConv());
1721  II->setAttributes(CI->getAttributes());
1722 
1723  // Make sure that anything using the call now uses the invoke! This also
1724  // updates the CallGraph if present, because it uses a WeakTrackingVH.
1725  CI->replaceAllUsesWith(II);
1726 
1727  // Delete the original call
1728  Split->getInstList().pop_front();
1729  return Split;
1730 }
1731 
1733  SmallPtrSetImpl<BasicBlock*> &Reachable,
1734  DeferredDominance *DDT = nullptr) {
1736  BasicBlock *BB = &F.front();
1737  Worklist.push_back(BB);
1738  Reachable.insert(BB);
1739  bool Changed = false;
1740  do {
1741  BB = Worklist.pop_back_val();
1742 
1743  // Do a quick scan of the basic block, turning any obviously unreachable
1744  // instructions into LLVM unreachable insts. The instruction combining pass
1745  // canonicalizes unreachable insts into stores to null or undef.
1746  for (Instruction &I : *BB) {
1747  // Assumptions that are known to be false are equivalent to unreachable.
1748  // Also, if the condition is undefined, then we make the choice most
1749  // beneficial to the optimizer, and choose that to also be unreachable.
1750  if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
1751  if (II->getIntrinsicID() == Intrinsic::assume) {
1752  if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
1753  // Don't insert a call to llvm.trap right before the unreachable.
1754  changeToUnreachable(II, false, false, DDT);
1755  Changed = true;
1756  break;
1757  }
1758  }
1759 
1760  if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
1761  // A call to the guard intrinsic bails out of the current compilation
1762  // unit if the predicate passed to it is false. If the predicate is a
1763  // constant false, then we know the guard will bail out of the current
1764  // compile unconditionally, so all code following it is dead.
1765  //
1766  // Note: unlike in llvm.assume, it is not "obviously profitable" for
1767  // guards to treat `undef` as `false` since a guard on `undef` can
1768  // still be useful for widening.
1769  if (match(II->getArgOperand(0), m_Zero()))
1770  if (!isa<UnreachableInst>(II->getNextNode())) {
1771  changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false,
1772  false, DDT);
1773  Changed = true;
1774  break;
1775  }
1776  }
1777  }
1778 
1779  if (auto *CI = dyn_cast<CallInst>(&I)) {
1780  Value *Callee = CI->getCalledValue();
1781  if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1782  changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DDT);
1783  Changed = true;
1784  break;
1785  }
1786  if (CI->doesNotReturn()) {
1787  // If we found a call to a no-return function, insert an unreachable
1788  // instruction after it. Make sure there isn't *already* one there
1789  // though.
1790  if (!isa<UnreachableInst>(CI->getNextNode())) {
1791  // Don't insert a call to llvm.trap right before the unreachable.
1792  changeToUnreachable(CI->getNextNode(), false, false, DDT);
1793  Changed = true;
1794  }
1795  break;
1796  }
1797  }
1798 
1799  // Store to undef and store to null are undefined and used to signal that
1800  // they should be changed to unreachable by passes that can't modify the
1801  // CFG.
1802  if (auto *SI = dyn_cast<StoreInst>(&I)) {
1803  // Don't touch volatile stores.
1804  if (SI->isVolatile()) continue;
1805 
1806  Value *Ptr = SI->getOperand(1);
1807 
1808  if (isa<UndefValue>(Ptr) ||
1809  (isa<ConstantPointerNull>(Ptr) &&
1810  SI->getPointerAddressSpace() == 0)) {
1811  changeToUnreachable(SI, true, false, DDT);
1812  Changed = true;
1813  break;
1814  }
1815  }
1816  }
1817 
1818  TerminatorInst *Terminator = BB->getTerminator();
1819  if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
1820  // Turn invokes that call 'nounwind' functions into ordinary calls.
1821  Value *Callee = II->getCalledValue();
1822  if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1823  changeToUnreachable(II, true, false, DDT);
1824  Changed = true;
1825  } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
1826  if (II->use_empty() && II->onlyReadsMemory()) {
1827  // jump to the normal destination branch.
1828  BasicBlock *NormalDestBB = II->getNormalDest();
1829  BasicBlock *UnwindDestBB = II->getUnwindDest();
1830  BranchInst::Create(NormalDestBB, II);
1831  UnwindDestBB->removePredecessor(II->getParent());
1832  II->eraseFromParent();
1833  if (DDT)
1834  DDT->deleteEdge(BB, UnwindDestBB);
1835  } else
1836  changeToCall(II, DDT);
1837  Changed = true;
1838  }
1839  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
1840  // Remove catchpads which cannot be reached.
1841  struct CatchPadDenseMapInfo {
1842  static CatchPadInst *getEmptyKey() {
1844  }
1845 
1846  static CatchPadInst *getTombstoneKey() {
1848  }
1849 
1850  static unsigned getHashValue(CatchPadInst *CatchPad) {
1851  return static_cast<unsigned>(hash_combine_range(
1852  CatchPad->value_op_begin(), CatchPad->value_op_end()));
1853  }
1854 
1855  static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
1856  if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
1857  RHS == getEmptyKey() || RHS == getTombstoneKey())
1858  return LHS == RHS;
1859  return LHS->isIdenticalTo(RHS);
1860  }
1861  };
1862 
1863  // Set of unique CatchPads.
1865  CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
1866  HandlerSet;
1867  detail::DenseSetEmpty Empty;
1868  for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
1869  E = CatchSwitch->handler_end();
1870  I != E; ++I) {
1871  BasicBlock *HandlerBB = *I;
1872  auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
1873  if (!HandlerSet.insert({CatchPad, Empty}).second) {
1874  CatchSwitch->removeHandler(I);
1875  --I;
1876  --E;
1877  Changed = true;
1878  }
1879  }
1880  }
1881 
1882  Changed |= ConstantFoldTerminator(BB, true, nullptr, DDT);
1883  for (BasicBlock *Successor : successors(BB))
1884  if (Reachable.insert(Successor).second)
1885  Worklist.push_back(Successor);
1886  } while (!Worklist.empty());
1887  return Changed;
1888 }
1889 
1891  TerminatorInst *TI = BB->getTerminator();
1892 
1893  if (auto *II = dyn_cast<InvokeInst>(TI)) {
1894  changeToCall(II, DDT);
1895  return;
1896  }
1897 
1898  TerminatorInst *NewTI;
1899  BasicBlock *UnwindDest;
1900 
1901  if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
1902  NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
1903  UnwindDest = CRI->getUnwindDest();
1904  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
1905  auto *NewCatchSwitch = CatchSwitchInst::Create(
1906  CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
1907  CatchSwitch->getName(), CatchSwitch);
1908  for (BasicBlock *PadBB : CatchSwitch->handlers())
1909  NewCatchSwitch->addHandler(PadBB);
1910 
1911  NewTI = NewCatchSwitch;
1912  UnwindDest = CatchSwitch->getUnwindDest();
1913  } else {
1914  llvm_unreachable("Could not find unwind successor");
1915  }
1916 
1917  NewTI->takeName(TI);
1918  NewTI->setDebugLoc(TI->getDebugLoc());
1919  UnwindDest->removePredecessor(BB);
1920  TI->replaceAllUsesWith(NewTI);
1921  TI->eraseFromParent();
1922  if (DDT)
1923  DDT->deleteEdge(BB, UnwindDest);
1924 }
1925 
1926 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
1927 /// if they are in a dead cycle. Return true if a change was made, false
1928 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
1929 /// after modifying the CFG.
1931  DeferredDominance *DDT) {
1932  SmallPtrSet<BasicBlock*, 16> Reachable;
1933  bool Changed = markAliveBlocks(F, Reachable, DDT);
1934 
1935  // If there are unreachable blocks in the CFG...
1936  if (Reachable.size() == F.size())
1937  return Changed;
1938 
1939  assert(Reachable.size() < F.size());
1940  NumRemoved += F.size()-Reachable.size();
1941 
1942  // Loop over all of the basic blocks that are not reachable, dropping all of
1943  // their internal references. Update DDT and LVI if available.
1944  std::vector <DominatorTree::UpdateType> Updates;
1945  for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
1946  auto *BB = &*I;
1947  if (Reachable.count(BB))
1948  continue;
1949  for (BasicBlock *Successor : successors(BB)) {
1950  if (Reachable.count(Successor))
1951  Successor->removePredecessor(BB);
1952  if (DDT)
1953  Updates.push_back({DominatorTree::Delete, BB, Successor});
1954  }
1955  if (LVI)
1956  LVI->eraseBlock(BB);
1957  BB->dropAllReferences();
1958  }
1959 
1960  for (Function::iterator I = ++F.begin(); I != F.end();) {
1961  auto *BB = &*I;
1962  if (Reachable.count(BB)) {
1963  ++I;
1964  continue;
1965  }
1966  if (DDT) {
1967  DDT->deleteBB(BB); // deferred deletion of BB.
1968  ++I;
1969  } else {
1970  I = F.getBasicBlockList().erase(I);
1971  }
1972  }
1973 
1974  if (DDT)
1975  DDT->applyUpdates(Updates);
1976  return true;
1977 }
1978 
1980  ArrayRef<unsigned> KnownIDs) {
1982  K->dropUnknownNonDebugMetadata(KnownIDs);
1983  K->getAllMetadataOtherThanDebugLoc(Metadata);
1984  for (const auto &MD : Metadata) {
1985  unsigned Kind = MD.first;
1986  MDNode *JMD = J->getMetadata(Kind);
1987  MDNode *KMD = MD.second;
1988 
1989  switch (Kind) {
1990  default:
1991  K->setMetadata(Kind, nullptr); // Remove unknown metadata
1992  break;
1993  case LLVMContext::MD_dbg:
1994  llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
1995  case LLVMContext::MD_tbaa:
1996  K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
1997  break;
1999  K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
2000  break;
2003  K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
2004  break;
2005  case LLVMContext::MD_range:
2006  K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
2007  break;
2009  K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
2010  break;
2012  // Only set the !invariant.load if it is present in both instructions.
2013  K->setMetadata(Kind, JMD);
2014  break;
2016  // Only set the !nonnull if it is present in both instructions.
2017  K->setMetadata(Kind, JMD);
2018  break;
2020  // Preserve !invariant.group in K.
2021  break;
2022  case LLVMContext::MD_align:
2023  K->setMetadata(Kind,
2025  break;
2028  K->setMetadata(Kind,
2030  break;
2031  }
2032  }
2033  // Set !invariant.group from J if J has it. If both instructions have it
2034  // then we will just pick it from J - even when they are different.
2035  // Also make sure that K is load or store - f.e. combining bitcast with load
2036  // could produce bitcast with invariant.group metadata, which is invalid.
2037  // FIXME: we should try to preserve both invariant.group md if they are
2038  // different, but right now instruction can only have one invariant.group.
2039  if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2040  if (isa<LoadInst>(K) || isa<StoreInst>(K))
2042 }
2043 
2045  unsigned KnownIDs[] = {
2052  combineMetadata(K, J, KnownIDs);
2053 }
2054 
2055 template <typename RootType, typename DominatesFn>
2056 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
2057  const RootType &Root,
2058  const DominatesFn &Dominates) {
2059  assert(From->getType() == To->getType());
2060 
2061  unsigned Count = 0;
2062  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2063  UI != UE;) {
2064  Use &U = *UI++;
2065  if (!Dominates(Root, U))
2066  continue;
2067  U.set(To);
2068  DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as "
2069  << *To << " in " << *U << "\n");
2070  ++Count;
2071  }
2072  return Count;
2073 }
2074 
2076  assert(From->getType() == To->getType());
2077  auto *BB = From->getParent();
2078  unsigned Count = 0;
2079 
2080  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2081  UI != UE;) {
2082  Use &U = *UI++;
2083  auto *I = cast<Instruction>(U.getUser());
2084  if (I->getParent() == BB)
2085  continue;
2086  U.set(To);
2087  ++Count;
2088  }
2089  return Count;
2090 }
2091 
2093  DominatorTree &DT,
2094  const BasicBlockEdge &Root) {
2095  auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2096  return DT.dominates(Root, U);
2097  };
2098  return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2099 }
2100 
2102  DominatorTree &DT,
2103  const BasicBlock *BB) {
2104  auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
2105  auto *I = cast<Instruction>(U.getUser())->getParent();
2106  return DT.properlyDominates(BB, I);
2107  };
2108  return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
2109 }
2110 
2112  const TargetLibraryInfo &TLI) {
2113  // Check if the function is specifically marked as a gc leaf function.
2114  if (CS.hasFnAttr("gc-leaf-function"))
2115  return true;
2116  if (const Function *F = CS.getCalledFunction()) {
2117  if (F->hasFnAttribute("gc-leaf-function"))
2118  return true;
2119 
2120  if (auto IID = F->getIntrinsicID())
2121  // Most LLVM intrinsics do not take safepoints.
2122  return IID != Intrinsic::experimental_gc_statepoint &&
2123  IID != Intrinsic::experimental_deoptimize;
2124  }
2125 
2126  // Lib calls can be materialized by some passes, and won't be
2127  // marked as 'gc-leaf-function.' All available Libcalls are
2128  // GC-leaf.
2129  LibFunc LF;
2130  if (TLI.getLibFunc(CS, LF)) {
2131  return TLI.has(LF);
2132  }
2133 
2134  return false;
2135 }
2136 
2138  LoadInst &NewLI) {
2139  auto *NewTy = NewLI.getType();
2140 
2141  // This only directly applies if the new type is also a pointer.
2142  if (NewTy->isPointerTy()) {
2144  return;
2145  }
2146 
2147  // The only other translation we can do is to integral loads with !range
2148  // metadata.
2149  if (!NewTy->isIntegerTy())
2150  return;
2151 
2152  MDBuilder MDB(NewLI.getContext());
2153  const Value *Ptr = OldLI.getPointerOperand();
2154  auto *ITy = cast<IntegerType>(NewTy);
2155  auto *NullInt = ConstantExpr::getPtrToInt(
2156  ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
2157  auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
2159  MDB.createRange(NonNullInt, NullInt));
2160 }
2161 
2162 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
2163  MDNode *N, LoadInst &NewLI) {
2164  auto *NewTy = NewLI.getType();
2165 
2166  // Give up unless it is converted to a pointer where there is a single very
2167  // valuable mapping we can do reliably.
2168  // FIXME: It would be nice to propagate this in more ways, but the type
2169  // conversions make it hard.
2170  if (!NewTy->isPointerTy())
2171  return;
2172 
2173  unsigned BitWidth = DL.getIndexTypeSizeInBits(NewTy);
2174  if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
2175  MDNode *NN = MDNode::get(OldLI.getContext(), None);
2177  }
2178 }
2179 
2180 namespace {
2181 
2182 /// A potential constituent of a bitreverse or bswap expression. See
2183 /// collectBitParts for a fuller explanation.
2184 struct BitPart {
2185  BitPart(Value *P, unsigned BW) : Provider(P) {
2186  Provenance.resize(BW);
2187  }
2188 
2189  /// The Value that this is a bitreverse/bswap of.
2190  Value *Provider;
2191 
2192  /// The "provenance" of each bit. Provenance[A] = B means that bit A
2193  /// in Provider becomes bit B in the result of this expression.
2194  SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
2195 
2196  enum { Unset = -1 };
2197 };
2198 
2199 } // end anonymous namespace
2200 
2201 /// Analyze the specified subexpression and see if it is capable of providing
2202 /// pieces of a bswap or bitreverse. The subexpression provides a potential
2203 /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in
2204 /// the output of the expression came from a corresponding bit in some other
2205 /// value. This function is recursive, and the end result is a mapping of
2206 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
2207 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
2208 ///
2209 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
2210 /// that the expression deposits the low byte of %X into the high byte of the
2211 /// result and that all other bits are zero. This expression is accepted and a
2212 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
2213 /// [0-7].
2214 ///
2215 /// To avoid revisiting values, the BitPart results are memoized into the
2216 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
2217 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
2218 /// store BitParts objects, not pointers. As we need the concept of a nullptr
2219 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
2220 /// type instead to provide the same functionality.
2221 ///
2222 /// Because we pass around references into \c BPS, we must use a container that
2223 /// does not invalidate internal references (std::map instead of DenseMap).
2224 static const Optional<BitPart> &
2225 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
2226  std::map<Value *, Optional<BitPart>> &BPS) {
2227  auto I = BPS.find(V);
2228  if (I != BPS.end())
2229  return I->second;
2230 
2231  auto &Result = BPS[V] = None;
2232  auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
2233 
2234  if (Instruction *I = dyn_cast<Instruction>(V)) {
2235  // If this is an or instruction, it may be an inner node of the bswap.
2236  if (I->getOpcode() == Instruction::Or) {
2237  auto &A = collectBitParts(I->getOperand(0), MatchBSwaps,
2238  MatchBitReversals, BPS);
2239  auto &B = collectBitParts(I->getOperand(1), MatchBSwaps,
2240  MatchBitReversals, BPS);
2241  if (!A || !B)
2242  return Result;
2243 
2244  // Try and merge the two together.
2245  if (!A->Provider || A->Provider != B->Provider)
2246  return Result;
2247 
2248  Result = BitPart(A->Provider, BitWidth);
2249  for (unsigned i = 0; i < A->Provenance.size(); ++i) {
2250  if (A->Provenance[i] != BitPart::Unset &&
2251  B->Provenance[i] != BitPart::Unset &&
2252  A->Provenance[i] != B->Provenance[i])
2253  return Result = None;
2254 
2255  if (A->Provenance[i] == BitPart::Unset)
2256  Result->Provenance[i] = B->Provenance[i];
2257  else
2258  Result->Provenance[i] = A->Provenance[i];
2259  }
2260 
2261  return Result;
2262  }
2263 
2264  // If this is a logical shift by a constant, recurse then shift the result.
2265  if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
2266  unsigned BitShift =
2267  cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
2268  // Ensure the shift amount is defined.
2269  if (BitShift > BitWidth)
2270  return Result;
2271 
2272  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2273  MatchBitReversals, BPS);
2274  if (!Res)
2275  return Result;
2276  Result = Res;
2277 
2278  // Perform the "shift" on BitProvenance.
2279  auto &P = Result->Provenance;
2280  if (I->getOpcode() == Instruction::Shl) {
2281  P.erase(std::prev(P.end(), BitShift), P.end());
2282  P.insert(P.begin(), BitShift, BitPart::Unset);
2283  } else {
2284  P.erase(P.begin(), std::next(P.begin(), BitShift));
2285  P.insert(P.end(), BitShift, BitPart::Unset);
2286  }
2287 
2288  return Result;
2289  }
2290 
2291  // If this is a logical 'and' with a mask that clears bits, recurse then
2292  // unset the appropriate bits.
2293  if (I->getOpcode() == Instruction::And &&
2294  isa<ConstantInt>(I->getOperand(1))) {
2295  APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1);
2296  const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
2297 
2298  // Check that the mask allows a multiple of 8 bits for a bswap, for an
2299  // early exit.
2300  unsigned NumMaskedBits = AndMask.countPopulation();
2301  if (!MatchBitReversals && NumMaskedBits % 8 != 0)
2302  return Result;
2303 
2304  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2305  MatchBitReversals, BPS);
2306  if (!Res)
2307  return Result;
2308  Result = Res;
2309 
2310  for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1)
2311  // If the AndMask is zero for this bit, clear the bit.
2312  if ((AndMask & Bit) == 0)
2313  Result->Provenance[i] = BitPart::Unset;
2314  return Result;
2315  }
2316 
2317  // If this is a zext instruction zero extend the result.
2318  if (I->getOpcode() == Instruction::ZExt) {
2319  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2320  MatchBitReversals, BPS);
2321  if (!Res)
2322  return Result;
2323 
2324  Result = BitPart(Res->Provider, BitWidth);
2325  auto NarrowBitWidth =
2326  cast<IntegerType>(cast<ZExtInst>(I)->getSrcTy())->getBitWidth();
2327  for (unsigned i = 0; i < NarrowBitWidth; ++i)
2328  Result->Provenance[i] = Res->Provenance[i];
2329  for (unsigned i = NarrowBitWidth; i < BitWidth; ++i)
2330  Result->Provenance[i] = BitPart::Unset;
2331  return Result;
2332  }
2333  }
2334 
2335  // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be
2336  // the input value to the bswap/bitreverse.
2337  Result = BitPart(V, BitWidth);
2338  for (unsigned i = 0; i < BitWidth; ++i)
2339  Result->Provenance[i] = i;
2340  return Result;
2341 }
2342 
2343 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
2344  unsigned BitWidth) {
2345  if (From % 8 != To % 8)
2346  return false;
2347  // Convert from bit indices to byte indices and check for a byte reversal.
2348  From >>= 3;
2349  To >>= 3;
2350  BitWidth >>= 3;
2351  return From == BitWidth - To - 1;
2352 }
2353 
2354 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
2355  unsigned BitWidth) {
2356  return From == BitWidth - To - 1;
2357 }
2358 
2360  Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
2361  SmallVectorImpl<Instruction *> &InsertedInsts) {
2362  if (Operator::getOpcode(I) != Instruction::Or)
2363  return false;
2364  if (!MatchBSwaps && !MatchBitReversals)
2365  return false;
2366  IntegerType *ITy = dyn_cast<IntegerType>(I->getType());
2367  if (!ITy || ITy->getBitWidth() > 128)
2368  return false; // Can't do vectors or integers > 128 bits.
2369  unsigned BW = ITy->getBitWidth();
2370 
2371  unsigned DemandedBW = BW;
2372  IntegerType *DemandedTy = ITy;
2373  if (I->hasOneUse()) {
2374  if (TruncInst *Trunc = dyn_cast<TruncInst>(I->user_back())) {
2375  DemandedTy = cast<IntegerType>(Trunc->getType());
2376  DemandedBW = DemandedTy->getBitWidth();
2377  }
2378  }
2379 
2380  // Try to find all the pieces corresponding to the bswap.
2381  std::map<Value *, Optional<BitPart>> BPS;
2382  auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS);
2383  if (!Res)
2384  return false;
2385  auto &BitProvenance = Res->Provenance;
2386 
2387  // Now, is the bit permutation correct for a bswap or a bitreverse? We can
2388  // only byteswap values with an even number of bytes.
2389  bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true;
2390  for (unsigned i = 0; i < DemandedBW; ++i) {
2391  OKForBSwap &=
2392  bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW);
2393  OKForBitReverse &=
2394  bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW);
2395  }
2396 
2397  Intrinsic::ID Intrin;
2398  if (OKForBSwap && MatchBSwaps)
2399  Intrin = Intrinsic::bswap;
2400  else if (OKForBitReverse && MatchBitReversals)
2401  Intrin = Intrinsic::bitreverse;
2402  else
2403  return false;
2404 
2405  if (ITy != DemandedTy) {
2406  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
2407  Value *Provider = Res->Provider;
2408  IntegerType *ProviderTy = cast<IntegerType>(Provider->getType());
2409  // We may need to truncate the provider.
2410  if (DemandedTy != ProviderTy) {
2411  auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy,
2412  "trunc", I);
2413  InsertedInsts.push_back(Trunc);
2414  Provider = Trunc;
2415  }
2416  auto *CI = CallInst::Create(F, Provider, "rev", I);
2417  InsertedInsts.push_back(CI);
2418  auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I);
2419  InsertedInsts.push_back(ExtInst);
2420  return true;
2421  }
2422 
2423  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy);
2424  InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I));
2425  return true;
2426 }
2427 
2428 // CodeGen has special handling for some string functions that may replace
2429 // them with target-specific intrinsics. Since that'd skip our interceptors
2430 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
2431 // we mark affected calls as NoBuiltin, which will disable optimization
2432 // in CodeGen.
2434  CallInst *CI, const TargetLibraryInfo *TLI) {
2435  Function *F = CI->getCalledFunction();
2436  LibFunc Func;
2437  if (F && !F->hasLocalLinkage() && F->hasName() &&
2438  TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
2439  !F->doesNotAccessMemory())
2440  CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin);
2441 }
2442 
2443 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
2444  // We can't have a PHI with a metadata type.
2445  if (I->getOperand(OpIdx)->getType()->isMetadataTy())
2446  return false;
2447 
2448  // Early exit.
2449  if (!isa<Constant>(I->getOperand(OpIdx)))
2450  return true;
2451 
2452  switch (I->getOpcode()) {
2453  default:
2454  return true;
2455  case Instruction::Call:
2456  case Instruction::Invoke:
2457  // Can't handle inline asm. Skip it.
2458  if (isa<InlineAsm>(ImmutableCallSite(I).getCalledValue()))
2459  return false;
2460  // Many arithmetic intrinsics have no issue taking a
2461  // variable, however it's hard to distingish these from
2462  // specials such as @llvm.frameaddress that require a constant.
2463  if (isa<IntrinsicInst>(I))
2464  return false;
2465 
2466  // Constant bundle operands may need to retain their constant-ness for
2467  // correctness.
2468  if (ImmutableCallSite(I).isBundleOperand(OpIdx))
2469  return false;
2470  return true;
2471  case Instruction::ShuffleVector:
2472  // Shufflevector masks are constant.
2473  return OpIdx != 2;
2474  case Instruction::Switch:
2475  case Instruction::ExtractValue:
2476  // All operands apart from the first are constant.
2477  return OpIdx == 0;
2478  case Instruction::InsertValue:
2479  // All operands apart from the first and the second are constant.
2480  return OpIdx < 2;
2481  case Instruction::Alloca:
2482  // Static allocas (constant size in the entry block) are handled by
2483  // prologue/epilogue insertion so they're free anyway. We definitely don't
2484  // want to make them non-constant.
2485  return !dyn_cast<AllocaInst>(I)->isStaticAlloca();
2486  case Instruction::GetElementPtr:
2487  if (OpIdx == 0)
2488  return true;
2490  for (auto E = std::next(It, OpIdx); It != E; ++It)
2491  if (It.isStruct())
2492  return false;
2493  return true;
2494  }
2495 }
size_t size() const
Definition: Function.h:639
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static void appendOffset(SmallVectorImpl< uint64_t > &Ops, int64_t Offset)
Append Ops with operations to apply the Offset.
void getAllMetadataOtherThanDebugLoc(SmallVectorImpl< std::pair< unsigned, MDNode *>> &MDs) const
This does the same thing as getAllMetadata, except that it filters out the debug location.
Definition: Instruction.h:218
const NoneType None
Definition: None.h:24
uint64_t CallInst * C
DomTreeNodeBase< NodeT > * getNode(NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
use_iterator use_end()
Definition: Value.h:352
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
Function * getCalledFunction() const
Return the function called, or null if this is an indirect function invocation.
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional &#39;br Cond, TrueDest, FalseDest&#39; instruction.
Definition: IRBuilder.h:825
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:88
iterator_range< use_iterator > uses()
Definition: Value.h:360
void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs=false)
Notify the BasicBlock that the predecessor Pred is no longer able to reach it.
Definition: BasicBlock.cpp:277
bool hasLocalLinkage() const
Definition: GlobalValue.h:435
static unsigned enforceKnownAlignment(Value *V, unsigned Align, unsigned PrefAlign, const DataLayout &DL)
enforceKnownAlignment - If the specified pointer points to an object that we control, modify the object&#39;s alignment to PrefAlign.
Definition: Local.cpp:1098
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1542
unsigned getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to ensure that the alignment of V is at least PrefAlign bytes.
Definition: Local.cpp:1144
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, int Offset=0)
Replaces multiple llvm.dbg.value instructions when the alloca it describes is replaced with a new val...
Definition: Local.cpp:1480
bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress, DIBuilder &Builder, bool DerefBefore, int Offset, bool DerefAfter)
Replaces llvm.dbg.declare instruction when the alloca it describes is replaced with a new value...
Definition: Local.cpp:1445
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
void addAttribute(unsigned i, Attribute::AttrKind Kind)
adds the attribute to the list of attributes.
bool isMetadataTy() const
Return true if this is &#39;metadata&#39;.
Definition: Type.h:191
iterator erase(iterator where)
Definition: ilist.h:280
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: ValueMap.h:175
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1195
bool isBundleOperand(Value::const_user_iterator UI) const
Determine whether the passed iterator points to a bundle operand.
Definition: CallSite.h:162
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ)
CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an almost-empty BB ending in an unco...
Definition: Local.cpp:733
bool exceedsNaturalStackAlignment(unsigned Align) const
Returns true if the given alignment exceeds the natural stack alignment.
Definition: DataLayout.h:253
iterator end()
Definition: Function.h:636
match_zero m_Zero()
Match an arbitrary zero/null constant.
Definition: PatternMatch.h:145
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
This class represents zero extension of integer types.
value_op_iterator value_op_begin()
Definition: User.h:240
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:923
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1714
A cache of .assume calls within a function.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:738
value_op_iterator value_op_end()
Definition: User.h:243
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
STATISTIC(NumFunctions, "Total number of functions")
static void replaceUndefValuesInPhi(PHINode *PN, const IncomingValueMap &IncomingValues)
Replace the incoming undef values to a phi with the values from a block-to-value map.
Definition: Local.cpp:844
bool SimplifyInstructionsInBlock(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr)
Scan the specified basic block and try to simplify any instructions in it and recursively delete dead...
Definition: Local.cpp:557
A debug info location.
Definition: DebugLoc.h:34
Metadata node.
Definition: Metadata.h:862
F(f)
static CallInst * Create(Value *Func, ArrayRef< Value *> Args, ArrayRef< OperandBundleDef > Bundles=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
This class represents a sign extension of integer types.
An instruction for reading from memory.
Definition: Instructions.h:164
Hexagon Common GEP
CallingConv::ID getCallingConv() const
getCallingConv/setCallingConv - Get or set the calling convention of this function call...
static Value * selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB, IncomingValueMap &IncomingValues)
Determines the value to use as the phi node input for a block.
Definition: Local.cpp:803
This defines the Use class.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:31
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of &#39;From&#39; with &#39;To&#39; if that use is dominated by the given edge.
Definition: Local.cpp:2092
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
block_iterator block_end()
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
bool isIdenticalTo(const Instruction *I) const
Return true if the specified instruction is exactly identical to the current one. ...
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2164
unsigned getMDKindID(StringRef Name) const
getMDKindID - Return a unique non-zero ID for the specified metadata kind.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
The address of a basic block.
Definition: Constants.h:818
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr it the function does no...
Definition: BasicBlock.cpp:116
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT=nullptr, DeferredDominance *DDT=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!)...
Definition: Local.cpp:640
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
PointerType * getType() const
Overload to return most specific pointer type.
Definition: Instructions.h:97
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
static const Optional< BitPart > & collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, std::map< Value *, Optional< BitPart >> &BPS)
Analyze the specified subexpression and see if it is capable of providing pieces of a bswap or bitrev...
Definition: Local.cpp:2225
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:714
This file contains the simple types necessary to represent the attributes associated with functions a...
bool canSimplifyInvokeNoUnwind(const Function *F)
Only used in LLVM metadata.
Definition: Dwarf.h:125
static const unsigned MaximumAlignment
Definition: Value.h:600
block_iterator block_begin()
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This file implements a class to represent arbitrary precision integral constant values and operations...
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress, DIBuilder &Builder, int Offset)
Definition: Local.cpp:1452
void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode *> &InsertedPHIs)
Propagate dbg.value intrinsics through the newly inserted PHIs.
Definition: Local.cpp:1346
void addHandler(BasicBlock *Dest)
Add an entry to the switch instruction...
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
void findDbgValues(SmallVectorImpl< DbgValueInst *> &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: Local.cpp:1408
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1554
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:182
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a nonnull metadata node to a new load instruction.
Definition: Local.cpp:2137
static bool isEqual(const Function &Caller, const Function &Callee)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:125
void deleteBB(BasicBlock *DelBB)
Delays the deletion of a basic block until a flush() event.
Definition: Dominators.cpp:427
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage any dbg.value intrinsics referr...
Definition: Local.cpp:1491
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
bool has(LibFunc F) const
Tests whether a library function is available.
iterator find(const KeyT &Val)
Definition: ValueMap.h:158
bool isMathLibCallNoop(CallSite CS, const TargetLibraryInfo *TLI)
Check whether the given call has no side-effects.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:195
static bool areAllUsesEqual(Instruction *I)
areAllUsesEqual - Check whether the uses of a value are all the same.
Definition: Local.cpp:461
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:910
An instruction for storing to memory.
Definition: Instructions.h:306
bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI=nullptr, DeferredDominance *DDT=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:1930
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
Definition: Local.cpp:1039
static void gatherIncomingValuesToPhi(PHINode *PN, IncomingValueMap &IncomingValues)
Create a map from block to value for the operands of a given phi.
Definition: Local.cpp:828
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:66
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:301
iterator begin()
Definition: Function.h:634
AttributeList getAttributes() const
Return the parameter attributes for this call.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
amdgpu Simplify well known AMD library false Value * Callee
Function * getDeclaration(Module *M, ID id, ArrayRef< Type *> Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:980
This class represents a truncation of integer types.
Value * getOperand(unsigned i) const
Definition: User.h:154
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Queues multiple updates and discards duplicates.
Definition: Dominators.cpp:398
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
use_iterator_impl< Use > use_iterator
Definition: Value.h:337
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
bool doesNotAccessMemory() const
Determine if the function does not access memory.
Definition: Function.h:441
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:106
const BasicBlock & getEntryBlock() const
Definition: Function.h:618
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1164
#define P(N)
void deleteEdge(BasicBlock *From, BasicBlock *To)
Helper method for a single edge deletion.
Definition: Dominators.cpp:422
static MDNode * getMostGenericRange(MDNode *A, MDNode *B)
Definition: Metadata.cpp:978
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:171
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:200
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:282
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1355
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:217
void set(Value *Val)
Definition: Value.h:675
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
static MetadataAsValue * getIfExists(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:114
bool hasName() const
Definition: Value.h:251
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
void push_back(EltTy NewVal)
static bool LdStHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr, Instruction *I)
===---------------------------------------------------------------——===// Dbg Intrinsic utilities ...
Definition: Local.cpp:1176
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
Conditional or Unconditional Branch instruction.
bool isAddressOfVariable() const
Does this describe the address of a local variable.
Definition: IntrinsicInst.h:76
static MDNode * getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1050
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1388
Value * getAddress() const
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
This function has undefined behavior.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx)
Given an instruction, is it legal to set operand OpIdx to a non-constant value?
Definition: Local.cpp:2443
void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===---------------------------------------------------------------——===// Dbg Intrinsic utilities ...
Definition: Local.cpp:1212
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if this function has the given attribute.
Definition: CallSite.h:362
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
const Instruction & front() const
Definition: BasicBlock.h:264
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:536
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
static bool CanMergeValues(Value *First, Value *Second)
CanMergeValues - Return true if we can choose one of these values to use in place of the other...
Definition: Local.cpp:725
void pop_front()
Definition: ilist.h:327
DILocalVariable * getVariable() const
Definition: IntrinsicInst.h:80
void splice(iterator where, iplist_impl &L2)
Definition: ilist.h:342
const Instruction & back() const
Definition: BasicBlock.h:266
void copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a range metadata node to a new load instruction.
Definition: Local.cpp:2162
DIExpression * getExpression() const
Definition: IntrinsicInst.h:84
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
Value * getPointerOperand()
Definition: Instructions.h:270
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1628
bool callsGCLeafFunction(ImmutableCallSite CS, const TargetLibraryInfo &TLI)
Return true if the CallSite CS calls a gc leaf function.
Definition: Local.cpp:2111
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
self_iterator getIterator()
Definition: ilist_node.h:82
Class to represent integer types.
Definition: DerivedTypes.h:40
unsigned getIndexTypeSizeInBits(Type *Ty) const
Layout size of the index used in GEP calculation.
Definition: DataLayout.cpp:656
Metadata wrapper in the Value hierarchy.
Definition: Metadata.h:172
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DeferredDominance *DDT=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:103
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1369
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr)
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:423
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:567
static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:2354
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:835
bool LowerDbgDeclare(Function &F)
Lowers llvm.dbg.declare intrinsics into appropriate set of llvm.dbg.value intrinsics.
Definition: Local.cpp:1302
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1222
static InvokeInst * Create(Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value *> Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DeferredDominance *DDT=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes...
Definition: Local.cpp:926
void setCallingConv(CallingConv::ID CC)
static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB, const PredBlockVector &BBPreds, PHINode *PN)
Replace a value flowing from a block to a phi with potentially multiple instances of that value flowi...
Definition: Local.cpp:866
bool recursivelySimplifyInstruction(Instruction *I, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr)
Recursively attempt to simplify an instruction.
iterator end()
Definition: ValueMap.h:138
size_type size() const
Definition: SmallPtrSet.h:93
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:376
BasicBlock * getNormalDest() const
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:317
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:176
void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
Definition: BasicBlock.cpp:110
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
static CatchSwitchInst * Create(Value *ParentPad, BasicBlock *UnwindDest, unsigned NumHandlers, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static unsigned replaceDominatedUsesWith(Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates)
Definition: Local.cpp:2056
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:2343
iterator end()
Definition: BasicBlock.h:254
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:349
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:243
Module.h This file contains the declarations for the Module class.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:64
Provides information about what library functions are available for the current target.
static LocalAsMetadata * getIfExists(Value *Local)
Definition: Metadata.h:438
This is the common base class for debug info intrinsics.
Definition: IntrinsicInst.h:67
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
Definition: Local.cpp:480
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:383
DIExpression * createExpression(ArrayRef< uint64_t > Addr=None)
Create a new descriptor for the specified variable which has a complex address expression for its add...
Definition: DIBuilder.cpp:702
bool hasOptimizedCodeGen(LibFunc F) const
Tests if the function is both available and a candidate for optimized code generation.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:598
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than it&#39;s terminator and any present EH pad instruct...
Definition: Local.cpp:1610
unsigned getNumIncomingValues() const
Return the number of incoming edges.
void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT=nullptr)
Replace &#39;BB&#39;s terminator with one that does not have an unwind successor block.
Definition: Local.cpp:1890
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:238
DWARF expression.
bool isUsedByMetadata() const
Return true if there is metadata referencing this value.
Definition: Value.h:494
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
void setOperand(unsigned i_nocapture, Value *Val_nocapture)
This file contains constants used for implementing Dwarf debug support.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
Class for arbitrary precision integers.
Definition: APInt.h:69
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:602
Class to defer updates to a DominatorTree.
Definition: Dominators.h:313
iterator_range< user_iterator > users()
Definition: Value.h:405
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:91
TinyPtrVector< DbgInfoIntrinsic * > FindDbgAddrUses(Value *V)
Finds all intrinsics declaring local variables as living in the memory that &#39;V&#39; points to...
Definition: Local.cpp:1390
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:480
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:396
bool replaceDbgDeclare(Value *Address, Value *NewAddress, Instruction *InsertBefore, DIBuilder &Builder, bool DerefBefore, int Offset, bool DerefAfter)
Replaces llvm.dbg.declare instruction when the address it describes is replaced with a new value...
Definition: Local.cpp:1425
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:554
use_iterator use_begin()
Definition: Value.h:344
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
static bool simplifyAndDCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Local.cpp:501
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:285
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
static DIExpression * prepend(const DIExpression *DIExpr, bool DerefBefore, int64_t Offset=0, bool DerefAfter=false, bool StackValue=false)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value...
This represents the llvm.dbg.value instruction.
bool isTokenTy() const
Return true if this is &#39;token&#39;.
Definition: Type.h:194
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
Establish a view to a call site for examination.
Definition: CallSite.h:713
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:79
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1701
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:97
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
user_iterator_impl< User > user_iterator
Definition: Value.h:374
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc...
iterator end()
Definition: DenseMap.h:79
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:611
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:338
void maybeMarkSanitizerLibraryCallNoBuiltin(CallInst *CI, const TargetLibraryInfo *TLI)
Given a CallInst, check if it calls a string function known to CodeGen, and mark it with NoBuiltin if...
Definition: Local.cpp:2433
static DIExpression * doPrepend(const DIExpression *DIExpr, SmallVectorImpl< uint64_t > &Ops, bool StackValue=false)
Prepend DIExpr with the given opcodes and optionally turn it into a stack value.
static bool PhiHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr, PHINode *APN)
See if there is a dbg.value intrinsic for DIVar for the PHI node.
Definition: Local.cpp:1194
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:383
void combineMetadataForCSE(Instruction *K, const Instruction *J)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2044
void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred, DeferredDominance *DDT=nullptr)
Like BasicBlock::removePredecessor, this method is called when we&#39;re about to delete Pred as a predec...
Definition: Local.cpp:608
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:141
void findDbgUsers(SmallVectorImpl< DbgInfoIntrinsic *> &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: Local.cpp:1416
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DeferredDominance *DDT=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1631
void eraseBlock(BasicBlock *BB)
Inform the analysis cache that we have erased a block.
size_type size() const
Definition: ValueMap.h:143
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Definition: InstrTypes.h:1458
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:107
void recalculate(Function &F)
Drops all internal state and forces a (slow) recalculation of the DominatorTree based on the current ...
Definition: Dominators.cpp:470
const unsigned Kind
This pass computes, caches, and vends lazy value constraint information.
Definition: LazyValueInfo.h:32
static bool isArray(AllocaInst *AI)
Determine whether this alloca is either a VLA or an array.
Definition: Local.cpp:1295
const Value * getCalledValue() const
Get a pointer to the function that is invoked by this instruction.
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:381
const BasicBlock & front() const
Definition: Function.h:641
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
BasicBlock * getUnwindDest() const
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:346
LLVM Value Representation.
Definition: Value.h:73
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Definition: Operator.h:41
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional &#39;br label X&#39; instruction.
Definition: IRBuilder.h:819
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
static const Function * getParent(const Value *V)
const Value * getCalledValue() const
Get a pointer to the function that is invoked by this instruction.
BasicBlock * changeToInvokeAndSplitBasicBlock(CallInst *CI, BasicBlock *UnwindEdge)
Convert the CallInst to InvokeInst with the specified unwind edge basic block.
Definition: Local.cpp:1695
Invoke instruction.
bool wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used...
Definition: Local.cpp:353
#define DEBUG(X)
Definition: Debug.h:118
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:547
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:418
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction *> &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:2359
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:157
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
void setIncomingValue(unsigned i, Value *V)
void pop_back()
Definition: ilist.h:331
static void Split(std::vector< std::string > &V, StringRef S)
Splits a string of comma separated items in to a vector of strings.
static void changeToCall(InvokeInst *II, DeferredDominance *DDT=nullptr)
changeToCall - Convert the specified invoke into a normal call.
Definition: Local.cpp:1670
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
static MDNode * getMostGenericFPMath(MDNode *A, MDNode *B)
Definition: Metadata.cpp:930
This represents the llvm.dbg.declare instruction.
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:1979
bool use_empty() const
Definition: Value.h:328
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Type * getElementType() const
Definition: DerivedTypes.h:486
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:2075
static bool markAliveBlocks(Function &F, SmallPtrSetImpl< BasicBlock *> &Reachable, DeferredDominance *DDT=nullptr)
Definition: Local.cpp:1732
std::vector< uint32_t > Metadata
PAL metadata represented as a vector.
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:218
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60
gep_type_iterator gep_type_begin(const User *GEP)
user_iterator user_end()
Definition: Value.h:389