LLVM  16.0.0git
Local.cpp
Go to the documentation of this file.
1 //===- Local.cpp - Functions to perform local transformations -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This family of functions perform various local transformations to the
10 // program.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/DenseMapInfo.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/Hashing.h"
20 #include "llvm/ADT/None.h"
21 #include "llvm/ADT/Optional.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/Statistic.h"
38 #include "llvm/IR/Argument.h"
39 #include "llvm/IR/Attributes.h"
40 #include "llvm/IR/BasicBlock.h"
41 #include "llvm/IR/CFG.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"
47 #include "llvm/IR/DebugInfo.h"
49 #include "llvm/IR/DebugLoc.h"
50 #include "llvm/IR/DerivedTypes.h"
51 #include "llvm/IR/Dominators.h"
52 #include "llvm/IR/Function.h"
54 #include "llvm/IR/GlobalObject.h"
55 #include "llvm/IR/IRBuilder.h"
56 #include "llvm/IR/InstrTypes.h"
57 #include "llvm/IR/Instruction.h"
58 #include "llvm/IR/Instructions.h"
59 #include "llvm/IR/IntrinsicInst.h"
60 #include "llvm/IR/Intrinsics.h"
61 #include "llvm/IR/LLVMContext.h"
62 #include "llvm/IR/MDBuilder.h"
63 #include "llvm/IR/Metadata.h"
64 #include "llvm/IR/Module.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"
78 #include <algorithm>
79 #include <cassert>
80 #include <cstdint>
81 #include <iterator>
82 #include <map>
83 #include <utility>
84 
85 using namespace llvm;
86 using namespace llvm::PatternMatch;
87 
88 #define DEBUG_TYPE "local"
89 
90 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
91 STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd");
92 
94  "phicse-debug-hash",
95 #ifdef EXPENSIVE_CHECKS
96  cl::init(true),
97 #else
98  cl::init(false),
99 #endif
100  cl::Hidden,
101  cl::desc("Perform extra assertion checking to verify that PHINodes's hash "
102  "function is well-behaved w.r.t. its isEqual predicate"));
103 
105  "phicse-num-phi-smallsize", cl::init(32), cl::Hidden,
106  cl::desc(
107  "When the basic block contains not more than this number of PHI nodes, "
108  "perform a (faster!) exhaustive search instead of set-driven one."));
109 
110 // Max recursion depth for collectBitParts used when detecting bswap and
111 // bitreverse idioms.
112 static const unsigned BitPartRecursionMaxDepth = 48;
113 
114 //===----------------------------------------------------------------------===//
115 // Local constant propagation.
116 //
117 
118 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
119 /// constant value, convert it into an unconditional branch to the constant
120 /// destination. This is a nontrivial operation because the successors of this
121 /// basic block must have their PHI nodes updated.
122 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
123 /// conditions and indirectbr addresses this might make dead if
124 /// DeleteDeadConditions is true.
125 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
126  const TargetLibraryInfo *TLI,
127  DomTreeUpdater *DTU) {
128  Instruction *T = BB->getTerminator();
130 
131  // Branch - See if we are conditional jumping on constant
132  if (auto *BI = dyn_cast<BranchInst>(T)) {
133  if (BI->isUnconditional()) return false; // Can't optimize uncond branch
134 
135  BasicBlock *Dest1 = BI->getSuccessor(0);
136  BasicBlock *Dest2 = BI->getSuccessor(1);
137 
138  if (Dest2 == Dest1) { // Conditional branch to same location?
139  // This branch matches something like this:
140  // br bool %cond, label %Dest, label %Dest
141  // and changes it into: br label %Dest
142 
143  // Let the basic block know that we are letting go of one copy of it.
144  assert(BI->getParent() && "Terminator not inserted in block!");
145  Dest1->removePredecessor(BI->getParent());
146 
147  // Replace the conditional branch with an unconditional one.
148  BranchInst *NewBI = Builder.CreateBr(Dest1);
149 
150  // Transfer the metadata to the new branch instruction.
151  NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
152  LLVMContext::MD_annotation});
153 
154  Value *Cond = BI->getCondition();
155  BI->eraseFromParent();
156  if (DeleteDeadConditions)
158  return true;
159  }
160 
161  if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
162  // Are we branching on constant?
163  // YES. Change to unconditional branch...
164  BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
165  BasicBlock *OldDest = Cond->getZExtValue() ? Dest2 : Dest1;
166 
167  // Let the basic block know that we are letting go of it. Based on this,
168  // it will adjust it's PHI nodes.
169  OldDest->removePredecessor(BB);
170 
171  // Replace the conditional branch with an unconditional one.
172  BranchInst *NewBI = Builder.CreateBr(Destination);
173 
174  // Transfer the metadata to the new branch instruction.
175  NewBI->copyMetadata(*BI, {LLVMContext::MD_loop, LLVMContext::MD_dbg,
176  LLVMContext::MD_annotation});
177 
178  BI->eraseFromParent();
179  if (DTU)
180  DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}});
181  return true;
182  }
183 
184  return false;
185  }
186 
187  if (auto *SI = dyn_cast<SwitchInst>(T)) {
188  // If we are switching on a constant, we can convert the switch to an
189  // unconditional branch.
190  auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
191  BasicBlock *DefaultDest = SI->getDefaultDest();
192  BasicBlock *TheOnlyDest = DefaultDest;
193 
194  // If the default is unreachable, ignore it when searching for TheOnlyDest.
195  if (isa<UnreachableInst>(DefaultDest->getFirstNonPHIOrDbg()) &&
196  SI->getNumCases() > 0) {
197  TheOnlyDest = SI->case_begin()->getCaseSuccessor();
198  }
199 
200  bool Changed = false;
201 
202  // Figure out which case it goes to.
203  for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
204  // Found case matching a constant operand?
205  if (i->getCaseValue() == CI) {
206  TheOnlyDest = i->getCaseSuccessor();
207  break;
208  }
209 
210  // Check to see if this branch is going to the same place as the default
211  // dest. If so, eliminate it as an explicit compare.
212  if (i->getCaseSuccessor() == DefaultDest) {
213  MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
214  unsigned NCases = SI->getNumCases();
215  // Fold the case metadata into the default if there will be any branches
216  // left, unless the metadata doesn't match the switch.
217  if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
218  // Collect branch weights into a vector.
219  SmallVector<uint32_t, 8> Weights;
220  for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
221  ++MD_i) {
222  auto *CI = mdconst::extract<ConstantInt>(MD->getOperand(MD_i));
223  Weights.push_back(CI->getValue().getZExtValue());
224  }
225  // Merge weight of this case to the default weight.
226  unsigned idx = i->getCaseIndex();
227  Weights[0] += Weights[idx+1];
228  // Remove weight for this case.
229  std::swap(Weights[idx+1], Weights.back());
230  Weights.pop_back();
231  SI->setMetadata(LLVMContext::MD_prof,
232  MDBuilder(BB->getContext()).
233  createBranchWeights(Weights));
234  }
235  // Remove this entry.
236  BasicBlock *ParentBB = SI->getParent();
237  DefaultDest->removePredecessor(ParentBB);
238  i = SI->removeCase(i);
239  e = SI->case_end();
240  Changed = true;
241  continue;
242  }
243 
244  // Otherwise, check to see if the switch only branches to one destination.
245  // We do this by reseting "TheOnlyDest" to null when we find two non-equal
246  // destinations.
247  if (i->getCaseSuccessor() != TheOnlyDest)
248  TheOnlyDest = nullptr;
249 
250  // Increment this iterator as we haven't removed the case.
251  ++i;
252  }
253 
254  if (CI && !TheOnlyDest) {
255  // Branching on a constant, but not any of the cases, go to the default
256  // successor.
257  TheOnlyDest = SI->getDefaultDest();
258  }
259 
260  // If we found a single destination that we can fold the switch into, do so
261  // now.
262  if (TheOnlyDest) {
263  // Insert the new branch.
264  Builder.CreateBr(TheOnlyDest);
265  BasicBlock *BB = SI->getParent();
266 
267  SmallSet<BasicBlock *, 8> RemovedSuccessors;
268 
269  // Remove entries from PHI nodes which we no longer branch to...
270  BasicBlock *SuccToKeep = TheOnlyDest;
271  for (BasicBlock *Succ : successors(SI)) {
272  if (DTU && Succ != TheOnlyDest)
273  RemovedSuccessors.insert(Succ);
274  // Found case matching a constant operand?
275  if (Succ == SuccToKeep) {
276  SuccToKeep = nullptr; // Don't modify the first branch to TheOnlyDest
277  } else {
278  Succ->removePredecessor(BB);
279  }
280  }
281 
282  // Delete the old switch.
283  Value *Cond = SI->getCondition();
284  SI->eraseFromParent();
285  if (DeleteDeadConditions)
287  if (DTU) {
288  std::vector<DominatorTree::UpdateType> Updates;
289  Updates.reserve(RemovedSuccessors.size());
290  for (auto *RemovedSuccessor : RemovedSuccessors)
291  Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
292  DTU->applyUpdates(Updates);
293  }
294  return true;
295  }
296 
297  if (SI->getNumCases() == 1) {
298  // Otherwise, we can fold this switch into a conditional branch
299  // instruction if it has only one non-default destination.
300  auto FirstCase = *SI->case_begin();
301  Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
302  FirstCase.getCaseValue(), "cond");
303 
304  // Insert the new branch.
305  BranchInst *NewBr = Builder.CreateCondBr(Cond,
306  FirstCase.getCaseSuccessor(),
307  SI->getDefaultDest());
308  MDNode *MD = SI->getMetadata(LLVMContext::MD_prof);
309  if (MD && MD->getNumOperands() == 3) {
310  ConstantInt *SICase =
311  mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
312  ConstantInt *SIDef =
313  mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
314  assert(SICase && SIDef);
315  // The TrueWeight should be the weight for the single case of SI.
316  NewBr->setMetadata(LLVMContext::MD_prof,
317  MDBuilder(BB->getContext()).
318  createBranchWeights(SICase->getValue().getZExtValue(),
319  SIDef->getValue().getZExtValue()));
320  }
321 
322  // Update make.implicit metadata to the newly-created conditional branch.
323  MDNode *MakeImplicitMD = SI->getMetadata(LLVMContext::MD_make_implicit);
324  if (MakeImplicitMD)
325  NewBr->setMetadata(LLVMContext::MD_make_implicit, MakeImplicitMD);
326 
327  // Delete the old switch.
328  SI->eraseFromParent();
329  return true;
330  }
331  return Changed;
332  }
333 
334  if (auto *IBI = dyn_cast<IndirectBrInst>(T)) {
335  // indirectbr blockaddress(@F, @BB) -> br label @BB
336  if (auto *BA =
337  dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
338  BasicBlock *TheOnlyDest = BA->getBasicBlock();
339  SmallSet<BasicBlock *, 8> RemovedSuccessors;
340 
341  // Insert the new branch.
342  Builder.CreateBr(TheOnlyDest);
343 
344  BasicBlock *SuccToKeep = TheOnlyDest;
345  for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
346  BasicBlock *DestBB = IBI->getDestination(i);
347  if (DTU && DestBB != TheOnlyDest)
348  RemovedSuccessors.insert(DestBB);
349  if (IBI->getDestination(i) == SuccToKeep) {
350  SuccToKeep = nullptr;
351  } else {
352  DestBB->removePredecessor(BB);
353  }
354  }
355  Value *Address = IBI->getAddress();
356  IBI->eraseFromParent();
357  if (DeleteDeadConditions)
358  // Delete pointer cast instructions.
360 
361  // Also zap the blockaddress constant if there are no users remaining,
362  // otherwise the destination is still marked as having its address taken.
363  if (BA->use_empty())
364  BA->destroyConstant();
365 
366  // If we didn't find our destination in the IBI successor list, then we
367  // have undefined behavior. Replace the unconditional branch with an
368  // 'unreachable' instruction.
369  if (SuccToKeep) {
370  BB->getTerminator()->eraseFromParent();
371  new UnreachableInst(BB->getContext(), BB);
372  }
373 
374  if (DTU) {
375  std::vector<DominatorTree::UpdateType> Updates;
376  Updates.reserve(RemovedSuccessors.size());
377  for (auto *RemovedSuccessor : RemovedSuccessors)
378  Updates.push_back({DominatorTree::Delete, BB, RemovedSuccessor});
379  DTU->applyUpdates(Updates);
380  }
381  return true;
382  }
383  }
384 
385  return false;
386 }
387 
388 //===----------------------------------------------------------------------===//
389 // Local dead code elimination.
390 //
391 
392 /// isInstructionTriviallyDead - Return true if the result produced by the
393 /// instruction is not used, and the instruction has no side effects.
394 ///
396  const TargetLibraryInfo *TLI) {
397  if (!I->use_empty())
398  return false;
399  return wouldInstructionBeTriviallyDead(I, TLI);
400 }
401 
403  Instruction *I, const TargetLibraryInfo *TLI) {
404  // Instructions that are "markers" and have implied meaning on code around
405  // them (without explicit uses), are not dead on unused paths.
406  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
407  if (II->getIntrinsicID() == Intrinsic::stacksave ||
408  II->getIntrinsicID() == Intrinsic::launder_invariant_group ||
409  II->isLifetimeStartOrEnd())
410  return false;
411  return wouldInstructionBeTriviallyDead(I, TLI);
412 }
413 
415  const TargetLibraryInfo *TLI) {
416  if (I->isTerminator())
417  return false;
418 
419  // We don't want the landingpad-like instructions removed by anything this
420  // general.
421  if (I->isEHPad())
422  return false;
423 
424  // We don't want debug info removed by anything this general, unless
425  // debug info is empty.
426  if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
427  if (DDI->getAddress())
428  return false;
429  return true;
430  }
431  if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
432  if (DVI->hasArgList() || DVI->getValue(0))
433  return false;
434  return true;
435  }
436  if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(I)) {
437  if (DLI->getLabel())
438  return false;
439  return true;
440  }
441 
442  if (auto *CB = dyn_cast<CallBase>(I))
443  if (isRemovableAlloc(CB, TLI))
444  return true;
445 
446  if (!I->willReturn())
447  return false;
448 
449  if (!I->mayHaveSideEffects())
450  return true;
451 
452  // Special case intrinsics that "may have side effects" but can be deleted
453  // when dead.
454  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
455  // Safe to delete llvm.stacksave and launder.invariant.group if dead.
456  if (II->getIntrinsicID() == Intrinsic::stacksave ||
457  II->getIntrinsicID() == Intrinsic::launder_invariant_group)
458  return true;
459 
460  if (II->isLifetimeStartOrEnd()) {
461  auto *Arg = II->getArgOperand(1);
462  // Lifetime intrinsics are dead when their right-hand is undef.
463  if (isa<UndefValue>(Arg))
464  return true;
465  // If the right-hand is an alloc, global, or argument and the only uses
466  // are lifetime intrinsics then the intrinsics are dead.
467  if (isa<AllocaInst>(Arg) || isa<GlobalValue>(Arg) || isa<Argument>(Arg))
468  return llvm::all_of(Arg->uses(), [](Use &Use) {
469  if (IntrinsicInst *IntrinsicUse =
470  dyn_cast<IntrinsicInst>(Use.getUser()))
471  return IntrinsicUse->isLifetimeStartOrEnd();
472  return false;
473  });
474  return false;
475  }
476 
477  // Assumptions are dead if their condition is trivially true. Guards on
478  // true are operationally no-ops. In the future we can consider more
479  // sophisticated tradeoffs for guards considering potential for check
480  // widening, but for now we keep things simple.
481  if ((II->getIntrinsicID() == Intrinsic::assume &&
482  isAssumeWithEmptyBundle(cast<AssumeInst>(*II))) ||
483  II->getIntrinsicID() == Intrinsic::experimental_guard) {
484  if (ConstantInt *Cond = dyn_cast<ConstantInt>(II->getArgOperand(0)))
485  return !Cond->isZero();
486 
487  return false;
488  }
489 
490  if (auto *FPI = dyn_cast<ConstrainedFPIntrinsic>(I)) {
491  Optional<fp::ExceptionBehavior> ExBehavior = FPI->getExceptionBehavior();
492  return *ExBehavior != fp::ebStrict;
493  }
494  }
495 
496  if (auto *Call = dyn_cast<CallBase>(I)) {
497  if (Value *FreedOp = getFreedOperand(Call, TLI))
498  if (Constant *C = dyn_cast<Constant>(FreedOp))
499  return C->isNullValue() || isa<UndefValue>(C);
500  if (isMathLibCallNoop(Call, TLI))
501  return true;
502  }
503 
504  // Non-volatile atomic loads from constants can be removed.
505  if (auto *LI = dyn_cast<LoadInst>(I))
506  if (auto *GV = dyn_cast<GlobalVariable>(
507  LI->getPointerOperand()->stripPointerCasts()))
508  if (!LI->isVolatile() && GV->isConstant())
509  return true;
510 
511  return false;
512 }
513 
514 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
515 /// trivially dead instruction, delete it. If that makes any of its operands
516 /// trivially dead, delete them too, recursively. Return true if any
517 /// instructions were deleted.
519  Value *V, const TargetLibraryInfo *TLI, MemorySSAUpdater *MSSAU,
520  std::function<void(Value *)> AboutToDeleteCallback) {
521  Instruction *I = dyn_cast<Instruction>(V);
522  if (!I || !isInstructionTriviallyDead(I, TLI))
523  return false;
524 
526  DeadInsts.push_back(I);
527  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
528  AboutToDeleteCallback);
529 
530  return true;
531 }
532 
534  SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
535  MemorySSAUpdater *MSSAU,
536  std::function<void(Value *)> AboutToDeleteCallback) {
537  unsigned S = 0, E = DeadInsts.size(), Alive = 0;
538  for (; S != E; ++S) {
539  auto *I = dyn_cast<Instruction>(DeadInsts[S]);
540  if (!I || !isInstructionTriviallyDead(I)) {
541  DeadInsts[S] = nullptr;
542  ++Alive;
543  }
544  }
545  if (Alive == E)
546  return false;
547  RecursivelyDeleteTriviallyDeadInstructions(DeadInsts, TLI, MSSAU,
548  AboutToDeleteCallback);
549  return true;
550 }
551 
553  SmallVectorImpl<WeakTrackingVH> &DeadInsts, const TargetLibraryInfo *TLI,
554  MemorySSAUpdater *MSSAU,
555  std::function<void(Value *)> AboutToDeleteCallback) {
556  // Process the dead instruction list until empty.
557  while (!DeadInsts.empty()) {
558  Value *V = DeadInsts.pop_back_val();
559  Instruction *I = cast_or_null<Instruction>(V);
560  if (!I)
561  continue;
563  "Live instruction found in dead worklist!");
564  assert(I->use_empty() && "Instructions with uses are not dead.");
565 
566  // Don't lose the debug info while deleting the instructions.
568 
569  if (AboutToDeleteCallback)
570  AboutToDeleteCallback(I);
571 
572  // Null out all of the instruction's operands to see if any operand becomes
573  // dead as we go.
574  for (Use &OpU : I->operands()) {
575  Value *OpV = OpU.get();
576  OpU.set(nullptr);
577 
578  if (!OpV->use_empty())
579  continue;
580 
581  // If the operand is an instruction that became dead as we nulled out the
582  // operand, and if it is 'trivially' dead, delete it in a future loop
583  // iteration.
584  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
585  if (isInstructionTriviallyDead(OpI, TLI))
586  DeadInsts.push_back(OpI);
587  }
588  if (MSSAU)
589  MSSAU->removeMemoryAccess(I);
590 
591  I->eraseFromParent();
592  }
593 }
594 
597  findDbgUsers(DbgUsers, I);
598  for (auto *DII : DbgUsers) {
599  Value *Undef = UndefValue::get(I->getType());
600  DII->replaceVariableLocationOp(I, Undef);
601  }
602  return !DbgUsers.empty();
603 }
604 
605 /// areAllUsesEqual - Check whether the uses of a value are all the same.
606 /// This is similar to Instruction::hasOneUse() except this will also return
607 /// true when there are no uses or multiple uses that all refer to the same
608 /// value.
610  Value::user_iterator UI = I->user_begin();
611  Value::user_iterator UE = I->user_end();
612  if (UI == UE)
613  return true;
614 
615  User *TheUse = *UI;
616  for (++UI; UI != UE; ++UI) {
617  if (*UI != TheUse)
618  return false;
619  }
620  return true;
621 }
622 
623 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
624 /// dead PHI node, due to being a def-use chain of single-use nodes that
625 /// either forms a cycle or is terminated by a trivially dead instruction,
626 /// delete it. If that makes any of its operands trivially dead, delete them
627 /// too, recursively. Return true if a change was made.
629  const TargetLibraryInfo *TLI,
630  llvm::MemorySSAUpdater *MSSAU) {
632  for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
633  I = cast<Instruction>(*I->user_begin())) {
634  if (I->use_empty())
635  return RecursivelyDeleteTriviallyDeadInstructions(I, TLI, MSSAU);
636 
637  // If we find an instruction more than once, we're on a cycle that
638  // won't prove fruitful.
639  if (!Visited.insert(I).second) {
640  // Break the cycle and delete the instruction and its operands.
641  I->replaceAllUsesWith(PoisonValue::get(I->getType()));
643  return true;
644  }
645  }
646  return false;
647 }
648 
649 static bool
652  const DataLayout &DL,
653  const TargetLibraryInfo *TLI) {
654  if (isInstructionTriviallyDead(I, TLI)) {
656 
657  // Null out all of the instruction's operands to see if any operand becomes
658  // dead as we go.
659  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
660  Value *OpV = I->getOperand(i);
661  I->setOperand(i, nullptr);
662 
663  if (!OpV->use_empty() || I == OpV)
664  continue;
665 
666  // If the operand is an instruction that became dead as we nulled out the
667  // operand, and if it is 'trivially' dead, delete it in a future loop
668  // iteration.
669  if (Instruction *OpI = dyn_cast<Instruction>(OpV))
670  if (isInstructionTriviallyDead(OpI, TLI))
671  WorkList.insert(OpI);
672  }
673 
674  I->eraseFromParent();
675 
676  return true;
677  }
678 
679  if (Value *SimpleV = simplifyInstruction(I, DL)) {
680  // Add the users to the worklist. CAREFUL: an instruction can use itself,
681  // in the case of a phi node.
682  for (User *U : I->users()) {
683  if (U != I) {
684  WorkList.insert(cast<Instruction>(U));
685  }
686  }
687 
688  // Replace the instruction with its simplified value.
689  bool Changed = false;
690  if (!I->use_empty()) {
691  I->replaceAllUsesWith(SimpleV);
692  Changed = true;
693  }
694  if (isInstructionTriviallyDead(I, TLI)) {
695  I->eraseFromParent();
696  Changed = true;
697  }
698  return Changed;
699  }
700  return false;
701 }
702 
703 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
704 /// simplify any instructions in it and recursively delete dead instructions.
705 ///
706 /// This returns true if it changed the code, note that it can delete
707 /// instructions in other blocks as well in this block.
709  const TargetLibraryInfo *TLI) {
710  bool MadeChange = false;
711  const DataLayout &DL = BB->getModule()->getDataLayout();
712 
713 #ifndef NDEBUG
714  // In debug builds, ensure that the terminator of the block is never replaced
715  // or deleted by these simplifications. The idea of simplification is that it
716  // cannot introduce new instructions, and there is no way to replace the
717  // terminator of a block without introducing a new instruction.
718  AssertingVH<Instruction> TerminatorVH(&BB->back());
719 #endif
720 
722  // Iterate over the original function, only adding insts to the worklist
723  // if they actually need to be revisited. This avoids having to pre-init
724  // the worklist with the entire function's worth of instructions.
725  for (BasicBlock::iterator BI = BB->begin(), E = std::prev(BB->end());
726  BI != E;) {
727  assert(!BI->isTerminator());
728  Instruction *I = &*BI;
729  ++BI;
730 
731  // We're visiting this instruction now, so make sure it's not in the
732  // worklist from an earlier visit.
733  if (!WorkList.count(I))
734  MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
735  }
736 
737  while (!WorkList.empty()) {
738  Instruction *I = WorkList.pop_back_val();
739  MadeChange |= simplifyAndDCEInstruction(I, WorkList, DL, TLI);
740  }
741  return MadeChange;
742 }
743 
744 //===----------------------------------------------------------------------===//
745 // Control Flow Graph Restructuring.
746 //
747 
749  DomTreeUpdater *DTU) {
750 
751  // If BB has single-entry PHI nodes, fold them.
752  while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
753  Value *NewVal = PN->getIncomingValue(0);
754  // Replace self referencing PHI with poison, it must be dead.
755  if (NewVal == PN) NewVal = PoisonValue::get(PN->getType());
756  PN->replaceAllUsesWith(NewVal);
757  PN->eraseFromParent();
758  }
759 
760  BasicBlock *PredBB = DestBB->getSinglePredecessor();
761  assert(PredBB && "Block doesn't have a single predecessor!");
762 
763  bool ReplaceEntryBB = PredBB->isEntryBlock();
764 
765  // DTU updates: Collect all the edges that enter
766  // PredBB. These dominator edges will be redirected to DestBB.
768 
769  if (DTU) {
770  // To avoid processing the same predecessor more than once.
772  Updates.reserve(Updates.size() + 2 * pred_size(PredBB) + 1);
773  for (BasicBlock *PredOfPredBB : predecessors(PredBB))
774  // This predecessor of PredBB may already have DestBB as a successor.
775  if (PredOfPredBB != PredBB)
776  if (SeenPreds.insert(PredOfPredBB).second)
777  Updates.push_back({DominatorTree::Insert, PredOfPredBB, DestBB});
778  SeenPreds.clear();
779  for (BasicBlock *PredOfPredBB : predecessors(PredBB))
780  if (SeenPreds.insert(PredOfPredBB).second)
781  Updates.push_back({DominatorTree::Delete, PredOfPredBB, PredBB});
782  Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
783  }
784 
785  // Zap anything that took the address of DestBB. Not doing this will give the
786  // address an invalid value.
787  if (DestBB->hasAddressTaken()) {
788  BlockAddress *BA = BlockAddress::get(DestBB);
789  Constant *Replacement =
792  BA->getType()));
793  BA->destroyConstant();
794  }
795 
796  // Anything that branched to PredBB now branches to DestBB.
797  PredBB->replaceAllUsesWith(DestBB);
798 
799  // Splice all the instructions from PredBB to DestBB.
800  PredBB->getTerminator()->eraseFromParent();
801  DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
802  new UnreachableInst(PredBB->getContext(), PredBB);
803 
804  // If the PredBB is the entry block of the function, move DestBB up to
805  // become the entry block after we erase PredBB.
806  if (ReplaceEntryBB)
807  DestBB->moveAfter(PredBB);
808 
809  if (DTU) {
810  assert(PredBB->getInstList().size() == 1 &&
811  isa<UnreachableInst>(PredBB->getTerminator()) &&
812  "The successor list of PredBB isn't empty before "
813  "applying corresponding DTU updates.");
814  DTU->applyUpdatesPermissive(Updates);
815  DTU->deleteBB(PredBB);
816  // Recalculation of DomTree is needed when updating a forward DomTree and
817  // the Entry BB is replaced.
818  if (ReplaceEntryBB && DTU->hasDomTree()) {
819  // The entry block was removed and there is no external interface for
820  // the dominator tree to be notified of this change. In this corner-case
821  // we recalculate the entire tree.
822  DTU->recalculate(*(DestBB->getParent()));
823  }
824  }
825 
826  else {
827  PredBB->eraseFromParent(); // Nuke BB if DTU is nullptr.
828  }
829 }
830 
831 /// Return true if we can choose one of these values to use in place of the
832 /// other. Note that we will always choose the non-undef value to keep.
833 static bool CanMergeValues(Value *First, Value *Second) {
834  return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
835 }
836 
837 /// Return true if we can fold BB, an almost-empty BB ending in an unconditional
838 /// branch to Succ, into Succ.
839 ///
840 /// Assumption: Succ is the single successor for BB.
842  assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
843 
844  LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
845  << Succ->getName() << "\n");
846  // Shortcut, if there is only a single predecessor it must be BB and merging
847  // is always safe
848  if (Succ->getSinglePredecessor()) return true;
849 
850  // Make a list of the predecessors of BB
852 
853  // Look at all the phi nodes in Succ, to see if they present a conflict when
854  // merging these blocks
855  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
856  PHINode *PN = cast<PHINode>(I);
857 
858  // If the incoming value from BB is again a PHINode in
859  // BB which has the same incoming value for *PI as PN does, we can
860  // merge the phi nodes and then the blocks can still be merged
861  PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
862  if (BBPN && BBPN->getParent() == BB) {
863  for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
864  BasicBlock *IBB = PN->getIncomingBlock(PI);
865  if (BBPreds.count(IBB) &&
867  PN->getIncomingValue(PI))) {
868  LLVM_DEBUG(dbgs()
869  << "Can't fold, phi node " << PN->getName() << " in "
870  << Succ->getName() << " is conflicting with "
871  << BBPN->getName() << " with regard to common predecessor "
872  << IBB->getName() << "\n");
873  return false;
874  }
875  }
876  } else {
877  Value* Val = PN->getIncomingValueForBlock(BB);
878  for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
879  // See if the incoming value for the common predecessor is equal to the
880  // one for BB, in which case this phi node will not prevent the merging
881  // of the block.
882  BasicBlock *IBB = PN->getIncomingBlock(PI);
883  if (BBPreds.count(IBB) &&
884  !CanMergeValues(Val, PN->getIncomingValue(PI))) {
885  LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()
886  << " in " << Succ->getName()
887  << " is conflicting with regard to common "
888  << "predecessor " << IBB->getName() << "\n");
889  return false;
890  }
891  }
892  }
893  }
894 
895  return true;
896 }
897 
900 
901 /// Determines the value to use as the phi node input for a block.
902 ///
903 /// Select between \p OldVal any value that we know flows from \p BB
904 /// to a particular phi on the basis of which one (if either) is not
905 /// undef. Update IncomingValues based on the selected value.
906 ///
907 /// \param OldVal The value we are considering selecting.
908 /// \param BB The block that the value flows in from.
909 /// \param IncomingValues A map from block-to-value for other phi inputs
910 /// that we have examined.
911 ///
912 /// \returns the selected value.
914  IncomingValueMap &IncomingValues) {
915  if (!isa<UndefValue>(OldVal)) {
916  assert((!IncomingValues.count(BB) ||
917  IncomingValues.find(BB)->second == OldVal) &&
918  "Expected OldVal to match incoming value from BB!");
919 
920  IncomingValues.insert(std::make_pair(BB, OldVal));
921  return OldVal;
922  }
923 
924  IncomingValueMap::const_iterator It = IncomingValues.find(BB);
925  if (It != IncomingValues.end()) return It->second;
926 
927  return OldVal;
928 }
929 
930 /// Create a map from block to value for the operands of a
931 /// given phi.
932 ///
933 /// Create a map from block to value for each non-undef value flowing
934 /// into \p PN.
935 ///
936 /// \param PN The phi we are collecting the map for.
937 /// \param IncomingValues [out] The map from block to value for this phi.
939  IncomingValueMap &IncomingValues) {
940  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
942  Value *V = PN->getIncomingValue(i);
943 
944  if (!isa<UndefValue>(V))
945  IncomingValues.insert(std::make_pair(BB, V));
946  }
947 }
948 
949 /// Replace the incoming undef values to a phi with the values
950 /// from a block-to-value map.
951 ///
952 /// \param PN The phi we are replacing the undefs in.
953 /// \param IncomingValues A map from block to value.
955  const IncomingValueMap &IncomingValues) {
956  SmallVector<unsigned> TrueUndefOps;
957  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
958  Value *V = PN->getIncomingValue(i);
959 
960  if (!isa<UndefValue>(V)) continue;
961 
963  IncomingValueMap::const_iterator It = IncomingValues.find(BB);
964 
965  // Keep track of undef/poison incoming values. Those must match, so we fix
966  // them up below if needed.
967  // Note: this is conservatively correct, but we could try harder and group
968  // the undef values per incoming basic block.
969  if (It == IncomingValues.end()) {
970  TrueUndefOps.push_back(i);
971  continue;
972  }
973 
974  // There is a defined value for this incoming block, so map this undef
975  // incoming value to the defined value.
976  PN->setIncomingValue(i, It->second);
977  }
978 
979  // If there are both undef and poison values incoming, then convert those
980  // values to undef. It is invalid to have different values for the same
981  // incoming block.
982  unsigned PoisonCount = count_if(TrueUndefOps, [&](unsigned i) {
983  return isa<PoisonValue>(PN->getIncomingValue(i));
984  });
985  if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) {
986  for (unsigned i : TrueUndefOps)
988  }
989 }
990 
991 /// Replace a value flowing from a block to a phi with
992 /// potentially multiple instances of that value flowing from the
993 /// block's predecessors to the phi.
994 ///
995 /// \param BB The block with the value flowing into the phi.
996 /// \param BBPreds The predecessors of BB.
997 /// \param PN The phi that we are updating.
999  const PredBlockVector &BBPreds,
1000  PHINode *PN) {
1001  Value *OldVal = PN->removeIncomingValue(BB, false);
1002  assert(OldVal && "No entry in PHI for Pred BB!");
1003 
1004  IncomingValueMap IncomingValues;
1005 
1006  // We are merging two blocks - BB, and the block containing PN - and
1007  // as a result we need to redirect edges from the predecessors of BB
1008  // to go to the block containing PN, and update PN
1009  // accordingly. Since we allow merging blocks in the case where the
1010  // predecessor and successor blocks both share some predecessors,
1011  // and where some of those common predecessors might have undef
1012  // values flowing into PN, we want to rewrite those values to be
1013  // consistent with the non-undef values.
1014 
1015  gatherIncomingValuesToPhi(PN, IncomingValues);
1016 
1017  // If this incoming value is one of the PHI nodes in BB, the new entries
1018  // in the PHI node are the entries from the old PHI.
1019  if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
1020  PHINode *OldValPN = cast<PHINode>(OldVal);
1021  for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
1022  // Note that, since we are merging phi nodes and BB and Succ might
1023  // have common predecessors, we could end up with a phi node with
1024  // identical incoming branches. This will be cleaned up later (and
1025  // will trigger asserts if we try to clean it up now, without also
1026  // simplifying the corresponding conditional branch).
1027  BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
1028  Value *PredVal = OldValPN->getIncomingValue(i);
1029  Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
1030  IncomingValues);
1031 
1032  // And add a new incoming value for this predecessor for the
1033  // newly retargeted branch.
1034  PN->addIncoming(Selected, PredBB);
1035  }
1036  } else {
1037  for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
1038  // Update existing incoming values in PN for this
1039  // predecessor of BB.
1040  BasicBlock *PredBB = BBPreds[i];
1041  Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
1042  IncomingValues);
1043 
1044  // And add a new incoming value for this predecessor for the
1045  // newly retargeted branch.
1046  PN->addIncoming(Selected, PredBB);
1047  }
1048  }
1049 
1050  replaceUndefValuesInPhi(PN, IncomingValues);
1051 }
1052 
1054  DomTreeUpdater *DTU) {
1055  assert(BB != &BB->getParent()->getEntryBlock() &&
1056  "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
1057 
1058  // We can't eliminate infinite loops.
1059  BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
1060  if (BB == Succ) return false;
1061 
1062  // Check to see if merging these blocks would cause conflicts for any of the
1063  // phi nodes in BB or Succ. If not, we can safely merge.
1064  if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
1065 
1066  // Check for cases where Succ has multiple predecessors and a PHI node in BB
1067  // has uses which will not disappear when the PHI nodes are merged. It is
1068  // possible to handle such cases, but difficult: it requires checking whether
1069  // BB dominates Succ, which is non-trivial to calculate in the case where
1070  // Succ has multiple predecessors. Also, it requires checking whether
1071  // constructing the necessary self-referential PHI node doesn't introduce any
1072  // conflicts; this isn't too difficult, but the previous code for doing this
1073  // was incorrect.
1074  //
1075  // Note that if this check finds a live use, BB dominates Succ, so BB is
1076  // something like a loop pre-header (or rarely, a part of an irreducible CFG);
1077  // folding the branch isn't profitable in that case anyway.
1078  if (!Succ->getSinglePredecessor()) {
1079  BasicBlock::iterator BBI = BB->begin();
1080  while (isa<PHINode>(*BBI)) {
1081  for (Use &U : BBI->uses()) {
1082  if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
1083  if (PN->getIncomingBlock(U) != BB)
1084  return false;
1085  } else {
1086  return false;
1087  }
1088  }
1089  ++BBI;
1090  }
1091  }
1092 
1093  LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
1094 
1096  if (DTU) {
1097  // To avoid processing the same predecessor more than once.
1098  SmallPtrSet<BasicBlock *, 8> SeenPreds;
1099  // All predecessors of BB will be moved to Succ.
1100  SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ));
1101  Updates.reserve(Updates.size() + 2 * pred_size(BB) + 1);
1102  for (auto *PredOfBB : predecessors(BB))
1103  // This predecessor of BB may already have Succ as a successor.
1104  if (!PredsOfSucc.contains(PredOfBB))
1105  if (SeenPreds.insert(PredOfBB).second)
1106  Updates.push_back({DominatorTree::Insert, PredOfBB, Succ});
1107  SeenPreds.clear();
1108  for (auto *PredOfBB : predecessors(BB))
1109  if (SeenPreds.insert(PredOfBB).second)
1110  Updates.push_back({DominatorTree::Delete, PredOfBB, BB});
1111  Updates.push_back({DominatorTree::Delete, BB, Succ});
1112  }
1113 
1114  if (isa<PHINode>(Succ->begin())) {
1115  // If there is more than one pred of succ, and there are PHI nodes in
1116  // the successor, then we need to add incoming edges for the PHI nodes
1117  //
1118  const PredBlockVector BBPreds(predecessors(BB));
1119 
1120  // Loop over all of the PHI nodes in the successor of BB.
1121  for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
1122  PHINode *PN = cast<PHINode>(I);
1123 
1125  }
1126  }
1127 
1128  if (Succ->getSinglePredecessor()) {
1129  // BB is the only predecessor of Succ, so Succ will end up with exactly
1130  // the same predecessors BB had.
1131 
1132  // Copy over any phi, debug or lifetime instruction.
1133  BB->getTerminator()->eraseFromParent();
1134  Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(),
1135  BB->getInstList());
1136  } else {
1137  while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
1138  // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
1139  assert(PN->use_empty() && "There shouldn't be any uses here!");
1140  PN->eraseFromParent();
1141  }
1142  }
1143 
1144  // If the unconditional branch we replaced contains llvm.loop metadata, we
1145  // add the metadata to the branch instructions in the predecessors.
1146  unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
1147  Instruction *TI = BB->getTerminator();
1148  if (TI)
1149  if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
1150  for (BasicBlock *Pred : predecessors(BB))
1151  Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
1152 
1153  // Everything that jumped to BB now goes to Succ.
1154  BB->replaceAllUsesWith(Succ);
1155  if (!Succ->hasName()) Succ->takeName(BB);
1156 
1157  // Clear the successor list of BB to match updates applying to DTU later.
1158  if (BB->getTerminator())
1159  BB->getInstList().pop_back();
1160  new UnreachableInst(BB->getContext(), BB);
1161  assert(succ_empty(BB) && "The successor list of BB isn't empty before "
1162  "applying corresponding DTU updates.");
1163 
1164  if (DTU)
1165  DTU->applyUpdates(Updates);
1166 
1167  DeleteDeadBlock(BB, DTU);
1168 
1169  return true;
1170 }
1171 
1173  // This implementation doesn't currently consider undef operands
1174  // specially. Theoretically, two phis which are identical except for
1175  // one having an undef where the other doesn't could be collapsed.
1176 
1177  bool Changed = false;
1178 
1179  // Examine each PHI.
1180  // Note that increment of I must *NOT* be in the iteration_expression, since
1181  // we don't want to immediately advance when we restart from the beginning.
1182  for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) {
1183  ++I;
1184  // Is there an identical PHI node in this basic block?
1185  // Note that we only look in the upper square's triangle,
1186  // we already checked that the lower triangle PHI's aren't identical.
1187  for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
1188  if (!DuplicatePN->isIdenticalToWhenDefined(PN))
1189  continue;
1190  // A duplicate. Replace this PHI with the base PHI.
1191  ++NumPHICSEs;
1192  DuplicatePN->replaceAllUsesWith(PN);
1193  DuplicatePN->eraseFromParent();
1194  Changed = true;
1195 
1196  // The RAUW can change PHIs that we already visited.
1197  I = BB->begin();
1198  break; // Start over from the beginning.
1199  }
1200  }
1201  return Changed;
1202 }
1203 
1205  // This implementation doesn't currently consider undef operands
1206  // specially. Theoretically, two phis which are identical except for
1207  // one having an undef where the other doesn't could be collapsed.
1208 
1209  struct PHIDenseMapInfo {
1210  static PHINode *getEmptyKey() {
1212  }
1213 
1214  static PHINode *getTombstoneKey() {
1216  }
1217 
1218  static bool isSentinel(PHINode *PN) {
1219  return PN == getEmptyKey() || PN == getTombstoneKey();
1220  }
1221 
1222  // WARNING: this logic must be kept in sync with
1223  // Instruction::isIdenticalToWhenDefined()!
1224  static unsigned getHashValueImpl(PHINode *PN) {
1225  // Compute a hash value on the operands. Instcombine will likely have
1226  // sorted them, which helps expose duplicates, but we have to check all
1227  // the operands to be safe in case instcombine hasn't run.
1228  return static_cast<unsigned>(hash_combine(
1230  hash_combine_range(PN->block_begin(), PN->block_end())));
1231  }
1232 
1233  static unsigned getHashValue(PHINode *PN) {
1234 #ifndef NDEBUG
1235  // If -phicse-debug-hash was specified, return a constant -- this
1236  // will force all hashing to collide, so we'll exhaustively search
1237  // the table for a match, and the assertion in isEqual will fire if
1238  // there's a bug causing equal keys to hash differently.
1239  if (PHICSEDebugHash)
1240  return 0;
1241 #endif
1242  return getHashValueImpl(PN);
1243  }
1244 
1245  static bool isEqualImpl(PHINode *LHS, PHINode *RHS) {
1246  if (isSentinel(LHS) || isSentinel(RHS))
1247  return LHS == RHS;
1248  return LHS->isIdenticalTo(RHS);
1249  }
1250 
1251  static bool isEqual(PHINode *LHS, PHINode *RHS) {
1252  // These comparisons are nontrivial, so assert that equality implies
1253  // hash equality (DenseMap demands this as an invariant).
1254  bool Result = isEqualImpl(LHS, RHS);
1255  assert(!Result || (isSentinel(LHS) && LHS == RHS) ||
1257  return Result;
1258  }
1259  };
1260 
1261  // Set of unique PHINodes.
1263  PHISet.reserve(4 * PHICSENumPHISmallSize);
1264 
1265  // Examine each PHI.
1266  bool Changed = false;
1267  for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
1268  auto Inserted = PHISet.insert(PN);
1269  if (!Inserted.second) {
1270  // A duplicate. Replace this PHI with its duplicate.
1271  ++NumPHICSEs;
1272  PN->replaceAllUsesWith(*Inserted.first);
1273  PN->eraseFromParent();
1274  Changed = true;
1275 
1276  // The RAUW can change PHIs that we already visited. Start over from the
1277  // beginning.
1278  PHISet.clear();
1279  I = BB->begin();
1280  }
1281  }
1282 
1283  return Changed;
1284 }
1285 
1287  if (
1288 #ifndef NDEBUG
1289  !PHICSEDebugHash &&
1290 #endif
1294 }
1295 
1296 /// If the specified pointer points to an object that we control, try to modify
1297 /// the object's alignment to PrefAlign. Returns a minimum known alignment of
1298 /// the value after the operation, which may be lower than PrefAlign.
1299 ///
1300 /// Increating value alignment isn't often possible though. If alignment is
1301 /// important, a more reliable approach is to simply align all global variables
1302 /// and allocation instructions to their preferred alignment from the beginning.
1303 static Align tryEnforceAlignment(Value *V, Align PrefAlign,
1304  const DataLayout &DL) {
1305  V = V->stripPointerCasts();
1306 
1307  if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
1308  // TODO: Ideally, this function would not be called if PrefAlign is smaller
1309  // than the current alignment, as the known bits calculation should have
1310  // already taken it into account. However, this is not always the case,
1311  // as computeKnownBits() has a depth limit, while stripPointerCasts()
1312  // doesn't.
1313  Align CurrentAlign = AI->getAlign();
1314  if (PrefAlign <= CurrentAlign)
1315  return CurrentAlign;
1316 
1317  // If the preferred alignment is greater than the natural stack alignment
1318  // then don't round up. This avoids dynamic stack realignment.
1319  if (DL.exceedsNaturalStackAlignment(PrefAlign))
1320  return CurrentAlign;
1321  AI->setAlignment(PrefAlign);
1322  return PrefAlign;
1323  }
1324 
1325  if (auto *GO = dyn_cast<GlobalObject>(V)) {
1326  // TODO: as above, this shouldn't be necessary.
1327  Align CurrentAlign = GO->getPointerAlignment(DL);
1328  if (PrefAlign <= CurrentAlign)
1329  return CurrentAlign;
1330 
1331  // If there is a large requested alignment and we can, bump up the alignment
1332  // of the global. If the memory we set aside for the global may not be the
1333  // memory used by the final program then it is impossible for us to reliably
1334  // enforce the preferred alignment.
1335  if (!GO->canIncreaseAlignment())
1336  return CurrentAlign;
1337 
1338  GO->setAlignment(PrefAlign);
1339  return PrefAlign;
1340  }
1341 
1342  return Align(1);
1343 }
1344 
1346  const DataLayout &DL,
1347  const Instruction *CxtI,
1348  AssumptionCache *AC,
1349  const DominatorTree *DT) {
1350  assert(V->getType()->isPointerTy() &&
1351  "getOrEnforceKnownAlignment expects a pointer!");
1352 
1353  KnownBits Known = computeKnownBits(V, DL, 0, AC, CxtI, DT);
1354  unsigned TrailZ = Known.countMinTrailingZeros();
1355 
1356  // Avoid trouble with ridiculously large TrailZ values, such as
1357  // those computed from a null pointer.
1358  // LLVM doesn't support alignments larger than (1 << MaxAlignmentExponent).
1359  TrailZ = std::min(TrailZ, +Value::MaxAlignmentExponent);
1360 
1361  Align Alignment = Align(1ull << std::min(Known.getBitWidth() - 1, TrailZ));
1362 
1363  if (PrefAlign && *PrefAlign > Alignment)
1364  Alignment = std::max(Alignment, tryEnforceAlignment(V, *PrefAlign, DL));
1365 
1366  // We don't need to make any adjustment.
1367  return Alignment;
1368 }
1369 
1370 ///===---------------------------------------------------------------------===//
1371 /// Dbg Intrinsic utilities
1372 ///
1373 
1374 /// See if there is a dbg.value intrinsic for DIVar for the PHI node.
1376  DIExpression *DIExpr,
1377  PHINode *APN) {
1378  // Since we can't guarantee that the original dbg.declare intrinsic
1379  // is removed by LowerDbgDeclare(), we need to make sure that we are
1380  // not inserting the same dbg.value intrinsic over and over.
1382  findDbgValues(DbgValues, APN);
1383  for (auto *DVI : DbgValues) {
1384  assert(is_contained(DVI->getValues(), APN));
1385  if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
1386  return true;
1387  }
1388  return false;
1389 }
1390 
1391 /// Check if the alloc size of \p ValTy is large enough to cover the variable
1392 /// (or fragment of the variable) described by \p DII.
1393 ///
1394 /// This is primarily intended as a helper for the different
1395 /// ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is
1396 /// converted describes an alloca'd variable, so we need to use the
1397 /// alloc size of the value when doing the comparison. E.g. an i1 value will be
1398 /// identified as covering an n-bit fragment, if the store size of i1 is at
1399 /// least n bits.
1401  const DataLayout &DL = DII->getModule()->getDataLayout();
1402  TypeSize ValueSize = DL.getTypeAllocSizeInBits(ValTy);
1403  if (Optional<uint64_t> FragmentSize = DII->getFragmentSizeInBits()) {
1404  assert(!ValueSize.isScalable() &&
1405  "Fragments don't work on scalable types.");
1406  return ValueSize.getFixedSize() >= *FragmentSize;
1407  }
1408  // We can't always calculate the size of the DI variable (e.g. if it is a
1409  // VLA). Try to use the size of the alloca that the dbg intrinsic describes
1410  // intead.
1411  if (DII->isAddressOfVariable()) {
1412  // DII should have exactly 1 location when it is an address.
1413  assert(DII->getNumVariableLocationOps() == 1 &&
1414  "address of variable must have exactly 1 location operand.");
1415  if (auto *AI =
1416  dyn_cast_or_null<AllocaInst>(DII->getVariableLocationOp(0))) {
1417  if (Optional<TypeSize> FragmentSize = AI->getAllocationSizeInBits(DL)) {
1418  return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1419  }
1420  }
1421  }
1422  // Could not determine size of variable. Conservatively return false.
1423  return false;
1424 }
1425 
1426 /// Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted
1427 /// to a dbg.value. Because no machine insts can come from debug intrinsics,
1428 /// only the scope and inlinedAt is significant. Zero line numbers are used in
1429 /// case this DebugLoc leaks into any adjacent instructions.
1431  // Original dbg.declare must have a location.
1432  const DebugLoc &DeclareLoc = DII->getDebugLoc();
1433  MDNode *Scope = DeclareLoc.getScope();
1434  DILocation *InlinedAt = DeclareLoc.getInlinedAt();
1435  // Produce an unknown location with the correct scope / inlinedAt fields.
1436  return DILocation::get(DII->getContext(), 0, 0, Scope, InlinedAt);
1437 }
1438 
1439 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1440 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1443  assert(DII->isAddressOfVariable());
1444  auto *DIVar = DII->getVariable();
1445  assert(DIVar && "Missing variable");
1446  auto *DIExpr = DII->getExpression();
1447  Value *DV = SI->getValueOperand();
1448 
1449  DebugLoc NewLoc = getDebugValueLoc(DII, SI);
1450 
1451  if (!valueCoversEntireFragment(DV->getType(), DII)) {
1452  // FIXME: If storing to a part of the variable described by the dbg.declare,
1453  // then we want to insert a dbg.value for the corresponding fragment.
1454  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1455  << *DII << '\n');
1456  // For now, when there is a store to parts of the variable (but we do not
1457  // know which part) we insert an dbg.value intrinsic to indicate that we
1458  // know nothing about the variable's content.
1459  DV = UndefValue::get(DV->getType());
1460  Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1461  return;
1462  }
1463 
1464  Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1465 }
1466 
1467 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1468 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1470  LoadInst *LI, DIBuilder &Builder) {
1471  auto *DIVar = DII->getVariable();
1472  auto *DIExpr = DII->getExpression();
1473  assert(DIVar && "Missing variable");
1474 
1475  if (!valueCoversEntireFragment(LI->getType(), DII)) {
1476  // FIXME: If only referring to a part of the variable described by the
1477  // dbg.declare, then we want to insert a dbg.value for the corresponding
1478  // fragment.
1479  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1480  << *DII << '\n');
1481  return;
1482  }
1483 
1484  DebugLoc NewLoc = getDebugValueLoc(DII, nullptr);
1485 
1486  // We are now tracking the loaded value instead of the address. In the
1487  // future if multi-location support is added to the IR, it might be
1488  // preferable to keep tracking both the loaded value and the original
1489  // address in case the alloca can not be elided.
1490  Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
1491  LI, DIVar, DIExpr, NewLoc, (Instruction *)nullptr);
1492  DbgValue->insertAfter(LI);
1493 }
1494 
1495 /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
1496 /// llvm.dbg.declare or llvm.dbg.addr intrinsic.
1498  PHINode *APN, DIBuilder &Builder) {
1499  auto *DIVar = DII->getVariable();
1500  auto *DIExpr = DII->getExpression();
1501  assert(DIVar && "Missing variable");
1502 
1503  if (PhiHasDebugValue(DIVar, DIExpr, APN))
1504  return;
1505 
1506  if (!valueCoversEntireFragment(APN->getType(), DII)) {
1507  // FIXME: If only referring to a part of the variable described by the
1508  // dbg.declare, then we want to insert a dbg.value for the corresponding
1509  // fragment.
1510  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1511  << *DII << '\n');
1512  return;
1513  }
1514 
1515  BasicBlock *BB = APN->getParent();
1516  auto InsertionPt = BB->getFirstInsertionPt();
1517 
1518  DebugLoc NewLoc = getDebugValueLoc(DII, nullptr);
1519 
1520  // The block may be a catchswitch block, which does not have a valid
1521  // insertion point.
1522  // FIXME: Insert dbg.value markers in the successors when appropriate.
1523  if (InsertionPt != BB->end())
1524  Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, NewLoc, &*InsertionPt);
1525 }
1526 
1527 /// Determine whether this alloca is either a VLA or an array.
1528 static bool isArray(AllocaInst *AI) {
1529  return AI->isArrayAllocation() ||
1530  (AI->getAllocatedType() && AI->getAllocatedType()->isArrayTy());
1531 }
1532 
1533 /// Determine whether this alloca is a structure.
1534 static bool isStructure(AllocaInst *AI) {
1535  return AI->getAllocatedType() && AI->getAllocatedType()->isStructTy();
1536 }
1537 
1538 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1539 /// of llvm.dbg.value intrinsics.
1541  bool Changed = false;
1542  DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1544  for (auto &FI : F)
1545  for (Instruction &BI : FI)
1546  if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
1547  Dbgs.push_back(DDI);
1548 
1549  if (Dbgs.empty())
1550  return Changed;
1551 
1552  for (auto &I : Dbgs) {
1553  DbgDeclareInst *DDI = I;
1554  AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1555  // If this is an alloca for a scalar variable, insert a dbg.value
1556  // at each load and store to the alloca and erase the dbg.declare.
1557  // The dbg.values allow tracking a variable even if it is not
1558  // stored on the stack, while the dbg.declare can only describe
1559  // the stack slot (and at a lexical-scope granularity). Later
1560  // passes will attempt to elide the stack slot.
1561  if (!AI || isArray(AI) || isStructure(AI))
1562  continue;
1563 
1564  // A volatile load/store means that the alloca can't be elided anyway.
1565  if (llvm::any_of(AI->users(), [](User *U) -> bool {
1566  if (LoadInst *LI = dyn_cast<LoadInst>(U))
1567  return LI->isVolatile();
1568  if (StoreInst *SI = dyn_cast<StoreInst>(U))
1569  return SI->isVolatile();
1570  return false;
1571  }))
1572  continue;
1573 
1575  WorkList.push_back(AI);
1576  while (!WorkList.empty()) {
1577  const Value *V = WorkList.pop_back_val();
1578  for (const auto &AIUse : V->uses()) {
1579  User *U = AIUse.getUser();
1580  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1581  if (AIUse.getOperandNo() == 1)
1583  } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1584  ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1585  } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1586  // This is a call by-value or some other instruction that takes a
1587  // pointer to the variable. Insert a *value* intrinsic that describes
1588  // the variable by dereferencing the alloca.
1589  if (!CI->isLifetimeStartOrEnd()) {
1590  DebugLoc NewLoc = getDebugValueLoc(DDI, nullptr);
1591  auto *DerefExpr =
1592  DIExpression::append(DDI->getExpression(), dwarf::DW_OP_deref);
1593  DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DerefExpr,
1594  NewLoc, CI);
1595  }
1596  } else if (BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
1597  if (BI->getType()->isPointerTy())
1598  WorkList.push_back(BI);
1599  }
1600  }
1601  }
1602  DDI->eraseFromParent();
1603  Changed = true;
1604  }
1605 
1606  if (Changed)
1607  for (BasicBlock &BB : F)
1609 
1610  return Changed;
1611 }
1612 
1613 /// Propagate dbg.value intrinsics through the newly inserted PHIs.
1615  SmallVectorImpl<PHINode *> &InsertedPHIs) {
1616  assert(BB && "No BasicBlock to clone dbg.value(s) from.");
1617  if (InsertedPHIs.size() == 0)
1618  return;
1619 
1620  // Map existing PHI nodes to their dbg.values.
1621  ValueToValueMapTy DbgValueMap;
1622  for (auto &I : *BB) {
1623  if (auto DbgII = dyn_cast<DbgVariableIntrinsic>(&I)) {
1624  for (Value *V : DbgII->location_ops())
1625  if (auto *Loc = dyn_cast_or_null<PHINode>(V))
1626  DbgValueMap.insert({Loc, DbgII});
1627  }
1628  }
1629  if (DbgValueMap.size() == 0)
1630  return;
1631 
1632  // Map a pair of the destination BB and old dbg.value to the new dbg.value,
1633  // so that if a dbg.value is being rewritten to use more than one of the
1634  // inserted PHIs in the same destination BB, we can update the same dbg.value
1635  // with all the new PHIs instead of creating one copy for each.
1638  NewDbgValueMap;
1639  // Then iterate through the new PHIs and look to see if they use one of the
1640  // previously mapped PHIs. If so, create a new dbg.value intrinsic that will
1641  // propagate the info through the new PHI. If we use more than one new PHI in
1642  // a single destination BB with the same old dbg.value, merge the updates so
1643  // that we get a single new dbg.value with all the new PHIs.
1644  for (auto *PHI : InsertedPHIs) {
1645  BasicBlock *Parent = PHI->getParent();
1646  // Avoid inserting an intrinsic into an EH block.
1647  if (Parent->getFirstNonPHI()->isEHPad())
1648  continue;
1649  for (auto *VI : PHI->operand_values()) {
1650  auto V = DbgValueMap.find(VI);
1651  if (V != DbgValueMap.end()) {
1652  auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
1653  auto NewDI = NewDbgValueMap.find({Parent, DbgII});
1654  if (NewDI == NewDbgValueMap.end()) {
1655  auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone());
1656  NewDI = NewDbgValueMap.insert({{Parent, DbgII}, NewDbgII}).first;
1657  }
1658  DbgVariableIntrinsic *NewDbgII = NewDI->second;
1659  // If PHI contains VI as an operand more than once, we may
1660  // replaced it in NewDbgII; confirm that it is present.
1661  if (is_contained(NewDbgII->location_ops(), VI))
1662  NewDbgII->replaceVariableLocationOp(VI, PHI);
1663  }
1664  }
1665  }
1666  // Insert thew new dbg.values into their destination blocks.
1667  for (auto DI : NewDbgValueMap) {
1668  BasicBlock *Parent = DI.first.first;
1669  auto *NewDbgII = DI.second;
1670  auto InsertionPt = Parent->getFirstInsertionPt();
1671  assert(InsertionPt != Parent->end() && "Ill-formed basic block");
1672  NewDbgII->insertBefore(&*InsertionPt);
1673  }
1674 }
1675 
1676 bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress,
1677  DIBuilder &Builder, uint8_t DIExprFlags,
1678  int Offset) {
1679  auto DbgAddrs = FindDbgAddrUses(Address);
1680  for (DbgVariableIntrinsic *DII : DbgAddrs) {
1681  const DebugLoc &Loc = DII->getDebugLoc();
1682  auto *DIVar = DII->getVariable();
1683  auto *DIExpr = DII->getExpression();
1684  assert(DIVar && "Missing variable");
1685  DIExpr = DIExpression::prepend(DIExpr, DIExprFlags, Offset);
1686  // Insert llvm.dbg.declare immediately before DII, and remove old
1687  // llvm.dbg.declare.
1688  Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, DII);
1689  DII->eraseFromParent();
1690  }
1691  return !DbgAddrs.empty();
1692 }
1693 
1694 static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
1695  DIBuilder &Builder, int Offset) {
1696  const DebugLoc &Loc = DVI->getDebugLoc();
1697  auto *DIVar = DVI->getVariable();
1698  auto *DIExpr = DVI->getExpression();
1699  assert(DIVar && "Missing variable");
1700 
1701  // This is an alloca-based llvm.dbg.value. The first thing it should do with
1702  // the alloca pointer is dereference it. Otherwise we don't know how to handle
1703  // it and give up.
1704  if (!DIExpr || DIExpr->getNumElements() < 1 ||
1705  DIExpr->getElement(0) != dwarf::DW_OP_deref)
1706  return;
1707 
1708  // Insert the offset before the first deref.
1709  // We could just change the offset argument of dbg.value, but it's unsigned...
1710  if (Offset)
1711  DIExpr = DIExpression::prepend(DIExpr, 0, Offset);
1712 
1713  Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI);
1714  DVI->eraseFromParent();
1715 }
1716 
1718  DIBuilder &Builder, int Offset) {
1719  if (auto *L = LocalAsMetadata::getIfExists(AI))
1720  if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
1721  for (Use &U : llvm::make_early_inc_range(MDV->uses()))
1722  if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
1723  replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1724 }
1725 
1726 /// Where possible to salvage debug information for \p I do so.
1727 /// If not possible mark undef.
1730  findDbgUsers(DbgUsers, &I);
1731  salvageDebugInfoForDbgValues(I, DbgUsers);
1732 }
1733 
1736  // These are arbitrary chosen limits on the maximum number of values and the
1737  // maximum size of a debug expression we can salvage up to, used for
1738  // performance reasons.
1739  const unsigned MaxDebugArgs = 16;
1740  const unsigned MaxExpressionSize = 128;
1741  bool Salvaged = false;
1742 
1743  for (auto *DII : DbgUsers) {
1744  // Do not add DW_OP_stack_value for DbgDeclare and DbgAddr, because they
1745  // are implicitly pointing out the value as a DWARF memory location
1746  // description.
1747  bool StackValue = isa<DbgValueInst>(DII);
1748  auto DIILocation = DII->location_ops();
1749  assert(
1750  is_contained(DIILocation, &I) &&
1751  "DbgVariableIntrinsic must use salvaged instruction as its location");
1752  SmallVector<Value *, 4> AdditionalValues;
1753  // `I` may appear more than once in DII's location ops, and each use of `I`
1754  // must be updated in the DIExpression and potentially have additional
1755  // values added; thus we call salvageDebugInfoImpl for each `I` instance in
1756  // DIILocation.
1757  Value *Op0 = nullptr;
1758  DIExpression *SalvagedExpr = DII->getExpression();
1759  auto LocItr = find(DIILocation, &I);
1760  while (SalvagedExpr && LocItr != DIILocation.end()) {
1762  unsigned LocNo = std::distance(DIILocation.begin(), LocItr);
1763  uint64_t CurrentLocOps = SalvagedExpr->getNumLocationOperands();
1764  Op0 = salvageDebugInfoImpl(I, CurrentLocOps, Ops, AdditionalValues);
1765  if (!Op0)
1766  break;
1767  SalvagedExpr =
1768  DIExpression::appendOpsToArg(SalvagedExpr, Ops, LocNo, StackValue);
1769  LocItr = std::find(++LocItr, DIILocation.end(), &I);
1770  }
1771  // salvageDebugInfoImpl should fail on examining the first element of
1772  // DbgUsers, or none of them.
1773  if (!Op0)
1774  break;
1775 
1776  DII->replaceVariableLocationOp(&I, Op0);
1777  bool IsValidSalvageExpr = SalvagedExpr->getNumElements() <= MaxExpressionSize;
1778  if (AdditionalValues.empty() && IsValidSalvageExpr) {
1779  DII->setExpression(SalvagedExpr);
1780  } else if (isa<DbgValueInst>(DII) && IsValidSalvageExpr &&
1781  DII->getNumVariableLocationOps() + AdditionalValues.size() <=
1782  MaxDebugArgs) {
1783  DII->addVariableLocationOps(AdditionalValues, SalvagedExpr);
1784  } else {
1785  // Do not salvage using DIArgList for dbg.addr/dbg.declare, as it is
1786  // currently only valid for stack value expressions.
1787  // Also do not salvage if the resulting DIArgList would contain an
1788  // unreasonably large number of values.
1789  Value *Undef = UndefValue::get(I.getOperand(0)->getType());
1790  DII->replaceVariableLocationOp(I.getOperand(0), Undef);
1791  }
1792  LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
1793  Salvaged = true;
1794  }
1795 
1796  if (Salvaged)
1797  return;
1798 
1799  for (auto *DII : DbgUsers) {
1800  Value *Undef = UndefValue::get(I.getType());
1801  DII->replaceVariableLocationOp(&I, Undef);
1802  }
1803 }
1804 
1806  uint64_t CurrentLocOps,
1807  SmallVectorImpl<uint64_t> &Opcodes,
1808  SmallVectorImpl<Value *> &AdditionalValues) {
1809  unsigned BitWidth = DL.getIndexSizeInBits(GEP->getPointerAddressSpace());
1810  // Rewrite a GEP into a DIExpression.
1811  MapVector<Value *, APInt> VariableOffsets;
1812  APInt ConstantOffset(BitWidth, 0);
1813  if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
1814  return nullptr;
1815  if (!VariableOffsets.empty() && !CurrentLocOps) {
1816  Opcodes.insert(Opcodes.begin(), {dwarf::DW_OP_LLVM_arg, 0});
1817  CurrentLocOps = 1;
1818  }
1819  for (auto Offset : VariableOffsets) {
1820  AdditionalValues.push_back(Offset.first);
1821  assert(Offset.second.isStrictlyPositive() &&
1822  "Expected strictly positive multiplier for offset.");
1823  Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps++, dwarf::DW_OP_constu,
1824  Offset.second.getZExtValue(), dwarf::DW_OP_mul,
1825  dwarf::DW_OP_plus});
1826  }
1827  DIExpression::appendOffset(Opcodes, ConstantOffset.getSExtValue());
1828  return GEP->getOperand(0);
1829 }
1830 
1832  switch (Opcode) {
1833  case Instruction::Add:
1834  return dwarf::DW_OP_plus;
1835  case Instruction::Sub:
1836  return dwarf::DW_OP_minus;
1837  case Instruction::Mul:
1838  return dwarf::DW_OP_mul;
1839  case Instruction::SDiv:
1840  return dwarf::DW_OP_div;
1841  case Instruction::SRem:
1842  return dwarf::DW_OP_mod;
1843  case Instruction::Or:
1844  return dwarf::DW_OP_or;
1845  case Instruction::And:
1846  return dwarf::DW_OP_and;
1847  case Instruction::Xor:
1848  return dwarf::DW_OP_xor;
1849  case Instruction::Shl:
1850  return dwarf::DW_OP_shl;
1851  case Instruction::LShr:
1852  return dwarf::DW_OP_shr;
1853  case Instruction::AShr:
1854  return dwarf::DW_OP_shra;
1855  default:
1856  // TODO: Salvage from each kind of binop we know about.
1857  return 0;
1858  }
1859 }
1860 
1862  SmallVectorImpl<uint64_t> &Opcodes,
1863  SmallVectorImpl<Value *> &AdditionalValues) {
1864  // Handle binary operations with constant integer operands as a special case.
1865  auto *ConstInt = dyn_cast<ConstantInt>(BI->getOperand(1));
1866  // Values wider than 64 bits cannot be represented within a DIExpression.
1867  if (ConstInt && ConstInt->getBitWidth() > 64)
1868  return nullptr;
1869 
1870  Instruction::BinaryOps BinOpcode = BI->getOpcode();
1871  // Push any Constant Int operand onto the expression stack.
1872  if (ConstInt) {
1873  uint64_t Val = ConstInt->getSExtValue();
1874  // Add or Sub Instructions with a constant operand can potentially be
1875  // simplified.
1876  if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
1877  uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
1878  DIExpression::appendOffset(Opcodes, Offset);
1879  return BI->getOperand(0);
1880  }
1881  Opcodes.append({dwarf::DW_OP_constu, Val});
1882  } else {
1883  if (!CurrentLocOps) {
1884  Opcodes.append({dwarf::DW_OP_LLVM_arg, 0});
1885  CurrentLocOps = 1;
1886  }
1887  Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps});
1888  AdditionalValues.push_back(BI->getOperand(1));
1889  }
1890 
1891  // Add salvaged binary operator to expression stack, if it has a valid
1892  // representation in a DIExpression.
1893  uint64_t DwarfBinOp = getDwarfOpForBinOp(BinOpcode);
1894  if (!DwarfBinOp)
1895  return nullptr;
1896  Opcodes.push_back(DwarfBinOp);
1897  return BI->getOperand(0);
1898 }
1899 
1902  SmallVectorImpl<Value *> &AdditionalValues) {
1903  auto &M = *I.getModule();
1904  auto &DL = M.getDataLayout();
1905 
1906  if (auto *CI = dyn_cast<CastInst>(&I)) {
1907  Value *FromValue = CI->getOperand(0);
1908  // No-op casts are irrelevant for debug info.
1909  if (CI->isNoopCast(DL)) {
1910  return FromValue;
1911  }
1912 
1913  Type *Type = CI->getType();
1914  if (Type->isPointerTy())
1915  Type = DL.getIntPtrType(Type);
1916  // Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged.
1917  if (Type->isVectorTy() ||
1918  !(isa<TruncInst>(&I) || isa<SExtInst>(&I) || isa<ZExtInst>(&I) ||
1919  isa<IntToPtrInst>(&I) || isa<PtrToIntInst>(&I)))
1920  return nullptr;
1921 
1922  llvm::Type *FromType = FromValue->getType();
1923  if (FromType->isPointerTy())
1924  FromType = DL.getIntPtrType(FromType);
1925 
1926  unsigned FromTypeBitSize = FromType->getScalarSizeInBits();
1927  unsigned ToTypeBitSize = Type->getScalarSizeInBits();
1928 
1929  auto ExtOps = DIExpression::getExtOps(FromTypeBitSize, ToTypeBitSize,
1930  isa<SExtInst>(&I));
1931  Ops.append(ExtOps.begin(), ExtOps.end());
1932  return FromValue;
1933  }
1934 
1935  if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))
1936  return getSalvageOpsForGEP(GEP, DL, CurrentLocOps, Ops, AdditionalValues);
1937  if (auto *BI = dyn_cast<BinaryOperator>(&I))
1938  return getSalvageOpsForBinOp(BI, CurrentLocOps, Ops, AdditionalValues);
1939 
1940  // *Not* to do: we should not attempt to salvage load instructions,
1941  // because the validity and lifetime of a dbg.value containing
1942  // DW_OP_deref becomes difficult to analyze. See PR40628 for examples.
1943  return nullptr;
1944 }
1945 
1946 /// A replacement for a dbg.value expression.
1948 
1949 /// Point debug users of \p From to \p To using exprs given by \p RewriteExpr,
1950 /// possibly moving/undefing users to prevent use-before-def. Returns true if
1951 /// changes are made.
1952 static bool rewriteDebugUsers(
1953  Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT,
1955  // Find debug users of From.
1957  findDbgUsers(Users, &From);
1958  if (Users.empty())
1959  return false;
1960 
1961  // Prevent use-before-def of To.
1962  bool Changed = false;
1964  if (isa<Instruction>(&To)) {
1965  bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint;
1966 
1967  for (auto *DII : Users) {
1968  // It's common to see a debug user between From and DomPoint. Move it
1969  // after DomPoint to preserve the variable update without any reordering.
1970  if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) {
1971  LLVM_DEBUG(dbgs() << "MOVE: " << *DII << '\n');
1972  DII->moveAfter(&DomPoint);
1973  Changed = true;
1974 
1975  // Users which otherwise aren't dominated by the replacement value must
1976  // be salvaged or deleted.
1977  } else if (!DT.dominates(&DomPoint, DII)) {
1978  UndefOrSalvage.insert(DII);
1979  }
1980  }
1981  }
1982 
1983  // Update debug users without use-before-def risk.
1984  for (auto *DII : Users) {
1985  if (UndefOrSalvage.count(DII))
1986  continue;
1987 
1988  DbgValReplacement DVR = RewriteExpr(*DII);
1989  if (!DVR)
1990  continue;
1991 
1992  DII->replaceVariableLocationOp(&From, &To);
1993  DII->setExpression(*DVR);
1994  LLVM_DEBUG(dbgs() << "REWRITE: " << *DII << '\n');
1995  Changed = true;
1996  }
1997 
1998  if (!UndefOrSalvage.empty()) {
1999  // Try to salvage the remaining debug users.
2001  Changed = true;
2002  }
2003 
2004  return Changed;
2005 }
2006 
2007 /// Check if a bitcast between a value of type \p FromTy to type \p ToTy would
2008 /// losslessly preserve the bits and semantics of the value. This predicate is
2009 /// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result.
2010 ///
2011 /// Note that Type::canLosslesslyBitCastTo is not suitable here because it
2012 /// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>,
2013 /// and also does not allow lossless pointer <-> integer conversions.
2014 static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy,
2015  Type *ToTy) {
2016  // Trivially compatible types.
2017  if (FromTy == ToTy)
2018  return true;
2019 
2020  // Handle compatible pointer <-> integer conversions.
2021  if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) {
2022  bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy);
2023  bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) &&
2024  !DL.isNonIntegralPointerType(ToTy);
2025  return SameSize && LosslessConversion;
2026  }
2027 
2028  // TODO: This is not exhaustive.
2029  return false;
2030 }
2031 
2033  Instruction &DomPoint, DominatorTree &DT) {
2034  // Exit early if From has no debug users.
2035  if (!From.isUsedByMetadata())
2036  return false;
2037 
2038  assert(&From != &To && "Can't replace something with itself");
2039 
2040  Type *FromTy = From.getType();
2041  Type *ToTy = To.getType();
2042 
2043  auto Identity = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
2044  return DII.getExpression();
2045  };
2046 
2047  // Handle no-op conversions.
2048  Module &M = *From.getModule();
2049  const DataLayout &DL = M.getDataLayout();
2050  if (isBitCastSemanticsPreserving(DL, FromTy, ToTy))
2051  return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
2052 
2053  // Handle integer-to-integer widening and narrowing.
2054  // FIXME: Use DW_OP_convert when it's available everywhere.
2055  if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) {
2056  uint64_t FromBits = FromTy->getPrimitiveSizeInBits();
2057  uint64_t ToBits = ToTy->getPrimitiveSizeInBits();
2058  assert(FromBits != ToBits && "Unexpected no-op conversion");
2059 
2060  // When the width of the result grows, assume that a debugger will only
2061  // access the low `FromBits` bits when inspecting the source variable.
2062  if (FromBits < ToBits)
2063  return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
2064 
2065  // The width of the result has shrunk. Use sign/zero extension to describe
2066  // the source variable's high bits.
2067  auto SignOrZeroExt = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
2068  DILocalVariable *Var = DII.getVariable();
2069 
2070  // Without knowing signedness, sign/zero extension isn't possible.
2071  auto Signedness = Var->getSignedness();
2072  if (!Signedness)
2073  return None;
2074 
2075  bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2076  return DIExpression::appendExt(DII.getExpression(), ToBits, FromBits,
2077  Signed);
2078  };
2079  return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt);
2080  }
2081 
2082  // TODO: Floating-point conversions, vectors.
2083  return false;
2084 }
2085 
2086 std::pair<unsigned, unsigned>
2088  unsigned NumDeadInst = 0;
2089  unsigned NumDeadDbgInst = 0;
2090  // Delete the instructions backwards, as it has a reduced likelihood of
2091  // having to update as many def-use and use-def chains.
2092  Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
2093  while (EndInst != &BB->front()) {
2094  // Delete the next to last instruction.
2095  Instruction *Inst = &*--EndInst->getIterator();
2096  if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
2098  if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
2099  EndInst = Inst;
2100  continue;
2101  }
2102  if (isa<DbgInfoIntrinsic>(Inst))
2103  ++NumDeadDbgInst;
2104  else
2105  ++NumDeadInst;
2106  Inst->eraseFromParent();
2107  }
2108  return {NumDeadInst, NumDeadDbgInst};
2109 }
2110 
2111 unsigned llvm::changeToUnreachable(Instruction *I, bool PreserveLCSSA,
2112  DomTreeUpdater *DTU,
2113  MemorySSAUpdater *MSSAU) {
2114  BasicBlock *BB = I->getParent();
2115 
2116  if (MSSAU)
2117  MSSAU->changeToUnreachable(I);
2118 
2119  SmallSet<BasicBlock *, 8> UniqueSuccessors;
2120 
2121  // Loop over all of the successors, removing BB's entry from any PHI
2122  // nodes.
2123  for (BasicBlock *Successor : successors(BB)) {
2124  Successor->removePredecessor(BB, PreserveLCSSA);
2125  if (DTU)
2126  UniqueSuccessors.insert(Successor);
2127  }
2128  auto *UI = new UnreachableInst(I->getContext(), I);
2129  UI->setDebugLoc(I->getDebugLoc());
2130 
2131  // All instructions after this are dead.
2132  unsigned NumInstrsRemoved = 0;
2133  BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
2134  while (BBI != BBE) {
2135  if (!BBI->use_empty())
2136  BBI->replaceAllUsesWith(PoisonValue::get(BBI->getType()));
2137  BB->getInstList().erase(BBI++);
2138  ++NumInstrsRemoved;
2139  }
2140  if (DTU) {
2142  Updates.reserve(UniqueSuccessors.size());
2143  for (BasicBlock *UniqueSuccessor : UniqueSuccessors)
2144  Updates.push_back({DominatorTree::Delete, BB, UniqueSuccessor});
2145  DTU->applyUpdates(Updates);
2146  }
2147  return NumInstrsRemoved;
2148 }
2149 
2153  II->getOperandBundlesAsDefs(OpBundles);
2154  CallInst *NewCall = CallInst::Create(II->getFunctionType(),
2155  II->getCalledOperand(), Args, OpBundles);
2156  NewCall->setCallingConv(II->getCallingConv());
2157  NewCall->setAttributes(II->getAttributes());
2158  NewCall->setDebugLoc(II->getDebugLoc());
2159  NewCall->copyMetadata(*II);
2160 
2161  // If the invoke had profile metadata, try converting them for CallInst.
2162  uint64_t TotalWeight;
2163  if (NewCall->extractProfTotalWeight(TotalWeight)) {
2164  // Set the total weight if it fits into i32, otherwise reset.
2165  MDBuilder MDB(NewCall->getContext());
2166  auto NewWeights = uint32_t(TotalWeight) != TotalWeight
2167  ? nullptr
2168  : MDB.createBranchWeights({uint32_t(TotalWeight)});
2169  NewCall->setMetadata(LLVMContext::MD_prof, NewWeights);
2170  }
2171 
2172  return NewCall;
2173 }
2174 
2175 // changeToCall - Convert the specified invoke into a normal call.
2177  CallInst *NewCall = createCallMatchingInvoke(II);
2178  NewCall->takeName(II);
2179  NewCall->insertBefore(II);
2180  II->replaceAllUsesWith(NewCall);
2181 
2182  // Follow the call by a branch to the normal destination.
2183  BasicBlock *NormalDestBB = II->getNormalDest();
2184  BranchInst::Create(NormalDestBB, II);
2185 
2186  // Update PHI nodes in the unwind destination
2187  BasicBlock *BB = II->getParent();
2188  BasicBlock *UnwindDestBB = II->getUnwindDest();
2189  UnwindDestBB->removePredecessor(BB);
2190  II->eraseFromParent();
2191  if (DTU)
2192  DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2193  return NewCall;
2194 }
2195 
2197  BasicBlock *UnwindEdge,
2198  DomTreeUpdater *DTU) {
2199  BasicBlock *BB = CI->getParent();
2200 
2201  // Convert this function call into an invoke instruction. First, split the
2202  // basic block.
2203  BasicBlock *Split = SplitBlock(BB, CI, DTU, /*LI=*/nullptr, /*MSSAU*/ nullptr,
2204  CI->getName() + ".noexc");
2205 
2206  // Delete the unconditional branch inserted by SplitBlock
2207  BB->getInstList().pop_back();
2208 
2209  // Create the new invoke instruction.
2210  SmallVector<Value *, 8> InvokeArgs(CI->args());
2212 
2213  CI->getOperandBundlesAsDefs(OpBundles);
2214 
2215  // Note: we're round tripping operand bundles through memory here, and that
2216  // can potentially be avoided with a cleverer API design that we do not have
2217  // as of this time.
2218 
2219  InvokeInst *II =
2221  UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB);
2222  II->setDebugLoc(CI->getDebugLoc());
2223  II->setCallingConv(CI->getCallingConv());
2224  II->setAttributes(CI->getAttributes());
2225  II->setMetadata(LLVMContext::MD_prof, CI->getMetadata(LLVMContext::MD_prof));
2226 
2227  if (DTU)
2228  DTU->applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});
2229 
2230  // Make sure that anything using the call now uses the invoke! This also
2231  // updates the CallGraph if present, because it uses a WeakTrackingVH.
2232  CI->replaceAllUsesWith(II);
2233 
2234  // Delete the original call
2235  Split->getInstList().pop_front();
2236  return Split;
2237 }
2238 
2240  SmallPtrSetImpl<BasicBlock *> &Reachable,
2241  DomTreeUpdater *DTU = nullptr) {
2243  BasicBlock *BB = &F.front();
2244  Worklist.push_back(BB);
2245  Reachable.insert(BB);
2246  bool Changed = false;
2247  do {
2248  BB = Worklist.pop_back_val();
2249 
2250  // Do a quick scan of the basic block, turning any obviously unreachable
2251  // instructions into LLVM unreachable insts. The instruction combining pass
2252  // canonicalizes unreachable insts into stores to null or undef.
2253  for (Instruction &I : *BB) {
2254  if (auto *CI = dyn_cast<CallInst>(&I)) {
2255  Value *Callee = CI->getCalledOperand();
2256  // Handle intrinsic calls.
2257  if (Function *F = dyn_cast<Function>(Callee)) {
2258  auto IntrinsicID = F->getIntrinsicID();
2259  // Assumptions that are known to be false are equivalent to
2260  // unreachable. Also, if the condition is undefined, then we make the
2261  // choice most beneficial to the optimizer, and choose that to also be
2262  // unreachable.
2263  if (IntrinsicID == Intrinsic::assume) {
2264  if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
2265  // Don't insert a call to llvm.trap right before the unreachable.
2266  changeToUnreachable(CI, false, DTU);
2267  Changed = true;
2268  break;
2269  }
2270  } else if (IntrinsicID == Intrinsic::experimental_guard) {
2271  // A call to the guard intrinsic bails out of the current
2272  // compilation unit if the predicate passed to it is false. If the
2273  // predicate is a constant false, then we know the guard will bail
2274  // out of the current compile unconditionally, so all code following
2275  // it is dead.
2276  //
2277  // Note: unlike in llvm.assume, it is not "obviously profitable" for
2278  // guards to treat `undef` as `false` since a guard on `undef` can
2279  // still be useful for widening.
2280  if (match(CI->getArgOperand(0), m_Zero()))
2281  if (!isa<UnreachableInst>(CI->getNextNode())) {
2282  changeToUnreachable(CI->getNextNode(), false, DTU);
2283  Changed = true;
2284  break;
2285  }
2286  }
2287  } else if ((isa<ConstantPointerNull>(Callee) &&
2288  !NullPointerIsDefined(CI->getFunction())) ||
2289  isa<UndefValue>(Callee)) {
2290  changeToUnreachable(CI, false, DTU);
2291  Changed = true;
2292  break;
2293  }
2294  if (CI->doesNotReturn() && !CI->isMustTailCall()) {
2295  // If we found a call to a no-return function, insert an unreachable
2296  // instruction after it. Make sure there isn't *already* one there
2297  // though.
2298  if (!isa<UnreachableInst>(CI->getNextNode())) {
2299  // Don't insert a call to llvm.trap right before the unreachable.
2300  changeToUnreachable(CI->getNextNode(), false, DTU);
2301  Changed = true;
2302  }
2303  break;
2304  }
2305  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
2306  // Store to undef and store to null are undefined and used to signal
2307  // that they should be changed to unreachable by passes that can't
2308  // modify the CFG.
2309 
2310  // Don't touch volatile stores.
2311  if (SI->isVolatile()) continue;
2312 
2313  Value *Ptr = SI->getOperand(1);
2314 
2315  if (isa<UndefValue>(Ptr) ||
2316  (isa<ConstantPointerNull>(Ptr) &&
2317  !NullPointerIsDefined(SI->getFunction(),
2318  SI->getPointerAddressSpace()))) {
2319  changeToUnreachable(SI, false, DTU);
2320  Changed = true;
2321  break;
2322  }
2323  }
2324  }
2325 
2326  Instruction *Terminator = BB->getTerminator();
2327  if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
2328  // Turn invokes that call 'nounwind' functions into ordinary calls.
2329  Value *Callee = II->getCalledOperand();
2330  if ((isa<ConstantPointerNull>(Callee) &&
2331  !NullPointerIsDefined(BB->getParent())) ||
2332  isa<UndefValue>(Callee)) {
2333  changeToUnreachable(II, false, DTU);
2334  Changed = true;
2335  } else {
2336  if (II->doesNotReturn() &&
2337  !isa<UnreachableInst>(II->getNormalDest()->front())) {
2338  // If we found an invoke of a no-return function,
2339  // create a new empty basic block with an `unreachable` terminator,
2340  // and set it as the normal destination for the invoke,
2341  // unless that is already the case.
2342  // Note that the original normal destination could have other uses.
2343  BasicBlock *OrigNormalDest = II->getNormalDest();
2344  OrigNormalDest->removePredecessor(II->getParent());
2345  LLVMContext &Ctx = II->getContext();
2346  BasicBlock *UnreachableNormalDest = BasicBlock::Create(
2347  Ctx, OrigNormalDest->getName() + ".unreachable",
2348  II->getFunction(), OrigNormalDest);
2349  new UnreachableInst(Ctx, UnreachableNormalDest);
2350  II->setNormalDest(UnreachableNormalDest);
2351  if (DTU)
2352  DTU->applyUpdates(
2353  {{DominatorTree::Delete, BB, OrigNormalDest},
2354  {DominatorTree::Insert, BB, UnreachableNormalDest}});
2355  Changed = true;
2356  }
2357  if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
2358  if (II->use_empty() && !II->mayHaveSideEffects()) {
2359  // jump to the normal destination branch.
2360  BasicBlock *NormalDestBB = II->getNormalDest();
2361  BasicBlock *UnwindDestBB = II->getUnwindDest();
2362  BranchInst::Create(NormalDestBB, II);
2363  UnwindDestBB->removePredecessor(II->getParent());
2364  II->eraseFromParent();
2365  if (DTU)
2366  DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2367  } else
2368  changeToCall(II, DTU);
2369  Changed = true;
2370  }
2371  }
2372  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
2373  // Remove catchpads which cannot be reached.
2374  struct CatchPadDenseMapInfo {
2375  static CatchPadInst *getEmptyKey() {
2377  }
2378 
2379  static CatchPadInst *getTombstoneKey() {
2381  }
2382 
2383  static unsigned getHashValue(CatchPadInst *CatchPad) {
2384  return static_cast<unsigned>(hash_combine_range(
2385  CatchPad->value_op_begin(), CatchPad->value_op_end()));
2386  }
2387 
2388  static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
2389  if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
2390  RHS == getEmptyKey() || RHS == getTombstoneKey())
2391  return LHS == RHS;
2392  return LHS->isIdenticalTo(RHS);
2393  }
2394  };
2395 
2396  SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
2397  // Set of unique CatchPads.
2399  CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
2400  HandlerSet;
2401  detail::DenseSetEmpty Empty;
2402  for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
2403  E = CatchSwitch->handler_end();
2404  I != E; ++I) {
2405  BasicBlock *HandlerBB = *I;
2406  if (DTU)
2407  ++NumPerSuccessorCases[HandlerBB];
2408  auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
2409  if (!HandlerSet.insert({CatchPad, Empty}).second) {
2410  if (DTU)
2411  --NumPerSuccessorCases[HandlerBB];
2412  CatchSwitch->removeHandler(I);
2413  --I;
2414  --E;
2415  Changed = true;
2416  }
2417  }
2418  if (DTU) {
2419  std::vector<DominatorTree::UpdateType> Updates;
2420  for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases)
2421  if (I.second == 0)
2422  Updates.push_back({DominatorTree::Delete, BB, I.first});
2423  DTU->applyUpdates(Updates);
2424  }
2425  }
2426 
2427  Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
2428  for (BasicBlock *Successor : successors(BB))
2429  if (Reachable.insert(Successor).second)
2430  Worklist.push_back(Successor);
2431  } while (!Worklist.empty());
2432  return Changed;
2433 }
2434 
2436  Instruction *TI = BB->getTerminator();
2437 
2438  if (auto *II = dyn_cast<InvokeInst>(TI)) {
2439  changeToCall(II, DTU);
2440  return;
2441  }
2442 
2443  Instruction *NewTI;
2444  BasicBlock *UnwindDest;
2445 
2446  if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
2447  NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
2448  UnwindDest = CRI->getUnwindDest();
2449  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
2450  auto *NewCatchSwitch = CatchSwitchInst::Create(
2451  CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
2452  CatchSwitch->getName(), CatchSwitch);
2453  for (BasicBlock *PadBB : CatchSwitch->handlers())
2454  NewCatchSwitch->addHandler(PadBB);
2455 
2456  NewTI = NewCatchSwitch;
2457  UnwindDest = CatchSwitch->getUnwindDest();
2458  } else {
2459  llvm_unreachable("Could not find unwind successor");
2460  }
2461 
2462  NewTI->takeName(TI);
2463  NewTI->setDebugLoc(TI->getDebugLoc());
2464  UnwindDest->removePredecessor(BB);
2465  TI->replaceAllUsesWith(NewTI);
2466  TI->eraseFromParent();
2467  if (DTU)
2468  DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
2469 }
2470 
2471 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
2472 /// if they are in a dead cycle. Return true if a change was made, false
2473 /// otherwise.
2475  MemorySSAUpdater *MSSAU) {
2477  bool Changed = markAliveBlocks(F, Reachable, DTU);
2478 
2479  // If there are unreachable blocks in the CFG...
2480  if (Reachable.size() == F.size())
2481  return Changed;
2482 
2483  assert(Reachable.size() < F.size());
2484 
2485  // Are there any blocks left to actually delete?
2486  SmallSetVector<BasicBlock *, 8> BlocksToRemove;
2487  for (BasicBlock &BB : F) {
2488  // Skip reachable basic blocks
2489  if (Reachable.count(&BB))
2490  continue;
2491  // Skip already-deleted blocks
2492  if (DTU && DTU->isBBPendingDeletion(&BB))
2493  continue;
2494  BlocksToRemove.insert(&BB);
2495  }
2496 
2497  if (BlocksToRemove.empty())
2498  return Changed;
2499 
2500  Changed = true;
2501  NumRemoved += BlocksToRemove.size();
2502 
2503  if (MSSAU)
2504  MSSAU->removeBlocks(BlocksToRemove);
2505 
2506  DeleteDeadBlocks(BlocksToRemove.takeVector(), DTU);
2507 
2508  return Changed;
2509 }
2510 
2512  ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
2514  K->dropUnknownNonDebugMetadata(KnownIDs);
2516  for (const auto &MD : Metadata) {
2517  unsigned Kind = MD.first;
2518  MDNode *JMD = J->getMetadata(Kind);
2519  MDNode *KMD = MD.second;
2520 
2521  switch (Kind) {
2522  default:
2523  K->setMetadata(Kind, nullptr); // Remove unknown metadata
2524  break;
2525  case LLVMContext::MD_dbg:
2526  llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
2527  case LLVMContext::MD_tbaa:
2529  break;
2530  case LLVMContext::MD_alias_scope:
2532  break;
2533  case LLVMContext::MD_noalias:
2534  case LLVMContext::MD_mem_parallel_loop_access:
2535  K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
2536  break;
2537  case LLVMContext::MD_access_group:
2538  K->setMetadata(LLVMContext::MD_access_group,
2539  intersectAccessGroups(K, J));
2540  break;
2541  case LLVMContext::MD_range:
2542 
2543  // If K does move, use most generic range. Otherwise keep the range of
2544  // K.
2545  if (DoesKMove)
2546  // FIXME: If K does move, we should drop the range info and nonnull.
2547  // Currently this function is used with DoesKMove in passes
2548  // doing hoisting/sinking and the current behavior of using the
2549  // most generic range is correct in those cases.
2551  break;
2552  case LLVMContext::MD_fpmath:
2554  break;
2555  case LLVMContext::MD_invariant_load:
2556  // Only set the !invariant.load if it is present in both instructions.
2557  K->setMetadata(Kind, JMD);
2558  break;
2559  case LLVMContext::MD_nonnull:
2560  // If K does move, keep nonull if it is present in both instructions.
2561  if (DoesKMove)
2562  K->setMetadata(Kind, JMD);
2563  break;
2564  case LLVMContext::MD_invariant_group:
2565  // Preserve !invariant.group in K.
2566  break;
2567  case LLVMContext::MD_align:
2568  K->setMetadata(Kind,
2570  break;
2571  case LLVMContext::MD_dereferenceable:
2572  case LLVMContext::MD_dereferenceable_or_null:
2573  K->setMetadata(Kind,
2575  break;
2576  case LLVMContext::MD_preserve_access_index:
2577  // Preserve !preserve.access.index in K.
2578  break;
2579  }
2580  }
2581  // Set !invariant.group from J if J has it. If both instructions have it
2582  // then we will just pick it from J - even when they are different.
2583  // Also make sure that K is load or store - f.e. combining bitcast with load
2584  // could produce bitcast with invariant.group metadata, which is invalid.
2585  // FIXME: we should try to preserve both invariant.group md if they are
2586  // different, but right now instruction can only have one invariant.group.
2587  if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2588  if (isa<LoadInst>(K) || isa<StoreInst>(K))
2589  K->setMetadata(LLVMContext::MD_invariant_group, JMD);
2590 }
2591 
2593  bool KDominatesJ) {
2594  unsigned KnownIDs[] = {
2595  LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2596  LLVMContext::MD_noalias, LLVMContext::MD_range,
2597  LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull,
2598  LLVMContext::MD_invariant_group, LLVMContext::MD_align,
2599  LLVMContext::MD_dereferenceable,
2600  LLVMContext::MD_dereferenceable_or_null,
2601  LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index};
2602  combineMetadata(K, J, KnownIDs, KDominatesJ);
2603 }
2604 
2607  Source.getAllMetadata(MD);
2608  MDBuilder MDB(Dest.getContext());
2609  Type *NewType = Dest.getType();
2610  const DataLayout &DL = Source.getModule()->getDataLayout();
2611  for (const auto &MDPair : MD) {
2612  unsigned ID = MDPair.first;
2613  MDNode *N = MDPair.second;
2614  // Note, essentially every kind of metadata should be preserved here! This
2615  // routine is supposed to clone a load instruction changing *only its type*.
2616  // The only metadata it makes sense to drop is metadata which is invalidated
2617  // when the pointer type changes. This should essentially never be the case
2618  // in LLVM, but we explicitly switch over only known metadata to be
2619  // conservatively correct. If you are adding metadata to LLVM which pertains
2620  // to loads, you almost certainly want to add it here.
2621  switch (ID) {
2622  case LLVMContext::MD_dbg:
2623  case LLVMContext::MD_tbaa:
2624  case LLVMContext::MD_prof:
2625  case LLVMContext::MD_fpmath:
2626  case LLVMContext::MD_tbaa_struct:
2627  case LLVMContext::MD_invariant_load:
2628  case LLVMContext::MD_alias_scope:
2629  case LLVMContext::MD_noalias:
2630  case LLVMContext::MD_nontemporal:
2631  case LLVMContext::MD_mem_parallel_loop_access:
2632  case LLVMContext::MD_access_group:
2633  // All of these directly apply.
2634  Dest.setMetadata(ID, N);
2635  break;
2636 
2637  case LLVMContext::MD_nonnull:
2638  copyNonnullMetadata(Source, N, Dest);
2639  break;
2640 
2641  case LLVMContext::MD_align:
2642  case LLVMContext::MD_dereferenceable:
2643  case LLVMContext::MD_dereferenceable_or_null:
2644  // These only directly apply if the new type is also a pointer.
2645  if (NewType->isPointerTy())
2646  Dest.setMetadata(ID, N);
2647  break;
2648 
2649  case LLVMContext::MD_range:
2650  copyRangeMetadata(DL, Source, N, Dest);
2651  break;
2652  }
2653  }
2654 }
2655 
2657  auto *ReplInst = dyn_cast<Instruction>(Repl);
2658  if (!ReplInst)
2659  return;
2660 
2661  // Patch the replacement so that it is not more restrictive than the value
2662  // being replaced.
2663  // Note that if 'I' is a load being replaced by some operation,
2664  // for example, by an arithmetic operation, then andIRFlags()
2665  // would just erase all math flags from the original arithmetic
2666  // operation, which is clearly not wanted and not needed.
2667  if (!isa<LoadInst>(I))
2668  ReplInst->andIRFlags(I);
2669 
2670  // FIXME: If both the original and replacement value are part of the
2671  // same control-flow region (meaning that the execution of one
2672  // guarantees the execution of the other), then we can combine the
2673  // noalias scopes here and do better than the general conservative
2674  // answer used in combineMetadata().
2675 
2676  // In general, GVN unifies expressions over different control-flow
2677  // regions, and so we need a conservative combination of the noalias
2678  // scopes.
2679  static const unsigned KnownIDs[] = {
2680  LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2681  LLVMContext::MD_noalias, LLVMContext::MD_range,
2682  LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
2683  LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull,
2684  LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index};
2685  combineMetadata(ReplInst, I, KnownIDs, false);
2686 }
2687 
2688 template <typename RootType, typename DominatesFn>
2690  const RootType &Root,
2691  const DominatesFn &Dominates) {
2692  assert(From->getType() == To->getType());
2693 
2694  unsigned Count = 0;
2695  for (Use &U : llvm::make_early_inc_range(From->uses())) {
2696  if (!Dominates(Root, U))
2697  continue;
2698  U.set(To);
2699  LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()
2700  << "' as " << *To << " in " << *U << "\n");
2701  ++Count;
2702  }
2703  return Count;
2704 }
2705 
2707  assert(From->getType() == To->getType());
2708  auto *BB = From->getParent();
2709  unsigned Count = 0;
2710 
2711  for (Use &U : llvm::make_early_inc_range(From->uses())) {
2712  auto *I = cast<Instruction>(U.getUser());
2713  if (I->getParent() == BB)
2714  continue;
2715  U.set(To);
2716  ++Count;
2717  }
2718  return Count;
2719 }
2720 
2722  DominatorTree &DT,
2723  const BasicBlockEdge &Root) {
2724  auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2725  return DT.dominates(Root, U);
2726  };
2727  return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2728 }
2729 
2731  DominatorTree &DT,
2732  const BasicBlock *BB) {
2733  auto Dominates = [&DT](const BasicBlock *BB, const Use &U) {
2734  return DT.dominates(BB, U);
2735  };
2736  return ::replaceDominatedUsesWith(From, To, BB, Dominates);
2737 }
2738 
2740  const TargetLibraryInfo &TLI) {
2741  // Check if the function is specifically marked as a gc leaf function.
2742  if (Call->hasFnAttr("gc-leaf-function"))
2743  return true;
2744  if (const Function *F = Call->getCalledFunction()) {
2745  if (F->hasFnAttribute("gc-leaf-function"))
2746  return true;
2747 
2748  if (auto IID = F->getIntrinsicID()) {
2749  // Most LLVM intrinsics do not take safepoints.
2750  return IID != Intrinsic::experimental_gc_statepoint &&
2751  IID != Intrinsic::experimental_deoptimize &&
2752  IID != Intrinsic::memcpy_element_unordered_atomic &&
2753  IID != Intrinsic::memmove_element_unordered_atomic;
2754  }
2755  }
2756 
2757  // Lib calls can be materialized by some passes, and won't be
2758  // marked as 'gc-leaf-function.' All available Libcalls are
2759  // GC-leaf.
2760  LibFunc LF;
2761  if (TLI.getLibFunc(*Call, LF)) {
2762  return TLI.has(LF);
2763  }
2764 
2765  return false;
2766 }
2767 
2769  LoadInst &NewLI) {
2770  auto *NewTy = NewLI.getType();
2771 
2772  // This only directly applies if the new type is also a pointer.
2773  if (NewTy->isPointerTy()) {
2774  NewLI.setMetadata(LLVMContext::MD_nonnull, N);
2775  return;
2776  }
2777 
2778  // The only other translation we can do is to integral loads with !range
2779  // metadata.
2780  if (!NewTy->isIntegerTy())
2781  return;
2782 
2783  MDBuilder MDB(NewLI.getContext());
2784  const Value *Ptr = OldLI.getPointerOperand();
2785  auto *ITy = cast<IntegerType>(NewTy);
2786  auto *NullInt = ConstantExpr::getPtrToInt(
2787  ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
2788  auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
2789  NewLI.setMetadata(LLVMContext::MD_range,
2790  MDB.createRange(NonNullInt, NullInt));
2791 }
2792 
2793 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
2794  MDNode *N, LoadInst &NewLI) {
2795  auto *NewTy = NewLI.getType();
2796 
2797  // Give up unless it is converted to a pointer where there is a single very
2798  // valuable mapping we can do reliably.
2799  // FIXME: It would be nice to propagate this in more ways, but the type
2800  // conversions make it hard.
2801  if (!NewTy->isPointerTy())
2802  return;
2803 
2804  unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
2806  MDNode *NN = MDNode::get(OldLI.getContext(), None);
2807  NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
2808  }
2809 }
2810 
2813  findDbgUsers(DbgUsers, &I);
2814  for (auto *DII : DbgUsers)
2815  DII->eraseFromParent();
2816 }
2817 
2819  BasicBlock *BB) {
2820  // Since we are moving the instructions out of its basic block, we do not
2821  // retain their original debug locations (DILocations) and debug intrinsic
2822  // instructions.
2823  //
2824  // Doing so would degrade the debugging experience and adversely affect the
2825  // accuracy of profiling information.
2826  //
2827  // Currently, when hoisting the instructions, we take the following actions:
2828  // - Remove their debug intrinsic instructions.
2829  // - Set their debug locations to the values from the insertion point.
2830  //
2831  // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
2832  // need to be deleted, is because there will not be any instructions with a
2833  // DILocation in either branch left after performing the transformation. We
2834  // can only insert a dbg.value after the two branches are joined again.
2835  //
2836  // See PR38762, PR39243 for more details.
2837  //
2838  // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
2839  // encode predicated DIExpressions that yield different results on different
2840  // code paths.
2841 
2842  for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
2843  Instruction *I = &*II;
2844  I->dropUndefImplyingAttrsAndUnknownMetadata();
2845  if (I->isUsedByMetadata())
2846  dropDebugUsers(*I);
2847  if (I->isDebugOrPseudoInst()) {
2848  // Remove DbgInfo and pseudo probe Intrinsics.
2849  II = I->eraseFromParent();
2850  continue;
2851  }
2852  I->setDebugLoc(InsertPt->getDebugLoc());
2853  ++II;
2854  }
2855  DomBlock->getInstList().splice(InsertPt->getIterator(), BB->getInstList(),
2856  BB->begin(),
2857  BB->getTerminator()->getIterator());
2858 }
2859 
2860 namespace {
2861 
2862 /// A potential constituent of a bitreverse or bswap expression. See
2863 /// collectBitParts for a fuller explanation.
2864 struct BitPart {
2865  BitPart(Value *P, unsigned BW) : Provider(P) {
2866  Provenance.resize(BW);
2867  }
2868 
2869  /// The Value that this is a bitreverse/bswap of.
2870  Value *Provider;
2871 
2872  /// The "provenance" of each bit. Provenance[A] = B means that bit A
2873  /// in Provider becomes bit B in the result of this expression.
2874  SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
2875 
2876  enum { Unset = -1 };
2877 };
2878 
2879 } // end anonymous namespace
2880 
2881 /// Analyze the specified subexpression and see if it is capable of providing
2882 /// pieces of a bswap or bitreverse. The subexpression provides a potential
2883 /// piece of a bswap or bitreverse if it can be proved that each non-zero bit in
2884 /// the output of the expression came from a corresponding bit in some other
2885 /// value. This function is recursive, and the end result is a mapping of
2886 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
2887 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
2888 ///
2889 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
2890 /// that the expression deposits the low byte of %X into the high byte of the
2891 /// result and that all other bits are zero. This expression is accepted and a
2892 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
2893 /// [0-7].
2894 ///
2895 /// For vector types, all analysis is performed at the per-element level. No
2896 /// cross-element analysis is supported (shuffle/insertion/reduction), and all
2897 /// constant masks must be splatted across all elements.
2898 ///
2899 /// To avoid revisiting values, the BitPart results are memoized into the
2900 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
2901 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
2902 /// store BitParts objects, not pointers. As we need the concept of a nullptr
2903 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
2904 /// type instead to provide the same functionality.
2905 ///
2906 /// Because we pass around references into \c BPS, we must use a container that
2907 /// does not invalidate internal references (std::map instead of DenseMap).
2908 static const Optional<BitPart> &
2909 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
2910  std::map<Value *, Optional<BitPart>> &BPS, int Depth,
2911  bool &FoundRoot) {
2912  auto I = BPS.find(V);
2913  if (I != BPS.end())
2914  return I->second;
2915 
2916  auto &Result = BPS[V] = None;
2917  auto BitWidth = V->getType()->getScalarSizeInBits();
2918 
2919  // Can't do integer/elements > 128 bits.
2920  if (BitWidth > 128)
2921  return Result;
2922 
2923  // Prevent stack overflow by limiting the recursion depth
2925  LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n");
2926  return Result;
2927  }
2928 
2929  if (auto *I = dyn_cast<Instruction>(V)) {
2930  Value *X, *Y;
2931  const APInt *C;
2932 
2933  // If this is an or instruction, it may be an inner node of the bswap.
2934  if (match(V, m_Or(m_Value(X), m_Value(Y)))) {
2935  // Check we have both sources and they are from the same provider.
2936  const auto &A = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
2937  Depth + 1, FoundRoot);
2938  if (!A || !A->Provider)
2939  return Result;
2940 
2941  const auto &B = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
2942  Depth + 1, FoundRoot);
2943  if (!B || A->Provider != B->Provider)
2944  return Result;
2945 
2946  // Try and merge the two together.
2947  Result = BitPart(A->Provider, BitWidth);
2948  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) {
2949  if (A->Provenance[BitIdx] != BitPart::Unset &&
2950  B->Provenance[BitIdx] != BitPart::Unset &&
2951  A->Provenance[BitIdx] != B->Provenance[BitIdx])
2952  return Result = None;
2953 
2954  if (A->Provenance[BitIdx] == BitPart::Unset)
2955  Result->Provenance[BitIdx] = B->Provenance[BitIdx];
2956  else
2957  Result->Provenance[BitIdx] = A->Provenance[BitIdx];
2958  }
2959 
2960  return Result;
2961  }
2962 
2963  // If this is a logical shift by a constant, recurse then shift the result.
2964  if (match(V, m_LogicalShift(m_Value(X), m_APInt(C)))) {
2965  const APInt &BitShift = *C;
2966 
2967  // Ensure the shift amount is defined.
2968  if (BitShift.uge(BitWidth))
2969  return Result;
2970 
2971  // For bswap-only, limit shift amounts to whole bytes, for an early exit.
2972  if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0)
2973  return Result;
2974 
2975  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
2976  Depth + 1, FoundRoot);
2977  if (!Res)
2978  return Result;
2979  Result = Res;
2980 
2981  // Perform the "shift" on BitProvenance.
2982  auto &P = Result->Provenance;
2983  if (I->getOpcode() == Instruction::Shl) {
2984  P.erase(std::prev(P.end(), BitShift.getZExtValue()), P.end());
2985  P.insert(P.begin(), BitShift.getZExtValue(), BitPart::Unset);
2986  } else {
2987  P.erase(P.begin(), std::next(P.begin(), BitShift.getZExtValue()));
2988  P.insert(P.end(), BitShift.getZExtValue(), BitPart::Unset);
2989  }
2990 
2991  return Result;
2992  }
2993 
2994  // If this is a logical 'and' with a mask that clears bits, recurse then
2995  // unset the appropriate bits.
2996  if (match(V, m_And(m_Value(X), m_APInt(C)))) {
2997  const APInt &AndMask = *C;
2998 
2999  // Check that the mask allows a multiple of 8 bits for a bswap, for an
3000  // early exit.
3001  unsigned NumMaskedBits = AndMask.countPopulation();
3002  if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
3003  return Result;
3004 
3005  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3006  Depth + 1, FoundRoot);
3007  if (!Res)
3008  return Result;
3009  Result = Res;
3010 
3011  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3012  // If the AndMask is zero for this bit, clear the bit.
3013  if (AndMask[BitIdx] == 0)
3014  Result->Provenance[BitIdx] = BitPart::Unset;
3015  return Result;
3016  }
3017 
3018  // If this is a zext instruction zero extend the result.
3019  if (match(V, m_ZExt(m_Value(X)))) {
3020  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3021  Depth + 1, FoundRoot);
3022  if (!Res)
3023  return Result;
3024 
3025  Result = BitPart(Res->Provider, BitWidth);
3026  auto NarrowBitWidth = X->getType()->getScalarSizeInBits();
3027  for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3028  Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3029  for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx)
3030  Result->Provenance[BitIdx] = BitPart::Unset;
3031  return Result;
3032  }
3033 
3034  // If this is a truncate instruction, extract the lower bits.
3035  if (match(V, m_Trunc(m_Value(X)))) {
3036  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3037  Depth + 1, FoundRoot);
3038  if (!Res)
3039  return Result;
3040 
3041  Result = BitPart(Res->Provider, BitWidth);
3042  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3043  Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3044  return Result;
3045  }
3046 
3047  // BITREVERSE - most likely due to us previous matching a partial
3048  // bitreverse.
3049  if (match(V, m_BitReverse(m_Value(X)))) {
3050  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3051  Depth + 1, FoundRoot);
3052  if (!Res)
3053  return Result;
3054 
3055  Result = BitPart(Res->Provider, BitWidth);
3056  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3057  Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3058  return Result;
3059  }
3060 
3061  // BSWAP - most likely due to us previous matching a partial bswap.
3062  if (match(V, m_BSwap(m_Value(X)))) {
3063  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3064  Depth + 1, FoundRoot);
3065  if (!Res)
3066  return Result;
3067 
3068  unsigned ByteWidth = BitWidth / 8;
3069  Result = BitPart(Res->Provider, BitWidth);
3070  for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3071  unsigned ByteBitOfs = ByteIdx * 8;
3072  for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3073  Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] =
3074  Res->Provenance[ByteBitOfs + BitIdx];
3075  }
3076  return Result;
3077  }
3078 
3079  // Funnel 'double' shifts take 3 operands, 2 inputs and the shift
3080  // amount (modulo).
3081  // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
3082  // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW))
3083  if (match(V, m_FShl(m_Value(X), m_Value(Y), m_APInt(C))) ||
3084  match(V, m_FShr(m_Value(X), m_Value(Y), m_APInt(C)))) {
3085  // We can treat fshr as a fshl by flipping the modulo amount.
3086  unsigned ModAmt = C->urem(BitWidth);
3087  if (cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fshr)
3088  ModAmt = BitWidth - ModAmt;
3089 
3090  // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3091  if (!MatchBitReversals && (ModAmt % 8) != 0)
3092  return Result;
3093 
3094  // Check we have both sources and they are from the same provider.
3095  const auto &LHS = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3096  Depth + 1, FoundRoot);
3097  if (!LHS || !LHS->Provider)
3098  return Result;
3099 
3100  const auto &RHS = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
3101  Depth + 1, FoundRoot);
3102  if (!RHS || LHS->Provider != RHS->Provider)
3103  return Result;
3104 
3105  unsigned StartBitRHS = BitWidth - ModAmt;
3106  Result = BitPart(LHS->Provider, BitWidth);
3107  for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3108  Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx];
3109  for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3110  Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS];
3111  return Result;
3112  }
3113  }
3114 
3115  // If we've already found a root input value then we're never going to merge
3116  // these back together.
3117  if (FoundRoot)
3118  return Result;
3119 
3120  // Okay, we got to something that isn't a shift, 'or', 'and', etc. This must
3121  // be the root input value to the bswap/bitreverse.
3122  FoundRoot = true;
3123  Result = BitPart(V, BitWidth);
3124  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3125  Result->Provenance[BitIdx] = BitIdx;
3126  return Result;
3127 }
3128 
3129 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
3130  unsigned BitWidth) {
3131  if (From % 8 != To % 8)
3132  return false;
3133  // Convert from bit indices to byte indices and check for a byte reversal.
3134  From >>= 3;
3135  To >>= 3;
3136  BitWidth >>= 3;
3137  return From == BitWidth - To - 1;
3138 }
3139 
3140 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
3141  unsigned BitWidth) {
3142  return From == BitWidth - To - 1;
3143 }
3144 
3146  Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
3147  SmallVectorImpl<Instruction *> &InsertedInsts) {
3148  if (!match(I, m_Or(m_Value(), m_Value())) &&
3149  !match(I, m_FShl(m_Value(), m_Value(), m_Value())) &&
3150  !match(I, m_FShr(m_Value(), m_Value(), m_Value())))
3151  return false;
3152  if (!MatchBSwaps && !MatchBitReversals)
3153  return false;
3154  Type *ITy = I->getType();
3155  if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() > 128)
3156  return false; // Can't do integer/elements > 128 bits.
3157 
3158  // Try to find all the pieces corresponding to the bswap.
3159  bool FoundRoot = false;
3160  std::map<Value *, Optional<BitPart>> BPS;
3161  const auto &Res =
3162  collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0, FoundRoot);
3163  if (!Res)
3164  return false;
3165  ArrayRef<int8_t> BitProvenance = Res->Provenance;
3166  assert(all_of(BitProvenance,
3167  [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) &&
3168  "Illegal bit provenance index");
3169 
3170  // If the upper bits are zero, then attempt to perform as a truncated op.
3171  Type *DemandedTy = ITy;
3172  if (BitProvenance.back() == BitPart::Unset) {
3173  while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset)
3174  BitProvenance = BitProvenance.drop_back();
3175  if (BitProvenance.empty())
3176  return false; // TODO - handle null value?
3177  DemandedTy = Type::getIntNTy(I->getContext(), BitProvenance.size());
3178  if (auto *IVecTy = dyn_cast<VectorType>(ITy))
3179  DemandedTy = VectorType::get(DemandedTy, IVecTy);
3180  }
3181 
3182  // Check BitProvenance hasn't found a source larger than the result type.
3183  unsigned DemandedBW = DemandedTy->getScalarSizeInBits();
3184  if (DemandedBW > ITy->getScalarSizeInBits())
3185  return false;
3186 
3187  // Now, is the bit permutation correct for a bswap or a bitreverse? We can
3188  // only byteswap values with an even number of bytes.
3189  APInt DemandedMask = APInt::getAllOnes(DemandedBW);
3190  bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
3191  bool OKForBitReverse = MatchBitReversals;
3192  for (unsigned BitIdx = 0;
3193  (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
3194  if (BitProvenance[BitIdx] == BitPart::Unset) {
3195  DemandedMask.clearBit(BitIdx);
3196  continue;
3197  }
3198  OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[BitIdx], BitIdx,
3199  DemandedBW);
3200  OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[BitIdx],
3201  BitIdx, DemandedBW);
3202  }
3203 
3204  Intrinsic::ID Intrin;
3205  if (OKForBSwap)
3206  Intrin = Intrinsic::bswap;
3207  else if (OKForBitReverse)
3208  Intrin = Intrinsic::bitreverse;
3209  else
3210  return false;
3211 
3212  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
3213  Value *Provider = Res->Provider;
3214 
3215  // We may need to truncate the provider.
3216  if (DemandedTy != Provider->getType()) {
3217  auto *Trunc =
3218  CastInst::CreateIntegerCast(Provider, DemandedTy, false, "trunc", I);
3219  InsertedInsts.push_back(Trunc);
3220  Provider = Trunc;
3221  }
3222 
3223  Instruction *Result = CallInst::Create(F, Provider, "rev", I);
3224  InsertedInsts.push_back(Result);
3225 
3226  if (!DemandedMask.isAllOnes()) {
3227  auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
3228  Result = BinaryOperator::Create(Instruction::And, Result, Mask, "mask", I);
3229  InsertedInsts.push_back(Result);
3230  }
3231 
3232  // We may need to zeroextend back to the result type.
3233  if (ITy != Result->getType()) {
3234  auto *ExtInst = CastInst::CreateIntegerCast(Result, ITy, false, "zext", I);
3235  InsertedInsts.push_back(ExtInst);
3236  }
3237 
3238  return true;
3239 }
3240 
3241 // CodeGen has special handling for some string functions that may replace
3242 // them with target-specific intrinsics. Since that'd skip our interceptors
3243 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
3244 // we mark affected calls as NoBuiltin, which will disable optimization
3245 // in CodeGen.
3247  CallInst *CI, const TargetLibraryInfo *TLI) {
3248  Function *F = CI->getCalledFunction();
3249  LibFunc Func;
3250  if (F && !F->hasLocalLinkage() && F->hasName() &&
3251  TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
3252  !F->doesNotAccessMemory())
3253  CI->addFnAttr(Attribute::NoBuiltin);
3254 }
3255 
3256 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
3257  // We can't have a PHI with a metadata type.
3258  if (I->getOperand(OpIdx)->getType()->isMetadataTy())
3259  return false;
3260 
3261  // Early exit.
3262  if (!isa<Constant>(I->getOperand(OpIdx)))
3263  return true;
3264 
3265  switch (I->getOpcode()) {
3266  default:
3267  return true;
3268  case Instruction::Call:
3269  case Instruction::Invoke: {
3270  const auto &CB = cast<CallBase>(*I);
3271 
3272  // Can't handle inline asm. Skip it.
3273  if (CB.isInlineAsm())
3274  return false;
3275 
3276  // Constant bundle operands may need to retain their constant-ness for
3277  // correctness.
3278  if (CB.isBundleOperand(OpIdx))
3279  return false;
3280 
3281  if (OpIdx < CB.arg_size()) {
3282  // Some variadic intrinsics require constants in the variadic arguments,
3283  // which currently aren't markable as immarg.
3284  if (isa<IntrinsicInst>(CB) &&
3285  OpIdx >= CB.getFunctionType()->getNumParams()) {
3286  // This is known to be OK for stackmap.
3287  return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
3288  }
3289 
3290  // gcroot is a special case, since it requires a constant argument which
3291  // isn't also required to be a simple ConstantInt.
3292  if (CB.getIntrinsicID() == Intrinsic::gcroot)
3293  return false;
3294 
3295  // Some intrinsic operands are required to be immediates.
3296  return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
3297  }
3298 
3299  // It is never allowed to replace the call argument to an intrinsic, but it
3300  // may be possible for a call.
3301  return !isa<IntrinsicInst>(CB);
3302  }
3303  case Instruction::ShuffleVector:
3304  // Shufflevector masks are constant.
3305  return OpIdx != 2;
3306  case Instruction::Switch:
3307  case Instruction::ExtractValue:
3308  // All operands apart from the first are constant.
3309  return OpIdx == 0;
3310  case Instruction::InsertValue:
3311  // All operands apart from the first and the second are constant.
3312  return OpIdx < 2;
3313  case Instruction::Alloca:
3314  // Static allocas (constant size in the entry block) are handled by
3315  // prologue/epilogue insertion so they're free anyway. We definitely don't
3316  // want to make them non-constant.
3317  return !cast<AllocaInst>(I)->isStaticAlloca();
3318  case Instruction::GetElementPtr:
3319  if (OpIdx == 0)
3320  return true;
3322  for (auto E = std::next(It, OpIdx); It != E; ++It)
3323  if (It.isStruct())
3324  return false;
3325  return true;
3326  }
3327 }
3328 
3330  // First: Check if it's a constant
3331  if (Constant *C = dyn_cast<Constant>(Condition))
3332  return ConstantExpr::getNot(C);
3333 
3334  // Second: If the condition is already inverted, return the original value
3335  Value *NotCondition;
3336  if (match(Condition, m_Not(m_Value(NotCondition))))
3337  return NotCondition;
3338 
3339  BasicBlock *Parent = nullptr;
3340  Instruction *Inst = dyn_cast<Instruction>(Condition);
3341  if (Inst)
3342  Parent = Inst->getParent();
3343  else if (Argument *Arg = dyn_cast<Argument>(Condition))
3344  Parent = &Arg->getParent()->getEntryBlock();
3345  assert(Parent && "Unsupported condition to invert");
3346 
3347  // Third: Check all the users for an invert
3348  for (User *U : Condition->users())
3349  if (Instruction *I = dyn_cast<Instruction>(U))
3350  if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
3351  return I;
3352 
3353  // Last option: Create a new instruction
3354  auto *Inverted =
3355  BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv");
3356  if (Inst && !isa<PHINode>(Inst))
3357  Inverted->insertAfter(Inst);
3358  else
3359  Inverted->insertBefore(&*Parent->getFirstInsertionPt());
3360  return Inverted;
3361 }
3362 
3364  // Note: We explicitly check for attributes rather than using cover functions
3365  // because some of the cover functions include the logic being implemented.
3366 
3367  bool Changed = false;
3368  // readnone + not convergent implies nosync
3369  if (!F.hasFnAttribute(Attribute::NoSync) &&
3370  F.doesNotAccessMemory() && !F.isConvergent()) {
3371  F.setNoSync();
3372  Changed = true;
3373  }
3374 
3375  // readonly implies nofree
3376  if (!F.hasFnAttribute(Attribute::NoFree) && F.onlyReadsMemory()) {
3377  F.setDoesNotFreeMemory();
3378  Changed = true;
3379  }
3380 
3381  // willreturn implies mustprogress
3382  if (!F.hasFnAttribute(Attribute::MustProgress) && F.willReturn()) {
3383  F.setMustProgress();
3384  Changed = true;
3385  }
3386 
3387  // TODO: There are a bunch of cases of restrictive memory effects we
3388  // can infer by inspecting arguments of argmemonly-ish functions.
3389 
3390  return Changed;
3391 }
llvm::DIExpression::prepend
static DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...
Definition: DebugInfoMetadata.cpp:1453
i
i
Definition: README.txt:29
llvm::InvokeInst::getNormalDest
BasicBlock * getNormalDest() const
Definition: Instructions.h:3943
llvm::hasNItemsOrLess
bool hasNItemsOrLess(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;})
Returns true if the sequence [Begin, End) has N or less items.
Definition: STLExtras.h:2162
llvm::invertCondition
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3329
llvm::DbgVariableIntrinsic::getExpression
DIExpression * getExpression() const
Definition: IntrinsicInst.h:262
llvm::RecursivelyDeleteTriviallyDeadInstructions
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:518
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:308
llvm::PatternMatch::m_FShr
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2 >::Ty m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
Definition: PatternMatch.h:2200
selectIncomingValueForBlock
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:913
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4709
llvm::CatchSwitchInst::Create
static CatchSwitchInst * Create(Value *ParentPad, BasicBlock *UnwindDest, unsigned NumHandlers, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4355
llvm::ArrayRef::drop_back
ArrayRef< T > drop_back(size_t N=1) const
Drop the last N elements of the array.
Definition: ArrayRef.h:209
llvm::combineMetadata
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2511
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DbgDeclareInst::getAddress
Value * getAddress() const
Definition: IntrinsicInst.h:315
llvm::CallBase::getOperandBundlesAsDefs
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Definition: Instructions.cpp:397
llvm::InvokeInst::Create
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3855
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::ConvertDebugDeclareToDebugValue
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
Definition: Local.cpp:1441
llvm::DIExpression::getNumLocationOperands
uint64_t getNumLocationOperands() const
Return the number of unique location operands referred to (via DW_OP_LLVM_arg) in this expression; th...
Definition: DebugInfoMetadata.cpp:1686
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:65
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::reserve
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
Definition: DenseSet.h:90
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:178
llvm::ConstantExpr::getNot
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2619
Optional.h
ValueMapper.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::generic_gep_type_iterator
Definition: GetElementPtrTypeIterator.h:31
llvm::Intrinsic::getDeclaration
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:1421
Metadata.h
replaceOneDbgValueForAlloca
static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress, DIBuilder &Builder, int Offset)
Definition: Local.cpp:1694
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:223
getHashValueImpl
static unsigned getHashValueImpl(SimpleValue Val)
Definition: EarlyCSE.cpp:213
llvm::DIBuilder
Definition: DIBuilder.h:41
DebugInfoMetadata.h
llvm::ValueMap::end
iterator end()
Definition: ValueMap.h:136
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::Instruction::getNextNonDebugInstruction
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
Definition: Instruction.cpp:766
llvm::TypeSize::getFixedSize
ScalarTy getFixedSize() const
Definition: TypeSize.h:444
T
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:60
llvm::callsGCLeafFunction
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
Definition: Local.cpp:2739
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2895
tryEnforceAlignment
static Align tryEnforceAlignment(Value *V, Align PrefAlign, const DataLayout &DL)
If the specified pointer points to an object that we control, try to modify the object's alignment to...
Definition: Local.cpp:1303
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5256
llvm::Instruction::getAllMetadataOtherThanDebugLoc
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:294
GetElementPtrTypeIterator.h
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector< uint32_t, 8 >
Statistic.h
llvm::pred_size
unsigned pred_size(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:32
llvm::replaceNonLocalUsesWith
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:2706
areAllUsesEqual
static bool areAllUsesEqual(Instruction *I)
areAllUsesEqual - Check whether the uses of a value are all the same.
Definition: Local.cpp:609
llvm::APInt::getSExtValue
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1478
llvm::Value::hasName
bool hasName() const
Definition: Value.h:261
ErrorHandling.h
llvm::PatternMatch::m_CombineOr
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:218
gatherIncomingValuesToPhi
static void gatherIncomingValuesToPhi(PHINode *PN, IncomingValueMap &IncomingValues)
Create a map from block to value for the operands of a given phi.
Definition: Local.cpp:938
llvm::IRBuilder<>
DomTreeUpdater.h
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::findDbgUsers
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: DebugInfo.cpp:101
llvm::PHINode::removeIncomingValue
Value * removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty=true)
Remove an incoming value.
Definition: Instructions.cpp:114
getIntrinsicID
static unsigned getIntrinsicID(const SDNode *N)
Definition: AArch64ISelLowering.cpp:5820
llvm::dropDebugUsers
void dropDebugUsers(Instruction &I)
Remove the debug intrinsic instructions for the given instruction.
Definition: Local.cpp:2811
llvm::DeleteDeadBlocks
void DeleteDeadBlocks(ArrayRef< BasicBlock * > BBs, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified blocks from BB.
Definition: BasicBlockUtils.cpp:99
ValueTracking.h
llvm::isAssumeWithEmptyBundle
bool isAssumeWithEmptyBundle(AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
Definition: AssumeBundleQueries.cpp:125
Local.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:83
llvm::MemorySSAUpdater::removeBlocks
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
Definition: MemorySSAUpdater.cpp:1372
llvm::DbgVariableIntrinsic::replaceVariableLocationOp
void replaceVariableLocationOp(Value *OldValue, Value *NewValue)
Definition: IntrinsicInst.cpp:113
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::PatternMatch::m_BitReverse
m_Intrinsic_Ty< Opnd0 >::Ty m_BitReverse(const Opnd0 &Op0)
Definition: PatternMatch.h:2161
APInt.h
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1557
llvm::DenseMapIterator
Definition: DenseMap.h:57
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::removeUnreachableBlocks
bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function's entry.
Definition: Local.cpp:2474
Module.h
llvm::BasicBlock::eraseFromParent
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:132
llvm::DebugLoc::getInlinedAt
DILocation * getInlinedAt() const
Definition: DebugLoc.cpp:39
MemoryBuiltins.h
llvm::getOrEnforceKnownAlignment
Align getOrEnforceKnownAlignment(Value *V, MaybeAlign 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:1345
llvm::CallBase::getAttributes
AttributeList getAttributes() const
Return the parameter attributes for this call.
Definition: InstrTypes.h:1474
getDwarfOpForBinOp
uint64_t getDwarfOpForBinOp(Instruction::BinaryOps Opcode)
Definition: Local.cpp:1831
llvm::CallBase::getFunctionType
FunctionType * getFunctionType() const
Definition: InstrTypes.h:1254
llvm::BasicBlockEdge
Definition: Dominators.h:98
llvm::User::value_op_begin
value_op_iterator value_op_begin()
Definition: User.h:260
llvm::DominatorTreeBase< BasicBlock, false >::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
EHPersonalities.h
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::DbgVariableIntrinsic::getVariable
DILocalVariable * getVariable() const
Definition: IntrinsicInst.h:258
llvm::Optional
Definition: APInt.h:33
llvm::DenseMapBase::count
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:145
llvm::mapped_iterator
Definition: STLExtras.h:286
GlobalObject.h
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet< Instruction *, 4 >
llvm::FindDbgAddrUses
TinyPtrVector< DbgVariableIntrinsic * > FindDbgAddrUses(Value *V)
Finds all intrinsics declaring local variables as living in the memory that 'V' points to.
Definition: DebugInfo.cpp:45
Hashing.h
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::Instruction::copyMetadata
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
Definition: Instruction.cpp:867
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:285
llvm::CastInst::CreateIntegerCast
static CastInst * CreateIntegerCast(Value *S, Type *Ty, bool isSigned, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt, BitCast, or Trunc for int -> int casts.
Definition: Instructions.cpp:3409
BitPartRecursionMaxDepth
static const unsigned BitPartRecursionMaxDepth
Definition: Local.cpp:112
llvm::changeToCall
CallInst * changeToCall(InvokeInst *II, DomTreeUpdater *DTU=nullptr)
This function converts the specified invoek into a normall call.
Definition: Local.cpp:2176
STLExtras.h
llvm::DIExpression
DWARF expression.
Definition: DebugInfoMetadata.h:2558
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LoadInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:261
llvm::getConstantRangeFromMetadata
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Definition: ConstantRange.cpp:1800
llvm::gep_type_begin
gep_type_iterator gep_type_begin(const User *GEP)
Definition: GetElementPtrTypeIterator.h:123
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2289
llvm::succ_empty
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
isSentinel
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
Definition: DWARFAcceleratorTable.cpp:424
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2798
llvm::count_if
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1707
ConstantFolding.h
llvm::LinearPolySize::isScalable
bool isScalable() const
Returns whether the size is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:298
Use.h
llvm::combineMetadataForCSE
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2592
endif
__FakeVCSRevision h endif() endif() set(generated_files "$
Definition: CMakeLists.txt:16
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:239
llvm::isEqual
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
Definition: GCNRegPressure.cpp:55
llvm::DbgVariableIntrinsic::getVariableLocationOp
Value * getVariableLocationOp(unsigned OpIdx) const
Definition: IntrinsicInst.cpp:91
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:159
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1400
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::APInt::countPopulation
unsigned countPopulation() const
Count the number of bits set.
Definition: APInt.h:1571
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1428
llvm::RecursivelyDeleteDeadPHINode
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=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:628
KnownBits.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::KnownBits::countMinTrailingZeros
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:233
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1298
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
Instruction.h
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1171
llvm::ValueMap::size
size_type size() const
Definition: ValueMap.h:141
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Type::isArrayTy
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:220
rewriteDebugUsers
static bool rewriteDebugUsers(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT, function_ref< DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr)
Point debug users of From to To using exprs given by RewriteExpr, possibly moving/undefing users to p...
Definition: Local.cpp:1952
valueCoversEntireFragment
static bool valueCoversEntireFragment(Type *ValTy, DbgVariableIntrinsic *DII)
Check if the alloc size of ValTy is large enough to cover the variable (or fragment of the variable) ...
Definition: Local.cpp:1400
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1590
llvm::DIExpression::appendOpsToArg
static DIExpression * appendOpsToArg(const DIExpression *Expr, ArrayRef< uint64_t > Ops, unsigned ArgNo, bool StackValue=false)
Create a copy of Expr by appending the given list of Ops to each instance of the operand DW_OP_LLVM_a...
Definition: DebugInfoMetadata.cpp:1469
llvm::ArrayRef::back
const T & back() const
back - Get the last element.
Definition: ArrayRef.h:173
llvm::SimplifyInstructionsInBlock
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:708
llvm::Instruction::extractProfTotalWeight
bool extractProfTotalWeight(uint64_t &TotalVal) const
Retrieve total raw weight values of a branch.
Definition: Metadata.cpp:1497
replaceUndefValuesInPhi
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:954
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2795
llvm::DomTreeUpdater::isBBPendingDeletion
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
Definition: DomTreeUpdater.cpp:167
llvm::DbgValueInst
This represents the llvm.dbg.value instruction.
Definition: IntrinsicInst.h:352
DbgValReplacement
Optional< DIExpression * > DbgValReplacement
A replacement for a dbg.value expression.
Definition: Local.cpp:1947
llvm::AllocaInst::getAllocatedType
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:115
llvm::PatternMatch::m_FShl
m_Intrinsic_Ty< Opnd0, Opnd1, Opnd2 >::Ty m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
Definition: PatternMatch.h:2194
llvm::DILocalVariable
Local variable.
Definition: DebugInfoMetadata.h:3058
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
llvm::LibFunc
LibFunc
Definition: TargetLibraryInfo.h:35
llvm::DbgVariableIntrinsic::isAddressOfVariable
bool isAddressOfVariable() const
Does this describe the address of a local variable.
Definition: IntrinsicInst.h:236
CanPropagatePredecessorsForPHIs
static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ)
Return true if we can fold BB, an almost-empty BB ending in an unconditional branch to Succ,...
Definition: Local.cpp:841
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::ConstantExpr::getIntToPtr
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2183
llvm::CleanupReturnInst::Create
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4682
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1396
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1478
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
llvm::canReplaceOperandWithVariable
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:3256
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::MDBuilder::createBranchWeights
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
Definition: MDBuilder.cpp:37
llvm::CallInst::Create
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:1517
llvm::Instruction::isIdenticalToWhenDefined
bool isIdenticalToWhenDefined(const Instruction *I) const
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
Definition: Instruction.cpp:533
AssumeBundleQueries.h
llvm::ConstantExpr::getPtrToInt
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2169
llvm::DomTreeUpdater::recalculate
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
Definition: DomTreeUpdater.cpp:121
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
TargetLibraryInfo.h
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:232
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
DenseSet.h
llvm::BasicBlock::getFirstInsertionPt
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:246
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1629
llvm::inferAttributesFromOthers
bool inferAttributesFromOthers(Function &F)
If we can infer one attribute from another on the declaration of a function, explicitly materialize t...
Definition: Local.cpp:3363
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::DbgVariableIntrinsic::setExpression
void setExpression(DIExpression *NewExpr)
Definition: IntrinsicInst.h:222
llvm::removeAllNonTerminatorAndEHPadInstructions
std::pair< unsigned, unsigned > removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than its terminator and any present EH pad instructi...
Definition: Local.cpp:2087
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2884
llvm::TargetLibraryInfo::getLibFunc
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
Definition: TargetLibraryInfo.h:294
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:392
llvm::Type::isTokenTy
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:193
llvm::Instruction
Definition: Instruction.h:42
replaceDominatedUsesWith
static unsigned replaceDominatedUsesWith(Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates)
Definition: Local.cpp:2689
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:189
llvm::APInt::isAllOnes
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:347
bitTransformIsCorrectForBSwap
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:3129
llvm::CallBase::addFnAttr
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
Definition: InstrTypes.h:1506
MDBuilder.h
isStructure
static bool isStructure(AllocaInst *AI)
Determine whether this alloca is a structure.
Definition: Local.cpp:1534
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1466
llvm::salvageDebugInfo
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1334
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::copyRangeMetadata
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:2793
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1708
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
llvm::ConstantInt::get
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:879
DebugLoc.h
SmallPtrSet.h
llvm::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:670
Align
uint64_t Align
Definition: ELFObjHandler.cpp:81
PatternMatch.h
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:209
bitTransformIsCorrectForBitReverse
static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:3140
llvm::RemoveRedundantDbgInstrs
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
Definition: BasicBlockUtils.cpp:442
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::CallBase::getCallingConv
CallingConv::ID getCallingConv() const
Definition: InstrTypes.h:1455
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::Value::MaxAlignmentExponent
static constexpr unsigned MaxAlignmentExponent
The maximum alignment for instructions.
Definition: Value.h:792
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2791
llvm::DbgVariableIntrinsic::getNumVariableLocationOps
unsigned getNumVariableLocationOps() const
Definition: IntrinsicInst.h:226
llvm::None
const NoneType None
Definition: None.h:24
llvm::DomTreeUpdater::hasDomTree
bool hasDomTree() const
Returns true if it holds a DominatorTree.
Definition: DomTreeUpdater.h:57
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::DIBasicType::Signedness::Signed
@ Signed
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:271
CFG.h
llvm::getFreedOperand
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
Definition: MemoryBuiltins.cpp:576
llvm::LocalAsMetadata::getIfExists
static LocalAsMetadata * getIfExists(Value *Local)
Definition: Metadata.h:450
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3811
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::DIExpression::append
static DIExpression * append(const DIExpression *Expr, ArrayRef< uint64_t > Ops)
Append the opcodes Ops to DIExpr.
Definition: DebugInfoMetadata.cpp:1548
llvm::BasicBlock::isEntryBlock
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:396
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:196
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1292
llvm::SmallPtrSetImplBase::empty
bool empty() const
Definition: SmallPtrSet.h:92
llvm::isMathLibCallNoop
bool isMathLibCallNoop(const CallBase *Call, const TargetLibraryInfo *TLI)
Check whether the given call has no side-effects.
Definition: ConstantFolding.cpp:3236
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::wouldInstructionBeTriviallyDead
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:414
llvm::copyNonnullMetadata
void copyNonnullMetadata(const LoadInst &OldLI, MDNode *N, LoadInst &NewLI)
Copy a nonnull metadata node to a new load instruction.
Definition: Local.cpp:2768
llvm::copyMetadataForLoad
void copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source)
Copy the metadata from the source instruction to the destination (the replacement for the source inst...
Definition: Local.cpp:2605
VectorUtils.h
llvm::BasicBlock::hasAddressTaken
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:458
BasicBlock.h
llvm::cl::opt< bool >
llvm::removeUnwindEdge
void removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
Definition: Local.cpp:2435
llvm::DbgVariableIntrinsic
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:153
llvm::TryToSimplifyUncondBranchFromEmptyBlock
bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is known to contain an unconditional branch, and contains no instructions other than PHI nodes,...
Definition: Local.cpp:1053
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:537
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
VI
@ VI
Definition: SIInstrInfo.cpp:7877
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
LiveDebugValues::DbgValue
Class recording the (high level) value of a variable.
Definition: InstrRefBasedImpl.h:435
llvm::MDNode::intersect
static MDNode * intersect(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1020
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:77
llvm::MapVector::find
iterator find(const KeyT &Key)
Definition: MapVector.h:148
uint64_t
llvm::MemorySSAUpdater
Definition: MemorySSAUpdater.h:54
llvm::DbgDeclareInst
This represents the llvm.dbg.declare instruction.
Definition: IntrinsicInst.h:313
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1610
llvm::MemorySSAUpdater::changeToUnreachable
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
Definition: MemorySSAUpdater.cpp:1408
llvm::DbgLabelInst
This represents the llvm.dbg.label instruction.
Definition: IntrinsicInst.h:375
llvm::Type::isIntOrPtrTy
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
Definition: Type.h:211
llvm::canSimplifyInvokeNoUnwind
bool canSimplifyInvokeNoUnwind(const Function *F)
Definition: EHPersonalities.cpp:77
llvm::ConstantPointerNull::get
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1694
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2849
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1099
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::Instruction::moveAfter
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:100
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:54
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3190
llvm::DenseMap
Definition: DenseMap.h:714
DebugInfo.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::succ_begin
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:99
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:929
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:439
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:596
DIBuilder.h
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1093
llvm::insertDebugValuesForPHIs
void insertDebugValuesForPHIs(BasicBlock *BB, SmallVectorImpl< PHINode * > &InsertedPHIs)
Propagate dbg.value intrinsics through the newly inserted PHIs.
Definition: Local.cpp:1614
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1673
llvm::findDbgValues
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V)
Finds the llvm.dbg.value intrinsics describing a value.
Definition: DebugInfo.cpp:75
llvm::simplifyInstruction
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
Definition: InstructionSimplify.cpp:6454
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:351
llvm::MDNode::getMostGenericTBAA
static MDNode * getMostGenericTBAA(MDNode *A, MDNode *B)
Definition: TypeBasedAliasAnalysis.cpp:478
llvm::hoistAllInstructionsInto
void hoistAllInstructionsInto(BasicBlock *DomBlock, Instruction *InsertPt, BasicBlock *BB)
Hoist all of the instructions in the IfBlock to the dominant block DomBlock, by moving its instructio...
Definition: Local.cpp:2818
llvm::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:52
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:222
llvm::detail::DenseSetEmpty
Definition: DenseSet.h:30
llvm::MDNode::getMostGenericAlignmentOrDereferenceable
static MDNode * getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1185
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
PHICSENumPHISmallSize
static cl::opt< unsigned > PHICSENumPHISmallSize("phicse-num-phi-smallsize", cl::init(32), cl::Hidden, cl::desc("When the basic block contains not more than this number of PHI nodes, " "perform a (faster!) exhaustive search instead of set-driven one."))
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::salvageDebugInfoForDbgValues
void salvageDebugInfoForDbgValues(Instruction &I, ArrayRef< DbgVariableIntrinsic * > Insns)
Implementation of salvageDebugInfo, applying only to instructions in Insns, rather than all debug use...
Definition: Local.cpp:1734
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::wouldInstructionBeTriviallyDeadOnUnusedPaths
bool wouldInstructionBeTriviallyDeadOnUnusedPaths(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction has no side effects on any paths other than whe...
Definition: Local.cpp:402
llvm::ValueMap::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: ValueMap.h:173
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
llvm::LinearPolySize< TypeSize >::isKnownGE
static bool isKnownGE(const LinearPolySize &LHS, const LinearPolySize &RHS)
Definition: TypeSize.h:346
llvm::TargetLibraryInfo::has
bool has(LibFunc F) const
Tests whether a library function is available.
Definition: TargetLibraryInfo.h:328
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
NDEBUG
#define NDEBUG
Definition: regutils.h:48
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
llvm::replaceDominatedUsesWith
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
Definition: Local.cpp:2721
llvm::replaceAllDbgUsesWith
bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)
Point debug users of From to To or salvage them.
Definition: Local.cpp:2032
llvm::changeToInvokeAndSplitBasicBlock
BasicBlock * changeToInvokeAndSplitBasicBlock(CallInst *CI, BasicBlock *UnwindEdge, DomTreeUpdater *DTU=nullptr)
Convert the CallInst to InvokeInst with the specified unwind edge basic block.
Definition: Local.cpp:2196
llvm::PHINode::block_begin
block_iterator block_begin()
Definition: Instructions.h:2761
llvm::detail::DenseSetPair
Definition: DenseSet.h:34
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::DIVariable::getSignedness
Optional< DIBasicType::Signedness > getSignedness() const
Return the signedness of this variable's type, or None if this type is neither signed nor unsigned.
Definition: DebugInfoMetadata.h:2514
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::NVPTX::PTXLdStInstCode::FromType
FromType
Definition: NVPTX.h:115
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
getSalvageOpsForGEP
Value * getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1805
llvm::intersectAccessGroups
MDNode * intersectAccessGroups(const Instruction *Inst1, const Instruction *Inst2)
Compute the access-group list of access groups that Inst1 and Inst2 are both in.
Definition: VectorUtils.cpp:793
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:849
llvm::dwarf::DW_OP_LLVM_arg
@ DW_OP_LLVM_arg
Only used in LLVM metadata.
Definition: Dwarf.h:148
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:98
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:395
llvm::BinaryOperator
Definition: InstrTypes.h:188
None.h
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::pop_back_val
T pop_back_val()
Definition: SetVector.h:232
llvm::MapVector::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:118
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1597
llvm::BasicBlock::moveAfter
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:141
DataLayout.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
Dwarf.h
llvm::PatternMatch::m_Undef
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:136
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:847
uint32_t
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
llvm::MDNode::getMostGenericAliasScope
static MDNode * getMostGenericAliasScope(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1033
PhiHasDebugValue
static bool PhiHasDebugValue(DILocalVariable *DIVar, DIExpression *DIExpr, PHINode *APN)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
Definition: Local.cpp:1375
llvm::AllocaInst::isArrayAllocation
bool isArrayAllocation() const
Return true if there is an allocation size parameter to the allocation instruction that is not 1.
Definition: Instructions.cpp:1401
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
ConstantRange.h
llvm::recognizeBSwapOrBitReverseIdiom
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
Definition: Local.cpp:3145
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
isEqualImpl
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
Definition: EarlyCSE.cpp:331
llvm::DbgVariableIntrinsic::getFragmentSizeInBits
Optional< uint64_t > getFragmentSizeInBits() const
Get the size (in bits) of the variable, or fragment of the variable that is described.
Definition: IntrinsicInst.cpp:169
llvm::maybeMarkSanitizerLibraryCallNoBuiltin
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:3246
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::ValueMap< const Value *, WeakTrackingVH >
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
ValueHandle.h
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
isBitCastSemanticsPreserving
static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy, Type *ToTy)
Check if a bitcast between a value of type FromTy to type ToTy would losslessly preserve the bits and...
Definition: Local.cpp:2014
isArray
static bool isArray(AllocaInst *AI)
Determine whether this alloca is either a VLA or an array.
Definition: Local.cpp:1528
llvm::APInt::clearBit
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1357
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:685
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::replaceDbgValueForAlloca
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:1717
llvm::MapVector::end
iterator end()
Definition: MapVector.h:72
Argument.h
llvm::PHINode::block_end
block_iterator block_end()
Definition: Instructions.h:2769
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:186
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
llvm::EliminateDuplicatePHINodes
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
Definition: Local.cpp:1286
Attributes.h
llvm::MapVector::empty
bool empty() const
Definition: MapVector.h:80
llvm::User::value_op_end
value_op_iterator value_op_end()
Definition: User.h:263
Constant.h
llvm::DIExpression::appendOffset
static void appendOffset(SmallVectorImpl< uint64_t > &Ops, int64_t Offset)
Append Ops with operations to apply the Offset.
Definition: DebugInfoMetadata.cpp:1382
llvm::ConstantFoldTerminator
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
Definition: Local.cpp:125
llvm::Instruction::dropUnknownNonDebugMetadata
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1402
llvm::DIExpression::appendExt
static DIExpression * appendExt(const DIExpression *Expr, unsigned FromSize, unsigned ToSize, bool Signed)
Append a zero- or sign-extension to Expr.
Definition: DebugInfoMetadata.cpp:1731
llvm::KnownBits
Definition: KnownBits.h:23
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:243
llvm::Value::user_iterator
user_iterator_impl< User > user_iterator
Definition: Value.h:390
redirectValuesFromPredecessorsToPhi
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:998
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
CanMergeValues
static bool CanMergeValues(Value *First, Value *Second)
Return true if we can choose one of these values to use in place of the other.
Definition: Local.cpp:833
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
collectBitParts
static const Optional< BitPart > & collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals, std::map< Value *, Optional< BitPart >> &BPS, int Depth, bool &FoundRoot)
Analyze the specified subexpression and see if it is capable of providing pieces of a bswap or bitrev...
Definition: Local.cpp:2909
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2625
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:202
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::TypeSize
Definition: TypeSize.h:435
llvm::salvageDebugInfoImpl
Value * salvageDebugInfoImpl(Instruction &I, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Ops, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1900
Casting.h
markAliveBlocks
static bool markAliveBlocks(Function &F, SmallPtrSetImpl< BasicBlock * > &Reachable, DomTreeUpdater *DTU=nullptr)
Definition: Local.cpp:2239
llvm::isRemovableAlloc
bool isRemovableAlloc(const CallBase *V, const TargetLibraryInfo *TLI)
Return true if this is a call to an allocation function that does not have side effects that we are r...
Definition: MemoryBuiltins.cpp:355
Function.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::PatternMatch::m_BSwap
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
Definition: PatternMatch.h:2166
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::ValueMap::find
iterator find(const KeyT &Val)
Definition: ValueMap.h:156
llvm::Instruction::isEHPad
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:649
llvm::ConstantRange::contains
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Definition: ConstantRange.cpp:449
llvm::DIExpression::getExtOps
static ExtOps getExtOps(unsigned FromSize, unsigned ToSize, bool Signed)
Returns the ops for a zero- or sign-extension in a DIExpression.
Definition: DebugInfoMetadata.cpp:1723
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::SmallSet::insert
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:178
llvm::CallBase::getCalledOperand
Value * getCalledOperand() const
Definition: InstrTypes.h:1389
llvm::LowerDbgDeclare
bool LowerDbgDeclare(Function &F)
Lowers llvm.dbg.declare intrinsics into appropriate set of llvm.dbg.value intrinsics.
Definition: Local.cpp:1540
llvm::replaceDbgUsesWithUndef
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in @llvm.dbg intrinsics with undef.
Definition: Local.cpp:595
EliminateDuplicatePHINodesSetBasedImpl
static bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB)
Definition: Local.cpp:1204
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::PatternMatch::m_LogicalShift
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
Definition: PatternMatch.h:1311
llvm::MDBuilder
Definition: MDBuilder.h:36
llvm::CatchPadInst
Definition: Instructions.h:4531
getSalvageOpsForBinOp
Value * getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1861
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:773
llvm::pred_begin
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:109
llvm::changeToUnreachable
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2111
llvm::BasicBlock::getInstList
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:373
llvm::MetadataAsValue::getIfExists
static MetadataAsValue * getIfExists(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:111
Instructions.h
llvm::MDNode::getMostGenericRange
static MDNode * getMostGenericRange(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1113
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:217
SmallVector.h
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:354
User.h
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
llvm::SmallSet::size
size_type size() const
Definition: SmallSet.h:160
Dominators.h
llvm::MDNode::getMostGenericFPMath
static MDNode * getMostGenericFPMath(MDNode *A, MDNode *B)
Definition: Metadata.cpp:1065
llvm::MDBuilder::createRange
MDNode * createRange(const APInt &Lo, const APInt &Hi)
Return metadata describing the range [Lo, Hi).
Definition: MDBuilder.cpp:84
llvm::generic_gep_type_iterator::isStruct
bool isStruct() const
Definition: GetElementPtrTypeIterator.h:111
N
#define N
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
llvm::DbgVariableIntrinsic::location_ops
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
Definition: IntrinsicInst.cpp:74
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:660
llvm::BlockAddress::get
static BlockAddress * get(Function *F, BasicBlock *BB)
Return a BlockAddress for the specified function and basic block.
Definition: Constants.cpp:1746
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2815
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
Users
iv Induction Variable Users
Definition: IVUsers.cpp:48
llvm::BasicBlock::getFirstNonPHIOrDbg
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:216
llvm::PHINode
Definition: Instructions.h:2699
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::DIExpression::getNumElements
unsigned getNumElements() const
Definition: DebugInfoMetadata.h:2584
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:342
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
DenseMapInfo.h
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
llvm::DeleteDeadBlock
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Definition: BasicBlockUtils.cpp:94
DerivedTypes.h
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
EliminateDuplicatePHINodesNaiveImpl
static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB)
Definition: Local.cpp:1172
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4771
llvm::TargetLibraryInfo::hasOptimizedCodeGen
bool hasOptimizedCodeGen(LibFunc F) const
Tests if the function is both available and a candidate for optimized code generation.
Definition: TargetLibraryInfo.h:343
llvm::createCallMatchingInvoke
CallInst * createCallMatchingInvoke(InvokeInst *II)
Create a call that matches the invoke II in terms of arguments, attributes, debug information,...
Definition: Local.cpp:2150
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::takeVector
SmallVector< T, N > takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:66
llvm::patchReplacementInstruction
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition: Local.cpp:2656
llvm::KnownBits::getBitWidth
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
llvm::MergeBasicBlockIntoOnlyPred
void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
BB is a block with one predecessor and its predecessor is known to have one successor (BB!...
Definition: Local.cpp:748
llvm::fp::ebStrict
@ ebStrict
This corresponds to "fpexcept.strict".
Definition: FPEnv.h:41
LLVMContext.h
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:59
llvm::DebugLoc::getScope
MDNode * getScope() const
Definition: DebugLoc.cpp:34
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::cl::desc
Definition: CommandLine.h:412
simplifyAndDCEInstruction
static bool simplifyAndDCEInstruction(Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Local.cpp:650
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3134
raw_ostream.h
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1611
llvm::NullPointerIsDefined
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
Definition: Function.cpp:2049
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:650
llvm::BinaryOperator::Create
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
Definition: Instructions.cpp:2839
BasicBlockUtils.h
llvm::replaceDbgDeclare
bool replaceDbgDeclare(Value *Address, Value *NewAddress, DIBuilder &Builder, uint8_t DIExprFlags, int Offset)
Replaces llvm.dbg.declare instruction when the address it describes is replaced with a new value.
Definition: Local.cpp:1676
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:837
Value.h
llvm::InvokeInst::getUnwindDest
BasicBlock * getUnwindDest() const
Definition: Instructions.h:3946
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:250
llvm::RecursivelyDeleteTriviallyDeadInstructionsPermissive
bool RecursivelyDeleteTriviallyDeadInstructionsPermissive(SmallVectorImpl< WeakTrackingVH > &DeadInsts, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
Same functionality as RecursivelyDeleteTriviallyDeadInstructions, but allow instructions that are not...
Definition: Local.cpp:533
llvm::MCID::Terminator
@ Terminator
Definition: MCInstrDesc.h:157
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::VectorType::get
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:668
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
PHICSEDebugHash
static cl::opt< bool > PHICSEDebugHash("phicse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that PHINodes's hash " "function is well-behaved w.r.t. its isEqual predicate"))
getDebugValueLoc
static DebugLoc getDebugValueLoc(DbgVariableIntrinsic *DII, Instruction *Src)
Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted to a dbg....
Definition: Local.cpp:1430
llvm::Constant::destroyConstant
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:450
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1332
llvm::MemorySSAUpdater::removeMemoryAccess
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Definition: MemorySSAUpdater.cpp:1305
SetVector.h
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1459
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Type::getPrimitiveSizeInBits
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:164
llvm::SmallPtrSetImpl::insert
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:365
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:792
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1727