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  assert(ValueSize.isScalable() == FragmentSize->isScalable() &&
1417  "Both sizes should agree on the scalable flag.");
1418  return TypeSize::isKnownGE(ValueSize, *FragmentSize);
1419  }
1420  }
1421  }
1422  // Could not determine size of variable. Conservatively return false.
1423  return false;
1424 }
1425 
1426 /// Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted
1427 /// to a dbg.value. Because no machine insts can come from debug intrinsics,
1428 /// only the scope and inlinedAt is significant. Zero line numbers are used in
1429 /// case this DebugLoc leaks into any adjacent instructions.
1431  // Original dbg.declare must have a location.
1432  const DebugLoc &DeclareLoc = DII->getDebugLoc();
1433  MDNode *Scope = DeclareLoc.getScope();
1434  DILocation *InlinedAt = DeclareLoc.getInlinedAt();
1435  // Produce an unknown location with the correct scope / inlinedAt fields.
1436  return DILocation::get(DII->getContext(), 0, 0, Scope, InlinedAt);
1437 }
1438 
1439 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
1440 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1443  assert(DII->isAddressOfVariable());
1444  auto *DIVar = DII->getVariable();
1445  assert(DIVar && "Missing variable");
1446  auto *DIExpr = DII->getExpression();
1447  Value *DV = SI->getValueOperand();
1448 
1449  DebugLoc NewLoc = getDebugValueLoc(DII, SI);
1450 
1451  if (!valueCoversEntireFragment(DV->getType(), DII)) {
1452  // FIXME: If storing to a part of the variable described by the dbg.declare,
1453  // then we want to insert a dbg.value for the corresponding fragment.
1454  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1455  << *DII << '\n');
1456  // For now, when there is a store to parts of the variable (but we do not
1457  // know which part) we insert an dbg.value instrinsic to indicate that we
1458  // know nothing about the variable's content.
1459  DV = UndefValue::get(DV->getType());
1460  Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1461  return;
1462  }
1463 
1464  Builder.insertDbgValueIntrinsic(DV, DIVar, DIExpr, NewLoc, SI);
1465 }
1466 
1467 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1468 /// that has an associated llvm.dbg.declare or llvm.dbg.addr intrinsic.
1470  LoadInst *LI, DIBuilder &Builder) {
1471  auto *DIVar = DII->getVariable();
1472  auto *DIExpr = DII->getExpression();
1473  assert(DIVar && "Missing variable");
1474 
1475  if (!valueCoversEntireFragment(LI->getType(), DII)) {
1476  // FIXME: If only referring to a part of the variable described by the
1477  // dbg.declare, then we want to insert a dbg.value for the corresponding
1478  // fragment.
1479  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1480  << *DII << '\n');
1481  return;
1482  }
1483 
1484  DebugLoc NewLoc = getDebugValueLoc(DII, nullptr);
1485 
1486  // We are now tracking the loaded value instead of the address. In the
1487  // future if multi-location support is added to the IR, it might be
1488  // preferable to keep tracking both the loaded value and the original
1489  // address in case the alloca can not be elided.
1490  Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
1491  LI, DIVar, DIExpr, NewLoc, (Instruction *)nullptr);
1492  DbgValue->insertAfter(LI);
1493 }
1494 
1495 /// Inserts a llvm.dbg.value intrinsic after a phi that has an associated
1496 /// llvm.dbg.declare or llvm.dbg.addr intrinsic.
1498  PHINode *APN, DIBuilder &Builder) {
1499  auto *DIVar = DII->getVariable();
1500  auto *DIExpr = DII->getExpression();
1501  assert(DIVar && "Missing variable");
1502 
1503  if (PhiHasDebugValue(DIVar, DIExpr, APN))
1504  return;
1505 
1506  if (!valueCoversEntireFragment(APN->getType(), DII)) {
1507  // FIXME: If only referring to a part of the variable described by the
1508  // dbg.declare, then we want to insert a dbg.value for the corresponding
1509  // fragment.
1510  LLVM_DEBUG(dbgs() << "Failed to convert dbg.declare to dbg.value: "
1511  << *DII << '\n');
1512  return;
1513  }
1514 
1515  BasicBlock *BB = APN->getParent();
1516  auto InsertionPt = BB->getFirstInsertionPt();
1517 
1518  DebugLoc NewLoc = getDebugValueLoc(DII, nullptr);
1519 
1520  // The block may be a catchswitch block, which does not have a valid
1521  // insertion point.
1522  // FIXME: Insert dbg.value markers in the successors when appropriate.
1523  if (InsertionPt != BB->end())
1524  Builder.insertDbgValueIntrinsic(APN, DIVar, DIExpr, NewLoc, &*InsertionPt);
1525 }
1526 
1527 /// Determine whether this alloca is either a VLA or an array.
1528 static bool isArray(AllocaInst *AI) {
1529  return AI->isArrayAllocation() ||
1530  (AI->getAllocatedType() && AI->getAllocatedType()->isArrayTy());
1531 }
1532 
1533 /// Determine whether this alloca is a structure.
1534 static bool isStructure(AllocaInst *AI) {
1535  return AI->getAllocatedType() && AI->getAllocatedType()->isStructTy();
1536 }
1537 
1538 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1539 /// of llvm.dbg.value intrinsics.
1541  bool Changed = false;
1542  DIBuilder DIB(*F.getParent(), /*AllowUnresolved*/ false);
1544  for (auto &FI : F)
1545  for (Instruction &BI : FI)
1546  if (auto DDI = dyn_cast<DbgDeclareInst>(&BI))
1547  Dbgs.push_back(DDI);
1548 
1549  if (Dbgs.empty())
1550  return Changed;
1551 
1552  for (auto &I : Dbgs) {
1553  DbgDeclareInst *DDI = I;
1554  AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1555  // If this is an alloca for a scalar variable, insert a dbg.value
1556  // at each load and store to the alloca and erase the dbg.declare.
1557  // The dbg.values allow tracking a variable even if it is not
1558  // stored on the stack, while the dbg.declare can only describe
1559  // the stack slot (and at a lexical-scope granularity). Later
1560  // passes will attempt to elide the stack slot.
1561  if (!AI || isArray(AI) || isStructure(AI))
1562  continue;
1563 
1564  // A volatile load/store means that the alloca can't be elided anyway.
1565  if (llvm::any_of(AI->users(), [](User *U) -> bool {
1566  if (LoadInst *LI = dyn_cast<LoadInst>(U))
1567  return LI->isVolatile();
1568  if (StoreInst *SI = dyn_cast<StoreInst>(U))
1569  return SI->isVolatile();
1570  return false;
1571  }))
1572  continue;
1573 
1575  WorkList.push_back(AI);
1576  while (!WorkList.empty()) {
1577  const Value *V = WorkList.pop_back_val();
1578  for (auto &AIUse : V->uses()) {
1579  User *U = AIUse.getUser();
1580  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1581  if (AIUse.getOperandNo() == 1)
1583  } else if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1584  ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1585  } else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1586  // This is a call by-value or some other instruction that takes a
1587  // pointer to the variable. Insert a *value* intrinsic that describes
1588  // the variable by dereferencing the alloca.
1589  if (!CI->isLifetimeStartOrEnd()) {
1590  DebugLoc NewLoc = getDebugValueLoc(DDI, nullptr);
1591  auto *DerefExpr =
1592  DIExpression::append(DDI->getExpression(), dwarf::DW_OP_deref);
1593  DIB.insertDbgValueIntrinsic(AI, DDI->getVariable(), DerefExpr,
1594  NewLoc, CI);
1595  }
1596  } else if (BitCastInst *BI = dyn_cast<BitCastInst>(U)) {
1597  if (BI->getType()->isPointerTy())
1598  WorkList.push_back(BI);
1599  }
1600  }
1601  }
1602  DDI->eraseFromParent();
1603  Changed = true;
1604  }
1605 
1606  if (Changed)
1607  for (BasicBlock &BB : F)
1609 
1610  return Changed;
1611 }
1612 
1613 /// Propagate dbg.value intrinsics through the newly inserted PHIs.
1615  SmallVectorImpl<PHINode *> &InsertedPHIs) {
1616  assert(BB && "No BasicBlock to clone dbg.value(s) from.");
1617  if (InsertedPHIs.size() == 0)
1618  return;
1619 
1620  // Map existing PHI nodes to their dbg.values.
1621  ValueToValueMapTy DbgValueMap;
1622  for (auto &I : *BB) {
1623  if (auto DbgII = dyn_cast<DbgVariableIntrinsic>(&I)) {
1624  for (Value *V : DbgII->location_ops())
1625  if (auto *Loc = dyn_cast_or_null<PHINode>(V))
1626  DbgValueMap.insert({Loc, DbgII});
1627  }
1628  }
1629  if (DbgValueMap.size() == 0)
1630  return;
1631 
1632  // Map a pair of the destination BB and old dbg.value to the new dbg.value,
1633  // so that if a dbg.value is being rewritten to use more than one of the
1634  // inserted PHIs in the same destination BB, we can update the same dbg.value
1635  // with all the new PHIs instead of creating one copy for each.
1638  NewDbgValueMap;
1639  // Then iterate through the new PHIs and look to see if they use one of the
1640  // previously mapped PHIs. If so, create a new dbg.value intrinsic that will
1641  // propagate the info through the new PHI. If we use more than one new PHI in
1642  // a single destination BB with the same old dbg.value, merge the updates so
1643  // that we get a single new dbg.value with all the new PHIs.
1644  for (auto PHI : InsertedPHIs) {
1645  BasicBlock *Parent = PHI->getParent();
1646  // Avoid inserting an intrinsic into an EH block.
1647  if (Parent->getFirstNonPHI()->isEHPad())
1648  continue;
1649  for (auto VI : PHI->operand_values()) {
1650  auto V = DbgValueMap.find(VI);
1651  if (V != DbgValueMap.end()) {
1652  auto *DbgII = cast<DbgVariableIntrinsic>(V->second);
1653  auto NewDI = NewDbgValueMap.find({Parent, DbgII});
1654  if (NewDI == NewDbgValueMap.end()) {
1655  auto *NewDbgII = cast<DbgVariableIntrinsic>(DbgII->clone());
1656  NewDI = NewDbgValueMap.insert({{Parent, DbgII}, NewDbgII}).first;
1657  }
1658  DbgVariableIntrinsic *NewDbgII = NewDI->second;
1659  // If PHI contains VI as an operand more than once, we may
1660  // replaced it in NewDbgII; confirm that it is present.
1661  if (is_contained(NewDbgII->location_ops(), VI))
1662  NewDbgII->replaceVariableLocationOp(VI, PHI);
1663  }
1664  }
1665  }
1666  // Insert thew new dbg.values into their destination blocks.
1667  for (auto DI : NewDbgValueMap) {
1668  BasicBlock *Parent = DI.first.first;
1669  auto *NewDbgII = DI.second;
1670  auto InsertionPt = Parent->getFirstInsertionPt();
1671  assert(InsertionPt != Parent->end() && "Ill-formed basic block");
1672  NewDbgII->insertBefore(&*InsertionPt);
1673  }
1674 }
1675 
1676 bool llvm::replaceDbgDeclare(Value *Address, Value *NewAddress,
1677  DIBuilder &Builder, uint8_t DIExprFlags,
1678  int Offset) {
1679  auto DbgAddrs = FindDbgAddrUses(Address);
1680  for (DbgVariableIntrinsic *DII : DbgAddrs) {
1681  const DebugLoc &Loc = DII->getDebugLoc();
1682  auto *DIVar = DII->getVariable();
1683  auto *DIExpr = DII->getExpression();
1684  assert(DIVar && "Missing variable");
1685  DIExpr = DIExpression::prepend(DIExpr, DIExprFlags, Offset);
1686  // Insert llvm.dbg.declare immediately before DII, and remove old
1687  // llvm.dbg.declare.
1688  Builder.insertDeclare(NewAddress, DIVar, DIExpr, Loc, DII);
1689  DII->eraseFromParent();
1690  }
1691  return !DbgAddrs.empty();
1692 }
1693 
1694 static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress,
1695  DIBuilder &Builder, int Offset) {
1696  const DebugLoc &Loc = DVI->getDebugLoc();
1697  auto *DIVar = DVI->getVariable();
1698  auto *DIExpr = DVI->getExpression();
1699  assert(DIVar && "Missing variable");
1700 
1701  // This is an alloca-based llvm.dbg.value. The first thing it should do with
1702  // the alloca pointer is dereference it. Otherwise we don't know how to handle
1703  // it and give up.
1704  if (!DIExpr || DIExpr->getNumElements() < 1 ||
1705  DIExpr->getElement(0) != dwarf::DW_OP_deref)
1706  return;
1707 
1708  // Insert the offset before the first deref.
1709  // We could just change the offset argument of dbg.value, but it's unsigned...
1710  if (Offset)
1711  DIExpr = DIExpression::prepend(DIExpr, 0, Offset);
1712 
1713  Builder.insertDbgValueIntrinsic(NewAddress, DIVar, DIExpr, Loc, DVI);
1714  DVI->eraseFromParent();
1715 }
1716 
1718  DIBuilder &Builder, int Offset) {
1719  if (auto *L = LocalAsMetadata::getIfExists(AI))
1720  if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
1721  for (Use &U : llvm::make_early_inc_range(MDV->uses()))
1722  if (auto *DVI = dyn_cast<DbgValueInst>(U.getUser()))
1723  replaceOneDbgValueForAlloca(DVI, NewAllocaAddress, Builder, Offset);
1724 }
1725 
1726 /// Where possible to salvage debug information for \p I do so
1727 /// and return True. If not possible mark undef and return False.
1730  findDbgUsers(DbgUsers, &I);
1731  salvageDebugInfoForDbgValues(I, DbgUsers);
1732 }
1733 
1736  // This is an arbitrary chosen limit on the maximum number of values we can
1737  // salvage up to in a DIArgList, used for performance reasons.
1738  const unsigned MaxDebugArgs = 16;
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  DIExpression *SalvagedExpr = DII->getExpression();
1756  auto LocItr = find(DIILocation, &I);
1757  while (SalvagedExpr && LocItr != DIILocation.end()) {
1758  unsigned LocNo = std::distance(DIILocation.begin(), LocItr);
1759  SalvagedExpr = salvageDebugInfoImpl(I, SalvagedExpr, StackValue, LocNo,
1760  AdditionalValues);
1761  LocItr = std::find(++LocItr, DIILocation.end(), &I);
1762  }
1763  // salvageDebugInfoImpl should fail on examining the first element of
1764  // DbgUsers, or none of them.
1765  if (!SalvagedExpr)
1766  break;
1767 
1768  DII->replaceVariableLocationOp(&I, I.getOperand(0));
1769  if (AdditionalValues.empty()) {
1770  DII->setExpression(SalvagedExpr);
1771  } else if (isa<DbgValueInst>(DII) &&
1772  DII->getNumVariableLocationOps() + AdditionalValues.size() <=
1773  MaxDebugArgs) {
1774  DII->addVariableLocationOps(AdditionalValues, SalvagedExpr);
1775  } else {
1776  // Do not salvage using DIArgList for dbg.addr/dbg.declare, as it is
1777  // currently only valid for stack value expressions.
1778  // Also do not salvage if the resulting DIArgList would contain an
1779  // unreasonably large number of values.
1780  Value *Undef = UndefValue::get(I.getOperand(0)->getType());
1781  DII->replaceVariableLocationOp(I.getOperand(0), Undef);
1782  }
1783  LLVM_DEBUG(dbgs() << "SALVAGE: " << *DII << '\n');
1784  Salvaged = true;
1785  }
1786 
1787  if (Salvaged)
1788  return;
1789 
1790  for (auto *DII : DbgUsers) {
1791  Value *Undef = UndefValue::get(I.getType());
1792  DII->replaceVariableLocationOp(&I, Undef);
1793  }
1794 }
1795 
1797  uint64_t CurrentLocOps,
1798  SmallVectorImpl<uint64_t> &Opcodes,
1799  SmallVectorImpl<Value *> &AdditionalValues) {
1800  unsigned BitWidth = DL.getIndexSizeInBits(GEP->getPointerAddressSpace());
1801  // Rewrite a GEP into a DIExpression.
1802  MapVector<Value *, APInt> VariableOffsets;
1803  APInt ConstantOffset(BitWidth, 0);
1804  if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
1805  return false;
1806  if (!VariableOffsets.empty() && !CurrentLocOps) {
1807  Opcodes.insert(Opcodes.begin(), {dwarf::DW_OP_LLVM_arg, 0});
1808  CurrentLocOps = 1;
1809  }
1810  for (auto Offset : VariableOffsets) {
1811  AdditionalValues.push_back(Offset.first);
1812  assert(Offset.second.isStrictlyPositive() &&
1813  "Expected strictly positive multiplier for offset.");
1814  Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps++, dwarf::DW_OP_constu,
1815  Offset.second.getZExtValue(), dwarf::DW_OP_mul,
1816  dwarf::DW_OP_plus});
1817  }
1818  DIExpression::appendOffset(Opcodes, ConstantOffset.getSExtValue());
1819  return true;
1820 }
1821 
1823  switch (Opcode) {
1824  case Instruction::Add:
1825  return dwarf::DW_OP_plus;
1826  case Instruction::Sub:
1827  return dwarf::DW_OP_minus;
1828  case Instruction::Mul:
1829  return dwarf::DW_OP_mul;
1830  case Instruction::SDiv:
1831  return dwarf::DW_OP_div;
1832  case Instruction::SRem:
1833  return dwarf::DW_OP_mod;
1834  case Instruction::Or:
1835  return dwarf::DW_OP_or;
1836  case Instruction::And:
1837  return dwarf::DW_OP_and;
1838  case Instruction::Xor:
1839  return dwarf::DW_OP_xor;
1840  case Instruction::Shl:
1841  return dwarf::DW_OP_shl;
1842  case Instruction::LShr:
1843  return dwarf::DW_OP_shr;
1844  case Instruction::AShr:
1845  return dwarf::DW_OP_shra;
1846  default:
1847  // TODO: Salvage from each kind of binop we know about.
1848  return 0;
1849  }
1850 }
1851 
1852 bool getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps,
1853  SmallVectorImpl<uint64_t> &Opcodes,
1854  SmallVectorImpl<Value *> &AdditionalValues) {
1855  // Handle binary operations with constant integer operands as a special case.
1856  auto *ConstInt = dyn_cast<ConstantInt>(BI->getOperand(1));
1857  // Values wider than 64 bits cannot be represented within a DIExpression.
1858  if (ConstInt && ConstInt->getBitWidth() > 64)
1859  return false;
1860 
1861  Instruction::BinaryOps BinOpcode = BI->getOpcode();
1862  // Push any Constant Int operand onto the expression stack.
1863  if (ConstInt) {
1864  uint64_t Val = ConstInt->getSExtValue();
1865  // Add or Sub Instructions with a constant operand can potentially be
1866  // simplified.
1867  if (BinOpcode == Instruction::Add || BinOpcode == Instruction::Sub) {
1868  uint64_t Offset = BinOpcode == Instruction::Add ? Val : -int64_t(Val);
1870  return true;
1871  }
1872  Opcodes.append({dwarf::DW_OP_constu, Val});
1873  } else {
1874  if (!CurrentLocOps) {
1875  Opcodes.append({dwarf::DW_OP_LLVM_arg, 0});
1876  CurrentLocOps = 1;
1877  }
1878  Opcodes.append({dwarf::DW_OP_LLVM_arg, CurrentLocOps});
1879  AdditionalValues.push_back(BI->getOperand(1));
1880  }
1881 
1882  // Add salvaged binary operator to expression stack, if it has a valid
1883  // representation in a DIExpression.
1884  uint64_t DwarfBinOp = getDwarfOpForBinOp(BinOpcode);
1885  if (!DwarfBinOp)
1886  return false;
1887  Opcodes.push_back(DwarfBinOp);
1888 
1889  return true;
1890 }
1891 
1892 DIExpression *
1894  bool WithStackValue, unsigned LocNo,
1895  SmallVectorImpl<Value *> &AdditionalValues) {
1896  uint64_t CurrentLocOps = SrcDIExpr->getNumLocationOperands();
1897  auto &M = *I.getModule();
1898  auto &DL = M.getDataLayout();
1899 
1900  // Apply a vector of opcodes to the source DIExpression.
1901  auto doSalvage = [&](SmallVectorImpl<uint64_t> &Ops) -> DIExpression * {
1902  DIExpression *DIExpr = SrcDIExpr;
1903  if (!Ops.empty()) {
1904  DIExpr = DIExpression::appendOpsToArg(DIExpr, Ops, LocNo, WithStackValue);
1905  }
1906  return DIExpr;
1907  };
1908 
1909  // initializer-list helper for applying operators to the source DIExpression.
1910  auto applyOps = [&](ArrayRef<uint64_t> Opcodes) {
1911  SmallVector<uint64_t, 8> Ops(Opcodes.begin(), Opcodes.end());
1912  return doSalvage(Ops);
1913  };
1914 
1915  if (auto *CI = dyn_cast<CastInst>(&I)) {
1916  // No-op casts are irrelevant for debug info.
1917  if (CI->isNoopCast(DL))
1918  return SrcDIExpr;
1919 
1920  Type *Type = CI->getType();
1921  // Casts other than Trunc, SExt, or ZExt to scalar types cannot be salvaged.
1922  if (Type->isVectorTy() ||
1923  !(isa<TruncInst>(&I) || isa<SExtInst>(&I) || isa<ZExtInst>(&I)))
1924  return nullptr;
1925 
1926  Value *FromValue = CI->getOperand(0);
1927  unsigned FromTypeBitSize = FromValue->getType()->getScalarSizeInBits();
1928  unsigned ToTypeBitSize = Type->getScalarSizeInBits();
1929 
1930  return applyOps(DIExpression::getExtOps(FromTypeBitSize, ToTypeBitSize,
1931  isa<SExtInst>(&I)));
1932  }
1933 
1935  if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
1936  if (getSalvageOpsForGEP(GEP, DL, CurrentLocOps, Ops, AdditionalValues))
1937  return doSalvage(Ops);
1938  } else if (auto *BI = dyn_cast<BinaryOperator>(&I)) {
1939  if (getSalvageOpsForBinOp(BI, CurrentLocOps, Ops, AdditionalValues))
1940  return doSalvage(Ops);
1941  }
1942  // *Not* to do: we should not attempt to salvage load instructions,
1943  // because the validity and lifetime of a dbg.value containing
1944  // DW_OP_deref becomes difficult to analyze. See PR40628 for examples.
1945  return nullptr;
1946 }
1947 
1948 /// A replacement for a dbg.value expression.
1950 
1951 /// Point debug users of \p From to \p To using exprs given by \p RewriteExpr,
1952 /// possibly moving/undefing users to prevent use-before-def. Returns true if
1953 /// changes are made.
1954 static bool rewriteDebugUsers(
1955  Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT,
1957  // Find debug users of From.
1959  findDbgUsers(Users, &From);
1960  if (Users.empty())
1961  return false;
1962 
1963  // Prevent use-before-def of To.
1964  bool Changed = false;
1966  if (isa<Instruction>(&To)) {
1967  bool DomPointAfterFrom = From.getNextNonDebugInstruction() == &DomPoint;
1968 
1969  for (auto *DII : Users) {
1970  // It's common to see a debug user between From and DomPoint. Move it
1971  // after DomPoint to preserve the variable update without any reordering.
1972  if (DomPointAfterFrom && DII->getNextNonDebugInstruction() == &DomPoint) {
1973  LLVM_DEBUG(dbgs() << "MOVE: " << *DII << '\n');
1974  DII->moveAfter(&DomPoint);
1975  Changed = true;
1976 
1977  // Users which otherwise aren't dominated by the replacement value must
1978  // be salvaged or deleted.
1979  } else if (!DT.dominates(&DomPoint, DII)) {
1980  UndefOrSalvage.insert(DII);
1981  }
1982  }
1983  }
1984 
1985  // Update debug users without use-before-def risk.
1986  for (auto *DII : Users) {
1987  if (UndefOrSalvage.count(DII))
1988  continue;
1989 
1990  DbgValReplacement DVR = RewriteExpr(*DII);
1991  if (!DVR)
1992  continue;
1993 
1994  DII->replaceVariableLocationOp(&From, &To);
1995  DII->setExpression(*DVR);
1996  LLVM_DEBUG(dbgs() << "REWRITE: " << *DII << '\n');
1997  Changed = true;
1998  }
1999 
2000  if (!UndefOrSalvage.empty()) {
2001  // Try to salvage the remaining debug users.
2003  Changed = true;
2004  }
2005 
2006  return Changed;
2007 }
2008 
2009 /// Check if a bitcast between a value of type \p FromTy to type \p ToTy would
2010 /// losslessly preserve the bits and semantics of the value. This predicate is
2011 /// symmetric, i.e swapping \p FromTy and \p ToTy should give the same result.
2012 ///
2013 /// Note that Type::canLosslesslyBitCastTo is not suitable here because it
2014 /// allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>,
2015 /// and also does not allow lossless pointer <-> integer conversions.
2016 static bool isBitCastSemanticsPreserving(const DataLayout &DL, Type *FromTy,
2017  Type *ToTy) {
2018  // Trivially compatible types.
2019  if (FromTy == ToTy)
2020  return true;
2021 
2022  // Handle compatible pointer <-> integer conversions.
2023  if (FromTy->isIntOrPtrTy() && ToTy->isIntOrPtrTy()) {
2024  bool SameSize = DL.getTypeSizeInBits(FromTy) == DL.getTypeSizeInBits(ToTy);
2025  bool LosslessConversion = !DL.isNonIntegralPointerType(FromTy) &&
2026  !DL.isNonIntegralPointerType(ToTy);
2027  return SameSize && LosslessConversion;
2028  }
2029 
2030  // TODO: This is not exhaustive.
2031  return false;
2032 }
2033 
2035  Instruction &DomPoint, DominatorTree &DT) {
2036  // Exit early if From has no debug users.
2037  if (!From.isUsedByMetadata())
2038  return false;
2039 
2040  assert(&From != &To && "Can't replace something with itself");
2041 
2042  Type *FromTy = From.getType();
2043  Type *ToTy = To.getType();
2044 
2045  auto Identity = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
2046  return DII.getExpression();
2047  };
2048 
2049  // Handle no-op conversions.
2050  Module &M = *From.getModule();
2051  const DataLayout &DL = M.getDataLayout();
2052  if (isBitCastSemanticsPreserving(DL, FromTy, ToTy))
2053  return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
2054 
2055  // Handle integer-to-integer widening and narrowing.
2056  // FIXME: Use DW_OP_convert when it's available everywhere.
2057  if (FromTy->isIntegerTy() && ToTy->isIntegerTy()) {
2058  uint64_t FromBits = FromTy->getPrimitiveSizeInBits();
2059  uint64_t ToBits = ToTy->getPrimitiveSizeInBits();
2060  assert(FromBits != ToBits && "Unexpected no-op conversion");
2061 
2062  // When the width of the result grows, assume that a debugger will only
2063  // access the low `FromBits` bits when inspecting the source variable.
2064  if (FromBits < ToBits)
2065  return rewriteDebugUsers(From, To, DomPoint, DT, Identity);
2066 
2067  // The width of the result has shrunk. Use sign/zero extension to describe
2068  // the source variable's high bits.
2069  auto SignOrZeroExt = [&](DbgVariableIntrinsic &DII) -> DbgValReplacement {
2070  DILocalVariable *Var = DII.getVariable();
2071 
2072  // Without knowing signedness, sign/zero extension isn't possible.
2073  auto Signedness = Var->getSignedness();
2074  if (!Signedness)
2075  return None;
2076 
2077  bool Signed = *Signedness == DIBasicType::Signedness::Signed;
2078  return DIExpression::appendExt(DII.getExpression(), ToBits, FromBits,
2079  Signed);
2080  };
2081  return rewriteDebugUsers(From, To, DomPoint, DT, SignOrZeroExt);
2082  }
2083 
2084  // TODO: Floating-point conversions, vectors.
2085  return false;
2086 }
2087 
2088 std::pair<unsigned, unsigned>
2090  unsigned NumDeadInst = 0;
2091  unsigned NumDeadDbgInst = 0;
2092  // Delete the instructions backwards, as it has a reduced likelihood of
2093  // having to update as many def-use and use-def chains.
2094  Instruction *EndInst = BB->getTerminator(); // Last not to be deleted.
2095  while (EndInst != &BB->front()) {
2096  // Delete the next to last instruction.
2097  Instruction *Inst = &*--EndInst->getIterator();
2098  if (!Inst->use_empty() && !Inst->getType()->isTokenTy())
2099  Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
2100  if (Inst->isEHPad() || Inst->getType()->isTokenTy()) {
2101  EndInst = Inst;
2102  continue;
2103  }
2104  if (isa<DbgInfoIntrinsic>(Inst))
2105  ++NumDeadDbgInst;
2106  else
2107  ++NumDeadInst;
2108  Inst->eraseFromParent();
2109  }
2110  return {NumDeadInst, NumDeadDbgInst};
2111 }
2112 
2113 unsigned llvm::changeToUnreachable(Instruction *I, bool PreserveLCSSA,
2114  DomTreeUpdater *DTU,
2115  MemorySSAUpdater *MSSAU) {
2116  BasicBlock *BB = I->getParent();
2117 
2118  if (MSSAU)
2119  MSSAU->changeToUnreachable(I);
2120 
2121  SmallSet<BasicBlock *, 8> UniqueSuccessors;
2122 
2123  // Loop over all of the successors, removing BB's entry from any PHI
2124  // nodes.
2125  for (BasicBlock *Successor : successors(BB)) {
2126  Successor->removePredecessor(BB, PreserveLCSSA);
2127  if (DTU)
2128  UniqueSuccessors.insert(Successor);
2129  }
2130  auto *UI = new UnreachableInst(I->getContext(), I);
2131  UI->setDebugLoc(I->getDebugLoc());
2132 
2133  // All instructions after this are dead.
2134  unsigned NumInstrsRemoved = 0;
2135  BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
2136  while (BBI != BBE) {
2137  if (!BBI->use_empty())
2138  BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
2139  BB->getInstList().erase(BBI++);
2140  ++NumInstrsRemoved;
2141  }
2142  if (DTU) {
2144  Updates.reserve(UniqueSuccessors.size());
2145  for (BasicBlock *UniqueSuccessor : UniqueSuccessors)
2146  Updates.push_back({DominatorTree::Delete, BB, UniqueSuccessor});
2147  DTU->applyUpdates(Updates);
2148  }
2149  return NumInstrsRemoved;
2150 }
2151 
2155  II->getOperandBundlesAsDefs(OpBundles);
2156  CallInst *NewCall = CallInst::Create(II->getFunctionType(),
2157  II->getCalledOperand(), Args, OpBundles);
2158  NewCall->setCallingConv(II->getCallingConv());
2159  NewCall->setAttributes(II->getAttributes());
2160  NewCall->setDebugLoc(II->getDebugLoc());
2161  NewCall->copyMetadata(*II);
2162 
2163  // If the invoke had profile metadata, try converting them for CallInst.
2164  uint64_t TotalWeight;
2165  if (NewCall->extractProfTotalWeight(TotalWeight)) {
2166  // Set the total weight if it fits into i32, otherwise reset.
2167  MDBuilder MDB(NewCall->getContext());
2168  auto NewWeights = uint32_t(TotalWeight) != TotalWeight
2169  ? nullptr
2170  : MDB.createBranchWeights({uint32_t(TotalWeight)});
2171  NewCall->setMetadata(LLVMContext::MD_prof, NewWeights);
2172  }
2173 
2174  return NewCall;
2175 }
2176 
2177 /// changeToCall - Convert the specified invoke into a normal call.
2179  CallInst *NewCall = createCallMatchingInvoke(II);
2180  NewCall->takeName(II);
2181  NewCall->insertBefore(II);
2182  II->replaceAllUsesWith(NewCall);
2183 
2184  // Follow the call by a branch to the normal destination.
2185  BasicBlock *NormalDestBB = II->getNormalDest();
2186  BranchInst::Create(NormalDestBB, II);
2187 
2188  // Update PHI nodes in the unwind destination
2189  BasicBlock *BB = II->getParent();
2190  BasicBlock *UnwindDestBB = II->getUnwindDest();
2191  UnwindDestBB->removePredecessor(BB);
2192  II->eraseFromParent();
2193  if (DTU)
2194  DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2195 }
2196 
2198  BasicBlock *UnwindEdge,
2199  DomTreeUpdater *DTU) {
2200  BasicBlock *BB = CI->getParent();
2201 
2202  // Convert this function call into an invoke instruction. First, split the
2203  // basic block.
2204  BasicBlock *Split = SplitBlock(BB, CI, DTU, /*LI=*/nullptr, /*MSSAU*/ nullptr,
2205  CI->getName() + ".noexc");
2206 
2207  // Delete the unconditional branch inserted by SplitBlock
2208  BB->getInstList().pop_back();
2209 
2210  // Create the new invoke instruction.
2211  SmallVector<Value *, 8> InvokeArgs(CI->args());
2213 
2214  CI->getOperandBundlesAsDefs(OpBundles);
2215 
2216  // Note: we're round tripping operand bundles through memory here, and that
2217  // can potentially be avoided with a cleverer API design that we do not have
2218  // as of this time.
2219 
2220  InvokeInst *II =
2222  UnwindEdge, InvokeArgs, OpBundles, CI->getName(), BB);
2223  II->setDebugLoc(CI->getDebugLoc());
2224  II->setCallingConv(CI->getCallingConv());
2225  II->setAttributes(CI->getAttributes());
2226 
2227  if (DTU)
2228  DTU->applyUpdates({{DominatorTree::Insert, BB, UnwindEdge}});
2229 
2230  // Make sure that anything using the call now uses the invoke! This also
2231  // updates the CallGraph if present, because it uses a WeakTrackingVH.
2232  CI->replaceAllUsesWith(II);
2233 
2234  // Delete the original call
2235  Split->getInstList().pop_front();
2236  return Split;
2237 }
2238 
2240  SmallPtrSetImpl<BasicBlock *> &Reachable,
2241  DomTreeUpdater *DTU = nullptr) {
2243  BasicBlock *BB = &F.front();
2244  Worklist.push_back(BB);
2245  Reachable.insert(BB);
2246  bool Changed = false;
2247  do {
2248  BB = Worklist.pop_back_val();
2249 
2250  // Do a quick scan of the basic block, turning any obviously unreachable
2251  // instructions into LLVM unreachable insts. The instruction combining pass
2252  // canonicalizes unreachable insts into stores to null or undef.
2253  for (Instruction &I : *BB) {
2254  if (auto *CI = dyn_cast<CallInst>(&I)) {
2255  Value *Callee = CI->getCalledOperand();
2256  // Handle intrinsic calls.
2257  if (Function *F = dyn_cast<Function>(Callee)) {
2258  auto IntrinsicID = F->getIntrinsicID();
2259  // Assumptions that are known to be false are equivalent to
2260  // unreachable. Also, if the condition is undefined, then we make the
2261  // choice most beneficial to the optimizer, and choose that to also be
2262  // unreachable.
2263  if (IntrinsicID == Intrinsic::assume) {
2264  if (match(CI->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
2265  // Don't insert a call to llvm.trap right before the unreachable.
2266  changeToUnreachable(CI, false, DTU);
2267  Changed = true;
2268  break;
2269  }
2270  } else if (IntrinsicID == Intrinsic::experimental_guard) {
2271  // A call to the guard intrinsic bails out of the current
2272  // compilation unit if the predicate passed to it is false. If the
2273  // predicate is a constant false, then we know the guard will bail
2274  // out of the current compile unconditionally, so all code following
2275  // it is dead.
2276  //
2277  // Note: unlike in llvm.assume, it is not "obviously profitable" for
2278  // guards to treat `undef` as `false` since a guard on `undef` can
2279  // still be useful for widening.
2280  if (match(CI->getArgOperand(0), m_Zero()))
2281  if (!isa<UnreachableInst>(CI->getNextNode())) {
2282  changeToUnreachable(CI->getNextNode(), false, DTU);
2283  Changed = true;
2284  break;
2285  }
2286  }
2287  } else if ((isa<ConstantPointerNull>(Callee) &&
2288  !NullPointerIsDefined(CI->getFunction())) ||
2289  isa<UndefValue>(Callee)) {
2290  changeToUnreachable(CI, false, DTU);
2291  Changed = true;
2292  break;
2293  }
2294  if (CI->doesNotReturn() && !CI->isMustTailCall()) {
2295  // If we found a call to a no-return function, insert an unreachable
2296  // instruction after it. Make sure there isn't *already* one there
2297  // though.
2298  if (!isa<UnreachableInst>(CI->getNextNode())) {
2299  // Don't insert a call to llvm.trap right before the unreachable.
2300  changeToUnreachable(CI->getNextNode(), false, DTU);
2301  Changed = true;
2302  }
2303  break;
2304  }
2305  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
2306  // Store to undef and store to null are undefined and used to signal
2307  // that they should be changed to unreachable by passes that can't
2308  // modify the CFG.
2309 
2310  // Don't touch volatile stores.
2311  if (SI->isVolatile()) continue;
2312 
2313  Value *Ptr = SI->getOperand(1);
2314 
2315  if (isa<UndefValue>(Ptr) ||
2316  (isa<ConstantPointerNull>(Ptr) &&
2317  !NullPointerIsDefined(SI->getFunction(),
2318  SI->getPointerAddressSpace()))) {
2319  changeToUnreachable(SI, false, DTU);
2320  Changed = true;
2321  break;
2322  }
2323  }
2324  }
2325 
2326  Instruction *Terminator = BB->getTerminator();
2327  if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
2328  // Turn invokes that call 'nounwind' functions into ordinary calls.
2329  Value *Callee = II->getCalledOperand();
2330  if ((isa<ConstantPointerNull>(Callee) &&
2331  !NullPointerIsDefined(BB->getParent())) ||
2332  isa<UndefValue>(Callee)) {
2333  changeToUnreachable(II, false, DTU);
2334  Changed = true;
2335  } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
2336  if (II->use_empty() && II->onlyReadsMemory()) {
2337  // jump to the normal destination branch.
2338  BasicBlock *NormalDestBB = II->getNormalDest();
2339  BasicBlock *UnwindDestBB = II->getUnwindDest();
2340  BranchInst::Create(NormalDestBB, II);
2341  UnwindDestBB->removePredecessor(II->getParent());
2342  II->eraseFromParent();
2343  if (DTU)
2344  DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}});
2345  } else
2346  changeToCall(II, DTU);
2347  Changed = true;
2348  }
2349  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
2350  // Remove catchpads which cannot be reached.
2351  struct CatchPadDenseMapInfo {
2352  static CatchPadInst *getEmptyKey() {
2354  }
2355 
2356  static CatchPadInst *getTombstoneKey() {
2358  }
2359 
2360  static unsigned getHashValue(CatchPadInst *CatchPad) {
2361  return static_cast<unsigned>(hash_combine_range(
2362  CatchPad->value_op_begin(), CatchPad->value_op_end()));
2363  }
2364 
2365  static bool isEqual(CatchPadInst *LHS, CatchPadInst *RHS) {
2366  if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
2367  RHS == getEmptyKey() || RHS == getTombstoneKey())
2368  return LHS == RHS;
2369  return LHS->isIdenticalTo(RHS);
2370  }
2371  };
2372 
2373  SmallDenseMap<BasicBlock *, int, 8> NumPerSuccessorCases;
2374  // Set of unique CatchPads.
2376  CatchPadDenseMapInfo, detail::DenseSetPair<CatchPadInst *>>
2377  HandlerSet;
2378  detail::DenseSetEmpty Empty;
2379  for (CatchSwitchInst::handler_iterator I = CatchSwitch->handler_begin(),
2380  E = CatchSwitch->handler_end();
2381  I != E; ++I) {
2382  BasicBlock *HandlerBB = *I;
2383  if (DTU)
2384  ++NumPerSuccessorCases[HandlerBB];
2385  auto *CatchPad = cast<CatchPadInst>(HandlerBB->getFirstNonPHI());
2386  if (!HandlerSet.insert({CatchPad, Empty}).second) {
2387  if (DTU)
2388  --NumPerSuccessorCases[HandlerBB];
2389  CatchSwitch->removeHandler(I);
2390  --I;
2391  --E;
2392  Changed = true;
2393  }
2394  }
2395  if (DTU) {
2396  std::vector<DominatorTree::UpdateType> Updates;
2397  for (const std::pair<BasicBlock *, int> &I : NumPerSuccessorCases)
2398  if (I.second == 0)
2399  Updates.push_back({DominatorTree::Delete, BB, I.first});
2400  DTU->applyUpdates(Updates);
2401  }
2402  }
2403 
2404  Changed |= ConstantFoldTerminator(BB, true, nullptr, DTU);
2405  for (BasicBlock *Successor : successors(BB))
2406  if (Reachable.insert(Successor).second)
2407  Worklist.push_back(Successor);
2408  } while (!Worklist.empty());
2409  return Changed;
2410 }
2411 
2413  Instruction *TI = BB->getTerminator();
2414 
2415  if (auto *II = dyn_cast<InvokeInst>(TI)) {
2416  changeToCall(II, DTU);
2417  return;
2418  }
2419 
2420  Instruction *NewTI;
2421  BasicBlock *UnwindDest;
2422 
2423  if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
2424  NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
2425  UnwindDest = CRI->getUnwindDest();
2426  } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
2427  auto *NewCatchSwitch = CatchSwitchInst::Create(
2428  CatchSwitch->getParentPad(), nullptr, CatchSwitch->getNumHandlers(),
2429  CatchSwitch->getName(), CatchSwitch);
2430  for (BasicBlock *PadBB : CatchSwitch->handlers())
2431  NewCatchSwitch->addHandler(PadBB);
2432 
2433  NewTI = NewCatchSwitch;
2434  UnwindDest = CatchSwitch->getUnwindDest();
2435  } else {
2436  llvm_unreachable("Could not find unwind successor");
2437  }
2438 
2439  NewTI->takeName(TI);
2440  NewTI->setDebugLoc(TI->getDebugLoc());
2441  UnwindDest->removePredecessor(BB);
2442  TI->replaceAllUsesWith(NewTI);
2443  TI->eraseFromParent();
2444  if (DTU)
2445  DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}});
2446 }
2447 
2448 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
2449 /// if they are in a dead cycle. Return true if a change was made, false
2450 /// otherwise.
2452  MemorySSAUpdater *MSSAU) {
2454  bool Changed = markAliveBlocks(F, Reachable, DTU);
2455 
2456  // If there are unreachable blocks in the CFG...
2457  if (Reachable.size() == F.size())
2458  return Changed;
2459 
2460  assert(Reachable.size() < F.size());
2461 
2462  // Are there any blocks left to actually delete?
2463  SmallSetVector<BasicBlock *, 8> BlocksToRemove;
2464  for (BasicBlock &BB : F) {
2465  // Skip reachable basic blocks
2466  if (Reachable.count(&BB))
2467  continue;
2468  // Skip already-deleted blocks
2469  if (DTU && DTU->isBBPendingDeletion(&BB))
2470  continue;
2471  BlocksToRemove.insert(&BB);
2472  }
2473 
2474  if (BlocksToRemove.empty())
2475  return Changed;
2476 
2477  Changed = true;
2478  NumRemoved += BlocksToRemove.size();
2479 
2480  if (MSSAU)
2481  MSSAU->removeBlocks(BlocksToRemove);
2482 
2483  DeleteDeadBlocks(BlocksToRemove.takeVector(), DTU);
2484 
2485  return Changed;
2486 }
2487 
2489  ArrayRef<unsigned> KnownIDs, bool DoesKMove) {
2491  K->dropUnknownNonDebugMetadata(KnownIDs);
2493  for (const auto &MD : Metadata) {
2494  unsigned Kind = MD.first;
2495  MDNode *JMD = J->getMetadata(Kind);
2496  MDNode *KMD = MD.second;
2497 
2498  switch (Kind) {
2499  default:
2500  K->setMetadata(Kind, nullptr); // Remove unknown metadata
2501  break;
2502  case LLVMContext::MD_dbg:
2503  llvm_unreachable("getAllMetadataOtherThanDebugLoc returned a MD_dbg");
2504  case LLVMContext::MD_tbaa:
2506  break;
2507  case LLVMContext::MD_alias_scope:
2509  break;
2510  case LLVMContext::MD_noalias:
2511  case LLVMContext::MD_mem_parallel_loop_access:
2512  K->setMetadata(Kind, MDNode::intersect(JMD, KMD));
2513  break;
2514  case LLVMContext::MD_access_group:
2515  K->setMetadata(LLVMContext::MD_access_group,
2516  intersectAccessGroups(K, J));
2517  break;
2518  case LLVMContext::MD_range:
2519 
2520  // If K does move, use most generic range. Otherwise keep the range of
2521  // K.
2522  if (DoesKMove)
2523  // FIXME: If K does move, we should drop the range info and nonnull.
2524  // Currently this function is used with DoesKMove in passes
2525  // doing hoisting/sinking and the current behavior of using the
2526  // most generic range is correct in those cases.
2528  break;
2529  case LLVMContext::MD_fpmath:
2531  break;
2532  case LLVMContext::MD_invariant_load:
2533  // Only set the !invariant.load if it is present in both instructions.
2534  K->setMetadata(Kind, JMD);
2535  break;
2536  case LLVMContext::MD_nonnull:
2537  // If K does move, keep nonull if it is present in both instructions.
2538  if (DoesKMove)
2539  K->setMetadata(Kind, JMD);
2540  break;
2541  case LLVMContext::MD_invariant_group:
2542  // Preserve !invariant.group in K.
2543  break;
2544  case LLVMContext::MD_align:
2545  K->setMetadata(Kind,
2547  break;
2548  case LLVMContext::MD_dereferenceable:
2549  case LLVMContext::MD_dereferenceable_or_null:
2550  K->setMetadata(Kind,
2552  break;
2553  case LLVMContext::MD_preserve_access_index:
2554  // Preserve !preserve.access.index in K.
2555  break;
2556  }
2557  }
2558  // Set !invariant.group from J if J has it. If both instructions have it
2559  // then we will just pick it from J - even when they are different.
2560  // Also make sure that K is load or store - f.e. combining bitcast with load
2561  // could produce bitcast with invariant.group metadata, which is invalid.
2562  // FIXME: we should try to preserve both invariant.group md if they are
2563  // different, but right now instruction can only have one invariant.group.
2564  if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
2565  if (isa<LoadInst>(K) || isa<StoreInst>(K))
2566  K->setMetadata(LLVMContext::MD_invariant_group, JMD);
2567 }
2568 
2570  bool KDominatesJ) {
2571  unsigned KnownIDs[] = {
2572  LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2573  LLVMContext::MD_noalias, LLVMContext::MD_range,
2574  LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull,
2575  LLVMContext::MD_invariant_group, LLVMContext::MD_align,
2576  LLVMContext::MD_dereferenceable,
2577  LLVMContext::MD_dereferenceable_or_null,
2578  LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index};
2579  combineMetadata(K, J, KnownIDs, KDominatesJ);
2580 }
2581 
2584  Source.getAllMetadata(MD);
2585  MDBuilder MDB(Dest.getContext());
2586  Type *NewType = Dest.getType();
2587  const DataLayout &DL = Source.getModule()->getDataLayout();
2588  for (const auto &MDPair : MD) {
2589  unsigned ID = MDPair.first;
2590  MDNode *N = MDPair.second;
2591  // Note, essentially every kind of metadata should be preserved here! This
2592  // routine is supposed to clone a load instruction changing *only its type*.
2593  // The only metadata it makes sense to drop is metadata which is invalidated
2594  // when the pointer type changes. This should essentially never be the case
2595  // in LLVM, but we explicitly switch over only known metadata to be
2596  // conservatively correct. If you are adding metadata to LLVM which pertains
2597  // to loads, you almost certainly want to add it here.
2598  switch (ID) {
2599  case LLVMContext::MD_dbg:
2600  case LLVMContext::MD_tbaa:
2601  case LLVMContext::MD_prof:
2602  case LLVMContext::MD_fpmath:
2603  case LLVMContext::MD_tbaa_struct:
2604  case LLVMContext::MD_invariant_load:
2605  case LLVMContext::MD_alias_scope:
2606  case LLVMContext::MD_noalias:
2607  case LLVMContext::MD_nontemporal:
2608  case LLVMContext::MD_mem_parallel_loop_access:
2609  case LLVMContext::MD_access_group:
2610  // All of these directly apply.
2611  Dest.setMetadata(ID, N);
2612  break;
2613 
2614  case LLVMContext::MD_nonnull:
2615  copyNonnullMetadata(Source, N, Dest);
2616  break;
2617 
2618  case LLVMContext::MD_align:
2619  case LLVMContext::MD_dereferenceable:
2620  case LLVMContext::MD_dereferenceable_or_null:
2621  // These only directly apply if the new type is also a pointer.
2622  if (NewType->isPointerTy())
2623  Dest.setMetadata(ID, N);
2624  break;
2625 
2626  case LLVMContext::MD_range:
2627  copyRangeMetadata(DL, Source, N, Dest);
2628  break;
2629  }
2630  }
2631 }
2632 
2634  auto *ReplInst = dyn_cast<Instruction>(Repl);
2635  if (!ReplInst)
2636  return;
2637 
2638  // Patch the replacement so that it is not more restrictive than the value
2639  // being replaced.
2640  // Note that if 'I' is a load being replaced by some operation,
2641  // for example, by an arithmetic operation, then andIRFlags()
2642  // would just erase all math flags from the original arithmetic
2643  // operation, which is clearly not wanted and not needed.
2644  if (!isa<LoadInst>(I))
2645  ReplInst->andIRFlags(I);
2646 
2647  // FIXME: If both the original and replacement value are part of the
2648  // same control-flow region (meaning that the execution of one
2649  // guarantees the execution of the other), then we can combine the
2650  // noalias scopes here and do better than the general conservative
2651  // answer used in combineMetadata().
2652 
2653  // In general, GVN unifies expressions over different control-flow
2654  // regions, and so we need a conservative combination of the noalias
2655  // scopes.
2656  static const unsigned KnownIDs[] = {
2657  LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
2658  LLVMContext::MD_noalias, LLVMContext::MD_range,
2659  LLVMContext::MD_fpmath, LLVMContext::MD_invariant_load,
2660  LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull,
2661  LLVMContext::MD_access_group, LLVMContext::MD_preserve_access_index};
2662  combineMetadata(ReplInst, I, KnownIDs, false);
2663 }
2664 
2665 template <typename RootType, typename DominatesFn>
2667  const RootType &Root,
2668  const DominatesFn &Dominates) {
2669  assert(From->getType() == To->getType());
2670 
2671  unsigned Count = 0;
2672  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2673  UI != UE;) {
2674  Use &U = *UI++;
2675  if (!Dominates(Root, U))
2676  continue;
2677  U.set(To);
2678  LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()
2679  << "' as " << *To << " in " << *U << "\n");
2680  ++Count;
2681  }
2682  return Count;
2683 }
2684 
2686  assert(From->getType() == To->getType());
2687  auto *BB = From->getParent();
2688  unsigned Count = 0;
2689 
2690  for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2691  UI != UE;) {
2692  Use &U = *UI++;
2693  auto *I = cast<Instruction>(U.getUser());
2694  if (I->getParent() == BB)
2695  continue;
2696  U.set(To);
2697  ++Count;
2698  }
2699  return Count;
2700 }
2701 
2703  DominatorTree &DT,
2704  const BasicBlockEdge &Root) {
2705  auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
2706  return DT.dominates(Root, U);
2707  };
2708  return ::replaceDominatedUsesWith(From, To, Root, Dominates);
2709 }
2710 
2712  DominatorTree &DT,
2713  const BasicBlock *BB) {
2714  auto Dominates = [&DT](const BasicBlock *BB, const Use &U) {
2715  return DT.dominates(BB, U);
2716  };
2717  return ::replaceDominatedUsesWith(From, To, BB, Dominates);
2718 }
2719 
2721  const TargetLibraryInfo &TLI) {
2722  // Check if the function is specifically marked as a gc leaf function.
2723  if (Call->hasFnAttr("gc-leaf-function"))
2724  return true;
2725  if (const Function *F = Call->getCalledFunction()) {
2726  if (F->hasFnAttribute("gc-leaf-function"))
2727  return true;
2728 
2729  if (auto IID = F->getIntrinsicID()) {
2730  // Most LLVM intrinsics do not take safepoints.
2731  return IID != Intrinsic::experimental_gc_statepoint &&
2732  IID != Intrinsic::experimental_deoptimize &&
2733  IID != Intrinsic::memcpy_element_unordered_atomic &&
2734  IID != Intrinsic::memmove_element_unordered_atomic;
2735  }
2736  }
2737 
2738  // Lib calls can be materialized by some passes, and won't be
2739  // marked as 'gc-leaf-function.' All available Libcalls are
2740  // GC-leaf.
2741  LibFunc LF;
2742  if (TLI.getLibFunc(*Call, LF)) {
2743  return TLI.has(LF);
2744  }
2745 
2746  return false;
2747 }
2748 
2750  LoadInst &NewLI) {
2751  auto *NewTy = NewLI.getType();
2752 
2753  // This only directly applies if the new type is also a pointer.
2754  if (NewTy->isPointerTy()) {
2755  NewLI.setMetadata(LLVMContext::MD_nonnull, N);
2756  return;
2757  }
2758 
2759  // The only other translation we can do is to integral loads with !range
2760  // metadata.
2761  if (!NewTy->isIntegerTy())
2762  return;
2763 
2764  MDBuilder MDB(NewLI.getContext());
2765  const Value *Ptr = OldLI.getPointerOperand();
2766  auto *ITy = cast<IntegerType>(NewTy);
2767  auto *NullInt = ConstantExpr::getPtrToInt(
2768  ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
2769  auto *NonNullInt = ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
2770  NewLI.setMetadata(LLVMContext::MD_range,
2771  MDB.createRange(NonNullInt, NullInt));
2772 }
2773 
2774 void llvm::copyRangeMetadata(const DataLayout &DL, const LoadInst &OldLI,
2775  MDNode *N, LoadInst &NewLI) {
2776  auto *NewTy = NewLI.getType();
2777 
2778  // Give up unless it is converted to a pointer where there is a single very
2779  // valuable mapping we can do reliably.
2780  // FIXME: It would be nice to propagate this in more ways, but the type
2781  // conversions make it hard.
2782  if (!NewTy->isPointerTy())
2783  return;
2784 
2785  unsigned BitWidth = DL.getPointerTypeSizeInBits(NewTy);
2787  MDNode *NN = MDNode::get(OldLI.getContext(), None);
2788  NewLI.setMetadata(LLVMContext::MD_nonnull, NN);
2789  }
2790 }
2791 
2794  findDbgUsers(DbgUsers, &I);
2795  for (auto *DII : DbgUsers)
2796  DII->eraseFromParent();
2797 }
2798 
2800  BasicBlock *BB) {
2801  // Since we are moving the instructions out of its basic block, we do not
2802  // retain their original debug locations (DILocations) and debug intrinsic
2803  // instructions.
2804  //
2805  // Doing so would degrade the debugging experience and adversely affect the
2806  // accuracy of profiling information.
2807  //
2808  // Currently, when hoisting the instructions, we take the following actions:
2809  // - Remove their debug intrinsic instructions.
2810  // - Set their debug locations to the values from the insertion point.
2811  //
2812  // As per PR39141 (comment #8), the more fundamental reason why the dbg.values
2813  // need to be deleted, is because there will not be any instructions with a
2814  // DILocation in either branch left after performing the transformation. We
2815  // can only insert a dbg.value after the two branches are joined again.
2816  //
2817  // See PR38762, PR39243 for more details.
2818  //
2819  // TODO: Extend llvm.dbg.value to take more than one SSA Value (PR39141) to
2820  // encode predicated DIExpressions that yield different results on different
2821  // code paths.
2822 
2823  for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;) {
2824  Instruction *I = &*II;
2825  I->dropUndefImplyingAttrsAndUnknownMetadata();
2826  if (I->isUsedByMetadata())
2827  dropDebugUsers(*I);
2828  if (I->isDebugOrPseudoInst()) {
2829  // Remove DbgInfo and pseudo probe Intrinsics.
2830  II = I->eraseFromParent();
2831  continue;
2832  }
2833  I->setDebugLoc(InsertPt->getDebugLoc());
2834  ++II;
2835  }
2836  DomBlock->getInstList().splice(InsertPt->getIterator(), BB->getInstList(),
2837  BB->begin(),
2838  BB->getTerminator()->getIterator());
2839 }
2840 
2841 namespace {
2842 
2843 /// A potential constituent of a bitreverse or bswap expression. See
2844 /// collectBitParts for a fuller explanation.
2845 struct BitPart {
2846  BitPart(Value *P, unsigned BW) : Provider(P) {
2847  Provenance.resize(BW);
2848  }
2849 
2850  /// The Value that this is a bitreverse/bswap of.
2851  Value *Provider;
2852 
2853  /// The "provenance" of each bit. Provenance[A] = B means that bit A
2854  /// in Provider becomes bit B in the result of this expression.
2855  SmallVector<int8_t, 32> Provenance; // int8_t means max size is i128.
2856 
2857  enum { Unset = -1 };
2858 };
2859 
2860 } // end anonymous namespace
2861 
2862 /// Analyze the specified subexpression and see if it is capable of providing
2863 /// pieces of a bswap or bitreverse. The subexpression provides a potential
2864 /// piece of a bswap or bitreverse if it can be proved that each non-zero bit in
2865 /// the output of the expression came from a corresponding bit in some other
2866 /// value. This function is recursive, and the end result is a mapping of
2867 /// bitnumber to bitnumber. It is the caller's responsibility to validate that
2868 /// the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.
2869 ///
2870 /// For example, if the current subexpression if "(shl i32 %X, 24)" then we know
2871 /// that the expression deposits the low byte of %X into the high byte of the
2872 /// result and that all other bits are zero. This expression is accepted and a
2873 /// BitPart is returned with Provider set to %X and Provenance[24-31] set to
2874 /// [0-7].
2875 ///
2876 /// For vector types, all analysis is performed at the per-element level. No
2877 /// cross-element analysis is supported (shuffle/insertion/reduction), and all
2878 /// constant masks must be splatted across all elements.
2879 ///
2880 /// To avoid revisiting values, the BitPart results are memoized into the
2881 /// provided map. To avoid unnecessary copying of BitParts, BitParts are
2882 /// constructed in-place in the \c BPS map. Because of this \c BPS needs to
2883 /// store BitParts objects, not pointers. As we need the concept of a nullptr
2884 /// BitParts (Value has been analyzed and the analysis failed), we an Optional
2885 /// type instead to provide the same functionality.
2886 ///
2887 /// Because we pass around references into \c BPS, we must use a container that
2888 /// does not invalidate internal references (std::map instead of DenseMap).
2889 static const Optional<BitPart> &
2890 collectBitParts(Value *V, bool MatchBSwaps, bool MatchBitReversals,
2891  std::map<Value *, Optional<BitPart>> &BPS, int Depth,
2892  bool &FoundRoot) {
2893  auto I = BPS.find(V);
2894  if (I != BPS.end())
2895  return I->second;
2896 
2897  auto &Result = BPS[V] = None;
2898  auto BitWidth = V->getType()->getScalarSizeInBits();
2899 
2900  // Can't do integer/elements > 128 bits.
2901  if (BitWidth > 128)
2902  return Result;
2903 
2904  // Prevent stack overflow by limiting the recursion depth
2906  LLVM_DEBUG(dbgs() << "collectBitParts max recursion depth reached.\n");
2907  return Result;
2908  }
2909 
2910  if (auto *I = dyn_cast<Instruction>(V)) {
2911  Value *X, *Y;
2912  const APInt *C;
2913 
2914  // If this is an or instruction, it may be an inner node of the bswap.
2915  if (match(V, m_Or(m_Value(X), m_Value(Y)))) {
2916  // Check we have both sources and they are from the same provider.
2917  const auto &A = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
2918  Depth + 1, FoundRoot);
2919  if (!A || !A->Provider)
2920  return Result;
2921 
2922  const auto &B = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
2923  Depth + 1, FoundRoot);
2924  if (!B || A->Provider != B->Provider)
2925  return Result;
2926 
2927  // Try and merge the two together.
2928  Result = BitPart(A->Provider, BitWidth);
2929  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx) {
2930  if (A->Provenance[BitIdx] != BitPart::Unset &&
2931  B->Provenance[BitIdx] != BitPart::Unset &&
2932  A->Provenance[BitIdx] != B->Provenance[BitIdx])
2933  return Result = None;
2934 
2935  if (A->Provenance[BitIdx] == BitPart::Unset)
2936  Result->Provenance[BitIdx] = B->Provenance[BitIdx];
2937  else
2938  Result->Provenance[BitIdx] = A->Provenance[BitIdx];
2939  }
2940 
2941  return Result;
2942  }
2943 
2944  // If this is a logical shift by a constant, recurse then shift the result.
2945  if (match(V, m_LogicalShift(m_Value(X), m_APInt(C)))) {
2946  const APInt &BitShift = *C;
2947 
2948  // Ensure the shift amount is defined.
2949  if (BitShift.uge(BitWidth))
2950  return Result;
2951 
2952  // For bswap-only, limit shift amounts to whole bytes, for an early exit.
2953  if (!MatchBitReversals && (BitShift.getZExtValue() % 8) != 0)
2954  return Result;
2955 
2956  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
2957  Depth + 1, FoundRoot);
2958  if (!Res)
2959  return Result;
2960  Result = Res;
2961 
2962  // Perform the "shift" on BitProvenance.
2963  auto &P = Result->Provenance;
2964  if (I->getOpcode() == Instruction::Shl) {
2965  P.erase(std::prev(P.end(), BitShift.getZExtValue()), P.end());
2966  P.insert(P.begin(), BitShift.getZExtValue(), BitPart::Unset);
2967  } else {
2968  P.erase(P.begin(), std::next(P.begin(), BitShift.getZExtValue()));
2969  P.insert(P.end(), BitShift.getZExtValue(), BitPart::Unset);
2970  }
2971 
2972  return Result;
2973  }
2974 
2975  // If this is a logical 'and' with a mask that clears bits, recurse then
2976  // unset the appropriate bits.
2977  if (match(V, m_And(m_Value(X), m_APInt(C)))) {
2978  const APInt &AndMask = *C;
2979 
2980  // Check that the mask allows a multiple of 8 bits for a bswap, for an
2981  // early exit.
2982  unsigned NumMaskedBits = AndMask.countPopulation();
2983  if (!MatchBitReversals && (NumMaskedBits % 8) != 0)
2984  return Result;
2985 
2986  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
2987  Depth + 1, FoundRoot);
2988  if (!Res)
2989  return Result;
2990  Result = Res;
2991 
2992  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
2993  // If the AndMask is zero for this bit, clear the bit.
2994  if (AndMask[BitIdx] == 0)
2995  Result->Provenance[BitIdx] = BitPart::Unset;
2996  return Result;
2997  }
2998 
2999  // If this is a zext instruction zero extend the result.
3000  if (match(V, m_ZExt(m_Value(X)))) {
3001  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3002  Depth + 1, FoundRoot);
3003  if (!Res)
3004  return Result;
3005 
3006  Result = BitPart(Res->Provider, BitWidth);
3007  auto NarrowBitWidth = X->getType()->getScalarSizeInBits();
3008  for (unsigned BitIdx = 0; BitIdx < NarrowBitWidth; ++BitIdx)
3009  Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3010  for (unsigned BitIdx = NarrowBitWidth; BitIdx < BitWidth; ++BitIdx)
3011  Result->Provenance[BitIdx] = BitPart::Unset;
3012  return Result;
3013  }
3014 
3015  // If this is a truncate instruction, extract the lower bits.
3016  if (match(V, m_Trunc(m_Value(X)))) {
3017  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3018  Depth + 1, FoundRoot);
3019  if (!Res)
3020  return Result;
3021 
3022  Result = BitPart(Res->Provider, BitWidth);
3023  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3024  Result->Provenance[BitIdx] = Res->Provenance[BitIdx];
3025  return Result;
3026  }
3027 
3028  // BITREVERSE - most likely due to us previous matching a partial
3029  // bitreverse.
3030  if (match(V, m_BitReverse(m_Value(X)))) {
3031  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3032  Depth + 1, FoundRoot);
3033  if (!Res)
3034  return Result;
3035 
3036  Result = BitPart(Res->Provider, BitWidth);
3037  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3038  Result->Provenance[(BitWidth - 1) - BitIdx] = Res->Provenance[BitIdx];
3039  return Result;
3040  }
3041 
3042  // BSWAP - most likely due to us previous matching a partial bswap.
3043  if (match(V, m_BSwap(m_Value(X)))) {
3044  const auto &Res = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3045  Depth + 1, FoundRoot);
3046  if (!Res)
3047  return Result;
3048 
3049  unsigned ByteWidth = BitWidth / 8;
3050  Result = BitPart(Res->Provider, BitWidth);
3051  for (unsigned ByteIdx = 0; ByteIdx < ByteWidth; ++ByteIdx) {
3052  unsigned ByteBitOfs = ByteIdx * 8;
3053  for (unsigned BitIdx = 0; BitIdx < 8; ++BitIdx)
3054  Result->Provenance[(BitWidth - 8 - ByteBitOfs) + BitIdx] =
3055  Res->Provenance[ByteBitOfs + BitIdx];
3056  }
3057  return Result;
3058  }
3059 
3060  // Funnel 'double' shifts take 3 operands, 2 inputs and the shift
3061  // amount (modulo).
3062  // fshl(X,Y,Z): (X << (Z % BW)) | (Y >> (BW - (Z % BW)))
3063  // fshr(X,Y,Z): (X << (BW - (Z % BW))) | (Y >> (Z % BW))
3064  if (match(V, m_FShl(m_Value(X), m_Value(Y), m_APInt(C))) ||
3065  match(V, m_FShr(m_Value(X), m_Value(Y), m_APInt(C)))) {
3066  // We can treat fshr as a fshl by flipping the modulo amount.
3067  unsigned ModAmt = C->urem(BitWidth);
3068  if (cast<IntrinsicInst>(I)->getIntrinsicID() == Intrinsic::fshr)
3069  ModAmt = BitWidth - ModAmt;
3070 
3071  // For bswap-only, limit shift amounts to whole bytes, for an early exit.
3072  if (!MatchBitReversals && (ModAmt % 8) != 0)
3073  return Result;
3074 
3075  // Check we have both sources and they are from the same provider.
3076  const auto &LHS = collectBitParts(X, MatchBSwaps, MatchBitReversals, BPS,
3077  Depth + 1, FoundRoot);
3078  if (!LHS || !LHS->Provider)
3079  return Result;
3080 
3081  const auto &RHS = collectBitParts(Y, MatchBSwaps, MatchBitReversals, BPS,
3082  Depth + 1, FoundRoot);
3083  if (!RHS || LHS->Provider != RHS->Provider)
3084  return Result;
3085 
3086  unsigned StartBitRHS = BitWidth - ModAmt;
3087  Result = BitPart(LHS->Provider, BitWidth);
3088  for (unsigned BitIdx = 0; BitIdx < StartBitRHS; ++BitIdx)
3089  Result->Provenance[BitIdx + ModAmt] = LHS->Provenance[BitIdx];
3090  for (unsigned BitIdx = 0; BitIdx < ModAmt; ++BitIdx)
3091  Result->Provenance[BitIdx] = RHS->Provenance[BitIdx + StartBitRHS];
3092  return Result;
3093  }
3094  }
3095 
3096  // If we've already found a root input value then we're never going to merge
3097  // these back together.
3098  if (FoundRoot)
3099  return Result;
3100 
3101  // Okay, we got to something that isn't a shift, 'or', 'and', etc. This must
3102  // be the root input value to the bswap/bitreverse.
3103  FoundRoot = true;
3104  Result = BitPart(V, BitWidth);
3105  for (unsigned BitIdx = 0; BitIdx < BitWidth; ++BitIdx)
3106  Result->Provenance[BitIdx] = BitIdx;
3107  return Result;
3108 }
3109 
3110 static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To,
3111  unsigned BitWidth) {
3112  if (From % 8 != To % 8)
3113  return false;
3114  // Convert from bit indices to byte indices and check for a byte reversal.
3115  From >>= 3;
3116  To >>= 3;
3117  BitWidth >>= 3;
3118  return From == BitWidth - To - 1;
3119 }
3120 
3121 static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To,
3122  unsigned BitWidth) {
3123  return From == BitWidth - To - 1;
3124 }
3125 
3127  Instruction *I, bool MatchBSwaps, bool MatchBitReversals,
3128  SmallVectorImpl<Instruction *> &InsertedInsts) {
3129  if (!match(I, m_Or(m_Value(), m_Value())) &&
3130  !match(I, m_FShl(m_Value(), m_Value(), m_Value())) &&
3131  !match(I, m_FShr(m_Value(), m_Value(), m_Value())))
3132  return false;
3133  if (!MatchBSwaps && !MatchBitReversals)
3134  return false;
3135  Type *ITy = I->getType();
3136  if (!ITy->isIntOrIntVectorTy() || ITy->getScalarSizeInBits() > 128)
3137  return false; // Can't do integer/elements > 128 bits.
3138 
3139  Type *DemandedTy = ITy;
3140  if (I->hasOneUse())
3141  if (auto *Trunc = dyn_cast<TruncInst>(I->user_back()))
3142  DemandedTy = Trunc->getType();
3143 
3144  // Try to find all the pieces corresponding to the bswap.
3145  bool FoundRoot = false;
3146  std::map<Value *, Optional<BitPart>> BPS;
3147  const auto &Res =
3148  collectBitParts(I, MatchBSwaps, MatchBitReversals, BPS, 0, FoundRoot);
3149  if (!Res)
3150  return false;
3151  ArrayRef<int8_t> BitProvenance = Res->Provenance;
3152  assert(all_of(BitProvenance,
3153  [](int8_t I) { return I == BitPart::Unset || 0 <= I; }) &&
3154  "Illegal bit provenance index");
3155 
3156  // If the upper bits are zero, then attempt to perform as a truncated op.
3157  if (BitProvenance.back() == BitPart::Unset) {
3158  while (!BitProvenance.empty() && BitProvenance.back() == BitPart::Unset)
3159  BitProvenance = BitProvenance.drop_back();
3160  if (BitProvenance.empty())
3161  return false; // TODO - handle null value?
3162  DemandedTy = Type::getIntNTy(I->getContext(), BitProvenance.size());
3163  if (auto *IVecTy = dyn_cast<VectorType>(ITy))
3164  DemandedTy = VectorType::get(DemandedTy, IVecTy);
3165  }
3166 
3167  // Check BitProvenance hasn't found a source larger than the result type.
3168  unsigned DemandedBW = DemandedTy->getScalarSizeInBits();
3169  if (DemandedBW > ITy->getScalarSizeInBits())
3170  return false;
3171 
3172  // Now, is the bit permutation correct for a bswap or a bitreverse? We can
3173  // only byteswap values with an even number of bytes.
3174  APInt DemandedMask = APInt::getAllOnesValue(DemandedBW);
3175  bool OKForBSwap = MatchBSwaps && (DemandedBW % 16) == 0;
3176  bool OKForBitReverse = MatchBitReversals;
3177  for (unsigned BitIdx = 0;
3178  (BitIdx < DemandedBW) && (OKForBSwap || OKForBitReverse); ++BitIdx) {
3179  if (BitProvenance[BitIdx] == BitPart::Unset) {
3180  DemandedMask.clearBit(BitIdx);
3181  continue;
3182  }
3183  OKForBSwap &= bitTransformIsCorrectForBSwap(BitProvenance[BitIdx], BitIdx,
3184  DemandedBW);
3185  OKForBitReverse &= bitTransformIsCorrectForBitReverse(BitProvenance[BitIdx],
3186  BitIdx, DemandedBW);
3187  }
3188 
3189  Intrinsic::ID Intrin;
3190  if (OKForBSwap)
3191  Intrin = Intrinsic::bswap;
3192  else if (OKForBitReverse)
3193  Intrin = Intrinsic::bitreverse;
3194  else
3195  return false;
3196 
3197  Function *F = Intrinsic::getDeclaration(I->getModule(), Intrin, DemandedTy);
3198  Value *Provider = Res->Provider;
3199 
3200  // We may need to truncate the provider.
3201  if (DemandedTy != Provider->getType()) {
3202  auto *Trunc =
3203  CastInst::CreateIntegerCast(Provider, DemandedTy, false, "trunc", I);
3204  InsertedInsts.push_back(Trunc);
3205  Provider = Trunc;
3206  }
3207 
3208  Instruction *Result = CallInst::Create(F, Provider, "rev", I);
3209  InsertedInsts.push_back(Result);
3210 
3211  if (!DemandedMask.isAllOnesValue()) {
3212  auto *Mask = ConstantInt::get(DemandedTy, DemandedMask);
3213  Result = BinaryOperator::Create(Instruction::And, Result, Mask, "mask", I);
3214  InsertedInsts.push_back(Result);
3215  }
3216 
3217  // We may need to zeroextend back to the result type.
3218  if (ITy != Result->getType()) {
3219  auto *ExtInst = CastInst::CreateIntegerCast(Result, ITy, false, "zext", I);
3220  InsertedInsts.push_back(ExtInst);
3221  }
3222 
3223  return true;
3224 }
3225 
3226 // CodeGen has special handling for some string functions that may replace
3227 // them with target-specific intrinsics. Since that'd skip our interceptors
3228 // in ASan/MSan/TSan/DFSan, and thus make us miss some memory accesses,
3229 // we mark affected calls as NoBuiltin, which will disable optimization
3230 // in CodeGen.
3232  CallInst *CI, const TargetLibraryInfo *TLI) {
3233  Function *F = CI->getCalledFunction();
3234  LibFunc Func;
3235  if (F && !F->hasLocalLinkage() && F->hasName() &&
3236  TLI->getLibFunc(F->getName(), Func) && TLI->hasOptimizedCodeGen(Func) &&
3237  !F->doesNotAccessMemory())
3238  CI->addAttribute(AttributeList::FunctionIndex, Attribute::NoBuiltin);
3239 }
3240 
3241 bool llvm::canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx) {
3242  // We can't have a PHI with a metadata type.
3243  if (I->getOperand(OpIdx)->getType()->isMetadataTy())
3244  return false;
3245 
3246  // Early exit.
3247  if (!isa<Constant>(I->getOperand(OpIdx)))
3248  return true;
3249 
3250  switch (I->getOpcode()) {
3251  default:
3252  return true;
3253  case Instruction::Call:
3254  case Instruction::Invoke: {
3255  const auto &CB = cast<CallBase>(*I);
3256 
3257  // Can't handle inline asm. Skip it.
3258  if (CB.isInlineAsm())
3259  return false;
3260 
3261  // Constant bundle operands may need to retain their constant-ness for
3262  // correctness.
3263  if (CB.isBundleOperand(OpIdx))
3264  return false;
3265 
3266  if (OpIdx < CB.getNumArgOperands()) {
3267  // Some variadic intrinsics require constants in the variadic arguments,
3268  // which currently aren't markable as immarg.
3269  if (isa<IntrinsicInst>(CB) &&
3270  OpIdx >= CB.getFunctionType()->getNumParams()) {
3271  // This is known to be OK for stackmap.
3272  return CB.getIntrinsicID() == Intrinsic::experimental_stackmap;
3273  }
3274 
3275  // gcroot is a special case, since it requires a constant argument which
3276  // isn't also required to be a simple ConstantInt.
3277  if (CB.getIntrinsicID() == Intrinsic::gcroot)
3278  return false;
3279 
3280  // Some intrinsic operands are required to be immediates.
3281  return !CB.paramHasAttr(OpIdx, Attribute::ImmArg);
3282  }
3283 
3284  // It is never allowed to replace the call argument to an intrinsic, but it
3285  // may be possible for a call.
3286  return !isa<IntrinsicInst>(CB);
3287  }
3288  case Instruction::ShuffleVector:
3289  // Shufflevector masks are constant.
3290  return OpIdx != 2;
3291  case Instruction::Switch:
3292  case Instruction::ExtractValue:
3293  // All operands apart from the first are constant.
3294  return OpIdx == 0;
3295  case Instruction::InsertValue:
3296  // All operands apart from the first and the second are constant.
3297  return OpIdx < 2;
3298  case Instruction::Alloca:
3299  // Static allocas (constant size in the entry block) are handled by
3300  // prologue/epilogue insertion so they're free anyway. We definitely don't
3301  // want to make them non-constant.
3302  return !cast<AllocaInst>(I)->isStaticAlloca();
3303  case Instruction::GetElementPtr:
3304  if (OpIdx == 0)
3305  return true;
3307  for (auto E = std::next(It, OpIdx); It != E; ++It)
3308  if (It.isStruct())
3309  return false;
3310  return true;
3311  }
3312 }
3313 
3315  // First: Check if it's a constant
3316  if (Constant *C = dyn_cast<Constant>(Condition))
3317  return ConstantExpr::getNot(C);
3318 
3319  // Second: If the condition is already inverted, return the original value
3320  Value *NotCondition;
3321  if (match(Condition, m_Not(m_Value(NotCondition))))
3322  return NotCondition;
3323 
3324  BasicBlock *Parent = nullptr;
3325  Instruction *Inst = dyn_cast<Instruction>(Condition);
3326  if (Inst)
3327  Parent = Inst->getParent();
3328  else if (Argument *Arg = dyn_cast<Argument>(Condition))
3329  Parent = &Arg->getParent()->getEntryBlock();
3330  assert(Parent && "Unsupported condition to invert");
3331 
3332  // Third: Check all the users for an invert
3333  for (User *U : Condition->users())
3334  if (Instruction *I = dyn_cast<Instruction>(U))
3335  if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
3336  return I;
3337 
3338  // Last option: Create a new instruction
3339  auto *Inverted =
3340  BinaryOperator::CreateNot(Condition, Condition->getName() + ".inv");
3341  if (Inst && !isa<PHINode>(Inst))
3342  Inverted->insertAfter(Inst);
3343  else
3344  Inverted->insertBefore(&*Parent->getFirstInsertionPt());
3345  return Inverted;
3346 }
3347 
3349  // Note: We explicitly check for attributes rather than using cover functions
3350  // because some of the cover functions include the logic being implemented.
3351 
3352  bool Changed = false;
3353  // readnone + not convergent implies nosync
3354  if (!F.hasFnAttribute(Attribute::NoSync) &&
3355  F.doesNotAccessMemory() && !F.isConvergent()) {
3356  F.setNoSync();
3357  Changed = true;
3358  }
3359 
3360  // readonly implies nofree
3361  if (!F.hasFnAttribute(Attribute::NoFree) && F.onlyReadsMemory()) {
3362  F.setDoesNotFreeMemory();
3363  Changed = true;
3364  }
3365 
3366  // willreturn implies mustprogress
3367  if (!F.hasFnAttribute(Attribute::MustProgress) && F.willReturn()) {
3368  F.setMustProgress();
3369  Changed = true;
3370  }
3371 
3372  // TODO: There are a bunch of cases of restrictive memory effects we
3373  // can infer by inspecting arguments of argmemonly-ish functions.
3374 
3375  return Changed;
3376 }
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:1285
i
i
Definition: README.txt:29
llvm::InvokeInst::getNormalDest
BasicBlock * getNormalDest() const
Definition: Instructions.h:3845
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:2092
llvm::invertCondition
Value * invertCondition(Value *Condition)
Invert the given true/false value, possibly reusing an existing copy.
Definition: Local.cpp:3314
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:4630
llvm::CatchSwitchInst::Create
static CatchSwitchInst * Create(Value *ParentPad, BasicBlock *UnwindDest, unsigned NumHandlers, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4263
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:2488
llvm
---------------------— PointerInfo ------------------------------------—
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:365
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:3757
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::ConvertDebugDeclareToDebugValue
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
Definition: Local.cpp:1441
llvm::DIExpression::getNumLocationOperands
uint64_t getNumLocationOperands() const
Return the number of unique location operands referred to (via DW_OP_LLVM_arg) in this expression; th...
Definition: DebugInfoMetadata.cpp:1479
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:2672
Optional.h
ValueMapper.h
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::BasicBlock::getFirstNonPHIOrDbg
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=false) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:219
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:1336
Metadata.h
replaceOneDbgValueForAlloca
static void replaceOneDbgValueForAlloca(DbgValueInst *DVI, Value *NewAddress, DIBuilder &Builder, int Offset)
Definition: Local.cpp:1694
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h: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:228
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
MemorySSAUpdater.h
llvm::Function
Definition: Function.h:61
llvm::callsGCLeafFunction
bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)
Return true if this call calls a gc leaf function.
Definition: Local.cpp:2720
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:2620
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:5164
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::RegState::Undef
@ Undef
Value of the register doesn't matter.
Definition: MachineInstrBuilder.h:52
llvm::replaceNonLocalUsesWith
unsigned replaceNonLocalUsesWith(Instruction *From, Value *To)
Definition: Local.cpp:2685
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:1643
llvm::Value::hasName
bool hasName() const
Definition: Value.h:262
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:9779
llvm::dropDebugUsers
void dropDebugUsers(Instruction &I)
Remove the debug intrinsic instructions for the given instruction.
Definition: Local.cpp:2792
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:1372
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:306
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:34
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1562
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:2451
Module.h
llvm::BasicBlock::eraseFromParent
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
Definition: BasicBlock.cpp:129
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:1468
getDwarfOpForBinOp
uint64_t getDwarfOpForBinOp(Instruction::BinaryOps Opcode)
Definition: Local.cpp:1822
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
getSalvageOpsForBinOp
bool getSalvageOpsForBinOp(BinaryOperator *BI, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1852
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
getSalvageOpsForGEP
bool getSalvageOpsForGEP(GetElementPtrInst *GEP, const DataLayout &DL, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
Definition: Local.cpp:1796
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
T
#define T
Definition: Mips16ISelLowering.cpp:341
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:264
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:3132
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:2557
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:1699
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:2696
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:1637
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:2569
endif
__FakeVCSRevision h endif() endif() set(generated_files "$
Definition: CMakeLists.txt:16
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
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:122
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1198
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:1728
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:224
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1108
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:1313
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:225
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:1954
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:1547
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:1301
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:1421
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::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2693
llvm::Value::use_iterator
use_iterator_impl< Use > use_iterator
Definition: Value.h:354
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:1949
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:3053
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:2207
llvm::CleanupReturnInst::Create
static CleanupReturnInst * Create(Value *CleanupPad, BasicBlock *UnwindBB=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:4590
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1393
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1472
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:3241
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:2193
llvm::DomTreeUpdater::recalculate
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
Definition: DomTreeUpdater.cpp:120
TargetLibraryInfo.h
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:237
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:377
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:249
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:3348
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:2089
llvm::PHINode::getIncomingValueForBlock
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: Instructions.h:2782
llvm::TargetLibraryInfo::getLibFunc
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
Definition: TargetLibraryInfo.h:289
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:198
llvm::Instruction
Definition: Instruction.h:45
replaceDominatedUsesWith
static unsigned replaceDominatedUsesWith(Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates)
Definition: Local.cpp:2666
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:153
bitTransformIsCorrectForBSwap
static bool bitTransformIsCorrectForBSwap(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:3110
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:6246
MDBuilder.h
isStructure
static bool isStructure(AllocaInst *AI)
Determine whether this alloca is a structure.
Definition: Local.cpp:1534
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1631
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:2774
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1784
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:899
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
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:212
bitTransformIsCorrectForBitReverse
static bool bitTransformIsCorrectForBitReverse(unsigned From, unsigned To, unsigned BitWidth)
Definition: Local.cpp:3121
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:1449
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::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2689
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:345
Type.h
llvm::APInt::isAllOnesValue
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:401
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::salvageDebugInfoImpl
DIExpression * salvageDebugInfoImpl(Instruction &I, DIExpression *DIExpr, bool StackVal, unsigned LocNo, SmallVectorImpl< Value * > &AdditionalValues)
Given an instruction I and DIExpression DIExpr operating on it, write the effects of I into the retur...
Definition: Local.cpp:1893
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:3713
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:1381
llvm::BasicBlock::isEntryBlock
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
Definition: BasicBlock.cpp:375
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:201
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:1102
llvm::isMathLibCallNoop
bool isMathLibCallNoop(const CallBase *Call, const TargetLibraryInfo *TLI)
Check whether the given call has no side-effects.
Definition: ConstantFolding.cpp:3180
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:2749
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:2582
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
llvm::Use::set
void set(Value *Val)
Definition: Value.h:860
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:2412
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:7542
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
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:1567
llvm::MemorySSAUpdater::changeToUnreachable
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
Definition: MemorySSAUpdater.cpp:1408
llvm::DbgLabelInst
This represents the llvm.dbg.label instruction.
Definition: IntrinsicInst.h:370
llvm::Type::isIntOrPtrTy
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
Definition: Type.h:216
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:1770
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2747
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:3088
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:443
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:572
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:1614
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1612
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:369
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:2799
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:1734
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:323
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:897
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:2702
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:2034
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:2197
llvm::PHINode::block_begin
block_iterator block_begin()
Definition: Instructions.h:2659
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:651
llvm::DIVariable::getSignedness
Optional< DIBasicType::Signedness > getSignedness() const
Return the signedness of this variable's type, or None if this type is neither signed nor unsigned.
Definition: DebugInfoMetadata.h:2513
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:70
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
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:673
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:99
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:398
llvm::BinaryOperator
Definition: InstrTypes.h:189
None.h
llvm::APInt::getAllOnesValue
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:567
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:1554
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:138
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:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
uint32_t
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:979
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:1378
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:3126
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:3231
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:297
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:148
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:2016
isArray
static bool isArray(AllocaInst *AI)
Determine whether this alloca is either a VLA or an array.
Definition: Local.cpp:1528
llvm::APInt::clearBit
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1525
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:675
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:1717
llvm::MapVector::end
iterator end()
Definition: MapVector.h:71
Argument.h
llvm::PHINode::block_end
block_iterator block_end()
Definition: Instructions.h:2667
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:32
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:1217
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:1524
llvm::KnownBits
Definition: KnownBits.h:23
llvm::Type::getIntNTy
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:207
llvm::Value::user_iterator
user_iterator_impl< User > user_iterator
Definition: Value.h:391
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:33
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:2890
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2678
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:207
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::Value::MaxAlignmentExponent
static const unsigned MaxAlignmentExponent
The maximum alignment for instructions.
Definition: Value.h:784
llvm::TypeSize
Definition: TypeSize.h:417
Casting.h
markAliveBlocks
static bool markAliveBlocks(Function &F, SmallPtrSetImpl< BasicBlock * > &Reachable, DomTreeUpdater *DTU=nullptr)
Definition: Local.cpp:2239
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:1728
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:219
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:663
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:394
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:1516
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::CallBase::getCalledOperand
Value * getCalledOperand() const
Definition: InstrTypes.h:1386
llvm::LowerDbgDeclare
bool LowerDbgDeclare(Function &F)
Lowers llvm.dbg.declare intrinsics into appropriate set of llvm.dbg.value intrinsics.
Definition: Local.cpp:1540
llvm::replaceDbgUsesWithUndef
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in @llvm.dbg intrinsics with undef.
Definition: Local.cpp: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:4439
llvm::AttributeList::FunctionIndex
@ FunctionIndex
Definition: Attributes.h:402
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:787
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:2113
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:222
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:372
User.h
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:604
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:2178
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:482
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:1822
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2713
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::PHINode
Definition: Instructions.h:2597
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:321
llvm::SmallVectorImpl< WeakTrackingVH >
llvm::CallBase::addAttribute
void addAttribute(unsigned i, Attribute::AttrKind Kind)
adds the attribute to the list of attributes.
Definition: InstrTypes.h:1489
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:4679
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:338
llvm::createCallMatchingInvoke
CallInst * createCallMatchingInvoke(InvokeInst *II)
Create a call that matches the invoke II in terms of arguments, attributes, debug information,...
Definition: Local.cpp:2152
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:2633
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:370
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:414
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:3032
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:1925
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:2564
BasicBlockUtils.h
llvm::replaceDbgDeclare
bool replaceDbgDeclare(Value *Address, Value *NewAddress, DIBuilder &Builder, uint8_t DIExprFlags, int Offset)
Replaces llvm.dbg.declare instruction when the address it describes is replaced with a new value.
Definition: Local.cpp:1676
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:814
Value.h
llvm::InvokeInst::getUnwindDest
BasicBlock * getUnwindDest() const
Definition: Instructions.h:3848
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:75
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:634
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
PHICSEDebugHash
static cl::opt< bool > PHICSEDebugHash("phicse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that PHINodes's hash " "function is well-behaved w.r.t. its isEqual predicate"))
getDebugValueLoc
static DebugLoc getDebugValueLoc(DbgVariableIntrinsic *DII, Instruction *Src)
Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted to a dbg....
Definition: Local.cpp:1430
llvm::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:487
llvm::MemorySSAUpdater::removeMemoryAccess
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Definition: MemorySSAUpdater.cpp:1305
SetVector.h
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1453
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:128
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:773