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 all_of(Solver.getStructLatticeValueFor(U),
80 [](const ValueLatticeElement &LV) {
81 return !SCCPSolver::isOverdefined(LV);
82 });
83 }
84
85 // We don't consider assume-like intrinsics to be actual address
86 // captures.
87 if (auto *II = dyn_cast<IntrinsicInst>(U)) {
88 if (II->isAssumeLikeIntrinsic())
89 return true;
90 }
91
92 return !SCCPSolver::isOverdefined(Solver.getLatticeValueFor(U));
93 }) &&
94 "We can only zap functions where all live users have a concrete value");
95
96 for (BasicBlock &BB : F) {
97 if (CallInst *CI = BB.getTerminatingMustTailCall()) {
98 LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present "
99 << "musttail call : " << *CI << "\n");
100 (void)CI;
101 return;
102 }
103
104 if (auto *RI = dyn_cast<ReturnInst>(Val: BB.getTerminator()))
105 if (!isa<UndefValue>(Val: RI->getOperand(i_nocapture: 0)))
106 ReturnsToZap.push_back(Elt: RI);
107 }
108}
109
110static bool runIPSCCP(
111 Module &M, const DataLayout &DL, FunctionAnalysisManager *FAM,
112 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
113 std::function<TargetTransformInfo &(Function &)> GetTTI,
114 std::function<AssumptionCache &(Function &)> GetAC,
115 std::function<DominatorTree &(Function &)> GetDT,
116 std::function<BlockFrequencyInfo &(Function &)> GetBFI,
117 bool IsFuncSpecEnabled) {
118 SCCPSolver Solver(DL, GetTLI, M.getContext());
119 FunctionSpecializer Specializer(Solver, M, FAM, GetBFI, GetTLI, GetTTI,
120 GetAC);
121
122 // Loop over all functions, marking arguments to those with their addresses
123 // taken or that are external as overdefined.
124 for (Function &F : M) {
125 if (F.isDeclaration())
126 continue;
127
128 DominatorTree &DT = GetDT(F);
129 AssumptionCache &AC = GetAC(F);
130 Solver.addPredicateInfo(F, DT, AC);
131
132 // Determine if we can track the function's return values. If so, add the
133 // function to the solver's set of return-tracked functions.
134 if (canTrackReturnsInterprocedurally(F: &F))
135 Solver.addTrackedFunction(F: &F);
136
137 // Determine if we can track the function's arguments. If so, add the
138 // function to the solver's set of argument-tracked functions.
139 if (canTrackArgumentsInterprocedurally(F: &F)) {
140 Solver.addArgumentTrackedFunction(F: &F);
141 continue;
142 }
143
144 // Assume the function is called.
145 Solver.markBlockExecutable(BB: &F.front());
146
147 // Assume nothing about the incoming arguments.
148 for (Argument &AI : F.args())
149 Solver.markOverdefined(V: &AI);
150 }
151
152 // Determine if we can track any of the module's global variables. If so, add
153 // the global variables we can track to the solver's set of tracked global
154 // variables.
155 for (GlobalVariable &G : M.globals()) {
156 G.removeDeadConstantUsers();
157 if (canTrackGlobalVariableInterprocedurally(GV: &G))
158 Solver.trackValueOfGlobalVariable(GV: &G);
159 }
160
161 // Solve for constants.
162 Solver.solveWhileResolvedUndefsIn(M);
163
164 if (IsFuncSpecEnabled) {
165 unsigned Iters = 0;
166 while (Iters++ < FuncSpecMaxIters && Specializer.run());
167 }
168
169 // Iterate over all of the instructions in the module, replacing them with
170 // constants if we have found them to be of constant values.
171 bool MadeChanges = false;
172 for (Function &F : M) {
173 if (F.isDeclaration())
174 continue;
175
176 SmallVector<BasicBlock *, 512> BlocksToErase;
177
178 if (Solver.isBlockExecutable(BB: &F.front())) {
179 bool ReplacedPointerArg = false;
180 for (Argument &Arg : F.args()) {
181 if (!Arg.use_empty() && Solver.tryToReplaceWithConstant(V: &Arg)) {
182 ReplacedPointerArg |= Arg.getType()->isPointerTy();
183 ++NumArgsElimed;
184 }
185 }
186
187 // If we replaced an argument, we may now also access a global (currently
188 // classified as "other" memory). Update memory attribute to reflect this.
189 if (ReplacedPointerArg) {
190 auto UpdateAttrs = [&](AttributeList AL) {
191 MemoryEffects ME = AL.getMemoryEffects();
192 if (ME == MemoryEffects::unknown())
193 return AL;
194
195 ME |= MemoryEffects(IRMemLocation::Other,
196 ME.getModRef(Loc: IRMemLocation::ArgMem));
197 return AL.addFnAttribute(
198 C&: F.getContext(),
199 Attr: Attribute::getWithMemoryEffects(Context&: F.getContext(), ME));
200 };
201
202 F.setAttributes(UpdateAttrs(F.getAttributes()));
203 for (User *U : F.users()) {
204 auto *CB = dyn_cast<CallBase>(Val: U);
205 if (!CB || CB->getCalledFunction() != &F)
206 continue;
207
208 CB->setAttributes(UpdateAttrs(CB->getAttributes()));
209 }
210 }
211 MadeChanges |= ReplacedPointerArg;
212 }
213
214 SmallPtrSet<Value *, 32> InsertedValues;
215 for (BasicBlock &BB : F) {
216 if (!Solver.isBlockExecutable(BB: &BB)) {
217 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB);
218 ++NumDeadBlocks;
219
220 MadeChanges = true;
221
222 if (&BB != &F.front())
223 BlocksToErase.push_back(Elt: &BB);
224 continue;
225 }
226
227 MadeChanges |= Solver.simplifyInstsInBlock(
228 BB, InsertedValues, InstRemovedStat&: NumInstRemoved, InstReplacedStat&: NumInstReplaced);
229 }
230
231 DominatorTree *DT = FAM->getCachedResult<DominatorTreeAnalysis>(IR&: F);
232 PostDominatorTree *PDT = FAM->getCachedResult<PostDominatorTreeAnalysis>(IR&: F);
233 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
234 // Change dead blocks to unreachable. We do it after replacing constants
235 // in all executable blocks, because changeToUnreachable may remove PHI
236 // nodes in executable blocks we found values for. The function's entry
237 // block is not part of BlocksToErase, so we have to handle it separately.
238 for (BasicBlock *BB : BlocksToErase) {
239 NumInstRemoved += changeToUnreachable(I: BB->getFirstNonPHIOrDbg(),
240 /*PreserveLCSSA=*/false, DTU: &DTU);
241 }
242 if (!Solver.isBlockExecutable(BB: &F.front()))
243 NumInstRemoved += changeToUnreachable(I: F.front().getFirstNonPHIOrDbg(),
244 /*PreserveLCSSA=*/false, DTU: &DTU);
245
246 BasicBlock *NewUnreachableBB = nullptr;
247 for (BasicBlock &BB : F)
248 MadeChanges |= Solver.removeNonFeasibleEdges(BB: &BB, DTU, NewUnreachableBB);
249
250 for (BasicBlock *DeadBB : BlocksToErase)
251 if (!DeadBB->hasAddressTaken())
252 DTU.deleteBB(DelBB: DeadBB);
253
254 for (BasicBlock &BB : F) {
255 for (Instruction &Inst : llvm::make_early_inc_range(Range&: BB)) {
256 if (Solver.getPredicateInfoFor(I: &Inst)) {
257 if (auto *II = dyn_cast<IntrinsicInst>(Val: &Inst)) {
258 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
259 Value *Op = II->getOperand(i_nocapture: 0);
260 Inst.replaceAllUsesWith(V: Op);
261 Inst.eraseFromParent();
262 }
263 }
264 }
265 }
266 }
267 }
268
269 // If we inferred constant or undef return values for a function, we replaced
270 // all call uses with the inferred value. This means we don't need to bother
271 // actually returning anything from the function. Replace all return
272 // instructions with return undef.
273 //
274 // Do this in two stages: first identify the functions we should process, then
275 // actually zap their returns. This is important because we can only do this
276 // if the address of the function isn't taken. In cases where a return is the
277 // last use of a function, the order of processing functions would affect
278 // whether other functions are optimizable.
279 SmallVector<ReturnInst*, 8> ReturnsToZap;
280
281 for (const auto &I : Solver.getTrackedRetVals()) {
282 Function *F = I.first;
283 const ValueLatticeElement &ReturnValue = I.second;
284
285 // If there is a known constant range for the return value, add !range
286 // metadata to the function's call sites.
287 if (ReturnValue.isConstantRange() &&
288 !ReturnValue.getConstantRange().isSingleElement()) {
289 // Do not add range metadata if the return value may include undef.
290 if (ReturnValue.isConstantRangeIncludingUndef())
291 continue;
292
293 auto &CR = ReturnValue.getConstantRange();
294 for (User *User : F->users()) {
295 auto *CB = dyn_cast<CallBase>(Val: User);
296 if (!CB || CB->getCalledFunction() != F)
297 continue;
298
299 // Do not touch existing metadata for now.
300 // TODO: We should be able to take the intersection of the existing
301 // metadata and the inferred range.
302 if (CB->getMetadata(KindID: LLVMContext::MD_range))
303 continue;
304
305 LLVMContext &Context = CB->getParent()->getContext();
306 Metadata *RangeMD[] = {
307 ConstantAsMetadata::get(C: ConstantInt::get(Context, V: CR.getLower())),
308 ConstantAsMetadata::get(C: ConstantInt::get(Context, V: CR.getUpper()))};
309 CB->setMetadata(KindID: LLVMContext::MD_range, Node: MDNode::get(Context, MDs: RangeMD));
310 }
311 continue;
312 }
313 if (F->getReturnType()->isVoidTy())
314 continue;
315 if (SCCPSolver::isConstant(LV: ReturnValue) || ReturnValue.isUnknownOrUndef())
316 findReturnsToZap(F&: *F, ReturnsToZap, Solver);
317 }
318
319 for (auto *F : Solver.getMRVFunctionsTracked()) {
320 assert(F->getReturnType()->isStructTy() &&
321 "The return type should be a struct");
322 StructType *STy = cast<StructType>(Val: F->getReturnType());
323 if (Solver.isStructLatticeConstant(F, STy))
324 findReturnsToZap(F&: *F, ReturnsToZap, Solver);
325 }
326
327 // Zap all returns which we've identified as zap to change.
328 SmallSetVector<Function *, 8> FuncZappedReturn;
329 for (ReturnInst *RI : ReturnsToZap) {
330 Function *F = RI->getParent()->getParent();
331 RI->setOperand(i_nocapture: 0, Val_nocapture: UndefValue::get(T: F->getReturnType()));
332 // Record all functions that are zapped.
333 FuncZappedReturn.insert(X: F);
334 }
335
336 // Remove the returned attribute for zapped functions and the
337 // corresponding call sites.
338 // Also remove any attributes that convert an undef return value into
339 // immediate undefined behavior
340 AttributeMask UBImplyingAttributes =
341 AttributeFuncs::getUBImplyingAttributes();
342 for (Function *F : FuncZappedReturn) {
343 for (Argument &A : F->args())
344 F->removeParamAttr(A.getArgNo(), Attribute::Returned);
345 F->removeRetAttrs(Attrs: UBImplyingAttributes);
346 for (Use &U : F->uses()) {
347 CallBase *CB = dyn_cast<CallBase>(Val: U.getUser());
348 if (!CB) {
349 assert(isa<BlockAddress>(U.getUser()) ||
350 (isa<Constant>(U.getUser()) &&
351 all_of(U.getUser()->users(), [](const User *UserUser) {
352 return cast<IntrinsicInst>(UserUser)->isAssumeLikeIntrinsic();
353 })));
354 continue;
355 }
356
357 for (Use &Arg : CB->args())
358 CB->removeParamAttr(CB->getArgOperandNo(U: &Arg), Attribute::Returned);
359 CB->removeRetAttrs(AttrsToRemove: UBImplyingAttributes);
360 }
361 }
362
363 // If we inferred constant or undef values for globals variables, we can
364 // delete the global and any stores that remain to it.
365 for (const auto &I : make_early_inc_range(Range: Solver.getTrackedGlobals())) {
366 GlobalVariable *GV = I.first;
367 if (SCCPSolver::isOverdefined(LV: I.second))
368 continue;
369 LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
370 << "' is constant!\n");
371 while (!GV->use_empty()) {
372 StoreInst *SI = cast<StoreInst>(Val: GV->user_back());
373 SI->eraseFromParent();
374 }
375
376 // Try to create a debug constant expression for the global variable
377 // initializer value.
378 SmallVector<DIGlobalVariableExpression *, 1> GVEs;
379 GV->getDebugInfo(GVs&: GVEs);
380 if (GVEs.size() == 1) {
381 DIBuilder DIB(M);
382 if (DIExpression *InitExpr = getExpressionForConstant(
383 DIB, C: *GV->getInitializer(), Ty&: *GV->getValueType()))
384 GVEs[0]->replaceOperandWith(I: 1, New: InitExpr);
385 }
386
387 MadeChanges = true;
388 M.eraseGlobalVariable(GV);
389 ++NumGlobalConst;
390 }
391
392 return MadeChanges;
393}
394
395PreservedAnalyses IPSCCPPass::run(Module &M, ModuleAnalysisManager &AM) {
396 const DataLayout &DL = M.getDataLayout();
397 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
398 auto GetTLI = [&FAM](Function &F) -> const TargetLibraryInfo & {
399 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
400 };
401 auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
402 return FAM.getResult<TargetIRAnalysis>(IR&: F);
403 };
404 auto GetAC = [&FAM](Function &F) -> AssumptionCache & {
405 return FAM.getResult<AssumptionAnalysis>(IR&: F);
406 };
407 auto GetDT = [&FAM](Function &F) -> DominatorTree & {
408 return FAM.getResult<DominatorTreeAnalysis>(IR&: F);
409 };
410 auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
411 return FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
412 };
413
414
415 if (!runIPSCCP(M, DL, FAM: &FAM, GetTLI, GetTTI, GetAC, GetDT, GetBFI,
416 IsFuncSpecEnabled: isFuncSpecEnabled()))
417 return PreservedAnalyses::all();
418
419 PreservedAnalyses PA;
420 PA.preserve<DominatorTreeAnalysis>();
421 PA.preserve<PostDominatorTreeAnalysis>();
422 PA.preserve<FunctionAnalysisManagerModuleProxy>();
423 return PA;
424}
425

source code of llvm/lib/Transforms/IPO/SCCP.cpp