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