LLVM  14.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/ArrayRef.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/MapVector.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/SetVector.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include "llvm/ADT/Statistic.h"
38 #include "llvm/IR/BasicBlock.h"
39 #include "llvm/IR/Constant.h"
40 #include "llvm/IR/Constants.h"
41 #include "llvm/IR/DataLayout.h"
42 #include "llvm/IR/DerivedTypes.h"
43 #include "llvm/IR/Function.h"
44 #include "llvm/IR/GlobalVariable.h"
45 #include "llvm/IR/InstVisitor.h"
46 #include "llvm/IR/InstrTypes.h"
47 #include "llvm/IR/Instruction.h"
48 #include "llvm/IR/Instructions.h"
49 #include "llvm/IR/Module.h"
50 #include "llvm/IR/PassManager.h"
51 #include "llvm/IR/Type.h"
52 #include "llvm/IR/User.h"
53 #include "llvm/IR/Value.h"
54 #include "llvm/InitializePasses.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/Casting.h"
57 #include "llvm/Support/Debug.h"
60 #include "llvm/Transforms/Scalar.h"
63 #include <cassert>
64 #include <utility>
65 #include <vector>
66 
67 using namespace llvm;
68 
69 #define DEBUG_TYPE "sccp"
70 
71 STATISTIC(NumInstRemoved, "Number of instructions removed");
72 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
73 STATISTIC(NumInstReplaced,
74  "Number of instructions replaced with (simpler) instruction");
75 
76 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
77 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
78 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
79 STATISTIC(
80  IPNumInstReplaced,
81  "Number of instructions replaced with (simpler) instruction by IPSCCP");
82 
83 // Helper to check if \p LV is either a constant or a constant
84 // range with a single element. This should cover exactly the same cases as the
85 // old ValueLatticeElement::isConstant() and is intended to be used in the
86 // transition to ValueLatticeElement.
87 static bool isConstant(const ValueLatticeElement &LV) {
88  return LV.isConstant() ||
90 }
91 
92 // Helper to check if \p LV is either overdefined or a constant range with more
93 // than a single element. This should cover exactly the same cases as the old
94 // ValueLatticeElement::isOverdefined() and is intended to be used in the
95 // transition to ValueLatticeElement.
96 static bool isOverdefined(const ValueLatticeElement &LV) {
97  return !LV.isUnknownOrUndef() && !isConstant(LV);
98 }
99 
100 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
101  Constant *Const = nullptr;
102  if (V->getType()->isStructTy()) {
103  std::vector<ValueLatticeElement> IVs = Solver.getStructLatticeValueFor(V);
104  if (llvm::any_of(IVs, isOverdefined))
105  return false;
106  std::vector<Constant *> ConstVals;
107  auto *ST = cast<StructType>(V->getType());
108  for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
109  ValueLatticeElement V = IVs[i];
110  ConstVals.push_back(isConstant(V)
111  ? Solver.getConstant(V)
112  : UndefValue::get(ST->getElementType(i)));
113  }
114  Const = ConstantStruct::get(ST, ConstVals);
115  } else {
116  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
117  if (isOverdefined(IV))
118  return false;
119 
120  Const =
121  isConstant(IV) ? Solver.getConstant(IV) : UndefValue::get(V->getType());
122  }
123  assert(Const && "Constant is nullptr here!");
124 
125  // Replacing `musttail` instructions with constant breaks `musttail` invariant
126  // unless the call itself can be removed.
127  // Calls with "clang.arc.attachedcall" implicitly use the return value and
128  // those uses cannot be updated with a constant.
129  CallBase *CB = dyn_cast<CallBase>(V);
130  if (CB && ((CB->isMustTailCall() && !CB->isSafeToRemove()) ||
132  Function *F = CB->getCalledFunction();
133 
134  // Don't zap returns of the callee
135  if (F)
137 
138  LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB
139  << " as a constant\n");
140  return false;
141  }
142 
143  LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');
144 
145  // Replaces all of the uses of a variable with uses of the constant.
146  V->replaceAllUsesWith(Const);
147  return true;
148 }
149 
151  SmallPtrSetImpl<Value *> &InsertedValues,
152  Statistic &InstRemovedStat,
153  Statistic &InstReplacedStat) {
154  bool MadeChanges = false;
155  for (Instruction &Inst : make_early_inc_range(BB)) {
156  if (Inst.getType()->isVoidTy())
157  continue;
158  if (tryToReplaceWithConstant(Solver, &Inst)) {
159  if (Inst.isSafeToRemove())
160  Inst.eraseFromParent();
161 
162  MadeChanges = true;
163  ++InstRemovedStat;
164  } else if (isa<SExtInst>(&Inst)) {
165  Value *ExtOp = Inst.getOperand(0);
166  if (isa<Constant>(ExtOp) || InsertedValues.count(ExtOp))
167  continue;
168  const ValueLatticeElement &IV = Solver.getLatticeValueFor(ExtOp);
169  if (!IV.isConstantRange(/*UndefAllowed=*/false))
170  continue;
171  if (IV.getConstantRange().isAllNonNegative()) {
172  auto *ZExt = new ZExtInst(ExtOp, Inst.getType(), "", &Inst);
173  InsertedValues.insert(ZExt);
174  Inst.replaceAllUsesWith(ZExt);
175  Solver.removeLatticeValueFor(&Inst);
176  Inst.eraseFromParent();
177  InstReplacedStat++;
178  MadeChanges = true;
179  }
180  }
181  }
182  return MadeChanges;
183 }
184 
185 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
186 // and return true if the function was modified.
187 static bool runSCCP(Function &F, const DataLayout &DL,
188  const TargetLibraryInfo *TLI) {
189  LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
190  SCCPSolver Solver(
191  DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
192  F.getContext());
193 
194  // Mark the first block of the function as being executable.
195  Solver.markBlockExecutable(&F.front());
196 
197  // Mark all arguments to the function as being overdefined.
198  for (Argument &AI : F.args())
199  Solver.markOverdefined(&AI);
200 
201  // Solve for constants.
202  bool ResolvedUndefs = true;
203  while (ResolvedUndefs) {
204  Solver.solve();
205  LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
206  ResolvedUndefs = Solver.resolvedUndefsIn(F);
207  }
208 
209  bool MadeChanges = false;
210 
211  // If we decided that there are basic blocks that are dead in this function,
212  // delete their contents now. Note that we cannot actually delete the blocks,
213  // as we cannot modify the CFG of the function.
214 
215  SmallPtrSet<Value *, 32> InsertedValues;
216  for (BasicBlock &BB : F) {
217  if (!Solver.isBlockExecutable(&BB)) {
218  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
219 
220  ++NumDeadBlocks;
221  NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB).first;
222 
223  MadeChanges = true;
224  continue;
225  }
226 
227  MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
228  NumInstRemoved, NumInstReplaced);
229  }
230 
231  return MadeChanges;
232 }
233 
235  const DataLayout &DL = F.getParent()->getDataLayout();
236  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
237  if (!runSCCP(F, DL, &TLI))
238  return PreservedAnalyses::all();
239 
240  auto PA = PreservedAnalyses();
241  PA.preserveSet<CFGAnalyses>();
242  return PA;
243 }
244 
245 namespace {
246 
247 //===--------------------------------------------------------------------===//
248 //
249 /// SCCP Class - This class uses the SCCPSolver to implement a per-function
250 /// Sparse Conditional Constant Propagator.
251 ///
252 class SCCPLegacyPass : public FunctionPass {
253 public:
254  // Pass identification, replacement for typeid
255  static char ID;
256 
257  SCCPLegacyPass() : FunctionPass(ID) {
259  }
260 
261  void getAnalysisUsage(AnalysisUsage &AU) const override {
264  AU.setPreservesCFG();
265  }
266 
267  // runOnFunction - Run the Sparse Conditional Constant Propagation
268  // algorithm, and return true if the function was modified.
269  bool runOnFunction(Function &F) override {
270  if (skipFunction(F))
271  return false;
272  const DataLayout &DL = F.getParent()->getDataLayout();
273  const TargetLibraryInfo *TLI =
274  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
275  return runSCCP(F, DL, TLI);
276  }
277 };
278 
279 } // end anonymous namespace
280 
281 char SCCPLegacyPass::ID = 0;
282 
283 INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp",
284  "Sparse Conditional Constant Propagation", false, false)
286 INITIALIZE_PASS_END(SCCPLegacyPass, "sccp",
287  "Sparse Conditional Constant Propagation", false, false)
288 
289 // createSCCPPass - This is the public interface to this file.
290 FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); }
291 
293  SmallVector<ReturnInst *, 8> &ReturnsToZap,
294  SCCPSolver &Solver) {
295  // We can only do this if we know that nothing else can call the function.
296  if (!Solver.isArgumentTrackedFunction(&F))
297  return;
298 
299  if (Solver.mustPreserveReturn(&F)) {
300  LLVM_DEBUG(
301  dbgs()
302  << "Can't zap returns of the function : " << F.getName()
303  << " due to present musttail or \"clang.arc.attachedcall\" call of "
304  "it\n");
305  return;
306  }
307 
308  assert(
309  all_of(F.users(),
310  [&Solver](User *U) {
311  if (isa<Instruction>(U) &&
312  !Solver.isBlockExecutable(cast<Instruction>(U)->getParent()))
313  return true;
314  // Non-callsite uses are not impacted by zapping. Also, constant
315  // uses (like blockaddresses) could stuck around, without being
316  // used in the underlying IR, meaning we do not have lattice
317  // values for them.
318  if (!isa<CallBase>(U))
319  return true;
320  if (U->getType()->isStructTy()) {
321  return all_of(Solver.getStructLatticeValueFor(U),
322  [](const ValueLatticeElement &LV) {
323  return !isOverdefined(LV);
324  });
325  }
326  return !isOverdefined(Solver.getLatticeValueFor(U));
327  }) &&
328  "We can only zap functions where all live users have a concrete value");
329 
330  for (BasicBlock &BB : F) {
331  if (CallInst *CI = BB.getTerminatingMustTailCall()) {
332  LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
333  << "musttail call : " << *CI << "\n");
334  (void)CI;
335  return;
336  }
337 
338  if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
339  if (!isa<UndefValue>(RI->getOperand(0)))
340  ReturnsToZap.push_back(RI);
341  }
342 }
343 
344 static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
345  DomTreeUpdater &DTU) {
346  SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
347  bool HasNonFeasibleEdges = false;
348  for (BasicBlock *Succ : successors(BB)) {
349  if (Solver.isEdgeFeasible(BB, Succ))
350  FeasibleSuccessors.insert(Succ);
351  else
352  HasNonFeasibleEdges = true;
353  }
354 
355  // All edges feasible, nothing to do.
356  if (!HasNonFeasibleEdges)
357  return false;
358 
359  // SCCP can only determine non-feasible edges for br, switch and indirectbr.
360  Instruction *TI = BB->getTerminator();
361  assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
362  isa<IndirectBrInst>(TI)) &&
363  "Terminator must be a br, switch or indirectbr");
364 
365  if (FeasibleSuccessors.size() == 1) {
366  // Replace with an unconditional branch to the only feasible successor.
367  BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
369  bool HaveSeenOnlyFeasibleSuccessor = false;
370  for (BasicBlock *Succ : successors(BB)) {
371  if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
372  // Don't remove the edge to the only feasible successor the first time
373  // we see it. We still do need to remove any multi-edges to it though.
374  HaveSeenOnlyFeasibleSuccessor = true;
375  continue;
376  }
377 
378  Succ->removePredecessor(BB);
379  Updates.push_back({DominatorTree::Delete, BB, Succ});
380  }
381 
382  BranchInst::Create(OnlyFeasibleSuccessor, BB);
383  TI->eraseFromParent();
384  DTU.applyUpdatesPermissive(Updates);
385  } else if (FeasibleSuccessors.size() > 1) {
386  SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));
388  for (auto CI = SI->case_begin(); CI != SI->case_end();) {
389  if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
390  ++CI;
391  continue;
392  }
393 
394  BasicBlock *Succ = CI->getCaseSuccessor();
395  Succ->removePredecessor(BB);
396  Updates.push_back({DominatorTree::Delete, BB, Succ});
397  SI.removeCase(CI);
398  // Don't increment CI, as we removed a case.
399  }
400 
401  DTU.applyUpdatesPermissive(Updates);
402  } else {
403  llvm_unreachable("Must have at least one feasible successor");
404  }
405  return true;
406 }
407 
409  Module &M, const DataLayout &DL,
410  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
411  function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
412  SCCPSolver Solver(DL, GetTLI, M.getContext());
413 
414  // Loop over all functions, marking arguments to those with their addresses
415  // taken or that are external as overdefined.
416  for (Function &F : M) {
417  if (F.isDeclaration())
418  continue;
419 
420  Solver.addAnalysis(F, getAnalysis(F));
421 
422  // Determine if we can track the function's return values. If so, add the
423  // function to the solver's set of return-tracked functions.
425  Solver.addTrackedFunction(&F);
426 
427  // Determine if we can track the function's arguments. If so, add the
428  // function to the solver's set of argument-tracked functions.
430  Solver.addArgumentTrackedFunction(&F);
431  continue;
432  }
433 
434  // Assume the function is called.
435  Solver.markBlockExecutable(&F.front());
436 
437  // Assume nothing about the incoming arguments.
438  for (Argument &AI : F.args())
439  Solver.markOverdefined(&AI);
440  }
441 
442  // Determine if we can track any of the module's global variables. If so, add
443  // the global variables we can track to the solver's set of tracked global
444  // variables.
445  for (GlobalVariable &G : M.globals()) {
446  G.removeDeadConstantUsers();
448  Solver.trackValueOfGlobalVariable(&G);
449  }
450 
451  // Solve for constants.
452  bool ResolvedUndefs = true;
453  Solver.solve();
454  while (ResolvedUndefs) {
455  LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
456  ResolvedUndefs = false;
457  for (Function &F : M) {
458  if (Solver.resolvedUndefsIn(F))
459  ResolvedUndefs = true;
460  }
461  if (ResolvedUndefs)
462  Solver.solve();
463  }
464 
465  bool MadeChanges = false;
466 
467  // Iterate over all of the instructions in the module, replacing them with
468  // constants if we have found them to be of constant values.
469 
470  for (Function &F : M) {
471  if (F.isDeclaration())
472  continue;
473 
474  SmallVector<BasicBlock *, 512> BlocksToErase;
475 
476  if (Solver.isBlockExecutable(&F.front())) {
477  bool ReplacedPointerArg = false;
478  for (Argument &Arg : F.args()) {
479  if (!Arg.use_empty() && tryToReplaceWithConstant(Solver, &Arg)) {
480  ReplacedPointerArg |= Arg.getType()->isPointerTy();
481  ++IPNumArgsElimed;
482  }
483  }
484 
485  // If we replaced an argument, the argmemonly and
486  // inaccessiblemem_or_argmemonly attributes do not hold any longer. Remove
487  // them from both the function and callsites.
488  if (ReplacedPointerArg) {
489  AttributeMask AttributesToRemove;
490  AttributesToRemove.addAttribute(Attribute::ArgMemOnly);
491  AttributesToRemove.addAttribute(Attribute::InaccessibleMemOrArgMemOnly);
492  F.removeFnAttrs(AttributesToRemove);
493 
494  for (User *U : F.users()) {
495  auto *CB = dyn_cast<CallBase>(U);
496  if (!CB || CB->getCalledFunction() != &F)
497  continue;
498 
499  CB->removeFnAttrs(AttributesToRemove);
500  }
501  }
502  MadeChanges |= ReplacedPointerArg;
503  }
504 
505  SmallPtrSet<Value *, 32> InsertedValues;
506  for (BasicBlock &BB : F) {
507  if (!Solver.isBlockExecutable(&BB)) {
508  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
509  ++NumDeadBlocks;
510 
511  MadeChanges = true;
512 
513  if (&BB != &F.front())
514  BlocksToErase.push_back(&BB);
515  continue;
516  }
517 
518  MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
519  IPNumInstRemoved, IPNumInstReplaced);
520  }
521 
522  DomTreeUpdater DTU = Solver.getDTU(F);
523  // Change dead blocks to unreachable. We do it after replacing constants
524  // in all executable blocks, because changeToUnreachable may remove PHI
525  // nodes in executable blocks we found values for. The function's entry
526  // block is not part of BlocksToErase, so we have to handle it separately.
527  for (BasicBlock *BB : BlocksToErase) {
528  NumInstRemoved += changeToUnreachable(BB->getFirstNonPHI(),
529  /*PreserveLCSSA=*/false, &DTU);
530  }
531  if (!Solver.isBlockExecutable(&F.front()))
532  NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
533  /*PreserveLCSSA=*/false, &DTU);
534 
535  for (BasicBlock &BB : F)
536  MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU);
537 
538  for (BasicBlock *DeadBB : BlocksToErase)
539  DTU.deleteBB(DeadBB);
540 
541  for (BasicBlock &BB : F) {
542  for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
543  if (Solver.getPredicateInfoFor(&Inst)) {
544  if (auto *II = dyn_cast<IntrinsicInst>(&Inst)) {
545  if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
546  Value *Op = II->getOperand(0);
547  Inst.replaceAllUsesWith(Op);
548  Inst.eraseFromParent();
549  }
550  }
551  }
552  }
553  }
554  }
555 
556  // If we inferred constant or undef return values for a function, we replaced
557  // all call uses with the inferred value. This means we don't need to bother
558  // actually returning anything from the function. Replace all return
559  // instructions with return undef.
560  //
561  // Do this in two stages: first identify the functions we should process, then
562  // actually zap their returns. This is important because we can only do this
563  // if the address of the function isn't taken. In cases where a return is the
564  // last use of a function, the order of processing functions would affect
565  // whether other functions are optimizable.
566  SmallVector<ReturnInst*, 8> ReturnsToZap;
567 
568  for (const auto &I : Solver.getTrackedRetVals()) {
569  Function *F = I.first;
570  const ValueLatticeElement &ReturnValue = I.second;
571 
572  // If there is a known constant range for the return value, add !range
573  // metadata to the function's call sites.
574  if (ReturnValue.isConstantRange() &&
575  !ReturnValue.getConstantRange().isSingleElement()) {
576  // Do not add range metadata if the return value may include undef.
577  if (ReturnValue.isConstantRangeIncludingUndef())
578  continue;
579 
580  auto &CR = ReturnValue.getConstantRange();
581  for (User *User : F->users()) {
582  auto *CB = dyn_cast<CallBase>(User);
583  if (!CB || CB->getCalledFunction() != F)
584  continue;
585 
586  // Limit to cases where the return value is guaranteed to be neither
587  // poison nor undef. Poison will be outside any range and currently
588  // values outside of the specified range cause immediate undefined
589  // behavior.
590  if (!isGuaranteedNotToBeUndefOrPoison(CB, nullptr, CB))
591  continue;
592 
593  // Do not touch existing metadata for now.
594  // TODO: We should be able to take the intersection of the existing
595  // metadata and the inferred range.
596  if (CB->getMetadata(LLVMContext::MD_range))
597  continue;
598 
599  LLVMContext &Context = CB->getParent()->getContext();
600  Metadata *RangeMD[] = {
603  CB->setMetadata(LLVMContext::MD_range, MDNode::get(Context, RangeMD));
604  }
605  continue;
606  }
607  if (F->getReturnType()->isVoidTy())
608  continue;
609  if (isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef())
610  findReturnsToZap(*F, ReturnsToZap, Solver);
611  }
612 
613  for (auto F : Solver.getMRVFunctionsTracked()) {
614  assert(F->getReturnType()->isStructTy() &&
615  "The return type should be a struct");
616  StructType *STy = cast<StructType>(F->getReturnType());
617  if (Solver.isStructLatticeConstant(F, STy))
618  findReturnsToZap(*F, ReturnsToZap, Solver);
619  }
620 
621  // Zap all returns which we've identified as zap to change.
622  SmallSetVector<Function *, 8> FuncZappedReturn;
623  for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
624  Function *F = ReturnsToZap[i]->getParent()->getParent();
625  ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
626  // Record all functions that are zapped.
627  FuncZappedReturn.insert(F);
628  }
629 
630  // Remove the returned attribute for zapped functions and the
631  // corresponding call sites.
632  for (Function *F : FuncZappedReturn) {
633  for (Argument &A : F->args())
634  F->removeParamAttr(A.getArgNo(), Attribute::Returned);
635  for (Use &U : F->uses()) {
636  // Skip over blockaddr users.
637  if (isa<BlockAddress>(U.getUser()))
638  continue;
639  CallBase *CB = cast<CallBase>(U.getUser());
640  for (Use &Arg : CB->args())
641  CB->removeParamAttr(CB->getArgOperandNo(&Arg), Attribute::Returned);
642  }
643  }
644 
645  // If we inferred constant or undef values for globals variables, we can
646  // delete the global and any stores that remain to it.
647  for (auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {
648  GlobalVariable *GV = I.first;
649  if (isOverdefined(I.second))
650  continue;
651  LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
652  << "' is constant!\n");
653  while (!GV->use_empty()) {
654  StoreInst *SI = cast<StoreInst>(GV->user_back());
655  SI->eraseFromParent();
656  MadeChanges = true;
657  }
658  M.getGlobalList().erase(GV);
659  ++IPNumGlobalConst;
660  }
661 
662  return MadeChanges;
663 }
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:155
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::ValueLatticeElement::getConstantRange
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
Definition: ValueLattice.h:270
llvm::ValueLatticeElement::isConstant
bool isConstant() const
Definition: ValueLattice.h:241
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
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::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:177
llvm::CallBase::getOperandBundle
Optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Definition: InstrTypes.h:1992
sccp
sccp
Definition: SCCP.cpp:286
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
PredicateInfo.h
llvm::SwitchInstProfUpdateWrapper
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Definition: Instructions.h:3578
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:783
Scalar.h
llvm::AnalysisResultsForFn
Helper struct for bundling up the analysis results per function for IPSCCP.
Definition: SCCPSolver.h:31
llvm::Function
Definition: Function.h:62
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1360
Pass.h
isConstant
static bool isConstant(const ValueLatticeElement &LV)
Definition: SCCP.cpp:87
llvm::SCCPSolver::getStructLatticeValueFor
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1676
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1175
Statistic.h
function
function Propagate constant arguments by specializing the function
Definition: SCCP.cpp:192
ErrorHandling.h
SCCP.h
llvm::initializeSCCPLegacyPassPass
void initializeSCCPLegacyPassPass(PassRegistry &)
MapVector.h
DomTreeUpdater.h
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::ConstantRange::isAllNonNegative
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
Definition: ConstantRange.cpp:402
ValueTracking.h
Local.h
GlobalsModRef.h
llvm::LLVMContext::OB_clang_arc_attachedcall
@ OB_clang_arc_attachedcall
Definition: LLVMContext.h:95
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:1708
DenseMap.h
Module.h
llvm::AttributeMask
Definition: Attributes.h:936
llvm::CallBase::isMustTailCall
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: Instructions.cpp:298
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
isGuaranteedNotToBeUndefOrPoison
static bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC, const Instruction *CtxI, const DominatorTree *DT, unsigned Depth, bool PoisonOnly)
Definition: ValueTracking.cpp:5026
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:31
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:1627
STLExtras.h
ConstantFolding.h
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1653
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
Context
ManagedStatic< detail::RecordContext > Context
Definition: Record.cpp:96
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
PointerIntPair.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:185
Instruction.h
llvm::CallBase::removeParamAttr
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
Definition: InstrTypes.h:1567
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:1649
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::ValueLatticeElement::isUnknownOrUndef
bool isUnknownOrUndef() const
Definition: ValueLattice.h:240
Constants.h
llvm::SCCPSolver::markOverdefined
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
Definition: SCCPSolver.cpp:1702
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
runSCCP
static bool runSCCP(Function &F, const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: SCCP.cpp:187
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1398
llvm::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:1657
llvm::ValueLatticeElement::isConstantRangeIncludingUndef
bool isConstantRangeIncludingUndef() const
Definition: ValueLattice.h:243
llvm::ConstantRange::isSingleElement
bool isSingleElement() const
Return true if this set contains exactly one member.
Definition: ConstantRange.h:261
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Propagation
Interprocedural Sparse Conditional Constant Propagation
Definition: SCCP.cpp:102
TargetLibraryInfo.h
DenseSet.h
false
Definition: StackSlotColoring.cpp:142
llvm::removeAllNonTerminatorAndEHPadInstructions
std::pair< unsigned, unsigned > removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than its terminator and any present EH pad instructi...
Definition: Local.cpp:2104
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1623
llvm::Instruction
Definition: Instruction.h:45
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:1782
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
tryToReplaceWithConstant
static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V)
Definition: SCCP.cpp:100
llvm::SCCPSolver::isStructLatticeConstant
bool isStructLatticeConstant(Function *F, StructType *STy)
Definition: SCCPSolver.cpp:1704
SmallPtrSet.h
llvm::Instruction::isSafeToRemove
bool isSafeToRemove() const
Return true if the instruction can be removed if the result is unused.
Definition: Instruction.cpp:697
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
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:408
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:223
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:1689
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
BasicBlock.h
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1684
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:309
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:78
simplifyInstsInBlock
static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
Definition: SCCP.cpp:150
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:465
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:1631
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::SCCPPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SCCP.cpp:234
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:642
llvm::SCCPSolver
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:44
llvm::SmallPtrSetImpl::begin
iterator begin() const
Definition: SmallPtrSet.h:402
ArrayRef.h
llvm::SCCPSolver::getTrackedGlobals
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
Definition: SCCPSolver.cpp:1694
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:382
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4812
llvm::createSCCPPass
FunctionPass * createSCCPPass()
Definition: SCCP.cpp:290
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:1635
isOverdefined
static bool isOverdefined(const ValueLatticeElement &LV)
Definition: SCCP.cpp:96
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:1656
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
InstVisitor.h
findReturnsToZap
static void findReturnsToZap(Function &F, SmallVector< ReturnInst *, 8 > &ReturnsToZap, SCCPSolver &Solver)
Definition: SCCP.cpp:292
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
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
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::SCCPSolver::removeLatticeValueFor
void removeLatticeValueFor(Value *V)
Definition: SCCPSolver.cpp:1680
llvm::ValueLatticeElement
This class represents lattice values for constants.
Definition: ValueLattice.h:27
llvm::SCCPSolver::mustPreserveReturn
bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
Definition: SCCPSolver.cpp:1649
llvm::TrackingStatistic
Definition: Statistic.h:49
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
ValueLatticeUtils.h
llvm::SCCPSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
Definition: SCCPSolver.cpp:1667
llvm::SmallPtrSetImplBase::size
size_type size() const
Definition: SmallPtrSet.h:92
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::SCCPSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
Definition: SCCPSolver.cpp:1671
Constant.h
removeNonFeasibleEdges
static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB, DomTreeUpdater &DTU)
Definition: SCCP.cpp:344
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
GlobalVariable.h
Casting.h
Function.h
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:221
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:1663
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:1374
llvm::changeToUnreachable
unsigned changeToUnreachable(Instruction *I, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:2128
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1645
Instructions.h
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:211
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:250
InstructionSimplify.h
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
llvm::BasicBlock::removePredecessor
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
Definition: BasicBlock.cpp:325
llvm::SCCPSolver::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
Definition: SCCPSolver.cpp:1637
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1176
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:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1478
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::SCCPSolver::solve
void solve()
Solve - Solve for constants and executable blocks.
Definition: SCCPSolver.cpp:1661
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::AttributeMask::addAttribute
AttributeMask & addAttribute(Attribute::AttrKind Val)
Add an attribute to the mask.
Definition: Attributes.h:951
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:1641
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:388
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
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:440
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:1698
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1334
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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::canTrackReturnsInterprocedurally
bool canTrackReturnsInterprocedurally(Function *F)
Determine if the values of the given function's returns can be tracked interprocedurally.
Definition: ValueLatticeUtils.cpp:23