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