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