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 Alignment,
1136  unsigned PrefAlign,
1137  const DataLayout &DL) {
1138  assert(PrefAlign > Alignment);
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  Alignment = std::max(AI->getAlignment(), Alignment);
1150  if (PrefAlign <= Alignment)
1151  return Alignment;
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(Align(PrefAlign)))
1156  return Alignment;
1157  AI->setAlignment(MaybeAlign(PrefAlign));
1158  return PrefAlign;
1159  }
1160 
1161  if (auto *GO = dyn_cast<GlobalObject>(V)) {
1162  // TODO: as above, this shouldn't be necessary.
1163  Alignment = std::max(GO->getAlignment(), Alignment);
1164  if (PrefAlign <= Alignment)
1165  return Alignment;
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 Alignment;
1173 
1174  GO->setAlignment(MaybeAlign(PrefAlign));
1175  return PrefAlign;
1176  }
1177 
1178  return Alignment;
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.
2215  MemorySSAUpdater *MSSAU) {
2217  bool Changed = markAliveBlocks(F, Reachable, DTU);
2218 
2219  // If there are unreachable blocks in the CFG...
2220  if (Reachable.size() == F.size())
2221  return Changed;
2222 
2223  assert(Reachable.size() < F.size());
2224  NumRemoved += F.size() - Reachable.size();
2225 
2226  SmallSetVector<BasicBlock *, 8> DeadBlockSet;
2227  for (BasicBlock &BB : F) {
2228  // Skip reachable basic blocks
2229  if (Reachable.find(&BB) != Reachable.end())
2230  continue;
2231  DeadBlockSet.insert(&BB);
2232  }
2233 
2234  if (MSSAU)
2235  MSSAU->removeBlocks(DeadBlockSet);
2236 
2237  // Loop over all of the basic blocks that are not reachable, dropping all of
2238  // their internal references. Update DTU if available.
2239  std::vector<DominatorTree::UpdateType> Updates;
2240  for (auto *BB : DeadBlockSet) {
2241  for (BasicBlock *Successor : successors(BB)) {
2242  if (!DeadBlockSet.count(Successor))
2243  Successor->removePredecessor(BB);
2244  if (DTU)
2245  Updates.push_back({DominatorTree::Delete, BB, Successor});
2246  }
2247  BB->dropAllReferences();
2248  if (DTU) {
2249  Instruction *TI = BB->getTerminator();
2250  assert(TI && "Basic block should have a terminator");
2251  // Terminators like invoke can have users. We have to replace their users,
2252  // before removing them.
2253  if (!TI->use_empty())
2255  TI->eraseFromParent();
2256  new UnreachableInst(BB->getContext(), BB);
2257  assert(succ_empty(BB) && "The successor list of BB isn't empty before "
2258  "applying corresponding DTU updates.");
2259  }
2260  }
2261 
2262  if (DTU) {
2263  DTU->applyUpdatesPermissive(Updates);
2264  bool Deleted = false;
2265  for (auto *BB : DeadBlockSet) {
2266  if (DTU->isBBPendingDeletion(BB))
2267  --NumRemoved;
2268  else
2269  Deleted = true;
2270  DTU->deleteBB(BB);
2271  }
2272  if (!Deleted)
2273  return false;
2274  } else {
2275  for (auto *BB : DeadBlockSet)
2276  BB->eraseFromParent();
2277  }
2278 
2279  return true;
2280 }
2281 
2283  ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
2285  K->dropUnknownNonDebugMetadata(KnownIDs);
2286  K->getAllMetadataOtherThanDebugLoc(Metadata);
2287  for (const auto &MD : Metadata) {
2288  unsigned Kind = MD.first;
2289  MDNode *JMD = J->getMetadata(Kind);
2290  MDNode *KMD = MD.second;
2291 
2292  switch (Kind) {
2293  default:
2294  K->setMetadata(Kind, nullptr); // Remove unknown metadata
2295  break;
2296  case LLVMContext::MD_dbg:
2297  llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
2298  case LLVMContext::MD_tbaa:
2299  K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
2300  break;
2301  case LLVMContext::MD_alias_scope:
2302  K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
2303  break;
2304  case LLVMContext::MD_noalias:
2305  case LLVMContext::MD_mem_parallel_loop_access:
2306  K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
2307  break;
2308  case LLVMContext::MD_access_group:
2309  K->setMetadata(LLVMContext::MD_access_group,
2310  intersectAccessGroups(K, J));
2311  break;
2312  case LLVMContext::MD_range:
2313 
2314  // If K does move, use most generic range. Otherwise keep the range of
2315  // K.
2316  if (DoesKMove)
2317  // FIXME: If K does move, we should drop the range info and nonnull.
2318  // Currently this function is used with DoesKMove in passes
2319  // doing hoisting/sinking and the current behavior of using the
2320  // most generic range is correct in those cases.
2321  K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
2322  break;
2323  case LLVMContext::MD_fpmath:
2324  K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
2325  break;
2326  case LLVMContext::MD_invariant_load:
2327  // Only set the !invariant.load if it is present in both instructions.
2328  K->setMetadata(Kind, JMD);
2329  break;
2330  case LLVMContext::MD_nonnull:
2331  // If K does move, keep nonull if it is present in both instructions.
2332  if (DoesKMove)
2333  K->setMetadata(Kind, JMD);
2334  break;
2335  case LLVMContext::MD_invariant_group:
2336  // Preserve !invariant.group in K.
2337  break;
2338  case LLVMContext::MD_align:
2339  K->setMetadata(Kind,
2341  break;
2342  case LLVMContext::MD_dereferenceable:
2343  case LLVMContext::MD_dereferenceable_or_null:
2344  K->setMetadata(Kind,
2346  break;
2347  case LLVMContext::MD_preserve_access_index:
2348  // Preserve !preserve.access.index in K.
2349  break;
2350  }
2351  }
2352  // Set !invariant.group from J if J has it. If both instructions have it
2353  // then we will just pick it from J - even when they are different.
2354  // Also make sure that K is load or store - f.e. combining bitcast with load
2355  // could produce bitcast with invariant.group metadata, which is invalid.
2356  // FIXME: we should try to preserve both invariant.group md if they are
2357  // different, but right now instruction can only have one invariant.group.
2358  if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2359  if (isa<LoadInst>(K) || isa<StoreInst>(K))
2360  K->setMetadata(LLVMContext::MD_invariant_group, JMD);
2361 }
2362 
2364  bool KDominatesJ) {
2365  unsigned KnownIDs[] = {
2366  LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2367  LLVMContext::MD_noalias, LLVMContext::MD_range,
2368  LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull,
2369  LLVMContext::MD_invariant_group, LLVMContext::MD_align,
2370  LLVMContext::MD_dereferenceable,
2371  LLVMContext::MD_dereferenceable_or_null,
2372  LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index};
2373  combineMetadata(K, J, KnownIDs, KDominatesJ);
2374 }
2375 
2378  Source.getAllMetadata(MD);
2379  MDBuilder MDB(Dest.getContext());
2380  Type *NewType = Dest.getType();
2381  const DataLayout &DL = Source.getModule()->getDataLayout();
2382  for (const auto &MDPair : MD) {
2383  unsigned ID = MDPair.first;
2384  MDNode *N = MDPair.second;
2385  // Note, essentially every kind of metadata should be preserved here! This
2386  // routine is supposed to clone a load instruction changing *only its type*.
2387  // The only metadata it makes sense to drop is metadata which is invalidated
2388  // when the pointer type changes. This should essentially never be the case
2389  // in LLVM, but we explicitly switch over only known metadata to be
2390  // conservatively correct. If you are adding metadata to LLVM which pertains
2391  // to loads, you almost certainly want to add it here.
2392  switch (ID) {
2393  case LLVMContext::MD_dbg:
2394  case LLVMContext::MD_tbaa:
2395  case LLVMContext::MD_prof:
2396  case LLVMContext::MD_fpmath:
2397  case LLVMContext::MD_tbaa_struct:
2398  case LLVMContext::MD_invariant_load:
2399  case LLVMContext::MD_alias_scope:
2400  case LLVMContext::MD_noalias:
2401  case LLVMContext::MD_nontemporal:
2402  case LLVMContext::MD_mem_parallel_loop_access:
2403  case LLVMContext::MD_access_group:
2404  // All of these directly apply.
2405  Dest.setMetadata(ID, N);
2406  break;
2407 
2408  case LLVMContext::MD_nonnull:
2409  copyNonnullMetadata(Source, N, Dest);
2410  break;
2411 
2412  case LLVMContext::MD_align:
2413  case LLVMContext::MD_dereferenceable:
2414  case LLVMContext::MD_dereferenceable_or_null:
2415  // These only directly apply if the new type is also a pointer.
2416  if (NewType->isPointerTy())
2417  Dest.setMetadata(ID, N);
2418  break;
2419 
2420  case LLVMContext::MD_range:
2421  copyRangeMetadata(DL, Source, N, Dest);
2422  break;
2423  }
2424  }
2425 }
2426 
2428  auto *ReplInst = dyn_cast<Instruction>(Repl);
2429  if (!ReplInst)
2430  return;
2431 
2432  // Patch the replacement so that it is not more restrictive than the value
2433  // being replaced.
2434  // Note that if 'I' is a load being replaced by some operation,
2435  // for example, by an arithmetic operation, then andIRFlags()
2436  // would just erase all math flags from the original arithmetic
2437  // operation, which is clearly not wanted and not needed.
2438  if (!isa<LoadInst>(I))
2439  ReplInst->andIRFlags(I);
2440 
2441  // FIXME: If both the original and replacement value are part of the
2442  // same control-flow region (meaning that the execution of one
2443  // guarantees the execution of the other), then we can combine the
2444  // noalias scopes here and do better than the general conservative
2445  // answer used in combineMetadata().
2446 
2447  // In general, GVN unifies expressions over different control-flow
2448  // regions, and so we need a conservative combination of the noalias
2449  // scopes.
2450  static const unsigned KnownIDs[] = {
2451  LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2452  LLVMContext::MD_noalias, LLVMContext::MD_range,
2453  LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
2454  LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull,
2455  LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index};
2456  combineMetadata(ReplInst, I, KnownIDs, false);
2457 }
2458 
2459 template <typename RootType, typename DominatesFn>
2460 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
2461  const RootType &Root,
2462  const DominatesFn &Dominates) {
2463  assert(From->getType() == To->getType());
2464 
2465  unsigned Count = 0;
2466  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2467  UI != UE;) {
2468  Use &U = *UI++;
2469  if (!Dominates(Root, U))
2470  continue;
2471  U.set(To);
2472  LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()
2473  << "' as " << *To << " in " << *U << "\n");
2474  ++Count;
2475  }
2476  return Count;
2477 }
2478 
2480  assert(From->getType() == To->getType());
2481  auto *BB = From->getParent();
2482  unsigned Count = 0;
2483 
2484  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2485  UI != UE;) {
2486  Use &U = *UI++;
2487  auto *I = cast<Instruction>(U.getUser());
2488  if (I->getParent() == BB)
2489  continue;
2490  U.set(To);
2491  ++Count;
2492  }
2493  return Count;
2494 }
2495 
2497  DominatorTree &DT,
2498  const BasicBlockEdge &Root) {
2499  auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2500  return DT.dominates(Root, U);
2501  };
2502  return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2503 }
2504 
2506  DominatorTree &DT,
2507  const BasicBlock *BB) {
2508  auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
2509  auto *I = cast<Instruction>(U.getUser())->getParent();
2510  return DT.properlyDominates(BB, I);
2511  };
2512  return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
2513 }
2514 
2516  const TargetLibraryInfo &TLI) {
2517  // Check if the function is specifically marked as a gc leaf function.
2518  if (Call->hasFnAttr("gc-leaf-function"))
2519  return true;
2520  if (const Function *F = Call->getCalledFunction()) {
2521  if (F->hasFnAttribute("gc-leaf-function"))
2522  return true;
2523 
2524  if (auto IID = F->getIntrinsicID())
2525  // Most LLVM intrinsics do not take safepoints.
2526  return IID != Intrinsic::experimental_gc_statepoint &&
2527  IID != Intrinsic::experimental_deoptimize;
2528  }
2529 
2530  // Lib calls can be materialized by some passes, and won't be
2531  // marked as 'gc-leaf-function.' All available Libcalls are
2532  // GC-leaf.
2533  LibFunc LF;
2534  if (TLI.getLibFunc(ImmutableCallSite(Call), LF)) {
2535  return TLI.has(LF);
2536  }
2537 
2538  return false;
2539 }
2540 
2542  LoadInst &NewLI) {
2543  auto *NewTy = NewLI.getType();
2544 
2545  // This only directly applies if the new type is also a pointer.
2546  if (NewTy->isPointerTy()) {
2547  NewLI.setMetadata(LLVMContext::MD_nonnull, N);
2548  return;
2549  }
2550 
2551  // The only other translation we can do is to integral loads with !range
2552  // metadata.
2553  if (!NewTy->isIntegerTy())
2554  return;
2555 
2556  MDBuilder MDB(NewLI.getContext());
2557  const Value *Ptr = OldLI.getPointerOperand();
2558  auto *ITy = cast<IntegerType>(NewTy);
2559  auto *NullInt = ConstantExpr::getPtrToInt(
2560  ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
2561  auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
2562  NewLI.setMetadata(LLVMContext::MD_range,
2563  MDB.createRange(NonNullInt, NullInt));
2564 }
2565 
2566 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
2567  MDNode *N, LoadInst &NewLI) {
2568  auto *NewTy = NewLI.getType();
2569 
2570  // Give up unless it is converted to a pointer where there is a single very
2571  // valuable mapping we can do reliably.
2572  // FIXME: It would be nice to propagate this in more ways, but the type
2573  // conversions make it hard.
2574  if (!NewTy->isPointerTy())
2575  return;
2576 
2577  unsigned BitWidth = DL.getIndexTypeSizeInBits(NewTy);
2578  if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
2579  MDNode *NN = MDNode::get(OldLI.getContext(), None);
2580  NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
2581  }
2582 }
2583 
2586  findDbgUsers(DbgUsers, &I);
2587  for (auto *DII : DbgUsers)
2588  DII->eraseFromParent();
2589 }
2590 
2592  BasicBlock *BB) {
2593  // Since we are moving the instructions out of its basic block, we do not
2594  // retain their original debug locations (DILocations) and debug intrinsic
2595  // instructions.
2596  //
2597  // Doing so would degrade the debugging experience and adversely affect the
2598  // accuracy of profiling information.
2599  //
2600  // Currently, when hoisting the instructions, we take the following actions:
2601  // - Remove their debug intrinsic instructions.
2602  // - Set their debug locations to the values from the insertion point.
2603  //
2604  // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
2605  // need to be deleted, is because there will not be any instructions with a
2606  // DILocation in either branch left after performing the transformation. We
2607  // can only insert a dbg.value after the two branches are joined again.
2608  //
2609  // See PR38762, PR39243 for more details.
2610  //
2611  // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
2612  // encode predicated DIExpressions that yield different results on different
2613  // code paths.
2614  for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
2615  Instruction *I = &*II;
2617  if (I->isUsedByMetadata())
2618  dropDebugUsers(*I);
2619  if (isa<DbgInfoIntrinsic>(I)) {
2620  // Remove DbgInfo Intrinsics.
2621  II = I->eraseFromParent();
2622  continue;
2623  }
2624  I->setDebugLoc(InsertPt->getDebugLoc());
2625  ++II;
2626  }
2627  DomBlock->getInstList().splice(InsertPt->getIterator(), BB->getInstList(),
2628  BB->begin(),
2629  BB->getTerminator()->getIterator());
2630 }
2631 
2632 namespace {
2633 
2634 /// A potential constituent of a bitreverse or bswap expression. See
2635 /// collectBitParts for a fuller explanation.
2636 struct BitPart {
2637  BitPart(Value *P, unsigned BW) : Provider(P) {
2638  Provenance.resize(BW);
2639  }
2640 
2641  /// The Value that this is a bitreverse/bswap of.
2642  Value *Provider;
2643 
2644  /// The "provenance" of each bit. Provenance[A] = B means that bit A
2645  /// in Provider becomes bit B in the result of this expression.
2646  SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
2647 
2648  enum { Unset = -1 };
2649 };
2650 
2651 } // end anonymous namespace
2652 
2653 /// Analyze the specified subexpression and see if it is capable of providing
2654 /// pieces of a bswap or bitreverse. The subexpression provides a potential
2655 /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in
2656 /// the output of the expression came from a corresponding bit in some other
2657 /// value. This function is recursive, and the end result is a mapping of
2658 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
2659 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
2660 ///
2661 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
2662 /// that the expression deposits the low byte of %X into the high byte of the
2663 /// result and that all other bits are zero. This expression is accepted and a
2664 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
2665 /// [0-7].
2666 ///
2667 /// To avoid revisiting values, the BitPart results are memoized into the
2668 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
2669 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
2670 /// store BitParts objects, not pointers. As we need the concept of a nullptr
2671 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
2672 /// type instead to provide the same functionality.
2673 ///
2674 /// Because we pass around references into \c BPS, we must use a container that
2675 /// does not invalidate internal references (std::map instead of DenseMap).
2676 static const Optional<BitPart> &
2677 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
2678  std::map<Value *, Optional<BitPart>> &BPS, int Depth) {
2679  auto I = BPS.find(V);
2680  if (I != BPS.end())
2681  return I->second;
2682 
2683  auto &Result = BPS[V] = None;
2684  auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
2685 
2686  // Prevent stack overflow by limiting the recursion depth
2687  if (Depth == BitPartRecursionMaxDepth) {
2688  LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n");
2689  return Result;
2690  }
2691 
2692  if (Instruction *I = dyn_cast<Instruction>(V)) {
2693  // If this is an or instruction, it may be an inner node of the bswap.
2694  if (I->getOpcode() == Instruction::Or) {
2695  auto &A = collectBitParts(I->getOperand(0), MatchBSwaps,
2696  MatchBitReversals, BPS, Depth + 1);
2697  auto &B = collectBitParts(I->getOperand(1), MatchBSwaps,
2698  MatchBitReversals, BPS, Depth + 1);
2699  if (!A || !B)
2700  return Result;
2701 
2702  // Try and merge the two together.
2703  if (!A->Provider || A->Provider != B->Provider)
2704  return Result;
2705 
2706  Result = BitPart(A->Provider, BitWidth);
2707  for (unsigned i = 0; i < A->Provenance.size(); ++i) {
2708  if (A->Provenance[i] != BitPart::Unset &&
2709  B->Provenance[i] != BitPart::Unset &&
2710  A->Provenance[i] != B->Provenance[i])
2711  return Result = None;
2712 
2713  if (A->Provenance[i] == BitPart::Unset)
2714  Result->Provenance[i] = B->Provenance[i];
2715  else
2716  Result->Provenance[i] = A->Provenance[i];
2717  }
2718 
2719  return Result;
2720  }
2721 
2722  // If this is a logical shift by a constant, recurse then shift the result.
2723  if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
2724  unsigned BitShift =
2725  cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
2726  // Ensure the shift amount is defined.
2727  if (BitShift > BitWidth)
2728  return Result;
2729 
2730  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2731  MatchBitReversals, BPS, Depth + 1);
2732  if (!Res)
2733  return Result;
2734  Result = Res;
2735 
2736  // Perform the "shift" on BitProvenance.
2737  auto &P = Result->Provenance;
2738  if (I->getOpcode() == Instruction::Shl) {
2739  P.erase(std::prev(P.end(), BitShift), P.end());
2740  P.insert(P.begin(), BitShift, BitPart::Unset);
2741  } else {
2742  P.erase(P.begin(), std::next(P.begin(), BitShift));
2743  P.insert(P.end(), BitShift, BitPart::Unset);
2744  }
2745 
2746  return Result;
2747  }
2748 
2749  // If this is a logical 'and' with a mask that clears bits, recurse then
2750  // unset the appropriate bits.
2751  if (I->getOpcode() == Instruction::And &&
2752  isa<ConstantInt>(I->getOperand(1))) {
2753  APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1);
2754  const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
2755 
2756  // Check that the mask allows a multiple of 8 bits for a bswap, for an
2757  // early exit.
2758  unsigned NumMaskedBits = AndMask.countPopulation();
2759  if (!MatchBitReversals && NumMaskedBits % 8 != 0)
2760  return Result;
2761 
2762  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2763  MatchBitReversals, BPS, Depth + 1);
2764  if (!Res)
2765  return Result;
2766  Result = Res;
2767 
2768  for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1)
2769  // If the AndMask is zero for this bit, clear the bit.
2770  if ((AndMask & Bit) == 0)
2771  Result->Provenance[i] = BitPart::Unset;
2772  return Result;
2773  }
2774 
2775  // If this is a zext instruction zero extend the result.
2776  if (I->getOpcode() == Instruction::ZExt) {
2777  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2778  MatchBitReversals, BPS, Depth + 1);
2779  if (!Res)
2780  return Result;
2781 
2782  Result = BitPart(Res->Provider, BitWidth);
2783  auto NarrowBitWidth =
2784  cast<IntegerType>(cast<ZExtInst>(I)->getSrcTy())->getBitWidth();
2785  for (unsigned i = 0; i < NarrowBitWidth; ++i)
2786  Result->Provenance[i] = Res->Provenance[i];
2787  for (unsigned i = NarrowBitWidth; i < BitWidth; ++i)
2788  Result->Provenance[i] = BitPart::Unset;
2789  return Result;
2790  }
2791  }
2792 
2793  // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be
2794  // the input value to the bswap/bitreverse.
2795  Result = BitPart(V, BitWidth);
2796  for (unsigned i = 0; i < BitWidth; ++i)
2797  Result->Provenance[i] = i;
2798  return Result;
2799 }
2800 
2801 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
2802  unsigned BitWidth) {
2803  if (From % 8 != To % 8)
2804  return false;
2805  // Convert from bit indices to byte indices and check for a byte reversal.
2806  From >>= 3;
2807  To >>= 3;
2808  BitWidth >>= 3;
2809  return From == BitWidth - To - 1;
2810 }
2811 
2812 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
2813  unsigned BitWidth) {
2814  return From == BitWidth - To - 1;
2815 }
2816 
2818  Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
2819  SmallVectorImpl<Instruction *> &InsertedInsts) {
2820  if (Operator::getOpcode(I) != Instruction::Or)
2821  return false;
2822  if (!MatchBSwaps && !MatchBitReversals)
2823  return false;
2824  IntegerType *ITy = dyn_cast<IntegerType>(I->getType());
2825  if (!ITy || ITy->getBitWidth() > 128)
2826  return false; // Can't do vectors or integers > 128 bits.
2827  unsigned BW = ITy->getBitWidth();
2828 
2829  unsigned DemandedBW = BW;
2830  IntegerType *DemandedTy = ITy;
2831  if (I->hasOneUse()) {
2832  if (TruncInst *Trunc = dyn_cast<TruncInst>(I->user_back())) {
2833  DemandedTy = cast<IntegerType>(Trunc->getType());
2834  DemandedBW = DemandedTy->getBitWidth();
2835  }
2836  }
2837 
2838  // Try to find all the pieces corresponding to the bswap.
2839  std::map<Value *, Optional<BitPart>> BPS;
2840  auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0);
2841  if (!Res)
2842  return false;
2843  auto &BitProvenance = Res->Provenance;
2844 
2845  // Now, is the bit permutation correct for a bswap or a bitreverse? We can
2846  // only byteswap values with an even number of bytes.
2847  bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true;
2848  for (unsigned i = 0; i < DemandedBW; ++i) {
2849  OKForBSwap &=
2850  bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW);
2851  OKForBitReverse &=
2852  bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW);
2853  }
2854 
2855  Intrinsic::ID Intrin;
2856  if (OKForBSwap && MatchBSwaps)
2857  Intrin = Intrinsic::bswap;
2858  else if (OKForBitReverse && MatchBitReversals)
2859  Intrin = Intrinsic::bitreverse;
2860  else
2861  return false;
2862 
2863  if (ITy != DemandedTy) {
2864  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
2865  Value *Provider = Res->Provider;
2866  IntegerType *ProviderTy = cast<IntegerType>(Provider->getType());
2867  // We may need to truncate the provider.
2868  if (DemandedTy != ProviderTy) {
2869  auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy,
2870  "trunc", I);
2871  InsertedInsts.push_back(Trunc);
2872  Provider = Trunc;
2873  }
2874  auto *CI = CallInst::Create(F, Provider, "rev", I);
2875  InsertedInsts.push_back(CI);
2876  auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I);
2877  InsertedInsts.push_back(ExtInst);
2878  return true;
2879  }
2880 
2881  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy);
2882  InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I));
2883  return true;
2884 }
2885 
2886 // CodeGen has special handling for some string functions that may replace
2887 // them with target-specific intrinsics. Since that'd skip our interceptors
2888 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
2889 // we mark affected calls as NoBuiltin, which will disable optimization
2890 // in CodeGen.
2892  CallInst *CI, const TargetLibraryInfo *TLI) {
2893  Function *F = CI->getCalledFunction();
2894  LibFunc Func;
2895  if (F && !F->hasLocalLinkage() && F->hasName() &&
2896  TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
2897  !F->doesNotAccessMemory())
2898  CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin);
2899 }
2900 
2901 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
2902  // We can't have a PHI with a metadata type.
2903  if (I->getOperand(OpIdx)->getType()->isMetadataTy())
2904  return false;
2905 
2906  // Early exit.
2907  if (!isa<Constant>(I->getOperand(OpIdx)))
2908  return true;
2909 
2910  switch (I->getOpcode()) {
2911  default:
2912  return true;
2913  case Instruction::Call:
2914  case Instruction::Invoke:
2915  // Can't handle inline asm. Skip it.
2916  if (isa<InlineAsm>(ImmutableCallSite(I).getCalledValue()))
2917  return false;
2918  // Many arithmetic intrinsics have no issue taking a
2919  // variable, however it's hard to distingish these from
2920  // specials such as @llvm.frameaddress that require a constant.
2921  if (isa<IntrinsicInst>(I))
2922  return false;
2923 
2924  // Constant bundle operands may need to retain their constant-ness for
2925  // correctness.
2926  if (ImmutableCallSite(I).isBundleOperand(OpIdx))
2927  return false;
2928  return true;
2929  case Instruction::ShuffleVector:
2930  // Shufflevector masks are constant.
2931  return OpIdx != 2;
2932  case Instruction::Switch:
2933  case Instruction::ExtractValue:
2934  // All operands apart from the first are constant.
2935  return OpIdx == 0;
2936  case Instruction::InsertValue:
2937  // All operands apart from the first and the second are constant.
2938  return OpIdx < 2;
2939  case Instruction::Alloca:
2940  // Static allocas (constant size in the entry block) are handled by
2941  // prologue/epilogue insertion so they're free anyway. We definitely don't
2942  // want to make them non-constant.
2943  return !cast<AllocaInst>(I)->isStaticAlloca();
2944  case Instruction::GetElementPtr:
2945  if (OpIdx == 0)
2946  return true;
2948  for (auto E = std::next(It, OpIdx); It != E; ++It)
2949  if (It.isStruct())
2950  return false;
2951  return true;
2952  }
2953 }
2954 
2957  AllocaForValueMapTy &AllocaForValue) {
2958  if (AllocaInst *AI = dyn_cast<AllocaInst>(V))
2959  return AI;
2960  // See if we've already calculated (or started to calculate) alloca for a
2961  // given value.
2962  AllocaForValueMapTy::iterator I = AllocaForValue.find(V);
2963  if (I != AllocaForValue.end())
2964  return I->second;
2965  // Store 0 while we're calculating alloca for value V to avoid
2966  // infinite recursion if the value references itself.
2967  AllocaForValue[V] = nullptr;
2968  AllocaInst *Res = nullptr;
2969  if (CastInst *CI = dyn_cast<CastInst>(V))
2970  Res = findAllocaForValue(CI->getOperand(0), AllocaForValue);
2971  else if (PHINode *PN = dyn_cast<PHINode>(V)) {
2972  for (Value *IncValue : PN->incoming_values()) {
2973  // Allow self-referencing phi-nodes.
2974  if (IncValue == PN)
2975  continue;
2976  AllocaInst *IncValueAI = findAllocaForValue(IncValue, AllocaForValue);
2977  // AI for incoming values should exist and should all be equal.
2978  if (IncValueAI == nullptr || (Res != nullptr && IncValueAI != Res))
2979  return nullptr;
2980  Res = IncValueAI;
2981  }
2982  } else if (GetElementPtrInst *EP = dyn_cast<GetElementPtrInst>(V)) {
2983  Res = findAllocaForValue(EP->getPointerOperand(), AllocaForValue);
2984  } else {
2985  LLVM_DEBUG(dbgs() << "Alloca search cancelled on unknown instruction: "
2986  << *V << "\n");
2987  }
2988  if (Res)
2989  AllocaForValue[V] = Res;
2990  return Res;
2991 }
size_t size() const
Definition: Function.h:690
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:415
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:367
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:375
bool hasLocalLinkage() const
Definition: GlobalValue.h:445
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:1571
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
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:403
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:191
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:66
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
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:308
void push_back(const T &Elt)
Definition: SmallVector.h:211
value_op_iterator value_op_begin()
Definition: User.h:255
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:743
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:169
Hexagon Common GEP
void setOperand(unsigned I, Metadata *New)
Set an operand.
Definition: Metadata.cpp:870
TypeSize getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:624
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:144
iv Induction Variable Users
Definition: IVUsers.cpp:51
bool exceedsNaturalStackAlignment(Align Alignment) const
Returns true if the given alignment exceeds the natural stack alignment.
Definition: DataLayout.h:264
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:2496
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
static unsigned enforceKnownAlignment(Value *V, unsigned Alignment, 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
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:273
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:140
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:2591
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:2427
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
iterator find(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:382
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:197
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:655
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:1583
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
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:2541
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:142
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:212
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:2282
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:2584
An instruction for storing to memory.
Definition: Instructions.h:325
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:71
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
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:1093
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:352
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:478
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:105
const BasicBlock & getEntryBlock() const
Definition: Function.h:669
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:881
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:196
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:223
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:240
void set(Value *Val)
Definition: Value.h:730
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:252
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:115
void push_back(EltTy NewVal)
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static bool LdStHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr, Instruction *I)
===---------------------------------------------------------------——===// Dbg Intrinsic utilities ...
Definition: Local.cpp: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:2901
Value * getIncomingValueForBlock(const BasicBlock *BB) const
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
const Instruction & front() const
Definition: BasicBlock.h:285
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:287
constexpr double e
Definition: MathExtras.h:57
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:2566
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
op_range operands()
Definition: User.h:237
Value * getPointerOperand()
Definition: Instructions.h:289
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2101
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:687
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:529
static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:2812
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:396
BasicBlock * getNormalDest() const
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:338
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:134
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
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
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:2460
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:2801
iterator end()
Definition: BasicBlock.h:275
This struct is a compact representation of a valid (power of two) or undefined (0) alignment...
Definition: Alignment.h:117
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:2515
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:1849
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:1604
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:509
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:599
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:420
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:477
bool isNonIntegralPointerType(PointerType *PT) const
Definition: DataLayout.h:380
bool isBundleOperand(Value::const_user_iterator UI) const
Determine whether the passed iterator points to a bundle operand.
Definition: CallSite.h:169
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:359
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:180
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:194
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:906
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:121
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
user_iterator_impl< User > user_iterator
Definition: Value.h:389
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:2376
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
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:2891
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:414
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:2214
TypeSize getTypeAllocSizeInBits(Type *Ty) const
Returns the offset in bits between successive objects of the specified type, including alignment padd...
Definition: DataLayout.h:499
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
iterator end() const
Definition: SmallPtrSet.h:401
size_type size() const
Definition: ValueMap.h:141
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:396
const BasicBlock & front() const
Definition: Function.h:692
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:2677
BasicBlock * getUnwindDest() const
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:74
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:2363
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:433
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:2817
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:343
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:2479
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:218
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:221
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h: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:404