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