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->getOffset() == 0 &&
1077  DVI->getVariable() == DIVar &&
1078  DVI->getExpression() == DIExpr)
1079  return true;
1080  }
1081  return false;
1082 }
1083 
1084 /// See if there is a dbg.value intrinsic for DIVar for the PHI node.
1086  DIExpression *DIExpr,
1087  PHINode *APN) {
1088  // Since we can't guarantee that the original dbg.declare instrinsic
1089  // is removed by LowerDbgDeclare(), we need to make sure that we are
1090  // not inserting the same dbg.value intrinsic over and over.
1092  findDbgValues(DbgValues, APN);
1093  for (auto *DVI : DbgValues) {
1094  assert(DVI->getValue() == APN);
1095  assert(DVI->getOffset() == 0);
1096  if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1097  return true;
1098  }
1099  return false;
1100 }
1101 
1102 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1103 /// that has an associated llvm.dbg.decl intrinsic.
1105  StoreInst *SI, DIBuilder &Builder) {
1106  auto *DIVar = DDI->getVariable();
1107  assert(DIVar && "Missing variable");
1108  auto *DIExpr = DDI->getExpression();
1109  Value *DV = SI->getOperand(0);
1110 
1111  // If an argument is zero extended then use argument directly. The ZExt
1112  // may be zapped by an optimization pass in future.
1113  Argument *ExtendedArg = nullptr;
1114  if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
1115  ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0));
1116  if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
1117  ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0));
1118  if (ExtendedArg) {
1119  // If this DDI was already describing only a fragment of a variable, ensure
1120  // that fragment is appropriately narrowed here.
1121  // But if a fragment wasn't used, describe the value as the original
1122  // argument (rather than the zext or sext) so that it remains described even
1123  // if the sext/zext is optimized away. This widens the variable description,
1124  // leaving it up to the consumer to know how the smaller value may be
1125  // represented in a larger register.
1126  if (auto Fragment = DIExpr->getFragmentInfo()) {
1127  unsigned FragmentOffset = Fragment->OffsetInBits;
1128  SmallVector<uint64_t, 3> Ops(DIExpr->elements_begin(),
1129  DIExpr->elements_end() - 3);
1131  Ops.push_back(FragmentOffset);
1132  const DataLayout &DL = DDI->getModule()->getDataLayout();
1133  Ops.push_back(DL.getTypeSizeInBits(ExtendedArg->getType()));
1134  DIExpr = Builder.createExpression(Ops);
1135  }
1136  DV = ExtendedArg;
1137  }
1138  if (!LdStHasDebugValue(DIVar, DIExpr, SI))
1139  Builder.insertDbgValueIntrinsic(DV, 0, DIVar, DIExpr, DDI->getDebugLoc(),
1140  SI);
1141 }
1142 
1143 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1144 /// that has an associated llvm.dbg.decl intrinsic.
1146  LoadInst *LI, DIBuilder &Builder) {
1147  auto *DIVar = DDI->getVariable();
1148  auto *DIExpr = DDI->getExpression();
1149  assert(DIVar && "Missing variable");
1150 
1151  if (LdStHasDebugValue(DIVar, DIExpr, LI))
1152  return;
1153 
1154  // We are now tracking the loaded value instead of the address. In the
1155  // future if multi-location support is added to the IR, it might be
1156  // preferable to keep tracking both the loaded value and the original
1157  // address in case the alloca can not be elided.
1158  Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
1159  LI, 0, DIVar, DIExpr, DDI->getDebugLoc(), (Instruction *)nullptr);
1160  DbgValue->insertAfter(LI);
1161 }
1162 
1163 /// Inserts a llvm.dbg.value intrinsic after a phi
1164 /// that has an associated llvm.dbg.decl intrinsic.
1166  PHINode *APN, DIBuilder &Builder) {
1167  auto *DIVar = DDI->getVariable();
1168  auto *DIExpr = DDI->getExpression();
1169  assert(DIVar && "Missing variable");
1170 
1171  if (PhiHasDebugValue(DIVar, DIExpr, APN))
1172  return;
1173 
1174  BasicBlock *BB = APN->getParent();
1175  auto InsertionPt = BB->getFirstInsertionPt();
1176 
1177  // The block may be a catchswitch block, which does not have a valid
1178  // insertion point.
1179  // FIXME: Insert dbg.value markers in the successors when appropriate.
1180  if (InsertionPt != BB->end())
1181  Builder.insertDbgValueIntrinsic(APN, 0, DIVar, DIExpr, DDI->getDebugLoc(),
1182  &*InsertionPt);
1183 }
1184 
1185 /// Determine whether this alloca is either a VLA or an array.
1186 static bool isArray(AllocaInst *AI) {
1187  return AI->isArrayAllocation() ||
1188  AI->getType()->getElementType()->isArrayTy();
1189 }
1190 
1191 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1192 /// of llvm.dbg.value intrinsics.
1194  DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1196  for (auto &FI : F)
1197  for (Instruction &BI : FI)
1198  if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
1199  Dbgs.push_back(DDI);
1200 
1201  if (Dbgs.empty())
1202  return false;
1203 
1204  for (auto &I : Dbgs) {
1205  DbgDeclareInst *DDI = I;
1206  AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1207  // If this is an alloca for a scalar variable, insert a dbg.value
1208  // at each load and store to the alloca and erase the dbg.declare.
1209  // The dbg.values allow tracking a variable even if it is not
1210  // stored on the stack, while the dbg.declare can only describe
1211  // the stack slot (and at a lexical-scope granularity). Later
1212  // passes will attempt to elide the stack slot.
1213  if (AI && !isArray(AI)) {
1214  for (auto &AIUse : AI->uses()) {
1215  User *U = AIUse.getUser();
1216  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1217  if (AIUse.getOperandNo() == 1)
1219  } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1220  ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1221  } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1222  // This is a call by-value or some other instruction that
1223  // takes a pointer to the variable. Insert a *value*
1224  // intrinsic that describes the alloca.
1225  DIB.insertDbgValueIntrinsic(AI, 0, DDI->getVariable(),
1226  DDI->getExpression(), DDI->getDebugLoc(),
1227  CI);
1228  }
1229  }
1230  DDI->eraseFromParent();
1231  }
1232  }
1233  return true;
1234 }
1235 
1236 /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the
1237 /// alloca 'V', if any.
1239  if (auto *L = LocalAsMetadata::getIfExists(V))
1240  if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1241  for (User *U : MDV->users())
1242  if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
1243  return DDI;
1244 
1245  return nullptr;
1246 }
1247 
1249  if (auto *L = LocalAsMetadata::getIfExists(V))
1250  if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
1251  for (User *U : MDV->users())
1252  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U))
1253  DbgValues.push_back(DVI);
1254 }
1255 
1256 
1258  Instruction *InsertBefore, DIBuilder &Builder,
1259  bool Deref, int Offset) {
1260  DbgDeclareInst *DDI = FindAllocaDbgDeclare(Address);
1261  if (!DDI)
1262  return false;
1263  DebugLoc Loc = DDI->getDebugLoc();
1264  auto *DIVar = DDI->getVariable();
1265  auto *DIExpr = DDI->getExpression();
1266  assert(DIVar && "Missing variable");
1267  DIExpr = DIExpression::prepend(DIExpr, Deref, Offset);
1268  // Insert llvm.dbg.declare immediately after the original alloca, and remove
1269  // old llvm.dbg.declare.
1270  Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, InsertBefore);
1271  DDI->eraseFromParent();
1272  return true;
1273 }
1274 
1276  DIBuilder &Builder, bool Deref, int Offset) {
1277  return replaceDbgDeclare(AI, NewAllocaAddress, AI->getNextNode(), Builder,
1278  Deref, Offset);
1279 }
1280 
1281 static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
1282  DIBuilder &Builder, int Offset) {
1283  DebugLoc Loc = DVI->getDebugLoc();
1284  auto *DIVar = DVI->getVariable();
1285  auto *DIExpr = DVI->getExpression();
1286  assert(DIVar && "Missing variable");
1287 
1288  // This is an alloca-based llvm.dbg.value. The first thing it should do with
1289  // the alloca pointer is dereference it. Otherwise we don't know how to handle
1290  // it and give up.
1291  if (!DIExpr || DIExpr->getNumElements() < 1 ||
1292  DIExpr->getElement(0) != dwarf::DW_OP_deref)
1293  return;
1294 
1295  // Insert the offset immediately after the first deref.
1296  // We could just change the offset argument of dbg.value, but it's unsigned...
1297  if (Offset) {
1299  Ops.push_back(dwarf::DW_OP_deref);
1300  DIExpression::appendOffset(Ops, Offset);
1301  Ops.append(DIExpr->elements_begin() + 1, DIExpr->elements_end());
1302  DIExpr = Builder.createExpression(Ops);
1303  }
1304 
1305  Builder.insertDbgValueIntrinsic(NewAddress, DVI->getOffset(), DIVar, DIExpr,
1306  Loc, DVI);
1307  DVI->eraseFromParent();
1308 }
1309 
1311  DIBuilder &Builder, int Offset) {
1312  if (auto *L = LocalAsMetadata::getIfExists(AI))
1313  if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
1314  for (auto UI = MDV->use_begin(), UE = MDV->use_end(); UI != UE;) {
1315  Use &U = *UI++;
1316  if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
1317  replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1318  }
1319 }
1320 
1323  auto &M = *I.getModule();
1324 
1325  auto MDWrap = [&](Value *V) {
1327  };
1328 
1329  if (isa<BitCastInst>(&I)) {
1330  findDbgValues(DbgValues, &I);
1331  for (auto *DVI : DbgValues) {
1332  // Bitcasts are entirely irrelevant for debug info. Rewrite the dbg.value
1333  // to use the cast's source.
1334  DVI->setOperand(0, MDWrap(I.getOperand(0)));
1335  DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n');
1336  }
1337  } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1338  findDbgValues(DbgValues, &I);
1339  for (auto *DVI : DbgValues) {
1340  unsigned BitWidth =
1341  M.getDataLayout().getPointerSizeInBits(GEP->getPointerAddressSpace());
1342  APInt Offset(BitWidth, 0);
1343  // Rewrite a constant GEP into a DIExpression. Since we are performing
1344  // arithmetic to compute the variable's *value* in the DIExpression, we
1345  // need to mark the expression with a DW_OP_stack_value.
1346  if (GEP->accumulateConstantOffset(M.getDataLayout(), Offset)) {
1347  auto *DIExpr = DVI->getExpression();
1348  DIBuilder DIB(M, /*AllowUnresolved*/ false);
1349  // GEP offsets are i32 and thus always fit into an int64_t.
1351  Offset.getSExtValue(),
1353  DVI->setOperand(0, MDWrap(I.getOperand(0)));
1354  DVI->setOperand(3, MetadataAsValue::get(I.getContext(), DIExpr));
1355  DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n');
1356  }
1357  }
1358  } else if (isa<LoadInst>(&I)) {
1359  findDbgValues(DbgValues, &I);
1360  for (auto *DVI : DbgValues) {
1361  // Rewrite the load into DW_OP_deref.
1362  auto *DIExpr = DVI->getExpression();
1363  DIBuilder DIB(M, /*AllowUnresolved*/ false);
1365  DVI->setOperand(0, MDWrap(I.getOperand(0)));
1366  DVI->setOperand(3, MetadataAsValue::get(I.getContext(), DIExpr));
1367  DEBUG(dbgs() << "SALVAGE: " << *DVI << '\n');
1368  }
1369  }
1370 }
1371 
1373  unsigned NumDeadInst = 0;
1374  // Delete the instructions backwards, as it has a reduced likelihood of
1375  // having to update as many def-use and use-def chains.
1376  Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
1377  while (EndInst != &BB->front()) {
1378  // Delete the next to last instruction.
1379  Instruction *Inst = &*--EndInst->getIterator();
1380  if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
1381  Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
1382  if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
1383  EndInst = Inst;
1384  continue;
1385  }
1386  if (!isa<DbgInfoIntrinsic>(Inst))
1387  ++NumDeadInst;
1388  Inst->eraseFromParent();
1389  }
1390  return NumDeadInst;
1391 }
1392 
1393 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
1394  bool PreserveLCSSA) {
1395  BasicBlock *BB = I->getParent();
1396  // Loop over all of the successors, removing BB's entry from any PHI
1397  // nodes.
1398  for (BasicBlock *Successor : successors(BB))
1399  Successor->removePredecessor(BB, PreserveLCSSA);
1400 
1401  // Insert a call to llvm.trap right before this. This turns the undefined
1402  // behavior into a hard fail instead of falling through into random code.
1403  if (UseLLVMTrap) {
1404  Function *TrapFn =
1405  Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
1406  CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
1407  CallTrap->setDebugLoc(I->getDebugLoc());
1408  }
1409  new UnreachableInst(I->getContext(), I);
1410 
1411  // All instructions after this are dead.
1412  unsigned NumInstrsRemoved = 0;
1413  BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
1414  while (BBI != BBE) {
1415  if (!BBI->use_empty())
1416  BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
1417  BB->getInstList().erase(BBI++);
1418  ++NumInstrsRemoved;
1419  }
1420  return NumInstrsRemoved;
1421 }
1422 
1423 /// changeToCall - Convert the specified invoke into a normal call.
1424 static void changeToCall(InvokeInst *II) {
1427  II->getOperandBundlesAsDefs(OpBundles);
1428  CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
1429  "", II);
1430  NewCall->takeName(II);
1431  NewCall->setCallingConv(II->getCallingConv());
1432  NewCall->setAttributes(II->getAttributes());
1433  NewCall->setDebugLoc(II->getDebugLoc());
1434  II->replaceAllUsesWith(NewCall);
1435 
1436  // Follow the call by a branch to the normal destination.
1437  BranchInst::Create(II->getNormalDest(), II);
1438 
1439  // Update PHI nodes in the unwind destination
1441  II->eraseFromParent();
1442 }
1443 
1445  BasicBlock *UnwindEdge) {
1446  BasicBlock *BB = CI->getParent();
1447 
1448  // Convert this function call into an invoke instruction. First, split the
1449  // basic block.
1450  BasicBlock *Split =
1451  BB->splitBasicBlock(CI->getIterator(), CI->getName() + ".noexc");
1452 
1453  // Delete the unconditional branch inserted by splitBasicBlock
1454  BB->getInstList().pop_back();
1455 
1456  // Create the new invoke instruction.
1457  SmallVector<Value *, 8> InvokeArgs(CI->arg_begin(), CI->arg_end());
1459 
1460  CI->getOperandBundlesAsDefs(OpBundles);
1461 
1462  // Note: we're round tripping operand bundles through memory here, and that
1463  // can potentially be avoided with a cleverer API design that we do not have
1464  // as of this time.
1465 
1466  InvokeInst *II = InvokeInst::Create(CI->getCalledValue(), Split, UnwindEdge,
1467  InvokeArgs, OpBundles, CI->getName(), BB);
1468  II->setDebugLoc(CI->getDebugLoc());
1469  II->setCallingConv(CI->getCallingConv());
1470  II->setAttributes(CI->getAttributes());
1471 
1472  // Make sure that anything using the call now uses the invoke! This also
1473  // updates the CallGraph if present, because it uses a WeakTrackingVH.
1474  CI->replaceAllUsesWith(II);
1475 
1476  // Delete the original call
1477  Split->getInstList().pop_front();
1478  return Split;
1479 }
1480 
1482  SmallPtrSetImpl<BasicBlock*> &Reachable) {
1483 
1485  BasicBlock *BB = &F.front();
1486  Worklist.push_back(BB);
1487  Reachable.insert(BB);
1488  bool Changed = false;
1489  do {
1490  BB = Worklist.pop_back_val();
1491 
1492  // Do a quick scan of the basic block, turning any obviously unreachable
1493  // instructions into LLVM unreachable insts. The instruction combining pass
1494  // canonicalizes unreachable insts into stores to null or undef.
1495  for (Instruction &I : *BB) {
1496  // Assumptions that are known to be false are equivalent to unreachable.
1497  // Also, if the condition is undefined, then we make the choice most
1498  // beneficial to the optimizer, and choose that to also be unreachable.
1499  if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
1500  if (II->getIntrinsicID() == Intrinsic::assume) {
1501  if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
1502  // Don't insert a call to llvm.trap right before the unreachable.
1503  changeToUnreachable(II, false);
1504  Changed = true;
1505  break;
1506  }
1507  }
1508 
1509  if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
1510  // A call to the guard intrinsic bails out of the current compilation
1511  // unit if the predicate passed to it is false. If the predicate is a
1512  // constant false, then we know the guard will bail out of the current
1513  // compile unconditionally, so all code following it is dead.
1514  //
1515  // Note: unlike in llvm.assume, it is not "obviously profitable" for
1516  // guards to treat `undef` as `false` since a guard on `undef` can
1517  // still be useful for widening.
1518  if (match(II->getArgOperand(0), m_Zero()))
1519  if (!isa<UnreachableInst>(II->getNextNode())) {
1520  changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false);
1521  Changed = true;
1522  break;
1523  }
1524  }
1525  }
1526 
1527  if (auto *CI = dyn_cast<CallInst>(&I)) {
1528  Value *Callee = CI->getCalledValue();
1529  if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1530  changeToUnreachable(CI, /*UseLLVMTrap=*/false);
1531  Changed = true;
1532  break;
1533  }
1534  if (CI->doesNotReturn()) {
1535  // If we found a call to a no-return function, insert an unreachable
1536  // instruction after it. Make sure there isn't *already* one there
1537  // though.
1538  if (!isa<UnreachableInst>(CI->getNextNode())) {
1539  // Don't insert a call to llvm.trap right before the unreachable.
1540  changeToUnreachable(CI->getNextNode(), false);
1541  Changed = true;
1542  }
1543  break;
1544  }
1545  }
1546 
1547  // Store to undef and store to null are undefined and used to signal that
1548  // they should be changed to unreachable by passes that can't modify the
1549  // CFG.
1550  if (auto *SI = dyn_cast<StoreInst>(&I)) {
1551  // Don't touch volatile stores.
1552  if (SI->isVolatile()) continue;
1553 
1554  Value *Ptr = SI->getOperand(1);
1555 
1556  if (isa<UndefValue>(Ptr) ||
1557  (isa<ConstantPointerNull>(Ptr) &&
1558  SI->getPointerAddressSpace() == 0)) {
1559  changeToUnreachable(SI, true);
1560  Changed = true;
1561  break;
1562  }
1563  }
1564  }
1565 
1566  TerminatorInst *Terminator = BB->getTerminator();
1567  if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
1568  // Turn invokes that call 'nounwind' functions into ordinary calls.
1569  Value *Callee = II->getCalledValue();
1570  if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1571  changeToUnreachable(II, true);
1572  Changed = true;
1573  } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
1574  if (II->use_empty() && II->onlyReadsMemory()) {
1575  // jump to the normal destination branch.
1576  BranchInst::Create(II->getNormalDest(), II);
1577  II->getUnwindDest()->removePredecessor(II->getParent());
1578  II->eraseFromParent();
1579  } else
1580  changeToCall(II);
1581  Changed = true;
1582  }
1583  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
1584  // Remove catchpads which cannot be reached.
1585  struct CatchPadDenseMapInfo {
1586  static CatchPadInst *getEmptyKey() {
1588  }
1589  static CatchPadInst *getTombstoneKey() {
1591  }
1592  static unsigned getHashValue(CatchPadInst *CatchPad) {
1593  return static_cast<unsigned>(hash_combine_range(
1594  CatchPad->value_op_begin(), CatchPad->value_op_end()));
1595  }
1596  static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
1597  if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
1598  RHS == getEmptyKey() || RHS == getTombstoneKey())
1599  return LHS == RHS;
1600  return LHS->isIdenticalTo(RHS);
1601  }
1602  };
1603 
1604  // Set of unique CatchPads.
1606  CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
1607  HandlerSet;
1608  detail::DenseSetEmpty Empty;
1609  for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
1610  E = CatchSwitch->handler_end();
1611  I != E; ++I) {
1612  BasicBlock *HandlerBB = *I;
1613  auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
1614  if (!HandlerSet.insert({CatchPad, Empty}).second) {
1615  CatchSwitch->removeHandler(I);
1616  --I;
1617  --E;
1618  Changed = true;
1619  }
1620  }
1621  }
1622 
1623  Changed |= ConstantFoldTerminator(BB, true);
1624  for (BasicBlock *Successor : successors(BB))
1625  if (Reachable.insert(Successor).second)
1626  Worklist.push_back(Successor);
1627  } while (!Worklist.empty());
1628  return Changed;
1629 }
1630 
1632  TerminatorInst *TI = BB->getTerminator();
1633 
1634  if (auto *II = dyn_cast<InvokeInst>(TI)) {
1635  changeToCall(II);
1636  return;
1637  }
1638 
1639  TerminatorInst *NewTI;
1640  BasicBlock *UnwindDest;
1641 
1642  if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
1643  NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
1644  UnwindDest = CRI->getUnwindDest();
1645  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
1646  auto *NewCatchSwitch = CatchSwitchInst::Create(
1647  CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
1648  CatchSwitch->getName(), CatchSwitch);
1649  for (BasicBlock *PadBB : CatchSwitch->handlers())
1650  NewCatchSwitch->addHandler(PadBB);
1651 
1652  NewTI = NewCatchSwitch;
1653  UnwindDest = CatchSwitch->getUnwindDest();
1654  } else {
1655  llvm_unreachable("Could not find unwind successor");
1656  }
1657 
1658  NewTI->takeName(TI);
1659  NewTI->setDebugLoc(TI->getDebugLoc());
1660  UnwindDest->removePredecessor(BB);
1661  TI->replaceAllUsesWith(NewTI);
1662  TI->eraseFromParent();
1663 }
1664 
1665 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
1666 /// if they are in a dead cycle. Return true if a change was made, false
1667 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
1668 /// after modifying the CFG.
1670  SmallPtrSet<BasicBlock*, 16> Reachable;
1671  bool Changed = markAliveBlocks(F, Reachable);
1672 
1673  // If there are unreachable blocks in the CFG...
1674  if (Reachable.size() == F.size())
1675  return Changed;
1676 
1677  assert(Reachable.size() < F.size());
1678  NumRemoved += F.size()-Reachable.size();
1679 
1680  // Loop over all of the basic blocks that are not reachable, dropping all of
1681  // their internal references...
1682  for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
1683  if (Reachable.count(&*BB))
1684  continue;
1685 
1686  for (BasicBlock *Successor : successors(&*BB))
1687  if (Reachable.count(Successor))
1688  Successor->removePredecessor(&*BB);
1689  if (LVI)
1690  LVI->eraseBlock(&*BB);
1691  BB->dropAllReferences();
1692  }
1693 
1694  for (Function::iterator I = ++F.begin(); I != F.end();)
1695  if (!Reachable.count(&*I))
1696  I = F.getBasicBlockList().erase(I);
1697  else
1698  ++I;
1699 
1700  return true;
1701 }
1702 
1704  ArrayRef<unsigned> KnownIDs) {
1706  K->dropUnknownNonDebugMetadata(KnownIDs);
1707  K->getAllMetadataOtherThanDebugLoc(Metadata);
1708  for (const auto &MD : Metadata) {
1709  unsigned Kind = MD.first;
1710  MDNode *JMD = J->getMetadata(Kind);
1711  MDNode *KMD = MD.second;
1712 
1713  switch (Kind) {
1714  default:
1715  K->setMetadata(Kind, nullptr); // Remove unknown metadata
1716  break;
1717  case LLVMContext::MD_dbg:
1718  llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
1719  case LLVMContext::MD_tbaa:
1720  K->setMetadata(Kind, MDNode::getMostGenericTBAA(JMD, KMD));
1721  break;
1723  K->setMetadata(Kind, MDNode::getMostGenericAliasScope(JMD, KMD));
1724  break;
1727  K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
1728  break;
1729  case LLVMContext::MD_range:
1730  K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD));
1731  break;
1733  K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD));
1734  break;
1736  // Only set the !invariant.load if it is present in both instructions.
1737  K->setMetadata(Kind, JMD);
1738  break;
1740  // Only set the !nonnull if it is present in both instructions.
1741  K->setMetadata(Kind, JMD);
1742  break;
1744  // Preserve !invariant.group in K.
1745  break;
1746  case LLVMContext::MD_align:
1747  K->setMetadata(Kind,
1749  break;
1752  K->setMetadata(Kind,
1754  break;
1755  }
1756  }
1757  // Set !invariant.group from J if J has it. If both instructions have it
1758  // then we will just pick it from J - even when they are different.
1759  // Also make sure that K is load or store - f.e. combining bitcast with load
1760  // could produce bitcast with invariant.group metadata, which is invalid.
1761  // FIXME: we should try to preserve both invariant.group md if they are
1762  // different, but right now instruction can only have one invariant.group.
1763  if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
1764  if (isa<LoadInst>(K) || isa<StoreInst>(K))
1766 }
1767 
1769  unsigned KnownIDs[] = {
1776  combineMetadata(K, J, KnownIDs);
1777 }
1778 
1779 template <typename RootType, typename DominatesFn>
1780 static unsigned replaceDominatedUsesWith(Value *From, Value *To,
1781  const RootType &Root,
1782  const DominatesFn &Dominates) {
1783  assert(From->getType() == To->getType());
1784 
1785  unsigned Count = 0;
1786  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
1787  UI != UE;) {
1788  Use &U = *UI++;
1789  if (!Dominates(Root, U))
1790  continue;
1791  U.set(To);
1792  DEBUG(dbgs() << "Replace dominated use of '" << From->getName() << "' as "
1793  << *To << " in " << *U << "\n");
1794  ++Count;
1795  }
1796  return Count;
1797 }
1798 
1800  assert(From->getType() == To->getType());
1801  auto *BB = From->getParent();
1802  unsigned Count = 0;
1803 
1804  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
1805  UI != UE;) {
1806  Use &U = *UI++;
1807  auto *I = cast<Instruction>(U.getUser());
1808  if (I->getParent() == BB)
1809  continue;
1810  U.set(To);
1811  ++Count;
1812  }
1813  return Count;
1814 }
1815 
1817  DominatorTree &DT,
1818  const BasicBlockEdge &Root) {
1819  auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
1820  return DT.dominates(Root, U);
1821  };
1822  return ::replaceDominatedUsesWith(From, To, Root, Dominates);
1823 }
1824 
1826  DominatorTree &DT,
1827  const BasicBlock *BB) {
1828  auto ProperlyDominates = [&DT](const BasicBlock *BB, const Use &U) {
1829  auto *I = cast<Instruction>(U.getUser())->getParent();
1830  return DT.properlyDominates(BB, I);
1831  };
1832  return ::replaceDominatedUsesWith(From, To, BB, ProperlyDominates);
1833 }
1834 
1836  // Check if the function is specifically marked as a gc leaf function.
1837  if (CS.hasFnAttr("gc-leaf-function"))
1838  return true;
1839  if (const Function *F = CS.getCalledFunction()) {
1840  if (F->hasFnAttribute("gc-leaf-function"))
1841  return true;
1842 
1843  if (auto IID = F->getIntrinsicID())
1844  // Most LLVM intrinsics do not take safepoints.
1845  return IID != Intrinsic::experimental_gc_statepoint &&
1846  IID != Intrinsic::experimental_deoptimize;
1847  }
1848 
1849  return false;
1850 }
1851 
1853  LoadInst &NewLI) {
1854  auto *NewTy = NewLI.getType();
1855 
1856  // This only directly applies if the new type is also a pointer.
1857  if (NewTy->isPointerTy()) {
1859  return;
1860  }
1861 
1862  // The only other translation we can do is to integral loads with !range
1863  // metadata.
1864  if (!NewTy->isIntegerTy())
1865  return;
1866 
1867  MDBuilder MDB(NewLI.getContext());
1868  const Value *Ptr = OldLI.getPointerOperand();
1869  auto *ITy = cast<IntegerType>(NewTy);
1870  auto *NullInt = ConstantExpr::getPtrToInt(
1871  ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
1872  auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
1874  MDB.createRange(NonNullInt, NullInt));
1875 }
1876 
1877 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
1878  MDNode *N, LoadInst &NewLI) {
1879  auto *NewTy = NewLI.getType();
1880 
1881  // Give up unless it is converted to a pointer where there is a single very
1882  // valuable mapping we can do reliably.
1883  // FIXME: It would be nice to propagate this in more ways, but the type
1884  // conversions make it hard.
1885  if (!NewTy->isPointerTy())
1886  return;
1887 
1888  unsigned BitWidth = DL.getTypeSizeInBits(NewTy);
1889  if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
1890  MDNode *NN = MDNode::get(OldLI.getContext(), None);
1892  }
1893 }
1894 
1895 namespace {
1896 /// A potential constituent of a bitreverse or bswap expression. See
1897 /// collectBitParts for a fuller explanation.
1898 struct BitPart {
1899  BitPart(Value *P, unsigned BW) : Provider(P) {
1900  Provenance.resize(BW);
1901  }
1902 
1903  /// The Value that this is a bitreverse/bswap of.
1904  Value *Provider;
1905  /// The "provenance" of each bit. Provenance[A] = B means that bit A
1906  /// in Provider becomes bit B in the result of this expression.
1907  SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
1908 
1909  enum { Unset = -1 };
1910 };
1911 } // end anonymous namespace
1912 
1913 /// Analyze the specified subexpression and see if it is capable of providing
1914 /// pieces of a bswap or bitreverse. The subexpression provides a potential
1915 /// piece of a bswap or bitreverse if it can be proven that each non-zero bit in
1916 /// the output of the expression came from a corresponding bit in some other
1917 /// value. This function is recursive, and the end result is a mapping of
1918 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
1919 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
1920 ///
1921 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
1922 /// that the expression deposits the low byte of %X into the high byte of the
1923 /// result and that all other bits are zero. This expression is accepted and a
1924 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
1925 /// [0-7].
1926 ///
1927 /// To avoid revisiting values, the BitPart results are memoized into the
1928 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
1929 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
1930 /// store BitParts objects, not pointers. As we need the concept of a nullptr
1931 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
1932 /// type instead to provide the same functionality.
1933 ///
1934 /// Because we pass around references into \c BPS, we must use a container that
1935 /// does not invalidate internal references (std::map instead of DenseMap).
1936 ///
1937 static const Optional<BitPart> &
1938 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
1939  std::map<Value *, Optional<BitPart>> &BPS) {
1940  auto I = BPS.find(V);
1941  if (I != BPS.end())
1942  return I->second;
1943 
1944  auto &Result = BPS[V] = None;
1945  auto BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
1946 
1947  if (Instruction *I = dyn_cast<Instruction>(V)) {
1948  // If this is an or instruction, it may be an inner node of the bswap.
1949  if (I->getOpcode() == Instruction::Or) {
1950  auto &A = collectBitParts(I->getOperand(0), MatchBSwaps,
1951  MatchBitReversals, BPS);
1952  auto &B = collectBitParts(I->getOperand(1), MatchBSwaps,
1953  MatchBitReversals, BPS);
1954  if (!A || !B)
1955  return Result;
1956 
1957  // Try and merge the two together.
1958  if (!A->Provider || A->Provider != B->Provider)
1959  return Result;
1960 
1961  Result = BitPart(A->Provider, BitWidth);
1962  for (unsigned i = 0; i < A->Provenance.size(); ++i) {
1963  if (A->Provenance[i] != BitPart::Unset &&
1964  B->Provenance[i] != BitPart::Unset &&
1965  A->Provenance[i] != B->Provenance[i])
1966  return Result = None;
1967 
1968  if (A->Provenance[i] == BitPart::Unset)
1969  Result->Provenance[i] = B->Provenance[i];
1970  else
1971  Result->Provenance[i] = A->Provenance[i];
1972  }
1973 
1974  return Result;
1975  }
1976 
1977  // If this is a logical shift by a constant, recurse then shift the result.
1978  if (I->isLogicalShift() && isa<ConstantInt>(I->getOperand(1))) {
1979  unsigned BitShift =
1980  cast<ConstantInt>(I->getOperand(1))->getLimitedValue(~0U);
1981  // Ensure the shift amount is defined.
1982  if (BitShift > BitWidth)
1983  return Result;
1984 
1985  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
1986  MatchBitReversals, BPS);
1987  if (!Res)
1988  return Result;
1989  Result = Res;
1990 
1991  // Perform the "shift" on BitProvenance.
1992  auto &P = Result->Provenance;
1993  if (I->getOpcode() == Instruction::Shl) {
1994  P.erase(std::prev(P.end(), BitShift), P.end());
1995  P.insert(P.begin(), BitShift, BitPart::Unset);
1996  } else {
1997  P.erase(P.begin(), std::next(P.begin(), BitShift));
1998  P.insert(P.end(), BitShift, BitPart::Unset);
1999  }
2000 
2001  return Result;
2002  }
2003 
2004  // If this is a logical 'and' with a mask that clears bits, recurse then
2005  // unset the appropriate bits.
2006  if (I->getOpcode() == Instruction::And &&
2007  isa<ConstantInt>(I->getOperand(1))) {
2008  APInt Bit(I->getType()->getPrimitiveSizeInBits(), 1);
2009  const APInt &AndMask = cast<ConstantInt>(I->getOperand(1))->getValue();
2010 
2011  // Check that the mask allows a multiple of 8 bits for a bswap, for an
2012  // early exit.
2013  unsigned NumMaskedBits = AndMask.countPopulation();
2014  if (!MatchBitReversals && NumMaskedBits % 8 != 0)
2015  return Result;
2016 
2017  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2018  MatchBitReversals, BPS);
2019  if (!Res)
2020  return Result;
2021  Result = Res;
2022 
2023  for (unsigned i = 0; i < BitWidth; ++i, Bit <<= 1)
2024  // If the AndMask is zero for this bit, clear the bit.
2025  if ((AndMask & Bit) == 0)
2026  Result->Provenance[i] = BitPart::Unset;
2027  return Result;
2028  }
2029 
2030  // If this is a zext instruction zero extend the result.
2031  if (I->getOpcode() == Instruction::ZExt) {
2032  auto &Res = collectBitParts(I->getOperand(0), MatchBSwaps,
2033  MatchBitReversals, BPS);
2034  if (!Res)
2035  return Result;
2036 
2037  Result = BitPart(Res->Provider, BitWidth);
2038  auto NarrowBitWidth =
2039  cast<IntegerType>(cast<ZExtInst>(I)->getSrcTy())->getBitWidth();
2040  for (unsigned i = 0; i < NarrowBitWidth; ++i)
2041  Result->Provenance[i] = Res->Provenance[i];
2042  for (unsigned i = NarrowBitWidth; i < BitWidth; ++i)
2043  Result->Provenance[i] = BitPart::Unset;
2044  return Result;
2045  }
2046  }
2047 
2048  // Okay, we got to something that isn't a shift, 'or' or 'and'. This must be
2049  // the input value to the bswap/bitreverse.
2050  Result = BitPart(V, BitWidth);
2051  for (unsigned i = 0; i < BitWidth; ++i)
2052  Result->Provenance[i] = i;
2053  return Result;
2054 }
2055 
2056 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
2057  unsigned BitWidth) {
2058  if (From % 8 != To % 8)
2059  return false;
2060  // Convert from bit indices to byte indices and check for a byte reversal.
2061  From >>= 3;
2062  To >>= 3;
2063  BitWidth >>= 3;
2064  return From == BitWidth - To - 1;
2065 }
2066 
2067 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
2068  unsigned BitWidth) {
2069  return From == BitWidth - To - 1;
2070 }
2071 
2072 /// Given an OR instruction, check to see if this is a bitreverse
2073 /// idiom. If so, insert the new intrinsic and return true.
2075  Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
2076  SmallVectorImpl<Instruction *> &InsertedInsts) {
2077  if (Operator::getOpcode(I) != Instruction::Or)
2078  return false;
2079  if (!MatchBSwaps && !MatchBitReversals)
2080  return false;
2081  IntegerType *ITy = dyn_cast<IntegerType>(I->getType());
2082  if (!ITy || ITy->getBitWidth() > 128)
2083  return false; // Can't do vectors or integers > 128 bits.
2084  unsigned BW = ITy->getBitWidth();
2085 
2086  unsigned DemandedBW = BW;
2087  IntegerType *DemandedTy = ITy;
2088  if (I->hasOneUse()) {
2089  if (TruncInst *Trunc = dyn_cast<TruncInst>(I->user_back())) {
2090  DemandedTy = cast<IntegerType>(Trunc->getType());
2091  DemandedBW = DemandedTy->getBitWidth();
2092  }
2093  }
2094 
2095  // Try to find all the pieces corresponding to the bswap.
2096  std::map<Value *, Optional<BitPart>> BPS;
2097  auto Res = collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS);
2098  if (!Res)
2099  return false;
2100  auto &BitProvenance = Res->Provenance;
2101 
2102  // Now, is the bit permutation correct for a bswap or a bitreverse? We can
2103  // only byteswap values with an even number of bytes.
2104  bool OKForBSwap = DemandedBW % 16 == 0, OKForBitReverse = true;
2105  for (unsigned i = 0; i < DemandedBW; ++i) {
2106  OKForBSwap &=
2107  bitTransformIsCorrectForBSwap(BitProvenance[i], i, DemandedBW);
2108  OKForBitReverse &=
2109  bitTransformIsCorrectForBitReverse(BitProvenance[i], i, DemandedBW);
2110  }
2111 
2112  Intrinsic::ID Intrin;
2113  if (OKForBSwap && MatchBSwaps)
2114  Intrin = Intrinsic::bswap;
2115  else if (OKForBitReverse && MatchBitReversals)
2116  Intrin = Intrinsic::bitreverse;
2117  else
2118  return false;
2119 
2120  if (ITy != DemandedTy) {
2121  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
2122  Value *Provider = Res->Provider;
2123  IntegerType *ProviderTy = cast<IntegerType>(Provider->getType());
2124  // We may need to truncate the provider.
2125  if (DemandedTy != ProviderTy) {
2126  auto *Trunc = CastInst::Create(Instruction::Trunc, Provider, DemandedTy,
2127  "trunc", I);
2128  InsertedInsts.push_back(Trunc);
2129  Provider = Trunc;
2130  }
2131  auto *CI = CallInst::Create(F, Provider, "rev", I);
2132  InsertedInsts.push_back(CI);
2133  auto *ExtInst = CastInst::Create(Instruction::ZExt, CI, ITy, "zext", I);
2134  InsertedInsts.push_back(ExtInst);
2135  return true;
2136  }
2137 
2138  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, ITy);
2139  InsertedInsts.push_back(CallInst::Create(F, Res->Provider, "rev", I));
2140  return true;
2141 }
2142 
2143 // CodeGen has special handling for some string functions that may replace
2144 // them with target-specific intrinsics. Since that'd skip our interceptors
2145 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
2146 // we mark affected calls as NoBuiltin, which will disable optimization
2147 // in CodeGen.
2149  CallInst *CI, const TargetLibraryInfo *TLI) {
2150  Function *F = CI->getCalledFunction();
2151  LibFunc Func;
2152  if (F && !F->hasLocalLinkage() && F->hasName() &&
2153  TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
2154  !F->doesNotAccessMemory())
2155  CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin);
2156 }
2157 
2158 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
2159  // We can't have a PHI with a metadata type.
2160  if (I->getOperand(OpIdx)->getType()->isMetadataTy())
2161  return false;
2162 
2163  // Early exit.
2164  if (!isa<Constant>(I->getOperand(OpIdx)))
2165  return true;
2166 
2167  switch (I->getOpcode()) {
2168  default:
2169  return true;
2170  case Instruction::Call:
2171  case Instruction::Invoke:
2172  // Can't handle inline asm. Skip it.
2173  if (isa<InlineAsm>(ImmutableCallSite(I).getCalledValue()))
2174  return false;
2175  // Many arithmetic intrinsics have no issue taking a
2176  // variable, however it's hard to distingish these from
2177  // specials such as @llvm.frameaddress that require a constant.
2178  if (isa<IntrinsicInst>(I))
2179  return false;
2180 
2181  // Constant bundle operands may need to retain their constant-ness for
2182  // correctness.
2183  if (ImmutableCallSite(I).isBundleOperand(OpIdx))
2184  return false;
2185  return true;
2186  case Instruction::ShuffleVector:
2187  // Shufflevector masks are constant.
2188  return OpIdx != 2;
2189  case Instruction::Switch:
2190  case Instruction::ExtractValue:
2191  // All operands apart from the first are constant.
2192  return OpIdx == 0;
2193  case Instruction::InsertValue:
2194  // All operands apart from the first and the second are constant.
2195  return OpIdx < 2;
2196  case Instruction::Alloca:
2197  // Static allocas (constant size in the entry block) are handled by
2198  // prologue/epilogue insertion so they're free anyway. We definitely don't
2199  // want to make them non-constant.
2200  return !dyn_cast<AllocaInst>(I)->isStaticAlloca();
2201  case Instruction::GetElementPtr:
2202  if (OpIdx == 0)
2203  return true;
2205  for (auto E = std::next(It, OpIdx); It != E; ++It)
2206  if (It.isStruct())
2207  return false;
2208  return true;
2209  }
2210 }
size_t size() const
Definition: Function.h:585
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:213
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:1275
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:1310
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:159
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
DbgDeclareInst * FindAllocaDbgDeclare(Value *V)
Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any.
Definition: Local.cpp:1238
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:582
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
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:1393
CallingConv::ID getCallingConv() const
getCallingConv/setCallingConv - Get or set the calling convention of this function call...
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:1816
Instruction * insertDbgValueIntrinsic(llvm::Value *Val, uint64_t Offset, DILocalVariable *VarInfo, DIExpression *Expr, const DILocation *DL, BasicBlock *InsertAtEnd)
Insert a new llvm.dbg.value intrinsic call.
Definition: DIBuilder.cpp:849
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()
DIExpression * getExpression() const
block_iterator block_end()
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
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:176
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:802
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:1938
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:123
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:1281
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:1248
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1554
#define F(x, y, z)
Definition: MD5.cpp:55
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:1424
void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a nonnull metadata node to a new load instruction.
Definition: Local.cpp:1852
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.
DILocalVariable * getVariable() const
Definition: IntrinsicInst.h:93
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage any dbg.value intrinsics referr...
Definition: Local.cpp:1321
static bool markAliveBlocks(Function &F, SmallPtrSetImpl< BasicBlock *> &Reachable)
Definition: Local.cpp:1481
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:190
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:121
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:580
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:133
int Switch(int a)
Definition: Switch2Test.cpp:11
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:131
bool doesNotAccessMemory() const
Determine if the function does not access memory.
Definition: Function.h:387
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:106
const BasicBlock & getEntryBlock() const
Definition: Function.h:564
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.
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:277
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
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.
void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, StoreInst *SI, DIBuilder &Builder)
===---------------------------------------------------------------——===// Dbg Intrinsic utilities ...
Definition: Local.cpp:1104
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
Definition: IntrinsicInst.h:91
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
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:2158
bool hasFnAttr(Attribute::AttrKind Kind) const
Return true if this function has the given attribute.
Definition: CallSite.h:359
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.
#define A
Definition: LargeTest.cpp:12
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:372
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:500
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
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:1877
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
Value * getPointerOperand()
Definition: Instructions.h:270
DIExpression * getExpression() const
Definition: IntrinsicInst.h:97
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1546
uint64_t getOffset() const
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
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
bool callsGCLeafFunction(ImmutableCallSite CS)
Return true if the CallSite CS calls a gc leaf function.
Definition: Local.cpp:1835
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:1257
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:2067
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:1193
#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:93
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
#define E
Definition: LargeTest.cpp:27
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
#define B
Definition: LargeTest.cpp:24
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:1780
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:2056
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:1669
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:232
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
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
const size_t N
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:661
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:1372
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
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:1631
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:280
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:687
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
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:73
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:557
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:2148
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:1085
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:1768
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:126
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:104
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:1186
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:587
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:1444
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
DILocalVariable * getVariable() const
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:503
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:2074
int * Ptr
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.
Definition: IntrinsicInst.h:89
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:1703
bool use_empty() const
Definition: Value.h:322
Type * getElementType() const
Definition: DerivedTypes.h:486
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:1799
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