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