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