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 
1865  if (!Signed) {
1866  // In the unsigned case, assume that a debugger will initialize the
1867  // high bits to 0 and do a no-op conversion.
1868  return Identity(DII);
1869  } else {
1870  // In the signed case, the high bits are given by sign extension, i.e:
1871  // (To >> (ToBits - 1)) * ((2 ^ FromBits) - 1)
1872  // Calculate the high bits and OR them together with the low bits.
1873  SmallVector<uint64_t, 8> Ops({dwarf::DW_OP_dup, dwarf::DW_OP_constu,
1874  (ToBits - 1), dwarf::DW_OP_shr,
1875  dwarf::DW_OP_lit0, dwarf::DW_OP_not,
1876  dwarf::DW_OP_mul, dwarf::DW_OP_or});
1877  return DIExpression::appendToStack(DII.getExpression(), Ops);
1878  }
1879  };
1880  return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt);
1881  }
1882 
1883  // TODO: Floating-point conversions, vectors.
1884  return false;
1885 }
1886 
1888  unsigned NumDeadInst = 0;
1889  // Delete the instructions backwards, as it has a reduced likelihood of
1890  // having to update as many def-use and use-def chains.
1891  Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
1892  while (EndInst != &BB->front()) {
1893  // Delete the next to last instruction.
1894  Instruction *Inst = &*--EndInst->getIterator();
1895  if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
1896  Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
1897  if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
1898  EndInst = Inst;
1899  continue;
1900  }
1901  if (!isa<DbgInfoIntrinsic>(Inst))
1902  ++NumDeadInst;
1903  Inst->eraseFromParent();
1904  }
1905  return NumDeadInst;
1906 }
1907 
1908 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
1909  bool PreserveLCSSA, DomTreeUpdater *DTU) {
1910  BasicBlock *BB = I->getParent();
1911  std::vector <DominatorTree::UpdateType> Updates;
1912 
1913  // Loop over all of the successors, removing BB's entry from any PHI
1914  // nodes.
1915  if (DTU)
1916  Updates.reserve(BB->getTerminator()->getNumSuccessors());
1917  for (BasicBlock *Successor : successors(BB)) {
1918  Successor->removePredecessor(BB, PreserveLCSSA);
1919  if (DTU)
1920  Updates.push_back({DominatorTree::Delete, BB, Successor});
1921  }
1922  // Insert a call to llvm.trap right before this. This turns the undefined
1923  // behavior into a hard fail instead of falling through into random code.
1924  if (UseLLVMTrap) {
1925  Function *TrapFn =
1926  Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
1927  CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
1928  CallTrap->setDebugLoc(I->getDebugLoc());
1929  }
1930  auto *UI = new UnreachableInst(I->getContext(), I);
1931  UI->setDebugLoc(I->getDebugLoc());
1932 
1933  // All instructions after this are dead.
1934  unsigned NumInstrsRemoved = 0;
1935  BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
1936  while (BBI != BBE) {
1937  if (!BBI->use_empty())
1938  BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
1939  BB->getInstList().erase(BBI++);
1940  ++NumInstrsRemoved;
1941  }
1942  if (DTU)
1943  DTU->applyUpdatesPermissive(Updates);
1944  return NumInstrsRemoved;
1945 }
1946 
1947 /// changeToCall - Convert the specified invoke into a normal call.
1948 static void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr) {
1951  II->getOperandBundlesAsDefs(OpBundles);
1952  CallInst *NewCall = CallInst::Create(
1953  II->getFunctionType(), II->getCalledValue(), Args, OpBundles, "", II);
1954  NewCall->takeName(II);
1955  NewCall->setCallingConv(II->getCallingConv());
1956  NewCall->setAttributes(II->getAttributes());
1957  NewCall->setDebugLoc(II->getDebugLoc());
1958  NewCall->copyMetadata(*II);
1959  II->replaceAllUsesWith(NewCall);
1960 
1961  // Follow the call by a branch to the normal destination.
1962  BasicBlock *NormalDestBB = II->getNormalDest();
1963  BranchInst::Create(NormalDestBB, II);
1964 
1965  // Update PHI nodes in the unwind destination
1966  BasicBlock *BB = II->getParent();
1967  BasicBlock *UnwindDestBB = II->getUnwindDest();
1968  UnwindDestBB->removePredecessor(BB);
1969  II->eraseFromParent();
1970  if (DTU)
1971  DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDestBB}});
1972 }
1973 
1975  BasicBlock *UnwindEdge) {
1976  BasicBlock *BB = CI->getParent();
1977 
1978  // Convert this function call into an invoke instruction. First, split the
1979  // basic block.
1980  BasicBlock *Split =
1981  BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc");
1982 
1983  // Delete the unconditional branch inserted by splitBasicBlock
1984  BB->getInstList().pop_back();
1985 
1986  // Create the new invoke instruction.
1987  SmallVector<Value *, 8> InvokeArgs(CI->arg_begin(), CI->arg_end());
1989 
1990  CI->getOperandBundlesAsDefs(OpBundles);
1991 
1992  // Note: we're round tripping operand bundles through memory here, and that
1993  // can potentially be avoided with a cleverer API design that we do not have
1994  // as of this time.
1995 
1996  InvokeInst *II =
1998  UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB);
1999  II->setDebugLoc(CI->getDebugLoc());
2000  II->setCallingConv(CI->getCallingConv());
2001  II->setAttributes(CI->getAttributes());
2002 
2003  // Make sure that anything using the call now uses the invoke! This also
2004  // updates the CallGraph if present, because it uses a WeakTrackingVH.
2005  CI->replaceAllUsesWith(II);
2006 
2007  // Delete the original call
2008  Split->getInstList().pop_front();
2009  return Split;
2010 }
2011 
2013  SmallPtrSetImpl<BasicBlock *> &Reachable,
2014  DomTreeUpdater *DTU = nullptr) {
2016  BasicBlock *BB = &F.front();
2017  Worklist.push_back(BB);
2018  Reachable.insert(BB);
2019  bool Changed = false;
2020  do {
2021  BB = Worklist.pop_back_val();
2022 
2023  // Do a quick scan of the basic block, turning any obviously unreachable
2024  // instructions into LLVM unreachable insts. The instruction combining pass
2025  // canonicalizes unreachable insts into stores to null or undef.
2026  for (Instruction &I : *BB) {
2027  if (auto *CI = dyn_cast<CallInst>(&I)) {
2028  Value *Callee = CI->getCalledValue();
2029  // Handle intrinsic calls.
2030  if (Function *F = dyn_cast<Function>(Callee)) {
2031  auto IntrinsicID = F->getIntrinsicID();
2032  // Assumptions that are known to be false are equivalent to
2033  // unreachable. Also, if the condition is undefined, then we make the
2034  // choice most beneficial to the optimizer, and choose that to also be
2035  // unreachable.
2036  if (IntrinsicID == Intrinsic::assume) {
2037  if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
2038  // Don't insert a call to llvm.trap right before the unreachable.
2039  changeToUnreachable(CI, false, false, DTU);
2040  Changed = true;
2041  break;
2042  }
2043  } else if (IntrinsicID == Intrinsic::experimental_guard) {
2044  // A call to the guard intrinsic bails out of the current
2045  // compilation unit if the predicate passed to it is false. If the
2046  // predicate is a constant false, then we know the guard will bail
2047  // out of the current compile unconditionally, so all code following
2048  // it is dead.
2049  //
2050  // Note: unlike in llvm.assume, it is not "obviously profitable" for
2051  // guards to treat `undef` as `false` since a guard on `undef` can
2052  // still be useful for widening.
2053  if (match(CI->getArgOperand(0), m_Zero()))
2054  if (!isa<UnreachableInst>(CI->getNextNode())) {
2055  changeToUnreachable(CI->getNextNode(), /*UseLLVMTrap=*/false,
2056  false, DTU);
2057  Changed = true;
2058  break;
2059  }
2060  }
2061  } else if ((isa<ConstantPointerNull>(Callee) &&
2062  !NullPointerIsDefined(CI->getFunction())) ||
2063  isa<UndefValue>(Callee)) {
2064  changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DTU);
2065  Changed = true;
2066  break;
2067  }
2068  if (CI->doesNotReturn()) {
2069  // If we found a call to a no-return function, insert an unreachable
2070  // instruction after it. Make sure there isn't *already* one there
2071  // though.
2072  if (!isa<UnreachableInst>(CI->getNextNode())) {
2073  // Don't insert a call to llvm.trap right before the unreachable.
2074  changeToUnreachable(CI->getNextNode(), false, false, DTU);
2075  Changed = true;
2076  }
2077  break;
2078  }
2079  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
2080  // Store to undef and store to null are undefined and used to signal
2081  // that they should be changed to unreachable by passes that can't
2082  // modify the CFG.
2083 
2084  // Don't touch volatile stores.
2085  if (SI->isVolatile()) continue;
2086 
2087  Value *Ptr = SI->getOperand(1);
2088 
2089  if (isa<UndefValue>(Ptr) ||
2090  (isa<ConstantPointerNull>(Ptr) &&
2091  !NullPointerIsDefined(SI->getFunction(),
2092  SI->getPointerAddressSpace()))) {
2093  changeToUnreachable(SI, true, false, DTU);
2094  Changed = true;
2095  break;
2096  }
2097  }
2098  }
2099 
2100  Instruction *Terminator = BB->getTerminator();
2101  if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
2102  // Turn invokes that call 'nounwind' functions into ordinary calls.
2103  Value *Callee = II->getCalledValue();
2104  if ((isa<ConstantPointerNull>(Callee) &&
2105  !NullPointerIsDefined(BB->getParent())) ||
2106  isa<UndefValue>(Callee)) {
2107  changeToUnreachable(II, true, false, DTU);
2108  Changed = true;
2109  } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
2110  if (II->use_empty() && II->onlyReadsMemory()) {
2111  // jump to the normal destination branch.
2112  BasicBlock *NormalDestBB = II->getNormalDest();
2113  BasicBlock *UnwindDestBB = II->getUnwindDest();
2114  BranchInst::Create(NormalDestBB, II);
2115  UnwindDestBB->removePredecessor(II->getParent());
2116  II->eraseFromParent();
2117  if (DTU)
2118  DTU->applyUpdatesPermissive(
2119  {{DominatorTree::Delete, BB, UnwindDestBB}});
2120  } else
2121  changeToCall(II, DTU);
2122  Changed = true;
2123  }
2124  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
2125  // Remove catchpads which cannot be reached.
2126  struct CatchPadDenseMapInfo {
2127  static CatchPadInst *getEmptyKey() {
2129  }
2130 
2131  static CatchPadInst *getTombstoneKey() {
2133  }
2134 
2135  static unsigned getHashValue(CatchPadInst *CatchPad) {
2136  return static_cast<unsigned>(hash_combine_range(
2137  CatchPad->value_op_begin(), CatchPad->value_op_end()));
2138  }
2139 
2140  static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
2141  if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
2142  RHS == getEmptyKey() || RHS == getTombstoneKey())
2143  return LHS == RHS;
2144  return LHS->isIdenticalTo(RHS);
2145  }
2146  };
2147 
2148  // Set of unique CatchPads.
2150  CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
2151  HandlerSet;
2152  detail::DenseSetEmpty Empty;
2153  for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
2154  E = CatchSwitch->handler_end();
2155  I != E; ++I) {
2156  BasicBlock *HandlerBB = *I;
2157  auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
2158  if (!HandlerSet.insert({CatchPad, Empty}).second) {
2159  CatchSwitch->removeHandler(I);
2160  --I;
2161  --E;
2162  Changed = true;
2163  }
2164  }
2165  }
2166 
2167  Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
2168  for (BasicBlock *Successor : successors(BB))
2169  if (Reachable.insert(Successor).second)
2170  Worklist.push_back(Successor);
2171  } while (!Worklist.empty());
2172  return Changed;
2173 }
2174 
2176  Instruction *TI = BB->getTerminator();
2177 
2178  if (auto *II = dyn_cast<InvokeInst>(TI)) {
2179  changeToCall(II, DTU);
2180  return;
2181  }
2182 
2183  Instruction *NewTI;
2184  BasicBlock *UnwindDest;
2185 
2186  if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
2187  NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
2188  UnwindDest = CRI->getUnwindDest();
2189  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
2190  auto *NewCatchSwitch = CatchSwitchInst::Create(
2191  CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
2192  CatchSwitch->getName(), CatchSwitch);
2193  for (BasicBlock *PadBB : CatchSwitch->handlers())
2194  NewCatchSwitch->addHandler(PadBB);
2195 
2196  NewTI = NewCatchSwitch;
2197  UnwindDest = CatchSwitch->getUnwindDest();
2198  } else {
2199  llvm_unreachable("Could not find unwind successor");
2200  }
2201 
2202  NewTI->takeName(TI);
2203  NewTI->setDebugLoc(TI->getDebugLoc());
2204  UnwindDest->removePredecessor(BB);
2205  TI->replaceAllUsesWith(NewTI);
2206  TI->eraseFromParent();
2207  if (DTU)
2208  DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDest}});
2209 }
2210 
2211 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
2212 /// if they are in a dead cycle. Return true if a change was made, false
2213 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
2214 /// after modifying the CFG.
2216  DomTreeUpdater *DTU,
2217  MemorySSAUpdater *MSSAU) {
2218  SmallPtrSet<BasicBlock*, 16> Reachable;
2219  bool Changed = markAliveBlocks(F, Reachable, DTU);
2220 
2221  // If there are unreachable blocks in the CFG...
2222  if (Reachable.size() == F.size())
2223  return Changed;
2224 
2225  assert(Reachable.size() < F.size());
2226  NumRemoved += F.size()-Reachable.size();
2227 
2228  SmallPtrSet<BasicBlock *, 16> DeadBlockSet;
2229  for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
2230  auto *BB = &*I;
2231  if (Reachable.count(BB))
2232  continue;
2233  DeadBlockSet.insert(BB);
2234  }
2235 
2236  if (MSSAU)
2237  MSSAU->removeBlocks(DeadBlockSet);
2238 
2239  // Loop over all of the basic blocks that are not reachable, dropping all of
2240  // their internal references. Update DTU and LVI if available.
2241  std::vector<DominatorTree::UpdateType> Updates;
2242  for (auto *BB : DeadBlockSet) {
2243  for (BasicBlock *Successor : successors(BB)) {
2244  if (!DeadBlockSet.count(Successor))
2245  Successor->removePredecessor(BB);
2246  if (DTU)
2247  Updates.push_back({DominatorTree::Delete, BB, Successor});
2248  }
2249  if (LVI)
2250  LVI->eraseBlock(BB);
2251  BB->dropAllReferences();
2252  }
2253  for (Function::iterator I = ++F.begin(); I != F.end();) {
2254  auto *BB = &*I;
2255  if (Reachable.count(BB)) {
2256  ++I;
2257  continue;
2258  }
2259  if (DTU) {
2260  // Remove the terminator of BB to clear the successor list of BB.
2261  if (BB->getTerminator())
2262  BB->getInstList().pop_back();
2263  new UnreachableInst(BB->getContext(), BB);
2264  assert(succ_empty(BB) && "The successor list of BB isn't empty before "
2265  "applying corresponding DTU updates.");
2266  ++I;
2267  } else {
2268  I = F.getBasicBlockList().erase(I);
2269  }
2270  }
2271 
2272  if (DTU) {
2273  DTU->applyUpdatesPermissive(Updates);
2274  bool Deleted = false;
2275  for (auto *BB : DeadBlockSet) {
2276  if (DTU->isBBPendingDeletion(BB))
2277  --NumRemoved;
2278  else
2279  Deleted = true;
2280  DTU->deleteBB(BB);
2281  }
2282  if (!Deleted)
2283  return false;
2284  }
2285  return true;
2286 }
2287 
2289  ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
2291  K->dropUnknownNonDebugMetadata(KnownIDs);
2292  K->getAllMetadataOtherThanDebugLoc(Metadata);
2293  for (const auto &MD : Metadata) {
2294  unsigned Kind = MD.first;
2295  MDNode *JMD = J->getMetadata(Kind);
2296  MDNode *KMD = MD.second;
2297 
2298  switch (Kind) {
2299  default:
2300  K->setMetadata(Kind, nullptr); // Remove unknown metadata
2301  break;
2302  case LLVMContext::MD_dbg:
2303  llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
2304  case LLVMContext::MD_tbaa:
2305  K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
2306  break;
2308  K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
2309  break;
2312  K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
2313  break;
2316  intersectAccessGroups(K, J));
2317  break;
2318  case LLVMContext::MD_range:
2319 
2320  // If K does move, use most generic range. Otherwise keep the range of
2321  // K.
2322  if (DoesKMove)
2323  // FIXME: If K does move, we should drop the range info and nonnull.
2324  // Currently this function is used with DoesKMove in passes
2325  // doing hoisting/sinking and the current behavior of using the
2326  // most generic range is correct in those cases.
2327  K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
2328  break;
2330  K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
2331  break;
2333  // Only set the !invariant.load if it is present in both instructions.
2334  K->setMetadata(Kind, JMD);
2335  break;
2337  // If K does move, keep nonull if it is present in both instructions.
2338  if (DoesKMove)
2339  K->setMetadata(Kind, JMD);
2340  break;
2342  // Preserve !invariant.group in K.
2343  break;
2344  case LLVMContext::MD_align:
2345  K->setMetadata(Kind,
2347  break;
2350  K->setMetadata(Kind,
2352  break;
2353  }
2354  }
2355  // Set !invariant.group from J if J has it. If both instructions have it
2356  // then we will just pick it from J - even when they are different.
2357  // Also make sure that K is load or store - f.e. combining bitcast with load
2358  // could produce bitcast with invariant.group metadata, which is invalid.
2359  // FIXME: we should try to preserve both invariant.group md if they are
2360  // different, but right now instruction can only have one invariant.group.
2361  if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2362  if (isa<LoadInst>(K) || isa<StoreInst>(K))
2364 }
2365 
2367  bool KDominatesJ) {
2368  unsigned KnownIDs[] = {
2376  combineMetadata(K, J, KnownIDs, KDominatesJ);
2377 }
2378 
2380  auto *ReplInst = dyn_cast<Instruction>(Repl);
2381  if (!ReplInst)
2382  return;
2383 
2384  // Patch the replacement so that it is not more restrictive than the value
2385  // being replaced.
2386  // Note that if 'I' is a load being replaced by some operation,
2387  // for example, by an arithmetic operation, then andIRFlags()
2388  // would just erase all math flags from the original arithmetic
2389  // operation, which is clearly not wanted and not needed.
2390  if (!isa<LoadInst>(I))
2391  ReplInst->andIRFlags(I);
2392 
2393  // FIXME: If both the original and replacement value are part of the
2394  // same control-flow region (meaning that the execution of one
2395  // guarantees the execution of the other), then we can combine the
2396  // noalias scopes here and do better than the general conservative
2397  // answer used in combineMetadata().
2398 
2399  // In general, GVN unifies expressions over different control-flow
2400  // regions, and so we need a conservative combination of the noalias
2401  // scopes.
2402  static const unsigned KnownIDs[] = {
2408  combineMetadata(ReplInst, I, KnownIDs, false);
2409 }
2410 
2411 template <typename RootType, typename DominatesFn>
2412 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
2413  const RootType &Root,
2414  const DominatesFn &Dominates) {
2415  assert(From->getType() == To->getType());
2416 
2417  unsigned Count = 0;
2418  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2419  UI != UE;) {
2420  Use &U = *UI++;
2421  if (!Dominates(Root, U))
2422  continue;
2423  U.set(To);
2424  LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()
2425  << "' as " << *To << " in " << *U << "\n");
2426  ++Count;
2427  }
2428  return Count;
2429 }
2430 
2432  assert(From->getType() == To->getType());
2433  auto *BB = From->getParent();
2434  unsigned Count = 0;
2435 
2436  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2437  UI != UE;) {
2438  Use &U = *UI++;
2439  auto *I = cast<Instruction>(U.getUser());
2440  if (I->getParent() == BB)
2441  continue;
2442  U.set(To);
2443  ++Count;
2444  }
2445  return Count;
2446 }
2447 
2449  DominatorTree &DT,
2450  const BasicBlockEdge &Root) {
2451  auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2452  return DT.dominates(Root, U);
2453  };
2454  return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2455 }
2456 
2458  DominatorTree &DT,
2459  const BasicBlock *BB) {
2460  auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
2461  auto *I = cast<Instruction>(U.getUser())->getParent();
2462  return DT.properlyDominates(BB, I);
2463  };
2464  return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
2465 }
2466 
2468  const TargetLibraryInfo &TLI) {
2469  // Check if the function is specifically marked as a gc leaf function.
2470  if (Call->hasFnAttr("gc-leaf-function"))
2471  return true;
2472  if (const Function *F = Call->getCalledFunction()) {
2473  if (F->hasFnAttribute("gc-leaf-function"))
2474  return true;
2475 
2476  if (auto IID = F->getIntrinsicID())
2477  // Most LLVM intrinsics do not take safepoints.
2478  return IID != Intrinsic::experimental_gc_statepoint &&
2479  IID != Intrinsic::experimental_deoptimize;
2480  }
2481 
2482  // Lib calls can be materialized by some passes, and won't be
2483  // marked as 'gc-leaf-function.' All available Libcalls are
2484  // GC-leaf.
2485  LibFunc LF;
2486  if (TLI.getLibFunc(ImmutableCallSite(Call), LF)) {
2487  return TLI.has(LF);
2488  }
2489 
2490  return false;
2491 }
2492 
2494  LoadInst &NewLI) {
2495  auto *NewTy = NewLI.getType();
2496 
2497  // This only directly applies if the new type is also a pointer.
2498  if (NewTy->isPointerTy()) {
2500  return;
2501  }
2502 
2503  // The only other translation we can do is to integral loads with !range
2504  // metadata.
2505  if (!NewTy->isIntegerTy())
2506  return;
2507 
2508  MDBuilder MDB(NewLI.getContext());
2509  const Value *Ptr = OldLI.getPointerOperand();
2510  auto *ITy = cast<IntegerType>(NewTy);
2511  auto *NullInt = ConstantExpr::getPtrToInt(
2512  ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
2513  auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
2515  MDB.createRange(NonNullInt, NullInt));
2516 }
2517 
2518 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
2519  MDNode *N, LoadInst &NewLI) {
2520  auto *NewTy = NewLI.getType();
2521 
2522  // Give up unless it is converted to a pointer where there is a single very
2523  // valuable mapping we can do reliably.
2524  // FIXME: It would be nice to propagate this in more ways, but the type
2525  // conversions make it hard.
2526  if (!NewTy->isPointerTy())
2527  return;
2528 
2529  unsigned BitWidth = DL.getIndexTypeSizeInBits(NewTy);
2530  if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
2531  MDNode *NN = MDNode::get(OldLI.getContext(), None);
2533  }
2534 }
2535 
2538  findDbgUsers(DbgUsers, &I);
2539  for (auto *DII : DbgUsers)
2540  DII->eraseFromParent();
2541 }
2542 
2544  BasicBlock *BB) {
2545  // Since we are moving the instructions out of its basic block, we do not
2546  // retain their original debug locations (DILocations) and debug intrinsic
2547  // instructions.
2548  //
2549  // Doing so would degrade the debugging experience and adversely affect the
2550  // accuracy of profiling information.
2551  //
2552  // Currently, when hoisting the instructions, we take the following actions:
2553  // - Remove their debug intrinsic instructions.
2554  // - Set their debug locations to the values from the insertion point.
2555  //
2556  // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
2557  // need to be deleted, is because there will not be any instructions with a
2558  // DILocation in either branch left after performing the transformation. We
2559  // can only insert a dbg.value after the two branches are joined again.
2560  //
2561  // See PR38762, PR39243 for more details.
2562  //
2563  // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
2564  // encode predicated DIExpressions that yield different results on different
2565  // code paths.
2566  for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
2567  Instruction *I = &*II;
2569  if (I->isUsedByMetadata())
2570  dropDebugUsers(*I);
2571  if (isa<DbgInfoIntrinsic>(I)) {
2572  // Remove DbgInfo Intrinsics.
2573  II = I->eraseFromParent();
2574  continue;
2575  }
2576  I->setDebugLoc(InsertPt->getDebugLoc());
2577  ++II;
2578  }
2579  DomBlock->getInstList().splice(InsertPt->getIterator(), BB->getInstList(),
2580  BB->begin(),
2581  BB->getTerminator()->getIterator());
2582 }
2583 
2584 namespace {
2585 
2586 /// A potential constituent of a bitreverse or bswap expression. See
2587 /// collectBitParts for a fuller explanation.
2588 struct BitPart {
2589  BitPart(Value *P, unsigned BW) : Provider(P) {
2590  Provenance.resize(BW);
2591  }
2592 
2593  /// The Value that this is a bitreverse/bswap of.
2594  Value *Provider;
2595 
2596  /// The "provenance" of each bit. Provenance[A] = B means that bit A
2597  /// in Provider becomes bit B in the result of this expression.
2598  SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
2599 
2600  enum { Unset = -1 };
2601 };
2602 
2603 } // end anonymous namespace
2604 
2605 /// Analyze the specified subexpression and see if it is capable of providing
2606 /// pieces of a bswap or bitreverse. The subexpression provides a potential
2607 /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in
2608 /// the output of the expression came from a corresponding bit in some other
2609 /// value. This function is recursive, and the end result is a mapping of
2610 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
2611 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
2612 ///
2613 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
2614 /// that the expression deposits the low byte of %X into the high byte of the
2615 /// result and that all other bits are zero. This expression is accepted and a
2616 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
2617 /// [0-7].
2618 ///
2619 /// To avoid revisiting values, the BitPart results are memoized into the
2620 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
2621 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
2622 /// store BitParts objects, not pointers. As we need the concept of a nullptr
2623 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
2624 /// type instead to provide the same functionality.
2625 ///
2626 /// Because we pass around references into \c BPS, we must use a container that
2627 /// does not invalidate internal references (std::map instead of DenseMap).
2628 static const Optional<BitPart> &
2629 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
2630  std::map<Value *, Optional<BitPart>> &BPS) {
2631  auto I = BPS.find(V);
2632  if (I != BPS.end())
2633  return I->second;
2634 
2635  auto &Result = BPS[V] = None;
2636  auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
2637 
2638  if (Instruction *I = dyn_cast<Instruction>(V)) {
2639  // If this is an or instruction, it may be an inner node of the bswap.
2640  if (I->getOpcode() == Instruction::Or) {
2641  auto &A = collectBitParts(I->getOperand(0), MatchBSwaps,
2642  MatchBitReversals, BPS);
2643  auto &B = collectBitParts(I->getOperand(1), MatchBSwaps,
2644  MatchBitReversals, BPS);
2645  if (!A || !B)
2646  return Result;
2647 
2648  // Try and merge the two together.
2649  if (!A->Provider || A->Provider != B->Provider)
2650  return Result;
2651 
2652  Result = BitPart(A->Provider, BitWidth);
2653  for (unsigned i = 0; i < A->Provenance.size(); ++i) {
2654  if (A->Provenance[i] != BitPart::Unset &&
2655  B->Provenance[i] != BitPart::Unset &&
2656  A->Provenance[i] != B->Provenance[i])
2657  return Result = None;
2658 
2659  if (A->Provenance[i] == BitPart::Unset)
2660  Result->Provenance[i] = B->Provenance[i];
2661  else
2662  Result->Provenance[i] = A->Provenance[i];
2663  }
2664 
2665  return Result;
2666  }
2667 
2668  // If this is a logical shift by a constant, recurse then shift the result.
2669  if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
2670  unsigned BitShift =
2671  cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
2672  // Ensure the shift amount is defined.
2673  if (BitShift > BitWidth)
2674  return Result;
2675 
2676  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2677  MatchBitReversals, BPS);
2678  if (!Res)
2679  return Result;
2680  Result = Res;
2681 
2682  // Perform the "shift" on BitProvenance.
2683  auto &P = Result->Provenance;
2684  if (I->getOpcode() == Instruction::Shl) {
2685  P.erase(std::prev(P.end(), BitShift), P.end());
2686  P.insert(P.begin(), BitShift, BitPart::Unset);
2687  } else {
2688  P.erase(P.begin(), std::next(P.begin(), BitShift));
2689  P.insert(P.end(), BitShift, BitPart::Unset);
2690  }
2691 
2692  return Result;
2693  }
2694 
2695  // If this is a logical 'and' with a mask that clears bits, recurse then
2696  // unset the appropriate bits.
2697  if (I->getOpcode() == Instruction::And &&
2698  isa<ConstantInt>(I->getOperand(1))) {
2699  APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1);
2700  const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
2701 
2702  // Check that the mask allows a multiple of 8 bits for a bswap, for an
2703  // early exit.
2704  unsigned NumMaskedBits = AndMask.countPopulation();
2705  if (!MatchBitReversals && NumMaskedBits % 8 != 0)
2706  return Result;
2707 
2708  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2709  MatchBitReversals, BPS);
2710  if (!Res)
2711  return Result;
2712  Result = Res;
2713 
2714  for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1)
2715  // If the AndMask is zero for this bit, clear the bit.
2716  if ((AndMask & Bit) == 0)
2717  Result->Provenance[i] = BitPart::Unset;
2718  return Result;
2719  }
2720 
2721  // If this is a zext instruction zero extend the result.
2722  if (I->getOpcode() == Instruction::ZExt) {
2723  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2724  MatchBitReversals, BPS);
2725  if (!Res)
2726  return Result;
2727 
2728  Result = BitPart(Res->Provider, BitWidth);
2729  auto NarrowBitWidth =
2730  cast<IntegerType>(cast<ZExtInst>(I)->getSrcTy())->getBitWidth();
2731  for (unsigned i = 0; i < NarrowBitWidth; ++i)
2732  Result->Provenance[i] = Res->Provenance[i];
2733  for (unsigned i = NarrowBitWidth; i < BitWidth; ++i)
2734  Result->Provenance[i] = BitPart::Unset;
2735  return Result;
2736  }
2737  }
2738 
2739  // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be
2740  // the input value to the bswap/bitreverse.
2741  Result = BitPart(V, BitWidth);
2742  for (unsigned i = 0; i < BitWidth; ++i)
2743  Result->Provenance[i] = i;
2744  return Result;
2745 }
2746 
2747 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
2748  unsigned BitWidth) {
2749  if (From % 8 != To % 8)
2750  return false;
2751  // Convert from bit indices to byte indices and check for a byte reversal.
2752  From >>= 3;
2753  To >>= 3;
2754  BitWidth >>= 3;
2755  return From == BitWidth - To - 1;
2756 }
2757 
2758 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
2759  unsigned BitWidth) {
2760  return From == BitWidth - To - 1;
2761 }
2762 
2764  Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
2765  SmallVectorImpl<Instruction *> &InsertedInsts) {
2766  if (Operator::getOpcode(I) != Instruction::Or)
2767  return false;
2768  if (!MatchBSwaps && !MatchBitReversals)
2769  return false;
2770  IntegerType *ITy = dyn_cast<IntegerType>(I->getType());
2771  if (!ITy || ITy->getBitWidth() > 128)
2772  return false; // Can't do vectors or integers > 128 bits.
2773  unsigned BW = ITy->getBitWidth();
2774 
2775  unsigned DemandedBW = BW;
2776  IntegerType *DemandedTy = ITy;
2777  if (I->hasOneUse()) {
2778  if (TruncInst *Trunc = dyn_cast<TruncInst>(I->user_back())) {
2779  DemandedTy = cast<IntegerType>(Trunc->getType());
2780  DemandedBW = DemandedTy->getBitWidth();
2781  }
2782  }
2783 
2784  // Try to find all the pieces corresponding to the bswap.
2785  std::map<Value *, Optional<BitPart>> BPS;
2786  auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS);
2787  if (!Res)
2788  return false;
2789  auto &BitProvenance = Res->Provenance;
2790 
2791  // Now, is the bit permutation correct for a bswap or a bitreverse? We can
2792  // only byteswap values with an even number of bytes.
2793  bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true;
2794  for (unsigned i = 0; i < DemandedBW; ++i) {
2795  OKForBSwap &=
2796  bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW);
2797  OKForBitReverse &=
2798  bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW);
2799  }
2800 
2801  Intrinsic::ID Intrin;
2802  if (OKForBSwap && MatchBSwaps)
2803  Intrin = Intrinsic::bswap;
2804  else if (OKForBitReverse && MatchBitReversals)
2805  Intrin = Intrinsic::bitreverse;
2806  else
2807  return false;
2808 
2809  if (ITy != DemandedTy) {
2810  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
2811  Value *Provider = Res->Provider;
2812  IntegerType *ProviderTy = cast<IntegerType>(Provider->getType());
2813  // We may need to truncate the provider.
2814  if (DemandedTy != ProviderTy) {
2815  auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy,
2816  "trunc", I);
2817  InsertedInsts.push_back(Trunc);
2818  Provider = Trunc;
2819  }
2820  auto *CI = CallInst::Create(F, Provider, "rev", I);
2821  InsertedInsts.push_back(CI);
2822  auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I);
2823  InsertedInsts.push_back(ExtInst);
2824  return true;
2825  }
2826 
2827  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy);
2828  InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I));
2829  return true;
2830 }
2831 
2832 // CodeGen has special handling for some string functions that may replace
2833 // them with target-specific intrinsics. Since that'd skip our interceptors
2834 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
2835 // we mark affected calls as NoBuiltin, which will disable optimization
2836 // in CodeGen.
2838  CallInst *CI, const TargetLibraryInfo *TLI) {
2839  Function *F = CI->getCalledFunction();
2840  LibFunc Func;
2841  if (F && !F->hasLocalLinkage() && F->hasName() &&
2842  TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
2843  !F->doesNotAccessMemory())
2844  CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin);
2845 }
2846 
2847 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
2848  // We can't have a PHI with a metadata type.
2849  if (I->getOperand(OpIdx)->getType()->isMetadataTy())
2850  return false;
2851 
2852  // Early exit.
2853  if (!isa<Constant>(I->getOperand(OpIdx)))
2854  return true;
2855 
2856  switch (I->getOpcode()) {
2857  default:
2858  return true;
2859  case Instruction::Call:
2860  case Instruction::Invoke:
2861  // Can't handle inline asm. Skip it.
2862  if (isa<InlineAsm>(ImmutableCallSite(I).getCalledValue()))
2863  return false;
2864  // Many arithmetic intrinsics have no issue taking a
2865  // variable, however it's hard to distingish these from
2866  // specials such as @llvm.frameaddress that require a constant.
2867  if (isa<IntrinsicInst>(I))
2868  return false;
2869 
2870  // Constant bundle operands may need to retain their constant-ness for
2871  // correctness.
2872  if (ImmutableCallSite(I).isBundleOperand(OpIdx))
2873  return false;
2874  return true;
2875  case Instruction::ShuffleVector:
2876  // Shufflevector masks are constant.
2877  return OpIdx != 2;
2878  case Instruction::Switch:
2879  case Instruction::ExtractValue:
2880  // All operands apart from the first are constant.
2881  return OpIdx == 0;
2882  case Instruction::InsertValue:
2883  // All operands apart from the first and the second are constant.
2884  return OpIdx < 2;
2885  case Instruction::Alloca:
2886  // Static allocas (constant size in the entry block) are handled by
2887  // prologue/epilogue insertion so they're free anyway. We definitely don't
2888  // want to make them non-constant.
2889  return !cast<AllocaInst>(I)->isStaticAlloca();
2890  case Instruction::GetElementPtr:
2891  if (OpIdx == 0)
2892  return true;
2894  for (auto E = std::next(It, OpIdx); It != E; ++It)
2895  if (It.isStruct())
2896  return false;
2897  return true;
2898  }
2899 }
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:2215
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
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:2448
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:2543
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:2379
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:1908
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:2629
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:2493
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:2288
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
static bool areAllUsesEqual(Instruction *I)
areAllUsesEqual - Check whether the uses of a value are all the same.
Definition: Local.cpp: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:2536
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:2012
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:2847
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:2518
static void changeToCall(InvokeInst *II, DomTreeUpdater *DTU=nullptr)
changeToCall - Convert the specified invoke into a normal call.
Definition: Local.cpp:1948
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:2758
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:2412
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:2747
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:2467
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:1887
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:2175
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:2837
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:1974
Invoke instruction.
bool wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used...
Definition: Local.cpp: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:2366
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:2763
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.
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:2431
std::vector< uint32_t > Metadata
PAL metadata represented as a vector.
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