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/DenseMap.h" 21 #include "llvm/ADT/MapVector.h" 22 #include "llvm/ADT/STLExtras.h" 23 #include "llvm/ADT/SetVector.h" 24 #include "llvm/ADT/SmallPtrSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/Statistic.h" 27 #include "llvm/Analysis/DomTreeUpdater.h" 28 #include "llvm/Analysis/GlobalsModRef.h" 29 #include "llvm/Analysis/TargetLibraryInfo.h" 30 #include "llvm/Analysis/ValueTracking.h" 31 #include "llvm/IR/BasicBlock.h" 32 #include "llvm/IR/Constant.h" 33 #include "llvm/IR/DerivedTypes.h" 34 #include "llvm/IR/Function.h" 35 #include "llvm/IR/GlobalVariable.h" 36 #include "llvm/IR/InstrTypes.h" 37 #include "llvm/IR/Instruction.h" 38 #include "llvm/IR/Instructions.h" 39 #include "llvm/IR/Module.h" 40 #include "llvm/IR/PassManager.h" 41 #include "llvm/IR/Type.h" 42 #include "llvm/IR/User.h" 43 #include "llvm/IR/Value.h" 44 #include "llvm/InitializePasses.h" 45 #include "llvm/Pass.h" 46 #include "llvm/Support/Casting.h" 47 #include "llvm/Support/Debug.h" 48 #include "llvm/Support/ErrorHandling.h" 49 #include "llvm/Support/raw_ostream.h" 50 #include "llvm/Transforms/Scalar.h" 51 #include "llvm/Transforms/Utils/Local.h" 52 #include "llvm/Transforms/Utils/SCCPSolver.h" 53 #include <cassert> 54 #include <utility> 55 #include <vector> 56 57 using namespace llvm; 58 59 #define DEBUG_TYPE "sccp" 60 61 STATISTIC(NumInstRemoved, "Number of instructions removed"); 62 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); 63 STATISTIC(NumInstReplaced, 64 "Number of instructions replaced with (simpler) instruction"); 65 66 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm, 67 // and return true if the function was modified. 68 static bool runSCCP(Function &F, const DataLayout &DL, 69 const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) { 70 LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); 71 SCCPSolver Solver( 72 DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; }, 73 F.getContext()); 74 75 // Mark the first block of the function as being executable. 76 Solver.markBlockExecutable(&F.front()); 77 78 // Mark all arguments to the function as being overdefined. 79 for (Argument &AI : F.args()) 80 Solver.markOverdefined(&AI); 81 82 // Solve for constants. 83 bool ResolvedUndefs = true; 84 while (ResolvedUndefs) { 85 Solver.solve(); 86 LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n"); 87 ResolvedUndefs = Solver.resolvedUndefsIn(F); 88 } 89 90 bool MadeChanges = false; 91 92 // If we decided that there are basic blocks that are dead in this function, 93 // delete their contents now. Note that we cannot actually delete the blocks, 94 // as we cannot modify the CFG of the function. 95 96 SmallPtrSet<Value *, 32> InsertedValues; 97 SmallVector<BasicBlock *, 8> BlocksToErase; 98 for (BasicBlock &BB : F) { 99 if (!Solver.isBlockExecutable(&BB)) { 100 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); 101 ++NumDeadBlocks; 102 BlocksToErase.push_back(&BB); 103 MadeChanges = true; 104 continue; 105 } 106 107 MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues, 108 NumInstRemoved, NumInstReplaced); 109 } 110 111 // Remove unreachable blocks and non-feasible edges. 112 for (BasicBlock *DeadBB : BlocksToErase) 113 NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(), 114 /*PreserveLCSSA=*/false, &DTU); 115 116 BasicBlock *NewUnreachableBB = nullptr; 117 for (BasicBlock &BB : F) 118 MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB); 119 120 for (BasicBlock *DeadBB : BlocksToErase) 121 if (!DeadBB->hasAddressTaken()) 122 DTU.deleteBB(DeadBB); 123 124 return MadeChanges; 125 } 126 127 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) { 128 const DataLayout &DL = F.getParent()->getDataLayout(); 129 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 130 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F); 131 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); 132 if (!runSCCP(F, DL, &TLI, DTU)) 133 return PreservedAnalyses::all(); 134 135 auto PA = PreservedAnalyses(); 136 PA.preserve<DominatorTreeAnalysis>(); 137 return PA; 138 } 139 140 namespace { 141 142 //===--------------------------------------------------------------------===// 143 // 144 /// SCCP Class - This class uses the SCCPSolver to implement a per-function 145 /// Sparse Conditional Constant Propagator. 146 /// 147 class SCCPLegacyPass : public FunctionPass { 148 public: 149 // Pass identification, replacement for typeid 150 static char ID; 151 152 SCCPLegacyPass() : FunctionPass(ID) { 153 initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry()); 154 } 155 156 void getAnalysisUsage(AnalysisUsage &AU) const override { 157 AU.addRequired<TargetLibraryInfoWrapperPass>(); 158 AU.addPreserved<GlobalsAAWrapperPass>(); 159 AU.addPreserved<DominatorTreeWrapperPass>(); 160 } 161 162 // runOnFunction - Run the Sparse Conditional Constant Propagation 163 // algorithm, and return true if the function was modified. 164 bool runOnFunction(Function &F) override { 165 if (skipFunction(F)) 166 return false; 167 const DataLayout &DL = F.getParent()->getDataLayout(); 168 const TargetLibraryInfo *TLI = 169 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 170 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 171 DomTreeUpdater DTU(DTWP ? &DTWP->getDomTree() : nullptr, 172 DomTreeUpdater::UpdateStrategy::Lazy); 173 return runSCCP(F, DL, TLI, DTU); 174 } 175 }; 176 177 } // end anonymous namespace 178 179 char SCCPLegacyPass::ID = 0; 180 181 INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp", 182 "Sparse Conditional Constant Propagation", false, false) 183 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 184 INITIALIZE_PASS_END(SCCPLegacyPass, "sccp", 185 "Sparse Conditional Constant Propagation", false, false) 186 187 // createSCCPPass - This is the public interface to this file. 188 FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); } 189 190