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