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