1//===-- SCCP.cpp ----------------------------------------------------------===//
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 Interprocedural Sparse Conditional Constant Propagation.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/IPO/SCCP.h"
14#include "llvm/ADT/SetVector.h"
15#include "llvm/Analysis/AssumptionCache.h"
16#include "llvm/Analysis/BlockFrequencyInfo.h"
17#include "llvm/Analysis/PostDominators.h"
18#include "llvm/Analysis/TargetLibraryInfo.h"
19#include "llvm/Analysis/TargetTransformInfo.h"
20#include "llvm/Analysis/ValueLattice.h"
21#include "llvm/Analysis/ValueLatticeUtils.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/AttributeMask.h"
24#include "llvm/IR/Constants.h"
25#include "llvm/IR/DIBuilder.h"
26#include "llvm/IR/IntrinsicInst.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Support/ModRef.h"
29#include "llvm/Transforms/IPO.h"
30#include "llvm/Transforms/IPO/FunctionSpecialization.h"
31#include "llvm/Transforms/Scalar/SCCP.h"
32#include "llvm/Transforms/Utils/Local.h"
33#include "llvm/Transforms/Utils/SCCPSolver.h"
34
35using namespace llvm;
36
37#define DEBUG_TYPE "sccp"
38
39STATISTIC(NumInstRemoved, "Number of instructions removed");
40STATISTIC(NumArgsElimed ,"Number of arguments constant propagated");
41STATISTIC(NumGlobalConst, "Number of globals found to be constant");
42STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
43STATISTIC(NumInstReplaced,
44 "Number of instructions replaced with (simpler) instruction");
45
46static cl::opt<unsigned> FuncSpecMaxIters(
47 "funcspec-max-iters", cl::init(Val: 10), cl::Hidden, cl::desc(
48 "The maximum number of iterations function specialization is run"));
49
50static void findReturnsToZap(Function &F,
51 SmallVector<ReturnInst *, 8> &ReturnsToZap,
52 SCCPSolver &Solver) {
53 // We can only do this if we know that nothing else can call the function.
54 if (!Solver.isArgumentTrackedFunction(F: &F))
55 return;
56
57 if (Solver.mustPreserveReturn(F: &F)) {
58 LLVM_DEBUG(
59 dbgs()
60 << "Can't zap returns of the function : " << F.getName()
61 << " due to present musttail or \"clang.arc.attachedcall\" call of "
62 "it\n");
63 return;
64 }
65
66 assert(
67 all_of(F.users(),
68 [&Solver](User *U) {
69 if (isa<Instruction>(U) &&
70 !Solver.isBlockExecutable(cast<Instruction>(U)->getParent()))
71 return true;
72 // Non-callsite uses are not impacted by zapping. Also, constant
73 // uses (like blockaddresses) could stuck around, without being
74 // used in the underlying IR, meaning we do not have lattice
75 // values for them.
76 if (!isa<CallBase>(U))
77 return true;
78 if (U->getType()->isStructTy()) {
79 return none_of(Solver.getStructLatticeValueFor(U),
80 SCCPSolver::isOverdefined);
81 }
82
83 // We don't consider assume-like intrinsics to be actual address
84 // captures.
85 if (auto *II = dyn_cast<IntrinsicInst>(U)) {
86 if (II->isAssumeLikeIntrinsic())
87 return true;
88 }
89
90 return !SCCPSolver::isOverdefined(Solver.getLatticeValueFor(U));
91 }) &&
92 "We can only zap functions where all live users have a concrete value");
93
94 for (BasicBlock &BB : F) {
95 if (CallInst *CI = BB.getTerminatingMustTailCall()) {
96 LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
97 << "musttail call : " << *CI << "\n");
98 (void)CI;
99 return;
100 }
101
102 if (auto *RI = dyn_cast<ReturnInst>(Val: BB.getTerminator()))
103 if (!isa<UndefValue>(Val: RI->getOperand(i_nocapture: 0)))
104 ReturnsToZap.push_back(Elt: RI);
105 }
106}
107
108static bool runIPSCCP(
109 Module &M, const DataLayout &DL, FunctionAnalysisManager *FAM,
110 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
111 std::function<TargetTransformInfo &(Function &)> GetTTI,
112 std::function<AssumptionCache &(Function &)> GetAC,
113 std::function<DominatorTree &(Function &)> GetDT,
114 std::function<BlockFrequencyInfo &(Function &)> GetBFI,
115 bool IsFuncSpecEnabled) {
116 SCCPSolver Solver(DL, GetTLI, M.getContext());
117 FunctionSpecializer Specializer(Solver, M, FAM, GetBFI, GetTLI, GetTTI,
118 GetAC);
119
120 // Loop over all functions, marking arguments to those with their addresses
121 // taken or that are external as overdefined.
122 for (Function &F : M) {
123 if (F.isDeclaration())
124 continue;
125
126 DominatorTree &DT = GetDT(F);
127 AssumptionCache &AC = GetAC(F);
128 Solver.addPredicateInfo(F, DT, AC);
129
130 // Determine if we can track the function's return values. If so, add the
131 // function to the solver's set of return-tracked functions.
132 if (canTrackReturnsInterprocedurally(F: &F))
133 Solver.addTrackedFunction(F: &F);
134
135 // Determine if we can track the function's arguments. If so, add the
136 // function to the solver's set of argument-tracked functions.
137 if (canTrackArgumentsInterprocedurally(F: &F)) {
138 Solver.addArgumentTrackedFunction(F: &F);
139 continue;
140 }
141
142 // Assume the function is called.
143 Solver.markBlockExecutable(BB: &F.front());
144
145 for (Argument &AI : F.args())
146 Solver.trackValueOfArgument(V: &AI);
147 }
148
149 // Determine if we can track any of the module's global variables. If so, add
150 // the global variables we can track to the solver's set of tracked global
151 // variables.
152 for (GlobalVariable &G : M.globals()) {
153 G.removeDeadConstantUsers();
154 if (canTrackGlobalVariableInterprocedurally(GV: &G))
155 Solver.trackValueOfGlobalVariable(GV: &G);
156 }
157
158 // Solve for constants.
159 Solver.solveWhileResolvedUndefsIn(M);
160
161 if (IsFuncSpecEnabled) {
162 unsigned Iters = 0;
163 while (Iters++ < FuncSpecMaxIters && Specializer.run());
164 }
165
166 // Iterate over all of the instructions in the module, replacing them with
167 // constants if we have found them to be of constant values.
168 bool MadeChanges = false;
169 for (Function &F : M) {
170 if (F.isDeclaration())
171 continue;
172 // Skip the dead functions marked by FunctionSpecializer, avoiding removing
173 // blocks in dead functions. Set MadeChanges if there is any dead function
174 // that will be removed later.
175 if (IsFuncSpecEnabled && Specializer.isDeadFunction(F: &F)) {
176 MadeChanges = true;
177 continue;
178 }
179
180 SmallVector<BasicBlock *, 512> BlocksToErase;
181
182 if (Solver.isBlockExecutable(BB: &F.front())) {
183 bool ReplacedPointerArg = false;
184 for (Argument &Arg : F.args()) {
185 if (!Arg.use_empty() && Solver.tryToReplaceWithConstant(V: &Arg)) {
186 ReplacedPointerArg |= Arg.getType()->isPointerTy();
187 ++NumArgsElimed;
188 }
189 }
190
191 // If we replaced an argument, we may now also access a global (currently
192 // classified as "other" memory). Update memory attribute to reflect this.
193 if (ReplacedPointerArg) {
194 auto UpdateAttrs = [&](AttributeList AL) {
195 MemoryEffects ME = AL.getMemoryEffects();
196 if (ME == MemoryEffects::unknown())
197 return AL;
198
199 ModRefInfo ArgMemMR = ME.getModRef(Loc: IRMemLocation::ArgMem);
200 ME |= MemoryEffects(IRMemLocation::ErrnoMem, ArgMemMR);
201 ME |= MemoryEffects(IRMemLocation::Other, ArgMemMR);
202
203 return AL.addFnAttribute(
204 C&: F.getContext(),
205 Attr: Attribute::getWithMemoryEffects(Context&: F.getContext(), ME));
206 };
207
208 F.setAttributes(UpdateAttrs(F.getAttributes()));
209 for (User *U : F.users()) {
210 auto *CB = dyn_cast<CallBase>(Val: U);
211 if (!CB || CB->getCalledFunction() != &F)
212 continue;
213
214 CB->setAttributes(UpdateAttrs(CB->getAttributes()));
215 }
216 }
217 MadeChanges |= ReplacedPointerArg;
218 }
219
220 SmallPtrSet<Value *, 32> InsertedValues;
221 for (BasicBlock &BB : F) {
222 if (!Solver.isBlockExecutable(BB: &BB)) {
223 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
224 ++NumDeadBlocks;
225
226 MadeChanges = true;
227
228 if (&BB != &F.front())
229 BlocksToErase.push_back(Elt: &BB);
230 continue;
231 }
232
233 MadeChanges |= Solver.simplifyInstsInBlock(
234 BB, InsertedValues, InstRemovedStat&: NumInstRemoved, InstReplacedStat&: NumInstReplaced);
235 }
236
237 DominatorTree *DT = FAM->getCachedResult<DominatorTreeAnalysis>(IR&: F);
238 PostDominatorTree *PDT = FAM->getCachedResult<PostDominatorTreeAnalysis>(IR&: F);
239 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
240 // Change dead blocks to unreachable. We do it after replacing constants
241 // in all executable blocks, because changeToUnreachable may remove PHI
242 // nodes in executable blocks we found values for. The function's entry
243 // block is not part of BlocksToErase, so we have to handle it separately.
244 for (BasicBlock *BB : BlocksToErase) {
245 NumInstRemoved += changeToUnreachable(I: &*BB->getFirstNonPHIOrDbg(),
246 /*PreserveLCSSA=*/false, DTU: &DTU);
247 }
248 if (!Solver.isBlockExecutable(BB: &F.front()))
249 NumInstRemoved += changeToUnreachable(I: &*F.front().getFirstNonPHIOrDbg(),
250 /*PreserveLCSSA=*/false, DTU: &DTU);
251
252 BasicBlock *NewUnreachableBB = nullptr;
253 for (BasicBlock &BB : F)
254 MadeChanges |= Solver.removeNonFeasibleEdges(BB: &BB, DTU, NewUnreachableBB);
255
256 for (BasicBlock *DeadBB : BlocksToErase)
257 if (!DeadBB->hasAddressTaken())
258 DTU.deleteBB(DelBB: DeadBB);
259
260 Solver.removeSSACopies(F);
261 }
262
263 // If we inferred constant or undef return values for a function, we replaced
264 // all call uses with the inferred value. This means we don't need to bother
265 // actually returning anything from the function. Replace all return
266 // instructions with return undef.
267 //
268 // Do this in two stages: first identify the functions we should process, then
269 // actually zap their returns. This is important because we can only do this
270 // if the address of the function isn't taken. In cases where a return is the
271 // last use of a function, the order of processing functions would affect
272 // whether other functions are optimizable.
273 SmallVector<ReturnInst*, 8> ReturnsToZap;
274
275 Solver.inferReturnAttributes();
276 Solver.inferArgAttributes();
277 for (const auto &[F, ReturnValue] : Solver.getTrackedRetVals()) {
278 assert(!F->getReturnType()->isVoidTy() &&
279 "should not track void functions");
280 if (SCCPSolver::isConstant(LV: ReturnValue) || ReturnValue.isUnknownOrUndef())
281 findReturnsToZap(F&: *F, ReturnsToZap, Solver);
282 }
283
284 for (auto *F : Solver.getMRVFunctionsTracked()) {
285 assert(F->getReturnType()->isStructTy() &&
286 "The return type should be a struct");
287 StructType *STy = cast<StructType>(Val: F->getReturnType());
288 if (Solver.isStructLatticeConstant(F, STy))
289 findReturnsToZap(F&: *F, ReturnsToZap, Solver);
290 }
291
292 // Zap all returns which we've identified as zap to change.
293 SmallSetVector<Function *, 8> FuncZappedReturn;
294 for (ReturnInst *RI : ReturnsToZap) {
295 Function *F = RI->getParent()->getParent();
296 RI->setOperand(i_nocapture: 0, Val_nocapture: PoisonValue::get(T: F->getReturnType()));
297 // Record all functions that are zapped.
298 FuncZappedReturn.insert(X: F);
299 }
300
301 // Remove the returned attribute for zapped functions and the
302 // corresponding call sites.
303 // Also remove any attributes that convert an undef return value into
304 // immediate undefined behavior
305 AttributeMask UBImplyingAttributes =
306 AttributeFuncs::getUBImplyingAttributes();
307 for (Function *F : FuncZappedReturn) {
308 for (Argument &A : F->args())
309 F->removeParamAttr(ArgNo: A.getArgNo(), Kind: Attribute::Returned);
310 F->removeRetAttrs(Attrs: UBImplyingAttributes);
311 for (Use &U : F->uses()) {
312 CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
313 if (!CB) {
314 assert(isa<Constant>(U.getUser()) &&
315 all_of(U.getUser()->users(), [](const User *UserUser) {
316 return cast<IntrinsicInst>(UserUser)->isAssumeLikeIntrinsic();
317 }));
318 continue;
319 }
320
321 for (Use &Arg : CB->args())
322 CB->removeParamAttr(ArgNo: CB->getArgOperandNo(U: &Arg), Kind: Attribute::Returned);
323 CB->removeRetAttrs(AttrsToRemove: UBImplyingAttributes);
324 }
325 }
326
327 // If we inferred constant or undef values for globals variables, we can
328 // delete the global and any stores that remain to it.
329 for (const auto &I : make_early_inc_range(Range: Solver.getTrackedGlobals())) {
330 GlobalVariable *GV = I.first;
331 if (SCCPSolver::isOverdefined(LV: I.second))
332 continue;
333 LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
334 << "' is constant!\n");
335 for (User *U : make_early_inc_range(Range: GV->users())) {
336 // We can remove LoadInst here. The LoadInsts in dead functions marked by
337 // FuncSpec are not simplified to constants, thus poison them.
338 assert((isa<StoreInst>(U) || isa<LoadInst>(U)) &&
339 "Only Store|Load Instruction can be user of GlobalVariable at "
340 "reaching here.");
341 Instruction *I = cast<Instruction>(Val: U);
342 if (isa<LoadInst>(Val: I))
343 I->replaceAllUsesWith(V: PoisonValue::get(T: I->getType()));
344 I->eraseFromParent();
345 }
346
347 // Try to create a debug constant expression for the global variable
348 // initializer value.
349 SmallVector<DIGlobalVariableExpression *, 1> GVEs;
350 GV->getDebugInfo(GVs&: GVEs);
351 if (GVEs.size() == 1) {
352 DIBuilder DIB(M);
353 if (DIExpression *InitExpr = getExpressionForConstant(
354 DIB, C: *GV->getInitializer(), Ty&: *GV->getValueType()))
355 GVEs[0]->replaceOperandWith(I: 1, New: InitExpr);
356 }
357
358 MadeChanges = true;
359 M.eraseGlobalVariable(GV);
360 ++NumGlobalConst;
361 }
362
363 return MadeChanges;
364}
365
366PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) {
367 const DataLayout &DL = M.getDataLayout();
368 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
369 auto GetTLI = [&FAM](Function &F) -> const TargetLibraryInfo & {
370 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
371 };
372 auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
373 return FAM.getResult<TargetIRAnalysis>(IR&: F);
374 };
375 auto GetAC = [&FAM](Function &F) -> AssumptionCache & {
376 return FAM.getResult<AssumptionAnalysis>(IR&: F);
377 };
378 auto GetDT = [&FAM](Function &F) -> DominatorTree & {
379 return FAM.getResult<DominatorTreeAnalysis>(IR&: F);
380 };
381 auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
382 return FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
383 };
384
385
386 if (!runIPSCCP(M, DL, FAM: &FAM, GetTLI, GetTTI, GetAC, GetDT, GetBFI,
387 IsFuncSpecEnabled: isFuncSpecEnabled()))
388 return PreservedAnalyses::all();
389
390 PreservedAnalyses PA;
391 PA.preserve<DominatorTreeAnalysis>();
392 PA.preserve<PostDominatorTreeAnalysis>();
393 PA.preserve<FunctionAnalysisManagerModuleProxy>();
394 return PA;
395}
396