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