xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/SCCP.cpp (revision 924226fba12cc9a228c73b956e1b7fa24c60b055)
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 
19 #include "llvm/Transforms/Scalar/SCCP.h"
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/MapVector.h"
24 #include "llvm/ADT/PointerIntPair.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"
30 #include "llvm/Analysis/ConstantFolding.h"
31 #include "llvm/Analysis/DomTreeUpdater.h"
32 #include "llvm/Analysis/GlobalsModRef.h"
33 #include "llvm/Analysis/InstructionSimplify.h"
34 #include "llvm/Analysis/TargetLibraryInfo.h"
35 #include "llvm/Analysis/ValueLattice.h"
36 #include "llvm/Analysis/ValueLatticeUtils.h"
37 #include "llvm/Analysis/ValueTracking.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"
58 #include "llvm/Support/ErrorHandling.h"
59 #include "llvm/Support/raw_ostream.h"
60 #include "llvm/Transforms/Scalar.h"
61 #include "llvm/Transforms/Utils/Local.h"
62 #include "llvm/Transforms/Utils/PredicateInfo.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() ||
89          (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
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()) ||
131              CB->getOperandBundle(LLVMContext::OB_clang_arc_attachedcall))) {
132     Function *F = CB->getCalledFunction();
133 
134     // Don't zap returns of the callee
135     if (F)
136       Solver.addToMustPreserveReturnsInFunctions(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 
150 static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB,
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 
234 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
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) {
258     initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry());
259   }
260 
261   void getAnalysisUsage(AnalysisUsage &AU) const override {
262     AU.addRequired<TargetLibraryInfoWrapperPass>();
263     AU.addPreserved<GlobalsAAWrapperPass>();
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)
285 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
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 
292 static void findReturnsToZap(Function &F,
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                                    BasicBlock *&NewUnreachableBB) {
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();
369     SmallVector<DominatorTree::UpdateType, 8> Updates;
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));
388     SmallVector<DominatorTree::UpdateType, 8> Updates;
389 
390     // If the default destination is unfeasible it will never be taken. Replace
391     // it with a new block with a single Unreachable instruction.
392     BasicBlock *DefaultDest = SI->getDefaultDest();
393     if (!FeasibleSuccessors.contains(DefaultDest)) {
394       if (!NewUnreachableBB) {
395         NewUnreachableBB =
396             BasicBlock::Create(DefaultDest->getContext(), "default.unreachable",
397                                DefaultDest->getParent(), DefaultDest);
398         new UnreachableInst(DefaultDest->getContext(), NewUnreachableBB);
399       }
400 
401       SI->setDefaultDest(NewUnreachableBB);
402       Updates.push_back({DominatorTree::Delete, BB, DefaultDest});
403       Updates.push_back({DominatorTree::Insert, BB, NewUnreachableBB});
404     }
405 
406     for (auto CI = SI->case_begin(); CI != SI->case_end();) {
407       if (FeasibleSuccessors.contains(CI->getCaseSuccessor())) {
408         ++CI;
409         continue;
410       }
411 
412       BasicBlock *Succ = CI->getCaseSuccessor();
413       Succ->removePredecessor(BB);
414       Updates.push_back({DominatorTree::Delete, BB, Succ});
415       SI.removeCase(CI);
416       // Don't increment CI, as we removed a case.
417     }
418 
419     DTU.applyUpdatesPermissive(Updates);
420   } else {
421     llvm_unreachable("Must have at least one feasible successor");
422   }
423   return true;
424 }
425 
426 bool llvm::runIPSCCP(
427     Module &M, const DataLayout &DL,
428     std::function<const TargetLibraryInfo &(Function &)> GetTLI,
429     function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
430   SCCPSolver Solver(DL, GetTLI, M.getContext());
431 
432   // Loop over all functions, marking arguments to those with their addresses
433   // taken or that are external as overdefined.
434   for (Function &F : M) {
435     if (F.isDeclaration())
436       continue;
437 
438     Solver.addAnalysis(F, getAnalysis(F));
439 
440     // Determine if we can track the function's return values. If so, add the
441     // function to the solver's set of return-tracked functions.
442     if (canTrackReturnsInterprocedurally(&F))
443       Solver.addTrackedFunction(&F);
444 
445     // Determine if we can track the function's arguments. If so, add the
446     // function to the solver's set of argument-tracked functions.
447     if (canTrackArgumentsInterprocedurally(&F)) {
448       Solver.addArgumentTrackedFunction(&F);
449       continue;
450     }
451 
452     // Assume the function is called.
453     Solver.markBlockExecutable(&F.front());
454 
455     // Assume nothing about the incoming arguments.
456     for (Argument &AI : F.args())
457       Solver.markOverdefined(&AI);
458   }
459 
460   // Determine if we can track any of the module's global variables. If so, add
461   // the global variables we can track to the solver's set of tracked global
462   // variables.
463   for (GlobalVariable &G : M.globals()) {
464     G.removeDeadConstantUsers();
465     if (canTrackGlobalVariableInterprocedurally(&G))
466       Solver.trackValueOfGlobalVariable(&G);
467   }
468 
469   // Solve for constants.
470   bool ResolvedUndefs = true;
471   Solver.solve();
472   while (ResolvedUndefs) {
473     LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
474     ResolvedUndefs = false;
475     for (Function &F : M) {
476       if (Solver.resolvedUndefsIn(F))
477         ResolvedUndefs = true;
478     }
479     if (ResolvedUndefs)
480       Solver.solve();
481   }
482 
483   bool MadeChanges = false;
484 
485   // Iterate over all of the instructions in the module, replacing them with
486   // constants if we have found them to be of constant values.
487 
488   for (Function &F : M) {
489     if (F.isDeclaration())
490       continue;
491 
492     SmallVector<BasicBlock *, 512> BlocksToErase;
493 
494     if (Solver.isBlockExecutable(&F.front())) {
495       bool ReplacedPointerArg = false;
496       for (Argument &Arg : F.args()) {
497         if (!Arg.use_empty() && tryToReplaceWithConstant(Solver, &Arg)) {
498           ReplacedPointerArg |= Arg.getType()->isPointerTy();
499           ++IPNumArgsElimed;
500         }
501       }
502 
503       // If we replaced an argument, the argmemonly and
504       // inaccessiblemem_or_argmemonly attributes do not hold any longer. Remove
505       // them from both the function and callsites.
506       if (ReplacedPointerArg) {
507         AttributeMask AttributesToRemove;
508         AttributesToRemove.addAttribute(Attribute::ArgMemOnly);
509         AttributesToRemove.addAttribute(Attribute::InaccessibleMemOrArgMemOnly);
510         F.removeFnAttrs(AttributesToRemove);
511 
512         for (User *U : F.users()) {
513           auto *CB = dyn_cast<CallBase>(U);
514           if (!CB || CB->getCalledFunction() != &F)
515             continue;
516 
517           CB->removeFnAttrs(AttributesToRemove);
518         }
519       }
520       MadeChanges |= ReplacedPointerArg;
521     }
522 
523     SmallPtrSet<Value *, 32> InsertedValues;
524     for (BasicBlock &BB : F) {
525       if (!Solver.isBlockExecutable(&BB)) {
526         LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
527         ++NumDeadBlocks;
528 
529         MadeChanges = true;
530 
531         if (&BB != &F.front())
532           BlocksToErase.push_back(&BB);
533         continue;
534       }
535 
536       MadeChanges |= simplifyInstsInBlock(Solver, BB, InsertedValues,
537                                           IPNumInstRemoved, IPNumInstReplaced);
538     }
539 
540     DomTreeUpdater DTU = Solver.getDTU(F);
541     // Change dead blocks to unreachable. We do it after replacing constants
542     // in all executable blocks, because changeToUnreachable may remove PHI
543     // nodes in executable blocks we found values for. The function's entry
544     // block is not part of BlocksToErase, so we have to handle it separately.
545     for (BasicBlock *BB : BlocksToErase) {
546       NumInstRemoved += changeToUnreachable(BB->getFirstNonPHI(),
547                                             /*PreserveLCSSA=*/false, &DTU);
548     }
549     if (!Solver.isBlockExecutable(&F.front()))
550       NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
551                                             /*PreserveLCSSA=*/false, &DTU);
552 
553     BasicBlock *NewUnreachableBB = nullptr;
554     for (BasicBlock &BB : F)
555       MadeChanges |= removeNonFeasibleEdges(Solver, &BB, DTU, NewUnreachableBB);
556 
557     for (BasicBlock *DeadBB : BlocksToErase)
558       DTU.deleteBB(DeadBB);
559 
560     for (BasicBlock &BB : F) {
561       for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
562         if (Solver.getPredicateInfoFor(&Inst)) {
563           if (auto *II = dyn_cast<IntrinsicInst>(&Inst)) {
564             if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
565               Value *Op = II->getOperand(0);
566               Inst.replaceAllUsesWith(Op);
567               Inst.eraseFromParent();
568             }
569           }
570         }
571       }
572     }
573   }
574 
575   // If we inferred constant or undef return values for a function, we replaced
576   // all call uses with the inferred value.  This means we don't need to bother
577   // actually returning anything from the function.  Replace all return
578   // instructions with return undef.
579   //
580   // Do this in two stages: first identify the functions we should process, then
581   // actually zap their returns.  This is important because we can only do this
582   // if the address of the function isn't taken.  In cases where a return is the
583   // last use of a function, the order of processing functions would affect
584   // whether other functions are optimizable.
585   SmallVector<ReturnInst*, 8> ReturnsToZap;
586 
587   for (const auto &I : Solver.getTrackedRetVals()) {
588     Function *F = I.first;
589     const ValueLatticeElement &ReturnValue = I.second;
590 
591     // If there is a known constant range for the return value, add !range
592     // metadata to the function's call sites.
593     if (ReturnValue.isConstantRange() &&
594         !ReturnValue.getConstantRange().isSingleElement()) {
595       // Do not add range metadata if the return value may include undef.
596       if (ReturnValue.isConstantRangeIncludingUndef())
597         continue;
598 
599       auto &CR = ReturnValue.getConstantRange();
600       for (User *User : F->users()) {
601         auto *CB = dyn_cast<CallBase>(User);
602         if (!CB || CB->getCalledFunction() != F)
603           continue;
604 
605         // Limit to cases where the return value is guaranteed to be neither
606         // poison nor undef. Poison will be outside any range and currently
607         // values outside of the specified range cause immediate undefined
608         // behavior.
609         if (!isGuaranteedNotToBeUndefOrPoison(CB, nullptr, CB))
610           continue;
611 
612         // Do not touch existing metadata for now.
613         // TODO: We should be able to take the intersection of the existing
614         // metadata and the inferred range.
615         if (CB->getMetadata(LLVMContext::MD_range))
616           continue;
617 
618         LLVMContext &Context = CB->getParent()->getContext();
619         Metadata *RangeMD[] = {
620             ConstantAsMetadata::get(ConstantInt::get(Context, CR.getLower())),
621             ConstantAsMetadata::get(ConstantInt::get(Context, CR.getUpper()))};
622         CB->setMetadata(LLVMContext::MD_range, MDNode::get(Context, RangeMD));
623       }
624       continue;
625     }
626     if (F->getReturnType()->isVoidTy())
627       continue;
628     if (isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef())
629       findReturnsToZap(*F, ReturnsToZap, Solver);
630   }
631 
632   for (auto F : Solver.getMRVFunctionsTracked()) {
633     assert(F->getReturnType()->isStructTy() &&
634            "The return type should be a struct");
635     StructType *STy = cast<StructType>(F->getReturnType());
636     if (Solver.isStructLatticeConstant(F, STy))
637       findReturnsToZap(*F, ReturnsToZap, Solver);
638   }
639 
640   // Zap all returns which we've identified as zap to change.
641   SmallSetVector<Function *, 8> FuncZappedReturn;
642   for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
643     Function *F = ReturnsToZap[i]->getParent()->getParent();
644     ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
645     // Record all functions that are zapped.
646     FuncZappedReturn.insert(F);
647   }
648 
649   // Remove the returned attribute for zapped functions and the
650   // corresponding call sites.
651   for (Function *F : FuncZappedReturn) {
652     for (Argument &A : F->args())
653       F->removeParamAttr(A.getArgNo(), Attribute::Returned);
654     for (Use &U : F->uses()) {
655       // Skip over blockaddr users.
656       if (isa<BlockAddress>(U.getUser()))
657         continue;
658       CallBase *CB = cast<CallBase>(U.getUser());
659       for (Use &Arg : CB->args())
660         CB->removeParamAttr(CB->getArgOperandNo(&Arg), Attribute::Returned);
661     }
662   }
663 
664   // If we inferred constant or undef values for globals variables, we can
665   // delete the global and any stores that remain to it.
666   for (auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {
667     GlobalVariable *GV = I.first;
668     if (isOverdefined(I.second))
669       continue;
670     LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
671                       << "' is constant!\n");
672     while (!GV->use_empty()) {
673       StoreInst *SI = cast<StoreInst>(GV->user_back());
674       SI->eraseFromParent();
675       MadeChanges = true;
676     }
677     M.getGlobalList().erase(GV);
678     ++IPNumGlobalConst;
679   }
680 
681   return MadeChanges;
682 }
683