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