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 (any_of(IVs,
105  [](const ValueLatticeElement &LV) { return isOverdefined(LV); }))
106  return false;
107  std::vector<Constant *> ConstVals;
108  auto *ST = cast<StructType>(V->getType());
109  for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
110  ValueLatticeElement V = IVs[i];
111  ConstVals.push_back(isConstant(V)
112  ? Solver.getConstant(V)
113  : UndefValue::get(ST->getElementType(i)));
114  }
115  Const = ConstantStruct::get(ST, ConstVals);
116  } else {
117  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
118  if (isOverdefined(IV))
119  return false;
120 
121  Const =
122  isConstant(IV) ? Solver.getConstant(IV) : UndefValue::get(V->getType());
123  }
124  assert(Const && "Constant is nullptr here!");
125 
126  // Replacing `musttail` instructions with constant breaks `musttail` invariant
127  // unless the call itself can be removed.
128  // Calls with "clang.arc.attachedcall" implicitly use the return value and
129  // those uses cannot be updated with a constant.
130  CallBase *CB = dyn_cast<CallBase>(V);
131  if (CB && ((CB->isMustTailCall() && !CB->isSafeToRemove()) ||
133  Function *F = CB->getCalledFunction();
134 
135  // Don't zap returns of the callee
136  if (F)
138 
139  LLVM_DEBUG(dbgs() << " Can\'t treat the result of call " << *CB
140  << " as a constant\n");
141  return false;
142  }
143 
144  LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n');
145 
146  // Replaces all of the uses of a variable with uses of the constant.
147  V->replaceAllUsesWith(Const);
148  return true;
149 }
150 
152  SmallPtrSetImpl<Value *> &InsertedValues,
153  Statistic &InstRemovedStat,
154  Statistic &InstReplacedStat) {
155  bool MadeChanges = false;
156  for (Instruction &Inst : make_early_inc_range(BB)) {
157  if (Inst.getType()->isVoidTy())
158  continue;
159  if (tryToReplaceWithConstant(Solver, &Inst)) {
160  if (Inst.isSafeToRemove())
161  Inst.eraseFromParent();
162 
163  MadeChanges = true;
164  ++InstRemovedStat;
165  } else if (isa<SExtInst>(&Inst)) {
166  Value *ExtOp = Inst.getOperand(0);
167  if (isa<Constant>(ExtOp) || InsertedValues.count(ExtOp))
168  continue;
169  const ValueLatticeElement &IV = Solver.getLatticeValueFor(ExtOp);
170  if (!IV.isConstantRange(/*UndefAllowed=*/false))
171  continue;
172  if (IV.getConstantRange().isAllNonNegative()) {
173  auto *ZExt = new ZExtInst(ExtOp, Inst.getType(), "", &Inst);
174  InsertedValues.insert(ZExt);
175  Inst.replaceAllUsesWith(ZExt);
176  Solver.removeLatticeValueFor(&Inst);
177  Inst.eraseFromParent();
178  InstReplacedStat++;
179  MadeChanges = true;
180  }
181  }
182  }
183  return MadeChanges;
184 }
185 
186 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
187 // and return true if the function was modified.
188 static bool runSCCP(Function &F, const DataLayout &DL,
189  const TargetLibraryInfo *TLI) {
190  LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
191  SCCPSolver Solver(
192  DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
193  F.getContext());
194 
195  // Mark the first block of the function as being executable.
196  Solver.markBlockExecutable(&F.front());
197 
198  // Mark all arguments to the function as being overdefined.
199  for (Argument &AI : F.args())
200  Solver.markOverdefined(&AI);
201 
202  // Solve for constants.
203  bool ResolvedUndefs = true;
204  while (ResolvedUndefs) {
205  Solver.solve();
206  LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
207  ResolvedUndefs = Solver.resolvedUndefsIn(F);
208  }
209 
210  bool MadeChanges = false;
211 
212  // If we decided that there are basic blocks that are dead in this function,
213  // delete their contents now. Note that we cannot actually delete the blocks,
214  // as we cannot modify the CFG of the function.
215 
216  SmallPtrSet<Value *, 32> InsertedValues;
217  for (BasicBlock &BB : F) {
218  if (!Solver.isBlockExecutable(&BB)) {
219  LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
220 
221  ++NumDeadBlocks;
222  NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB).first;
223 
224  MadeChanges = true;
225  continue;
226  }
227 
228  MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
229  NumInstRemoved, NumInstReplaced);
230  }
231 
232  return MadeChanges;
233 }
234 
236  const DataLayout &DL = F.getParent()->getDataLayout();
237  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
238  if (!runSCCP(F, DL, &TLI))
239  return PreservedAnalyses::all();
240 
241  auto PA = PreservedAnalyses();
242  PA.preserveSet<CFGAnalyses>();
243  return PA;
244 }
245 
246 namespace {
247 
248 //===--------------------------------------------------------------------===//
249 //
250 /// SCCP Class - This class uses the SCCPSolver to implement a per-function
251 /// Sparse Conditional Constant Propagator.
252 ///
253 class SCCPLegacyPass : public FunctionPass {
254 public:
255  // Pass identification, replacement for typeid
256  static char ID;
257 
258  SCCPLegacyPass() : FunctionPass(ID) {
260  }
261 
262  void getAnalysisUsage(AnalysisUsage &AU) const override {
265  AU.setPreservesCFG();
266  }
267 
268  // runOnFunction - Run the Sparse Conditional Constant Propagation
269  // algorithm, and return true if the function was modified.
270  bool runOnFunction(Function &F) override {
271  if (skipFunction(F))
272  return false;
273  const DataLayout &DL = F.getParent()->getDataLayout();
274  const TargetLibraryInfo *TLI =
275  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
276  return runSCCP(F, DL, TLI);
277  }
278 };
279 
280 } // end anonymous namespace
281 
282 char SCCPLegacyPass::ID = 0;
283 
284 INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp",
285  "Sparse Conditional Constant Propagation", false, false)
287 INITIALIZE_PASS_END(SCCPLegacyPass, "sccp",
288  "Sparse Conditional Constant Propagation", false, false)
289 
290 // createSCCPPass - This is the public interface to this file.
291 FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); }
292 
294  SmallVector<ReturnInst *, 8> &ReturnsToZap,
295  SCCPSolver &Solver) {
296  // We can only do this if we know that nothing else can call the function.
297  if (!Solver.isArgumentTrackedFunction(&F))
298  return;
299 
300  if (Solver.mustPreserveReturn(&F)) {
301  LLVM_DEBUG(
302  dbgs()
303  << "Can't zap returns of the function : " << F.getName()
304  << " due to present musttail or \"clang.arc.attachedcall\" call of "
305  "it\n");
306  return;
307  }
308 
309  assert(
310  all_of(F.users(),
311  [&Solver](User *U) {
312  if (isa<Instruction>(U) &&
313  !Solver.isBlockExecutable(cast<Instruction>(U)->getParent()))
314  return true;
315  // Non-callsite uses are not impacted by zapping. Also, constant
316  // uses (like blockaddresses) could stuck around, without being
317  // used in the underlying IR, meaning we do not have lattice
318  // values for them.
319  if (!isa<CallBase>(U))
320  return true;
321  if (U->getType()->isStructTy()) {
322  return all_of(Solver.getStructLatticeValueFor(U),
323  [](const ValueLatticeElement &LV) {
324  return !isOverdefined(LV);
325  });
326  }
327  return !isOverdefined(Solver.getLatticeValueFor(U));
328  }) &&
329  "We can only zap functions where all live users have a concrete value");
330 
331  for (BasicBlock &BB : F) {
332  if (CallInst *CI = BB.getTerminatingMustTailCall()) {
333  LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
334  << "musttail call : " << *CI << "\n");
335  (void)CI;
336  return;
337  }
338 
339  if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
340  if (!isa<UndefValue>(RI->getOperand(0)))
341  ReturnsToZap.push_back(RI);
342  }
343 }
344 
345 static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
346  DomTreeUpdater &DTU) {
347  SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
348  bool HasNonFeasibleEdges = false;
349  for (BasicBlock *Succ : successors(BB)) {
350  if (Solver.isEdgeFeasible(BB, Succ))
351  FeasibleSuccessors.insert(Succ);
352  else
353  HasNonFeasibleEdges = true;
354  }
355 
356  // All edges feasible, nothing to do.
357  if (!HasNonFeasibleEdges)
358  return false;
359 
360  // SCCP can only determine non-feasible edges for br, switch and indirectbr.
361  Instruction *TI = BB->getTerminator();
362  assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
363  isa<IndirectBrInst>(TI)) &&
364  "Terminator must be a br, switch or indirectbr");
365 
366  if (FeasibleSuccessors.size() == 1) {
367  // Replace with an unconditional branch to the only feasible successor.
368  BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
370  bool HaveSeenOnlyFeasibleSuccessor = false;
371  for (BasicBlock *Succ : successors(BB)) {
372  if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
373  // Don't remove the edge to the only feasible successor the first time
374  // we see it. We still do need to remove any multi-edges to it though.
375  HaveSeenOnlyFeasibleSuccessor = true;
376  continue;
377  }
378 
379  Succ->removePredecessor(BB);
380  Updates.push_back({DominatorTree::Delete, BB, Succ});
381  }
382 
383  BranchInst::Create(OnlyFeasibleSuccessor, BB);
384  TI->eraseFromParent();
385  DTU.applyUpdatesPermissive(Updates);
386  } else if (FeasibleSuccessors.size() > 1) {
387  SwitchInstProfUpdateWrapper SI(*cast<SwitchInst>(TI));
389  for (auto CI = SI->case_begin(); CI != SI->case_end();) {
390  if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
391  ++CI;
392  continue;
393  }
394 
395  BasicBlock *Succ = CI->getCaseSuccessor();
396  Succ->removePredecessor(BB);
397  Updates.push_back({DominatorTree::Delete, BB, Succ});
398  SI.removeCase(CI);
399  // Don't increment CI, as we removed a case.
400  }
401 
402  DTU.applyUpdatesPermissive(Updates);
403  } else {
404  llvm_unreachable("Must have at least one feasible successor");
405  }
406  return true;
407 }
408 
410  Module &M, const DataLayout &DL,
411  std::function<const TargetLibraryInfo &(Function &)> GetTLI,
412  function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
413  SCCPSolver Solver(DL, GetTLI, M.getContext());
414 
415  // Loop over all functions, marking arguments to those with their addresses
416  // taken or that are external as overdefined.
417  for (Function &F : M) {
418  if (F.isDeclaration())
419  continue;
420 
421  Solver.addAnalysis(F, getAnalysis(F));
422 
423  // Determine if we can track the function's return values. If so, add the
424  // function to the solver's set of return-tracked functions.
426  Solver.addTrackedFunction(&F);
427 
428  // Determine if we can track the function's arguments. If so, add the
429  // function to the solver's set of argument-tracked functions.
431  Solver.addArgumentTrackedFunction(&F);
432  continue;
433  }
434 
435  // Assume the function is called.
436  Solver.markBlockExecutable(&F.front());
437 
438  // Assume nothing about the incoming arguments.
439  for (Argument &AI : F.args())
440  Solver.markOverdefined(&AI);
441  }
442 
443  // Determine if we can track any of the module's global variables. If so, add
444  // the global variables we can track to the solver's set of tracked global
445  // variables.
446  for (GlobalVariable &G : M.globals()) {
447  G.removeDeadConstantUsers();
449  Solver.trackValueOfGlobalVariable(&G);
450  }
451 
452  // Solve for constants.
453  bool ResolvedUndefs = true;
454  Solver.solve();
455  while (ResolvedUndefs) {
456  LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
457  ResolvedUndefs = false;
458  for (Function &F : M) {
459  if (Solver.resolvedUndefsIn(F))
460  ResolvedUndefs = true;
461  }
462  if (ResolvedUndefs)
463  Solver.solve();
464  }
465 
466  bool MadeChanges = false;
467 
468  // Iterate over all of the instructions in the module, replacing them with
469  // constants if we have found them to be of constant values.
470 
471  for (Function &F : M) {
472  if (F.isDeclaration())
473  continue;
474 
475  SmallVector<BasicBlock *, 512> BlocksToErase;
476 
477  if (Solver.isBlockExecutable(&F.front())) {
478  bool ReplacedPointerArg = false;
479  for (Argument &Arg : F.args()) {
480  if (!Arg.use_empty() && tryToReplaceWithConstant(Solver, &Arg)) {
481  ReplacedPointerArg |= Arg.getType()->isPointerTy();
482  ++IPNumArgsElimed;
483  }
484  }
485 
486  // If we replaced an argument, the argmemonly and
487  // inaccessiblemem_or_argmemonly attributes do not hold any longer. Remove
488  // them from both the function and callsites.
489  if (ReplacedPointerArg) {
490  AttrBuilder AttributesToRemove;
491  AttributesToRemove.addAttribute(Attribute::ArgMemOnly);
492  AttributesToRemove.addAttribute(Attribute::InaccessibleMemOrArgMemOnly);
493  F.removeFnAttrs(AttributesToRemove);
494 
495  for (User *U : F.users()) {
496  auto *CB = dyn_cast<CallBase>(U);
497  if (!CB || CB->getCalledFunction() != &F)
498  continue;
499 
500  CB->removeFnAttrs(AttributesToRemove);
501  }
502  }
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
---------------------— PointerInfo ------------------------------------—
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:1987
sccp
sccp
Definition: SCCP.cpp:287
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
PredicateInfo.h
llvm::SwitchInstProfUpdateWrapper
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Definition: Instructions.h:3558
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:779
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:61
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1327
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:1662
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
function
function Propagate constant arguments by specializing the function
Definition: SCCP.cpp:190
ErrorHandling.h
SCCP.h
llvm::initializeSCCPLegacyPassPass
void initializeSCCPLegacyPassPass(PassRegistry &)
MapVector.h
DomTreeUpdater.h
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::ConstantRange::isAllNonNegative
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
Definition: ConstantRange.cpp:364
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:1694
DenseMap.h
Module.h
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:5133
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:1613
STLExtras.h
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::LLVMContext::OB_clang_arc_attachedcall
@ OB_clang_arc_attachedcall
Definition: LLVMContext.h:96
ConstantFolding.h
llvm::SCCPSolver::addArgumentTrackedFunction
void addArgumentTrackedFunction(Function *F)
Definition: SCCPSolver.cpp:1639
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
PointerIntPair.h
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
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
Instruction.h
llvm::CallBase::removeParamAttr
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
Definition: InstrTypes.h:1562
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1551
llvm::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:1688
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:188
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1393
llvm::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:1643
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:234
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:2077
llvm::SCCPSolver::addAnalysis
void addAnalysis(Function &F, AnalysisResultsForFn A)
Definition: SCCPSolver.cpp:1609
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:1771
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:1690
SmallPtrSet.h
llvm::Instruction::isSafeToRemove
bool isSafeToRemove() const
Return true if the instruction can be removed if the result is unused.
Definition: Instruction.cpp:687
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:345
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:409
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::Value::user_back
User * user_back()
Definition: Value.h:408
llvm::SCCPSolver::getTrackedRetVals
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
Definition: SCCPSolver.cpp:1675
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
BasicBlock.h
llvm::SCCPSolver::getLatticeValueFor
const ValueLatticeElement & getLatticeValueFor(Value *V) const
Definition: SCCPSolver.cpp:1670
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
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:151
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:463
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:68
llvm::SCCPSolver::getPredicateInfoFor
const PredicateBase * getPredicateInfoFor(Instruction *I)
Definition: SCCPSolver.cpp:1617
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::SCCPPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SCCP.cpp:235
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::AttrBuilder
Definition: Attributes.h:907
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
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:1680
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:67
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:4794
llvm::createSCCPPass
FunctionPass * createSCCPPass()
Definition: SCCP.cpp:291
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:1621
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:1558
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:293
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::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:1666
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:1635
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:1653
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:1657
Constant.h
removeNonFeasibleEdges
static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB, DomTreeUpdater &DTU)
Definition: SCCP.cpp:345
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
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:219
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:1649
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:1369
llvm::AttrBuilder::addAttribute
AttrBuilder & addAttribute(Attribute::AttrKind Val)
Add an attribute to the builder.
Definition: Attributes.h:933
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:2101
llvm::SCCPSolver::addToMustPreserveReturnsInFunctions
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
Definition: SCCPSolver.cpp:1631
Instructions.h
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:222
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:321
llvm::SCCPSolver::trackValueOfGlobalVariable
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
Definition: SCCPSolver.cpp:1623
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
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:1475
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:1647
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
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:1627
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:75
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:438
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:1684
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1319
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:37
llvm::canTrackReturnsInterprocedurally
bool canTrackReturnsInterprocedurally(Function *F)
Determine if the values of the given function's returns can be tracked interprocedurally.
Definition: ValueLatticeUtils.cpp:23