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/STLExtras.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/Analysis/DomTreeUpdater.h"
  25 #include "llvm/Analysis/GlobalsModRef.h"
  26 #include "llvm/Analysis/TargetLibraryInfo.h"
  27 #include "llvm/Analysis/ValueTracking.h"
  28 #include "llvm/IR/BasicBlock.h"
  29 #include "llvm/IR/Constant.h"
  30 #include "llvm/IR/DerivedTypes.h"
  31 #include "llvm/IR/Function.h"
  32 #include "llvm/IR/GlobalVariable.h"
  33 #include "llvm/IR/InstrTypes.h"
  34 #include "llvm/IR/Instruction.h"
  35 #include "llvm/IR/Instructions.h"
  36 #include "llvm/IR/Module.h"
  37 #include "llvm/IR/PassManager.h"
  38 #include "llvm/IR/Type.h"
  39 #include "llvm/IR/User.h"
  40 #include "llvm/IR/Value.h"
  41 #include "llvm/Pass.h"
  42 #include "llvm/Support/Casting.h"
  43 #include "llvm/Support/Debug.h"
  44 #include "llvm/Support/ErrorHandling.h"
  45 #include "llvm/Support/raw_ostream.h"
  46 #include "llvm/Transforms/Scalar.h"
  47 #include "llvm/Transforms/Utils/Local.h"
  48 #include "llvm/Transforms/Utils/SCCPSolver.h"
  49 #include <utility>
  50
  51 using namespace llvm;
  52
  53 #define DEBUG_TYPE "sccp"
  54
  55 STATISTIC(NumInstRemoved, "Number of instructions removed");
  56 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
  57 STATISTIC(NumInstReplaced,
  58           "Number of instructions replaced with (simpler) instruction");
  59
  60 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
  61 // and return true if the function was modified.
  62 static bool runSCCP(Function &F, const DataLayout &DL,
  63                     const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) {
  64   LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
  65   SCCPSolver Solver(
  66       DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
  67       F.getContext());
  68
  69   // Mark the first block of the function as being executable.
  70   Solver.markBlockExecutable(&F.front());
  71
  72   // Mark all arguments to the function as being overdefined.
  73   for (Argument &AI : F.args())
  74     Solver.markOverdefined(&AI);
  75
  76   // Solve for constants.
  77   bool ResolvedUndefs = true;
  78   while (ResolvedUndefs) {
  79     Solver.solve();
  80     LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n");
  81     ResolvedUndefs = Solver.resolvedUndefsIn(F);
  82   }
  83
  84   bool MadeChanges = false;
  85
  86   // If we decided that there are basic blocks that are dead in this function,
  87   // delete their contents now.  Note that we cannot actually delete the blocks,
  88   // as we cannot modify the CFG of the function.
  89
  90   SmallPtrSet<Value *, 32> InsertedValues;
  91   SmallVector<BasicBlock *, 8> BlocksToErase;
  92   for (BasicBlock &BB : F) {
  93     if (!Solver.isBlockExecutable(&BB)) {
  94       LLVM_DEBUG(dbgs() << "  BasicBlock Dead:" << BB);
  95       ++NumDeadBlocks;
  96       BlocksToErase.push_back(&BB);
  97       MadeChanges = true;
  98       continue;
  99     }
 100
 101     MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues,
 102                                                NumInstRemoved, NumInstReplaced);
 103   }
 104
 105   // Remove unreachable blocks and non-feasible edges.
 106   for (BasicBlock *DeadBB : BlocksToErase)
 107     NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(),
 108                                           /*PreserveLCSSA=*/false, &DTU);
 109
 110   BasicBlock *NewUnreachableBB = nullptr;
 111   for (BasicBlock &BB : F)
 112     MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB);
 113
 114   for (BasicBlock *DeadBB : BlocksToErase)
 115     if (!DeadBB->hasAddressTaken())
 116       DTU.deleteBB(DeadBB);
 117
 118   return MadeChanges;
 119 }
 120
 121 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
 122   const DataLayout &DL = F.getParent()->getDataLayout();
 123   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
 124   auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
 125   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
 126   if (!runSCCP(F, DL, &TLI, DTU))
 127     return PreservedAnalyses::all();
 128
 129   auto PA = PreservedAnalyses();
 130   PA.preserve<DominatorTreeAnalysis>();
 131   return PA;
 132 }