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