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