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