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.
runSCCP(Function & F,const DataLayout & DL,const TargetLibraryInfo * TLI,DomTreeUpdater & DTU)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
run(Function & F,FunctionAnalysisManager & AM)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
SCCPLegacyPass()152 SCCPLegacyPass() : FunctionPass(ID) {
153 initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry());
154 }
155
getAnalysisUsage(AnalysisUsage & AU) const156 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.
runOnFunction(Function & F)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)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)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