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 | |
35 | using namespace llvm; |
36 | |
37 | #define DEBUG_TYPE "sccp" |
38 | |
39 | STATISTIC(NumInstRemoved, "Number of instructions removed" ); |
40 | STATISTIC(NumArgsElimed ,"Number of arguments constant propagated" ); |
41 | STATISTIC(NumGlobalConst, "Number of globals found to be constant" ); |
42 | STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable" ); |
43 | STATISTIC(NumInstReplaced, |
44 | "Number of instructions replaced with (simpler) instruction" ); |
45 | |
46 | static 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 | |
50 | static 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 | |
110 | static 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 | |
395 | PreservedAnalyses 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 | |