llvm/lib/Transforms/Scalar/SCCP.cpp

   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 (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()) ||
 132              CB->getOperandBundle(LLVMContext::OB_clang_arc_attachedcall))) {
 133     Function *F = CB->getCalledFunction();
 134
 135     // Don't zap returns of the callee
 136     if (F)
 137       Solver.addToMustPreserveReturnsInFunctions(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
 151 static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB,
 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
 235 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
 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) {
 259     initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry());
 260   }
 261
 262   void getAnalysisUsage(AnalysisUsage &AU) const override {
 263     AU.addRequired<TargetLibraryInfoWrapperPass>();
 264     AU.addPreserved<GlobalsAAWrapperPass>();
 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)
 286 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 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
 293 static void findReturnsToZap(Function &F,
 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();
 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     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
 409 bool llvm::runIPSCCP(
 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.
 425     if (canTrackReturnsInterprocedurally(&F))
 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.
 430     if (canTrackArgumentsInterprocedurally(&F)) {
 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();
 448     if (canTrackGlobalVariableInterprocedurally(&G))
 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 (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
 543         Instruction *Inst = &*BI++;
 544         if (Solver.getPredicateInfoFor(Inst)) {
 545           if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
 546             if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
 547               Value *Op = II->getOperand(0);
 548               Inst->replaceAllUsesWith(Op);
 549               Inst->eraseFromParent();
 550             }
 551           }
 552         }
 553       }
 554     }
 555   }
 556
 557   // If we inferred constant or undef return values for a function, we replaced
 558   // all call uses with the inferred value.  This means we don't need to bother
 559   // actually returning anything from the function.  Replace all return
 560   // instructions with return undef.
 561   //
 562   // Do this in two stages: first identify the functions we should process, then
 563   // actually zap their returns.  This is important because we can only do this
 564   // if the address of the function isn't taken.  In cases where a return is the
 565   // last use of a function, the order of processing functions would affect
 566   // whether other functions are optimizable.
 567   SmallVector<ReturnInst*, 8> ReturnsToZap;
 568
 569   for (const auto &I : Solver.getTrackedRetVals()) {
 570     Function *F = I.first;
 571     const ValueLatticeElement &ReturnValue = I.second;
 572
 573     // If there is a known constant range for the return value, add !range
 574     // metadata to the function's call sites.
 575     if (ReturnValue.isConstantRange() &&
 576         !ReturnValue.getConstantRange().isSingleElement()) {
 577       // Do not add range metadata if the return value may include undef.
 578       if (ReturnValue.isConstantRangeIncludingUndef())
 579         continue;
 580
 581       auto &CR = ReturnValue.getConstantRange();
 582       for (User *User : F->users()) {
 583         auto *CB = dyn_cast<CallBase>(User);
 584         if (!CB || CB->getCalledFunction() != F)
 585           continue;
 586
 587         // Limit to cases where the return value is guaranteed to be neither
 588         // poison nor undef. Poison will be outside any range and currently
 589         // values outside of the specified range cause immediate undefined
 590         // behavior.
 591         if (!isGuaranteedNotToBeUndefOrPoison(CB, nullptr, CB))
 592           continue;
 593
 594         // Do not touch existing metadata for now.
 595         // TODO: We should be able to take the intersection of the existing
 596         // metadata and the inferred range.
 597         if (CB->getMetadata(LLVMContext::MD_range))
 598           continue;
 599
 600         LLVMContext &Context = CB->getParent()->getContext();
 601         Metadata *RangeMD[] = {
 602             ConstantAsMetadata::get(ConstantInt::get(Context, CR.getLower())),
 603             ConstantAsMetadata::get(ConstantInt::get(Context, CR.getUpper()))};
 604         CB->setMetadata(LLVMContext::MD_range, MDNode::get(Context, RangeMD));
 605       }
 606       continue;
 607     }
 608     if (F->getReturnType()->isVoidTy())
 609       continue;
 610     if (isConstant(ReturnValue) || ReturnValue.isUnknownOrUndef())
 611       findReturnsToZap(*F, ReturnsToZap, Solver);
 612   }
 613
 614   for (auto F : Solver.getMRVFunctionsTracked()) {
 615     assert(F->getReturnType()->isStructTy() &&
 616            "The return type should be a struct");
 617     StructType *STy = cast<StructType>(F->getReturnType());
 618     if (Solver.isStructLatticeConstant(F, STy))
 619       findReturnsToZap(*F, ReturnsToZap, Solver);
 620   }
 621
 622   // Zap all returns which we've identified as zap to change.
 623   SmallSetVector<Function *, 8> FuncZappedReturn;
 624   for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
 625     Function *F = ReturnsToZap[i]->getParent()->getParent();
 626     ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
 627     // Record all functions that are zapped.
 628     FuncZappedReturn.insert(F);
 629   }
 630
 631   // Remove the returned attribute for zapped functions and the
 632   // corresponding call sites.
 633   for (Function *F : FuncZappedReturn) {
 634     for (Argument &A : F->args())
 635       F->removeParamAttr(A.getArgNo(), Attribute::Returned);
 636     for (Use &U : F->uses()) {
 637       // Skip over blockaddr users.
 638       if (isa<BlockAddress>(U.getUser()))
 639         continue;
 640       CallBase *CB = cast<CallBase>(U.getUser());
 641       for (Use &Arg : CB->args())
 642         CB->removeParamAttr(CB->getArgOperandNo(&Arg), Attribute::Returned);
 643     }
 644   }
 645
 646   // If we inferred constant or undef values for globals variables, we can
 647   // delete the global and any stores that remain to it.
 648   for (auto &I : make_early_inc_range(Solver.getTrackedGlobals())) {
 649     GlobalVariable *GV = I.first;
 650     if (isOverdefined(I.second))
 651       continue;
 652     LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
 653                       << "' is constant!\n");
 654     while (!GV->use_empty()) {
 655       StoreInst *SI = cast<StoreInst>(GV->user_back());
 656       SI->eraseFromParent();
 657       MadeChanges = true;
 658     }
 659     M.getGlobalList().erase(GV);
 660     ++IPNumGlobalConst;
 661   }
 662
 663   return MadeChanges;
 664 }