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