LLVM  16.0.0git
SCCP.cpp
Go to the documentation of this file.
1 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
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 file implements sparse conditional constant propagation and merging:
10 //
11 // Specifically, this:
12 // * Assumes values are constant unless proven otherwise
13 // * Assumes BasicBlocks are dead unless proven otherwise
14 // * Proves values to be constant, and replaces them with constants
15 // * Proves conditional branches to be unconditional
16 //
17 //===----------------------------------------------------------------------===//
18 
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/MapVector.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"
33 #include "llvm/IR/BasicBlock.h"
34 #include "llvm/IR/Constant.h"
35 #include "llvm/IR/Constants.h"
36 #include "llvm/IR/DerivedTypes.h"
37 #include "llvm/IR/Function.h"
38 #include "llvm/IR/GlobalVariable.h"
39 #include "llvm/IR/InstrTypes.h"
40 #include "llvm/IR/Instruction.h"
41 #include "llvm/IR/Instructions.h"
42 #include "llvm/IR/IntrinsicInst.h"
43 #include "llvm/IR/Module.h"
44 #include "llvm/IR/PassManager.h"
45 #include "llvm/IR/Type.h"
46 #include "llvm/IR/User.h"
47 #include "llvm/IR/Value.h"
48 #include "llvm/InitializePasses.h"
49 #include "llvm/Pass.h"
50 #include "llvm/Support/Casting.h"
51 #include "llvm/Support/Debug.h"
54 #include "llvm/Transforms/Scalar.h"
57 #include <cassert>
58 #include <utility>
59 #include <vector>
60 
61 using namespace llvm;
62 
63 #define DEBUG_TYPE "sccp"
64 
65 STATISTIC(NumInstRemoved, "Number of instructions removed");
66 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
67 STATISTIC(NumInstReplaced,
68  "Number of instructions replaced with (simpler) instruction");
69 
70 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
71 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
72 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
73 STATISTIC(
74  IPNumInstReplaced,
75  "Number of instructions replaced with (simpler) instruction by IPSCCP");
76 
77 // Helper to check if \p LV is either a constant or a constant
78 // range with a single element. This should cover exactly the same cases as the
79 // old ValueLatticeElement::isConstant() and is intended to be used in the
80 // transition to ValueLatticeElement.
81 static bool isConstant(const ValueLatticeElement &LV) {
82  return LV.isConstant() ||
84 }
85 
86 // Helper to check if \p LV is either overdefined or a constant range with more
87 // than a single element. This should cover exactly the same cases as the old
88 // ValueLatticeElement::isOverdefined() and is intended to be used in the
89 // transition to ValueLatticeElement.
90 static bool isOverdefined(const ValueLatticeElement &LV) {
91  return !LV.isUnknownOrUndef() && !isConstant(LV);
92 }
93 
96  return true;
97 
98  // Some instructions can be handled but are rejected above. Catch
99  // those cases by falling through to here.
100  // TODO: Mark globals as being constant earlier, so
101  // TODO: wouldInstructionBeTriviallyDead() knows that atomic loads
102  // TODO: are safe to remove.
103  return isa<LoadInst>(I);
104 }
105 
106 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
107  Constant *Const = nullptr;
108  if (V->getType()->isStructTy()) {
109  std::vector<ValueLatticeElement> IVs = Solver.getStructLatticeValueFor(V);
110  if (llvm::any_of(IVs, isOverdefined))
111  return false;
112  std::vector<Constant *> ConstVals;
113  auto *ST = cast<StructType>(V->getType());
114  for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
115  ValueLatticeElement V = IVs[i];
116  ConstVals.push_back(isConstant(V)
117  ? Solver.getConstant(V)
118  : UndefValue::get(ST->getElementType(i)));
119  }
120  Const = ConstantStruct::get(ST, ConstVals);
121  } else {
122  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
123  if (isOverdefined(IV))
124  return false;
125 
126  Const =
127  isConstant(IV) ? Solver.getConstant(IV) : UndefValue::get(V->getType());
128  }
129  assert(Const && "Constant is nullptr here!");
130 
131  // Replacing `musttail` instructions with constant breaks `musttail` invariant
132  // unless the call itself can be removed.
133  // Calls with "clang.arc.attachedcall" implicitly use the return value and
134  // those uses cannot be updated with a constant.
135  CallBase *CB = dyn_cast<CallBase>(V);
136  if (CB && ((CB->isMustTailCall() &&
137  !canRemoveInstruction(CB)) ||
139  Function *F = CB->getCalledFunction();
140 
141  // Don't zap returns of the callee
142  if (F)
144 
145  LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB
146  << " as a constant\n");
147  return false;
148  }
149 
150  LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');
151 
152  // Replaces all of the uses of a variable with uses of the constant.
153  V->replaceAllUsesWith(Const);
154  return true;
155 }
156 
157 /// Try to replace signed instructions with their unsigned equivalent.
158 static bool replaceSignedInst(SCCPSolver &Solver,
159  SmallPtrSetImpl<Value *> &InsertedValues,
160  Instruction &Inst) {
161  // Determine if a signed value is known to be >= 0.
162  auto isNonNegative = [&Solver](Value *V) {
163  // If this value was constant-folded, it may not have a solver entry.
164  // Handle integers. Otherwise, return false.
165  if (auto *C = dyn_cast<Constant>(V)) {
166  auto *CInt = dyn_cast<ConstantInt>(C);
167  return CInt && !CInt->isNegative();
168  }
169  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
170  return IV.isConstantRange(/*UndefAllowed=*/false) &&
171  IV.getConstantRange().isAllNonNegative();
172  };
173 
174  Instruction *NewInst = nullptr;
175  switch (Inst.getOpcode()) {
176  // Note: We do not fold sitofp -> uitofp here because that could be more
177  // expensive in codegen and may not be reversible in the backend.
178  case Instruction::SExt: {
179  // If the source value is not negative, this is a zext.
180  Value *Op0 = Inst.getOperand(0);
181  if (InsertedValues.count(Op0) || !isNonNegative(Op0))
182  return false;
183  NewInst = new ZExtInst(Op0, Inst.getType(), "", &Inst);
184  break;
185  }
186  case Instruction::AShr: {
187  // If the shifted value is not negative, this is a logical shift right.
188  Value *Op0 = Inst.getOperand(0);
189  if (InsertedValues.count(Op0) || !isNonNegative(Op0))
190  return false;
191  NewInst = BinaryOperator::CreateLShr(Op0, Inst.getOperand(1), "", &Inst);
192  break;
193  }
194  case Instruction::SDiv:
195  case Instruction::SRem: {
196  // If both operands are not negative, this is the same as udiv/urem.
197  Value *Op0 = Inst.getOperand(0), *Op1 = Inst.getOperand(1);
198  if (InsertedValues.count(Op0) || InsertedValues.count(Op1) ||
199  !isNonNegative(Op0) || !isNonNegative(Op1))
200  return false;
201  auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv
202  : Instruction::URem;
203  NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", &Inst);
204  break;
205  }
206  default:
207  return false;
208  }
209 
210  // Wire up the new instruction and update state.
211  assert(NewInst && "Expected replacement instruction");
212  NewInst->takeName(&Inst);
213  InsertedValues.insert(NewInst);
214  Inst.replaceAllUsesWith(NewInst);
215  Solver.removeLatticeValueFor(&Inst);
216  Inst.eraseFromParent();
217  return true;
218 }
219 
221  SmallPtrSetImpl<Value *> &InsertedValues,
222  Statistic &InstRemovedStat,
223  Statistic &InstReplacedStat) {
224  bool MadeChanges = false;
225  for (Instruction &Inst : make_early_inc_range(BB)) {
226  if (Inst.getType()->isVoidTy())
227  continue;
228  if (tryToReplaceWithConstant(Solver, &Inst)) {
229  if (canRemoveInstruction(&Inst))
230  Inst.eraseFromParent();
231 
232  MadeChanges = true;
233  ++InstRemovedStat;
234  } else if (replaceSignedInst(Solver, InsertedValues, Inst)) {
235  MadeChanges = true;
236  ++InstReplacedStat;
237  }
238  }
239  return MadeChanges;
240 }
241 
242 static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
243  DomTreeUpdater &DTU,
244  BasicBlock *&NewUnreachableBB);
245 
246 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
247 // and return true if the function was modified.
248 static bool runSCCP(Function &F, const DataLayout &DL,
249  const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) {
250  LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
251  SCCPSolver Solver(
252  DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
253  F.getContext());
254 
255  // Mark the first block of the function as being executable.
256  Solver.markBlockExecutable(&F.front());
257 
258  // Mark all arguments to the function as being overdefined.
259  for (Argument &AI : F.args())
260  Solver.markOverdefined(&AI);
261 
262  // Solve for constants.
263  bool ResolvedUndefs = true;
264  while (ResolvedUndefs) {
265  Solver.solve();
266  LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
267  ResolvedUndefs = Solver.resolvedUndefsIn(F);
268  }
269 
270  bool MadeChanges = false;
271 
272  // If we decided that there are basic blocks that are dead in this function,
273  // delete their contents now. Note that we cannot actually delete the blocks,
274  // as we cannot modify the CFG of the function.
275 
276  SmallPtrSet<Value *, 32> InsertedValues;
277  SmallVector<BasicBlock *, 8> BlocksToErase;
278  for (BasicBlock &BB : F) {
279  if (!Solver.isBlockExecutable(&BB)) {
280  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
281  ++NumDeadBlocks;
282  BlocksToErase.push_back(&BB);
283  MadeChanges = true;
284  continue;
285  }
286 
287  MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
288  NumInstRemoved, NumInstReplaced);
289  }
290 
291  // Remove unreachable blocks and non-feasible edges.
292  for (BasicBlock *DeadBB : BlocksToErase)
293  NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(),
294  /*PreserveLCSSA=*/false, &DTU);
295 
296  BasicBlock *NewUnreachableBB = nullptr;
297  for (BasicBlock &BB : F)
298  MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU, NewUnreachableBB);
299 
300  for (BasicBlock *DeadBB : BlocksToErase)
301  if (!DeadBB->hasAddressTaken())
302  DTU.deleteBB(DeadBB);
303 
304  return MadeChanges;
305 }
306 
308  const DataLayout &DL = F.getParent()->getDataLayout();
309  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
310  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
312  if (!runSCCP(F, DL, &TLI, DTU))
313  return PreservedAnalyses::all();
314 
315  auto PA = PreservedAnalyses();
316  PA.preserve<DominatorTreeAnalysis>();
317  return PA;
318 }
319 
320 namespace {
321 
322 //===--------------------------------------------------------------------===//
323 //
324 /// SCCP Class - This class uses the SCCPSolver to implement a per-function
325 /// Sparse Conditional Constant Propagator.
326 ///
327 class SCCPLegacyPass : public FunctionPass {
328 public:
329  // Pass identification, replacement for typeid
330  static char ID;
331 
332  SCCPLegacyPass() : FunctionPass(ID) {
334  }
335 
336  void getAnalysisUsage(AnalysisUsage &AU) const override {
340  }
341 
342  // runOnFunction - Run the Sparse Conditional Constant Propagation
343  // algorithm, and return true if the function was modified.
344  bool runOnFunction(Function &F) override {
345  if (skipFunction(F))
346  return false;
347  const DataLayout &DL = F.getParent()->getDataLayout();
348  const TargetLibraryInfo *TLI =
349  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
350  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
351  DomTreeUpdater DTU(DTWP ? &DTWP->getDomTree() : nullptr,
353  return runSCCP(F, DL, TLI, DTU);
354  }
355 };
356 
357 } // end anonymous namespace
358 
359 char SCCPLegacyPass::ID = 0;
360 
361 INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp",
362  "Sparse Conditional Constant Propagation", false, false)
364 INITIALIZE_PASS_END(SCCPLegacyPass, "sccp",
365  "Sparse Conditional Constant Propagation", false, false)
366 
367 // createSCCPPass - This is the public interface to this file.
368 FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); }
369 
371  SmallVector<ReturnInst *, 8> &ReturnsToZap,
372  SCCPSolver &Solver) {
373  // We can only do this if we know that nothing else can call the function.
374  if (!Solver.isArgumentTrackedFunction(&F))
375  return;
376 
377  if (Solver.mustPreserveReturn(&F)) {
378  LLVM_DEBUG(
379  dbgs()
380  << "Can't zap returns of the function : " << F.getName()
381  << " due to present musttail or \"clang.arc.attachedcall\" call of "
382  "it\n");
383  return;
384  }
385 
386  assert(
387  all_of(F.users(),
388  [&Solver](User *U) {
389  if (isa<Instruction>(U) &&
390  !Solver.isBlockExecutable(cast<Instruction>(U)->getParent()))
391  return true;
392  // Non-callsite uses are not impacted by zapping. Also, constant
393  // uses (like blockaddresses) could stuck around, without being
394  // used in the underlying IR, meaning we do not have lattice
395  // values for them.
396  if (!isa<CallBase>(U))
397  return true;
398  if (U->getType()->isStructTy()) {
399  return all_of(Solver.getStructLatticeValueFor(U),
400  [](const ValueLatticeElement &LV) {
401  return !isOverdefined(LV);
402  });
403  }
404  return !isOverdefined(Solver.getLatticeValueFor(U));
405  }) &&
406  "We can only zap functions where all live users have a concrete value");
407 
408  for (BasicBlock &BB : F) {
409  if (CallInst *CI = BB.getTerminatingMustTailCall()) {
410  LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
411  << "musttail call : " << *CI << "\n");
412  (void)CI;
413  return;
414  }
415 
416  if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
417  if (!isa<UndefValue>(RI->getOperand(0)))
418  ReturnsToZap.push_back(RI);
419  }
420 }
421 
422 static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
423  DomTreeUpdater &DTU,
424  BasicBlock *&NewUnreachableBB) {
425  SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
426  bool HasNonFeasibleEdges = false;
427  for (BasicBlock *Succ : successors(BB)) {
428  if (Solver.isEdgeFeasible(BB, Succ))
429  FeasibleSuccessors.insert(Succ);
430  else
431  HasNonFeasibleEdges = true;
432  }
433 
434  // All edges feasible, nothing to do.
435  if (!HasNonFeasibleEdges)
436  return false;
437 
438  // SCCP can only determine non-feasible edges for br, switch and indirectbr.
439  Instruction *TI = BB->getTerminator();
440  assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
441  isa<IndirectBrInst>(TI)) &&
442  "Terminator must be a br, switch or indirectbr");
443 
444  if (FeasibleSuccessors.size() == 0) {
445  // Branch on undef/poison, replace with unreachable.
448  for (BasicBlock *Succ : successors(BB)) {
449  Succ->removePredecessor(BB);
450  if (SeenSuccs.insert(Succ).second)
451  Updates.push_back({DominatorTree::Delete, BB, Succ});
452  }
453  TI->eraseFromParent();
454  new UnreachableInst(BB->getContext(), BB);
455  DTU.applyUpdatesPermissive(Updates);
456  } else if (FeasibleSuccessors.size() == 1) {
457  // Replace with an unconditional branch to the only feasible successor.
458  BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
460  bool HaveSeenOnlyFeasibleSuccessor = false;
461  for (BasicBlock *Succ : successors(BB)) {
462  if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
463  // Don't remove the edge to the only feasible successor the first time
464  // we see it. We still do need to remove any multi-edges to it though.
465  HaveSeenOnlyFeasibleSuccessor = true;
466  continue;
467  }
468 
469  Succ->removePredecessor(BB);
470  Updates.push_back({DominatorTree::Delete, BB, Succ});
471  }
472 
473  BranchInst::Create(OnlyFeasibleSuccessor, BB);
474  TI->eraseFromParent();
475  DTU.applyUpdatesPermissive(Updates);
476  } else if (FeasibleSuccessors.size() > 1) {
477  SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));
479 
480  // If the default destination is unfeasible it will never be taken. Replace
481  // it with a new block with a single Unreachable instruction.
482  BasicBlock *DefaultDest = SI->getDefaultDest();
483  if (!FeasibleSuccessors.contains(DefaultDest)) {
484  if (!NewUnreachableBB) {
485  NewUnreachableBB =
486  BasicBlock::Create(DefaultDest->getContext(), "default.unreachable",
487  DefaultDest->getParent(), DefaultDest);
488  new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB);
489  }
490 
491  SI->setDefaultDest(NewUnreachableBB);
492  Updates.push_back({DominatorTree::Delete, BB, DefaultDest});
493  Updates.push_back({DominatorTree::Insert, BB, NewUnreachableBB});
494  }
495 
496  for (auto CI = SI->case_begin(); CI != SI->case_end();) {
497  if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
498  ++CI;
499  continue;
500  }
501 
502  BasicBlock *Succ = CI->getCaseSuccessor();
503  Succ->removePredecessor(BB);
504  Updates.push_back({DominatorTree::Delete, BB, Succ});
505  SI.removeCase(CI);
506  // Don't increment CI, as we removed a case.
507  }
508 
509  DTU.applyUpdatesPermissive(Updates);
510  } else {
511  llvm_unreachable("Must have at least one feasible successor");
512  }
513  return true;
514 }
515 
517  Module &M, const DataLayout &DL,
518  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
519  function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
520  SCCPSolver Solver(DL, GetTLI, M.getContext());
521 
522  // Loop over all functions, marking arguments to those with their addresses
523  // taken or that are external as overdefined.
524  for (Function &F : M) {
525  if (F.isDeclaration())
526  continue;
527 
528  Solver.addAnalysis(F, getAnalysis(F));
529 
530  // Determine if we can track the function's return values. If so, add the
531  // function to the solver's set of return-tracked functions.
533  Solver.addTrackedFunction(&F);
534 
535  // Determine if we can track the function's arguments. If so, add the
536  // function to the solver's set of argument-tracked functions.
538  Solver.addArgumentTrackedFunction(&F);
539  continue;
540  }
541 
542  // Assume the function is called.
543  Solver.markBlockExecutable(&F.front());
544 
545  // Assume nothing about the incoming arguments.
546  for (Argument &AI : F.args())
547  Solver.markOverdefined(&AI);
548  }
549 
550  // Determine if we can track any of the module's global variables. If so, add
551  // the global variables we can track to the solver's set of tracked global
552  // variables.
553  for (GlobalVariable &G : M.globals()) {
554  G.removeDeadConstantUsers();
556  Solver.trackValueOfGlobalVariable(&G);
557  }
558 
559  // Solve for constants.
560  bool ResolvedUndefs = true;
561  Solver.solve();
562  while (ResolvedUndefs) {
563  LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
564  ResolvedUndefs = false;
565  for (Function &F : M) {
566  if (Solver.resolvedUndefsIn(F))
567  ResolvedUndefs = true;
568  }
569  if (ResolvedUndefs)
570  Solver.solve();
571  }
572 
573  bool MadeChanges = false;
574 
575  // Iterate over all of the instructions in the module, replacing them with
576  // constants if we have found them to be of constant values.
577 
578  for (Function &F : M) {
579  if (F.isDeclaration())
580  continue;
581 
582  SmallVector<BasicBlock *, 512> BlocksToErase;
583 
584  if (Solver.isBlockExecutable(&F.front())) {
585  bool ReplacedPointerArg = false;
586  for (Argument &Arg : F.args()) {
587  if (!Arg.use_empty() && tryToReplaceWithConstant(Solver, &Arg)) {
588  ReplacedPointerArg |= Arg.getType()->isPointerTy();
589  ++IPNumArgsElimed;
590  }
591  }
592 
593  // If we replaced an argument, we may now also access a global (currently
594  // classified as "other" memory). Update memory attribute to reflect this.
595  if (ReplacedPointerArg) {
596  auto UpdateAttrs = [&](AttributeList AL) {
597  MemoryEffects ME = AL.getMemoryEffects();
598  if (ME == MemoryEffects::unknown())
599  return AL;
600 
602  ME.getModRef(MemoryEffects::ArgMem));
603  return AL.addFnAttribute(
604  F.getContext(),
605  Attribute::getWithMemoryEffects(F.getContext(), ME));
606  };
607 
608  F.setAttributes(UpdateAttrs(F.getAttributes()));
609  for (User *U : F.users()) {
610  auto *CB = dyn_cast<CallBase>(U);
611  if (!CB || CB->getCalledFunction() != &F)
612  continue;
613 
614  CB->setAttributes(UpdateAttrs(CB->getAttributes()));
615  }
616  }
617  MadeChanges |= ReplacedPointerArg;
618  }
619 
620  SmallPtrSet<Value *, 32> InsertedValues;
621  for (BasicBlock &BB : F) {
622  if (!Solver.isBlockExecutable(&BB)) {
623  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
624  ++NumDeadBlocks;
625 
626  MadeChanges = true;
627 
628  if (&BB != &F.front())
629  BlocksToErase.push_back(&BB);
630  continue;
631  }
632 
633  MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
634  IPNumInstRemoved, IPNumInstReplaced);
635  }
636 
637  DomTreeUpdater DTU = Solver.getDTU(F);
638  // Change dead blocks to unreachable. We do it after replacing constants
639  // in all executable blocks, because changeToUnreachable may remove PHI
640  // nodes in executable blocks we found values for. The function's entry
641  // block is not part of BlocksToErase, so we have to handle it separately.
642  for (BasicBlock *BB : BlocksToErase) {
643  NumInstRemoved += changeToUnreachable(BB->getFirstNonPHI(),
644  /*PreserveLCSSA=*/false, &DTU);
645  }
646  if (!Solver.isBlockExecutable(&F.front()))
647  NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
648  /*PreserveLCSSA=*/false, &DTU);
649 
650  BasicBlock *NewUnreachableBB = nullptr;
651  for (BasicBlock &BB : F)
652  MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU, NewUnreachableBB);
653 
654  for (BasicBlock *DeadBB : BlocksToErase)
655  if (!DeadBB->hasAddressTaken())
656  DTU.deleteBB(DeadBB);
657 
658  for (BasicBlock &BB : F) {
659  for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
660  if (Solver.getPredicateInfoFor(&Inst)) {
661  if (auto *II = dyn_cast<IntrinsicInst>(&Inst)) {
662  if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
663  Value *Op = II->getOperand(0);
664  Inst.replaceAllUsesWith(Op);
665  Inst.eraseFromParent();
666  }
667  }
668  }
669  }
670  }
671  }
672 
673  // If we inferred constant or undef return values for a function, we replaced
674  // all call uses with the inferred value. This means we don't need to bother
675  // actually returning anything from the function. Replace all return
676  // instructions with return undef.
677  //
678  // Do this in two stages: first identify the functions we should process, then
679  // actually zap their returns. This is important because we can only do this
680  // if the address of the function isn't taken. In cases where a return is the
681  // last use of a function, the order of processing functions would affect
682  // whether other functions are optimizable.
683  SmallVector<ReturnInst*, 8> ReturnsToZap;
684 
685  for (const auto &I : Solver.getTrackedRetVals()) {
686  Function *F = I.first;
687  const ValueLatticeElement &ReturnValue = I.second;
688 
689  // If there is a known constant range for the return value, add !range
690  // metadata to the function's call sites.
691  if (ReturnValue.isConstantRange() &&
692  !ReturnValue.getConstantRange().isSingleElement()) {
693  // Do not add range metadata if the return value may include undef.
694  if (ReturnValue.isConstantRangeIncludingUndef())
695  continue;
696 
697  auto &CR = ReturnValue.getConstantRange();
698  for (User *User : F->users()) {
699  auto *CB = dyn_cast<CallBase>(User);
700  if (!CB || CB->getCalledFunction() != F)
701  continue;
702 
703  // Limit to cases where the return value is guaranteed to be neither
704  // poison nor undef. Poison will be outside any range and currently
705  // values outside of the specified range cause immediate undefined
706  // behavior.
707  if (!isGuaranteedNotToBeUndefOrPoison(CB, nullptr, CB))
708  continue;
709 
710  // Do not touch existing metadata for now.
711  // TODO: We should be able to take the intersection of the existing
712  // metadata and the inferred range.
713  if (CB->getMetadata(LLVMContext::MD_range))
714  continue;
715 
716  LLVMContext &Context = CB->getParent()->getContext();
717  Metadata *RangeMD[] = {
720  CB->setMetadata(LLVMContext::MD_range, MDNode::get(Context, RangeMD));
721  }
722  continue;
723  }
724  if (F->getReturnType()->isVoidTy())
725  continue;
726  if (isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef())
727  findReturnsToZap(*F, ReturnsToZap, Solver);
728  }
729 
730  for (auto *F : Solver.getMRVFunctionsTracked()) {
731  assert(F->getReturnType()->isStructTy() &&
732  "The return type should be a struct");
733  StructType *STy = cast<StructType>(F->getReturnType());
734  if (Solver.isStructLatticeConstant(F, STy))
735  findReturnsToZap(*F, ReturnsToZap, Solver);
736  }
737 
738  // Zap all returns which we've identified as zap to change.
739  SmallSetVector<Function *, 8> FuncZappedReturn;
740  for (ReturnInst *RI : ReturnsToZap) {
741  Function *F = RI->getParent()->getParent();
742  RI->setOperand(0, UndefValue::get(F->getReturnType()));
743  // Record all functions that are zapped.
744  FuncZappedReturn.insert(F);
745  }
746 
747  // Remove the returned attribute for zapped functions and the
748  // corresponding call sites.
749  for (Function *F : FuncZappedReturn) {
750  for (Argument &A : F->args())
751  F->removeParamAttr(A.getArgNo(), Attribute::Returned);
752  for (Use &U : F->uses()) {
753  // Skip over blockaddr users.
754  if (isa<BlockAddress>(U.getUser()))
755  continue;
756  CallBase *CB = cast<CallBase>(U.getUser());
757  for (Use &Arg : CB->args())
758  CB->removeParamAttr(CB->getArgOperandNo(&Arg), Attribute::Returned);
759  }
760  }
761 
762  // If we inferred constant or undef values for globals variables, we can
763  // delete the global and any stores that remain to it.
764  for (const auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {
765  GlobalVariable *GV = I.first;
766  if (isOverdefined(I.second))
767  continue;
768  LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
769  << "' is constant!\n");
770  while (!GV->use_empty()) {
771  StoreInst *SI = cast<StoreInst>(GV->user_back());
772  SI->eraseFromParent();
773  MadeChanges = true;
774  }
775  M.getGlobalList().erase(GV);
776  ++IPNumGlobalConst;
777  }
778 
779  return MadeChanges;
780 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
removeNonFeasibleEdges
static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB)
Definition: SCCP.cpp:422
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm::ValueLatticeElement::getConstantRange
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
Definition: ValueLattice.h:272
llvm::ValueLatticeElement::isConstant
bool isConstant() const
Definition: ValueLattice.h:243
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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::AArch64CC::AL
@ AL
Definition: AArch64BaseInfo.h:269
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:177
llvm::LLVMContext::OB_clang_arc_attachedcall
@ OB_clang_arc_attachedcall
Definition: LLVMContext.h:95
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3052
sccp
sccp
Definition: SCCP.cpp:364
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
Insert
Vector Rotate Left Mask Mask Insert
Definition: README_P9.txt:112
llvm::SwitchInstProfUpdateWrapper
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Definition: Instructions.h:3620
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Scalar.h
llvm::AnalysisResultsForFn
Helper struct for bundling up the analysis results per function for IPSCCP.
Definition: SCCPSolver.h:41
llvm::Function
Definition: Function.h:60
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1306
Pass.h
isConstant
static bool isConstant(const ValueLatticeElement &LV)
Definition: SCCP.cpp:81
llvm::SCCPSolver::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1574
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
function
function Propagate constant arguments by specializing the function
Definition: SCCP.cpp:198
ErrorHandling.h
SCCP.h
llvm::initializeSCCPLegacyPassPass
void initializeSCCPLegacyPassPass(PassRegistry &)
MapVector.h
DomTreeUpdater.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
ValueTracking.h
Local.h
GlobalsModRef.h
llvm::SCCPSolver::getConstant
Constant * getConstant(const ValueLatticeElement &LV) const
Helper to return a Constant if LV is either a constant or a constant range with a single element.
Definition: SCCPSolver.cpp:1606
DenseMap.h
Module.h
llvm::AttributeList
Definition: Attributes.h:430
llvm::CallBase::isMustTailCall
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: Instructions.cpp:300
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
isGuaranteedNotToBeUndefOrPoison
static bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC, const Instruction *CtxI, const DominatorTree *DT, unsigned Depth, bool PoisonOnly)
Definition: ValueTracking.cpp:5309
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::SCCPSolver::markBlockExecutable
bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
Definition: SCCPSolver.cpp:1521
STLExtras.h
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1551
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MemoryEffects
Summary of how a function affects memory in the program.
Definition: ModRef.h:63
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
Instruction.h
llvm::CallBase::removeParamAttr
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
Definition: InstrTypes.h:1569
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:164
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:1709
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::ValueLatticeElement::isUnknownOrUndef
bool isUnknownOrUndef() const
Definition: ValueLattice.h:242
Constants.h
llvm::SCCPSolver::markOverdefined
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
Definition: SCCPSolver.cpp:1600
llvm::User
Definition: User.h:44
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(IPSCCPLegacyPass, "ipsccp", "Interprocedural Sparse Conditional Constant Propagation", false, false) INITIALIZE_PASS_END(IPSCCPLegacyPass
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1397
llvm::SCCPSolver::isArgumentTrackedFunction
bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
Definition: SCCPSolver.cpp:1555
llvm::ValueLatticeElement::isConstantRangeIncludingUndef
bool isConstantRangeIncludingUndef() const
Definition: ValueLattice.h:245
llvm::ConstantRange::isSingleElement
bool isSingleElement() const
Return true if this set contains exactly one member.
Definition: ConstantRange.h:261
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Propagation
Interprocedural Sparse Conditional Constant Propagation
Definition: SCCP.cpp:106
TargetLibraryInfo.h
false
Definition: StackSlotColoring.cpp:141
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1517
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
canRemoveInstruction
static bool canRemoveInstruction(Instruction *I)
Definition: SCCP.cpp:94
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
tryToReplaceWithConstant
static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V)
Definition: SCCP.cpp:106
llvm::SCCPSolver::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:1602
SmallPtrSet.h
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
llvm::canTrackGlobalVariableInterprocedurally
bool canTrackGlobalVariableInterprocedurally(GlobalVariable *GV)
Determine if the value maintained in the given global variable can be tracked interprocedurally.
Definition: ValueLatticeUtils.cpp:27
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
Type.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::runIPSCCP
bool runIPSCCP(Module &M, const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, function_ref< AnalysisResultsForFn(Function &)> getAnalysis)
Definition: SCCP.cpp:516
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::Value::user_back
User * user_back()
Definition: Value.h:407
llvm::SCCPSolver::getTrackedRetVals
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
Definition: SCCPSolver.cpp:1587
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
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:415
BasicBlock.h
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1582
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
simplifyInstsInBlock
static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
Definition: SCCP.cpp:220
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:475
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::SCCPSolver::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:1525
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::MemoryEffects::getModRef
ModRefInfo getModRef(Location Loc) const
Get ModRefInfo for the given Location.
Definition: ModRef.h:164
llvm::SCCPPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SCCP.cpp:307
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:716
llvm::SCCPSolver
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:63
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:403
llvm::SCCPSolver::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
Definition: SCCPSolver.cpp:1592
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
runSCCP
static bool runSCCP(Function &F, const DataLayout &DL, const TargetLibraryInfo *TLI, DomTreeUpdater &DTU)
Definition: SCCP.cpp:248
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4850
llvm::createSCCPPass
FunctionPass * createSCCPPass()
Definition: SCCP.cpp:368
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::SCCPSolver::getDTU
DomTreeUpdater getDTU(Function &F)
Definition: SCCPSolver.cpp:1533
isOverdefined
static bool isOverdefined(const ValueLatticeElement &LV)
Definition: SCCP.cpp:90
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:1716
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::CallBase::getOperandBundle
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:2018
findReturnsToZap
static void findReturnsToZap(Function &F, SmallVector< ReturnInst *, 8 > &ReturnsToZap, SCCPSolver &Solver)
Definition: SCCP.cpp:370
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
A
* A
Definition: README_ALTIVEC.txt:89
llvm::binaryformat::unknown
@ unknown
Definition: Swift.h:18
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::SCCPSolver::removeLatticeValueFor
void removeLatticeValueFor(Value *V)
Definition: SCCPSolver.cpp:1578
llvm::ValueLatticeElement
This class represents lattice values for constants.
Definition: ValueLattice.h:29
llvm::SCCPSolver::mustPreserveReturn
bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
Definition: SCCPSolver.cpp:1547
llvm::TrackingStatistic
Definition: Statistic.h:50
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
ValueLatticeUtils.h
llvm::SCCPSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:1565
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:93
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1569
Constant.h
SCCPSolver.h
replaceSignedInst
static bool replaceSignedInst(SCCPSolver &Solver, SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
Try to replace signed instructions with their unsigned equivalent.
Definition: SCCP.cpp:158
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
GlobalVariable.h
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
Casting.h
Function.h
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
llvm::SCCPSolver::resolvedUndefsIn
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
Definition: SCCPSolver.cpp:1561
llvm::CallBase::getArgOperandNo
unsigned getArgOperandNo(const Use *U) const
Given a use for a arg operand, get the arg operand number that corresponds to it.
Definition: InstrTypes.h:1373
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
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:2216
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1543
Instructions.h
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:231
SmallVector.h
User.h
llvm::canTrackArgumentsInterprocedurally
bool canTrackArgumentsInterprocedurally(Function *F)
Determine if the values of the given function's arguments can be tracked interprocedurally.
Definition: ValueLatticeUtils.cpp:19
llvm::ValueLatticeElement::isConstantRange
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
Definition: ValueLattice.h:252
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:142
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:342
IV
static const uint32_t IV[8]
Definition: blake3_impl.h:85
llvm::SCCPSolver::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
Definition: SCCPSolver.cpp:1535
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
DerivedTypes.h
llvm::SmallPtrSetImpl< Value * >
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
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
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4771
llvm::SCCPSolver::solve
void solve()
Solve - Solve for constants and executable blocks.
Definition: SCCPSolver.cpp:1559
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
raw_ostream.h
llvm::SCCPSolver::addTrackedFunction
void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
Definition: SCCPSolver.cpp:1539
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
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:2936
Value.h
InitializePasses.h
ValueLattice.h
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:249
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
isNonNegative
static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:695
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:450
llvm::SCCPSolver::getMRVFunctionsTracked
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.
Definition: SCCPSolver.cpp:1596
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1333
SetVector.h
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1251
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::canTrackReturnsInterprocedurally
bool canTrackReturnsInterprocedurally(Function *F)
Determine if the values of the given function's returns can be tracked interprocedurally.
Definition: ValueLatticeUtils.cpp:23