Bug Summary

File:build/source/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp
Warning:line 475, column 7
Value stored to 'Added' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name FunctionSpecialization.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -I lib/Transforms/IPO -I /build/source/llvm/lib/Transforms/IPO -I include -I /build/source/llvm/include -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm=build-llvm -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm=build-llvm -fcoverage-prefix-map=/build/source/= -source-date-epoch 1670066131 -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-12-03-132955-15984-1 -x c++ /build/source/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp
1//===- FunctionSpecialization.cpp - Function Specialization ---------------===//
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 specialises functions with constant parameters. Constant parameters
10// like function pointers and constant globals are propagated to the callee by
11// specializing the function. The main benefit of this pass at the moment is
12// that indirect calls are transformed into direct calls, which provides inline
13// opportunities that the inliner would not have been able to achieve. That's
14// why function specialisation is run before the inliner in the optimisation
15// pipeline; that is by design. Otherwise, we would only benefit from constant
16// passing, which is a valid use-case too, but hasn't been explored much in
17// terms of performance uplifts, cost-model and compile-time impact.
18//
19// Current limitations:
20// - It does not yet handle integer ranges. We do support "literal constants",
21// but that's off by default under an option.
22// - The cost-model could be further looked into (it mainly focuses on inlining
23// benefits),
24//
25// Ideas:
26// - With a function specialization attribute for arguments, we could have
27// a direct way to steer function specialization, avoiding the cost-model,
28// and thus control compile-times / code-size.
29//
30// Todos:
31// - Specializing recursive functions relies on running the transformation a
32// number of times, which is controlled by option
33// `func-specialization-max-iters`. Thus, increasing this value and the
34// number of iterations, will linearly increase the number of times recursive
35// functions get specialized, see also the discussion in
36// https://reviews.llvm.org/D106426 for details. Perhaps there is a
37// compile-time friendlier way to control/limit the number of specialisations
38// for recursive functions.
39// - Don't transform the function if function specialization does not trigger;
40// the SCCPSolver may make IR changes.
41//
42// References:
43// - 2021 LLVM Dev Mtg “Introducing function specialisation, and can we enable
44// it by default?”, https://www.youtube.com/watch?v=zJiCjeXgV5Q
45//
46//===----------------------------------------------------------------------===//
47
48#include "llvm/ADT/Statistic.h"
49#include "llvm/Analysis/CodeMetrics.h"
50#include "llvm/Analysis/InlineCost.h"
51#include "llvm/Analysis/LoopInfo.h"
52#include "llvm/Analysis/TargetTransformInfo.h"
53#include "llvm/Analysis/ValueLattice.h"
54#include "llvm/Analysis/ValueLatticeUtils.h"
55#include "llvm/IR/IntrinsicInst.h"
56#include "llvm/Transforms/Scalar/SCCP.h"
57#include "llvm/Transforms/Utils/Cloning.h"
58#include "llvm/Transforms/Utils/SCCPSolver.h"
59#include "llvm/Transforms/Utils/SizeOpts.h"
60#include <cmath>
61
62using namespace llvm;
63
64#define DEBUG_TYPE"function-specialization" "function-specialization"
65
66STATISTIC(NumFuncSpecialized, "Number of functions specialized")static llvm::Statistic NumFuncSpecialized = {"function-specialization"
, "NumFuncSpecialized", "Number of functions specialized"}
;
67
68static cl::opt<bool> ForceFunctionSpecialization(
69 "force-function-specialization", cl::init(false), cl::Hidden,
70 cl::desc("Force function specialization for every call site with a "
71 "constant argument"));
72
73static cl::opt<unsigned> FuncSpecializationMaxIters(
74 "func-specialization-max-iters", cl::Hidden,
75 cl::desc("The maximum number of iterations function specialization is run"),
76 cl::init(1));
77
78static cl::opt<unsigned> MaxClonesThreshold(
79 "func-specialization-max-clones", cl::Hidden,
80 cl::desc("The maximum number of clones allowed for a single function "
81 "specialization"),
82 cl::init(3));
83
84static cl::opt<unsigned> SmallFunctionThreshold(
85 "func-specialization-size-threshold", cl::Hidden,
86 cl::desc("Don't specialize functions that have less than this theshold "
87 "number of instructions"),
88 cl::init(100));
89
90static cl::opt<unsigned>
91 AvgLoopIterationCount("func-specialization-avg-iters-cost", cl::Hidden,
92 cl::desc("Average loop iteration count cost"),
93 cl::init(10));
94
95static cl::opt<bool> SpecializeOnAddresses(
96 "func-specialization-on-address", cl::init(false), cl::Hidden,
97 cl::desc("Enable function specialization on the address of global values"));
98
99// Disabled by default as it can significantly increase compilation times.
100// Running nikic's compile time tracker on x86 with instruction count as the
101// metric shows 3-4% regression for SPASS while being neutral for all other
102// benchmarks of the llvm test suite.
103//
104// https://llvm-compile-time-tracker.com
105// https://github.com/nikic/llvm-compile-time-tracker
106static cl::opt<bool> EnableSpecializationForLiteralConstant(
107 "function-specialization-for-literal-constant", cl::init(false), cl::Hidden,
108 cl::desc("Enable specialization of functions that take a literal constant "
109 "as an argument."));
110
111namespace {
112// Bookkeeping struct to pass data from the analysis and profitability phase
113// to the actual transform helper functions.
114struct SpecializationInfo {
115 SmallVector<ArgInfo, 8> Args; // Stores the {formal,actual} argument pairs.
116 InstructionCost Gain; // Profitability: Gain = Bonus - Cost.
117};
118} // Anonymous namespace
119
120using FuncList = SmallVectorImpl<Function *>;
121using CallArgBinding = std::pair<CallBase *, Constant *>;
122using CallSpecBinding = std::pair<CallBase *, SpecializationInfo>;
123// We are using MapVector because it guarantees deterministic iteration
124// order across executions.
125using SpecializationMap = SmallMapVector<CallBase *, SpecializationInfo, 8>;
126
127// Helper to check if \p LV is either a constant or a constant
128// range with a single element. This should cover exactly the same cases as the
129// old ValueLatticeElement::isConstant() and is intended to be used in the
130// transition to ValueLatticeElement.
131static bool isConstant(const ValueLatticeElement &LV) {
132 return LV.isConstant() ||
133 (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
134}
135
136// Helper to check if \p LV is either overdefined or a constant int.
137static bool isOverdefined(const ValueLatticeElement &LV) {
138 return !LV.isUnknownOrUndef() && !isConstant(LV);
139}
140
141static Constant *getPromotableAlloca(AllocaInst *Alloca, CallInst *Call) {
142 Value *StoreValue = nullptr;
143 for (auto *User : Alloca->users()) {
144 // We can't use llvm::isAllocaPromotable() as that would fail because of
145 // the usage in the CallInst, which is what we check here.
146 if (User == Call)
147 continue;
148 if (auto *Bitcast = dyn_cast<BitCastInst>(User)) {
149 if (!Bitcast->hasOneUse() || *Bitcast->user_begin() != Call)
150 return nullptr;
151 continue;
152 }
153
154 if (auto *Store = dyn_cast<StoreInst>(User)) {
155 // This is a duplicate store, bail out.
156 if (StoreValue || Store->isVolatile())
157 return nullptr;
158 StoreValue = Store->getValueOperand();
159 continue;
160 }
161 // Bail if there is any other unknown usage.
162 return nullptr;
163 }
164 return dyn_cast_or_null<Constant>(StoreValue);
165}
166
167// A constant stack value is an AllocaInst that has a single constant
168// value stored to it. Return this constant if such an alloca stack value
169// is a function argument.
170static Constant *getConstantStackValue(CallInst *Call, Value *Val,
171 SCCPSolver &Solver) {
172 if (!Val)
173 return nullptr;
174 Val = Val->stripPointerCasts();
175 if (auto *ConstVal = dyn_cast<ConstantInt>(Val))
176 return ConstVal;
177 auto *Alloca = dyn_cast<AllocaInst>(Val);
178 if (!Alloca || !Alloca->getAllocatedType()->isIntegerTy())
179 return nullptr;
180 return getPromotableAlloca(Alloca, Call);
181}
182
183// To support specializing recursive functions, it is important to propagate
184// constant arguments because after a first iteration of specialisation, a
185// reduced example may look like this:
186//
187// define internal void @RecursiveFn(i32* arg1) {
188// %temp = alloca i32, align 4
189// store i32 2 i32* %temp, align 4
190// call void @RecursiveFn.1(i32* nonnull %temp)
191// ret void
192// }
193//
194// Before a next iteration, we need to propagate the constant like so
195// which allows further specialization in next iterations.
196//
197// @funcspec.arg = internal constant i32 2
198//
199// define internal void @someFunc(i32* arg1) {
200// call void @otherFunc(i32* nonnull @funcspec.arg)
201// ret void
202// }
203//
204static void constantArgPropagation(FuncList &WorkList, Module &M,
205 SCCPSolver &Solver) {
206 // Iterate over the argument tracked functions see if there
207 // are any new constant values for the call instruction via
208 // stack variables.
209 for (auto *F : WorkList) {
210
211 for (auto *User : F->users()) {
212
213 auto *Call = dyn_cast<CallInst>(User);
214 if (!Call)
215 continue;
216
217 bool Changed = false;
218 for (const Use &U : Call->args()) {
219 unsigned Idx = Call->getArgOperandNo(&U);
220 Value *ArgOp = Call->getArgOperand(Idx);
221 Type *ArgOpType = ArgOp->getType();
222
223 if (!Call->onlyReadsMemory(Idx) || !ArgOpType->isPointerTy())
224 continue;
225
226 auto *ConstVal = getConstantStackValue(Call, ArgOp, Solver);
227 if (!ConstVal)
228 continue;
229
230 Value *GV = new GlobalVariable(M, ConstVal->getType(), true,
231 GlobalValue::InternalLinkage, ConstVal,
232 "funcspec.arg");
233 if (ArgOpType != ConstVal->getType())
234 GV = ConstantExpr::getBitCast(cast<Constant>(GV), ArgOpType);
235
236 Call->setArgOperand(Idx, GV);
237 Changed = true;
238 }
239
240 // Add the changed CallInst to Solver Worklist
241 if (Changed)
242 Solver.visitCall(*Call);
243 }
244 }
245}
246
247// ssa_copy intrinsics are introduced by the SCCP solver. These intrinsics
248// interfere with the constantArgPropagation optimization.
249static void removeSSACopy(Function &F) {
250 for (BasicBlock &BB : F) {
251 for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
252 auto *II = dyn_cast<IntrinsicInst>(&Inst);
253 if (!II)
254 continue;
255 if (II->getIntrinsicID() != Intrinsic::ssa_copy)
256 continue;
257 Inst.replaceAllUsesWith(II->getOperand(0));
258 Inst.eraseFromParent();
259 }
260 }
261}
262
263static void removeSSACopy(Module &M) {
264 for (Function &F : M)
265 removeSSACopy(F);
266}
267
268namespace {
269class FunctionSpecializer {
270
271 /// The IPSCCP Solver.
272 SCCPSolver &Solver;
273
274 /// Analysis manager, needed to invalidate analyses.
275 FunctionAnalysisManager *FAM;
276
277 /// Analyses used to help determine if a function should be specialized.
278 std::function<AssumptionCache &(Function &)> GetAC;
279 std::function<TargetTransformInfo &(Function &)> GetTTI;
280 std::function<TargetLibraryInfo &(Function &)> GetTLI;
281
282 SmallPtrSet<Function *, 4> SpecializedFuncs;
283 SmallPtrSet<Function *, 4> FullySpecialized;
284 SmallVector<Instruction *> ReplacedWithConstant;
285 DenseMap<Function *, CodeMetrics> FunctionMetrics;
286
287public:
288 FunctionSpecializer(SCCPSolver &Solver, FunctionAnalysisManager *FAM,
289 std::function<AssumptionCache &(Function &)> GetAC,
290 std::function<TargetTransformInfo &(Function &)> GetTTI,
291 std::function<TargetLibraryInfo &(Function &)> GetTLI)
292 : Solver(Solver), FAM(FAM), GetAC(GetAC), GetTTI(GetTTI), GetTLI(GetTLI) {
293 }
294
295 ~FunctionSpecializer() {
296 // Eliminate dead code.
297 removeDeadInstructions();
298 removeDeadFunctions();
299 }
300
301 /// Attempt to specialize functions in the module to enable constant
302 /// propagation across function boundaries.
303 ///
304 /// \returns true if at least one function is specialized.
305 bool specializeFunctions(FuncList &Candidates, FuncList &WorkList) {
306 bool Changed = false;
307 for (auto *F : Candidates) {
308 if (!isCandidateFunction(F))
309 continue;
310
311 auto Cost = getSpecializationCost(F);
312 if (!Cost.isValid()) {
313 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Invalid specialization cost.\n"
; } } while (false)
314 dbgs() << "FnSpecialization: Invalid specialization cost.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Invalid specialization cost.\n"
; } } while (false)
;
315 continue;
316 }
317
318 LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specialization cost for "
<< F->getName() << " is " << Cost <<
"\n"; } } while (false)
319 << F->getName() << " is " << Cost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specialization cost for "
<< F->getName() << " is " << Cost <<
"\n"; } } while (false)
;
320
321 SmallVector<CallSpecBinding, 8> Specializations;
322 if (!findSpecializations(F, Cost, Specializations)) {
323 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: No possible specializations found\n"
; } } while (false)
324 dbgs() << "FnSpecialization: No possible specializations found\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: No possible specializations found\n"
; } } while (false)
;
325 continue;
326 }
327
328 Changed = true;
329 for (auto &Entry : Specializations)
330 specializeFunction(F, Entry.second, WorkList);
331 }
332
333 updateSpecializedFuncs(Candidates, WorkList);
334 NumFuncSpecialized += NbFunctionsSpecialized;
335 return Changed;
336 }
337
338 void removeDeadInstructions() {
339 for (auto *I : ReplacedWithConstant) {
340 LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead instruction " << *Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Removing dead instruction "
<< *I << "\n"; } } while (false)
341 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Removing dead instruction "
<< *I << "\n"; } } while (false)
;
342 I->eraseFromParent();
343 }
344 ReplacedWithConstant.clear();
345 }
346
347 void removeDeadFunctions() {
348 for (auto *F : FullySpecialized) {
349 LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Removing dead function "
<< F->getName() << "\n"; } } while (false)
350 << F->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Removing dead function "
<< F->getName() << "\n"; } } while (false)
;
351 if (FAM)
352 FAM->clear(*F, F->getName());
353 F->eraseFromParent();
354 }
355 FullySpecialized.clear();
356 }
357
358 bool tryToReplaceWithConstant(Value *V) {
359 if (!V->getType()->isSingleValueType() || isa<CallBase>(V) ||
360 V->user_empty())
361 return false;
362
363 const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
364 if (isOverdefined(IV))
365 return false;
366 auto *Const =
367 isConstant(IV) ? Solver.getConstant(IV) : UndefValue::get(V->getType());
368
369 LLVM_DEBUG(dbgs() << "FnSpecialization: Replacing " << *Vdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Replacing "
<< *V << "\nFnSpecialization: with " << *Const
<< "\n"; } } while (false)
370 << "\nFnSpecialization: with " << *Const << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Replacing "
<< *V << "\nFnSpecialization: with " << *Const
<< "\n"; } } while (false)
;
371
372 // Record uses of V to avoid visiting irrelevant uses of const later.
373 SmallVector<Instruction *> UseInsts;
374 for (auto *U : V->users())
375 if (auto *I = dyn_cast<Instruction>(U))
376 if (Solver.isBlockExecutable(I->getParent()))
377 UseInsts.push_back(I);
378
379 V->replaceAllUsesWith(Const);
380
381 for (auto *I : UseInsts)
382 Solver.visit(I);
383
384 // Remove the instruction from Block and Solver.
385 if (auto *I = dyn_cast<Instruction>(V)) {
386 if (I->isSafeToRemove()) {
387 ReplacedWithConstant.push_back(I);
388 Solver.removeLatticeValueFor(I);
389 }
390 }
391 return true;
392 }
393
394private:
395 // The number of functions specialised, used for collecting statistics and
396 // also in the cost model.
397 unsigned NbFunctionsSpecialized = 0;
398
399 // Compute the code metrics for function \p F.
400 CodeMetrics &analyzeFunction(Function *F) {
401 auto I = FunctionMetrics.insert({F, CodeMetrics()});
402 CodeMetrics &Metrics = I.first->second;
403 if (I.second) {
404 // The code metrics were not cached.
405 SmallPtrSet<const Value *, 32> EphValues;
406 CodeMetrics::collectEphemeralValues(F, &(GetAC)(*F), EphValues);
407 for (BasicBlock &BB : *F)
408 Metrics.analyzeBasicBlock(&BB, (GetTTI)(*F), EphValues);
409
410 LLVM_DEBUG(dbgs() << "FnSpecialization: Code size of function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Code size of function "
<< F->getName() << " is " << Metrics.NumInsts
<< " instructions\n"; } } while (false)
411 << F->getName() << " is " << Metrics.NumInstsdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Code size of function "
<< F->getName() << " is " << Metrics.NumInsts
<< " instructions\n"; } } while (false)
412 << " instructions\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Code size of function "
<< F->getName() << " is " << Metrics.NumInsts
<< " instructions\n"; } } while (false)
;
413 }
414 return Metrics;
415 }
416
417 /// Clone the function \p F and remove the ssa_copy intrinsics added by
418 /// the SCCPSolver in the cloned version.
419 Function *cloneCandidateFunction(Function *F, ValueToValueMapTy &Mappings) {
420 Function *Clone = CloneFunction(F, Mappings);
421 removeSSACopy(*Clone);
422 return Clone;
423 }
424
425 /// This function decides whether it's worthwhile to specialize function
426 /// \p F based on the known constant values its arguments can take on. It
427 /// only discovers potential specialization opportunities without actually
428 /// applying them.
429 ///
430 /// \returns true if any specializations have been found.
431 bool findSpecializations(Function *F, InstructionCost Cost,
432 SmallVectorImpl<CallSpecBinding> &WorkList) {
433 // Get a list of interesting arguments.
434 SmallVector<Argument *, 4> Args;
435 for (Argument &Arg : F->args())
436 if (isArgumentInteresting(&Arg))
437 Args.push_back(&Arg);
438
439 if (!Args.size())
440 return false;
441
442 // Find all the call sites for the function.
443 SpecializationMap Specializations;
444 for (User *U : F->users()) {
445 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
446 continue;
447 auto &CS = *cast<CallBase>(U);
448 // If the call site has attribute minsize set, that callsite won't be
449 // specialized.
450 if (CS.hasFnAttr(Attribute::MinSize))
451 continue;
452
453 // If the parent of the call site will never be executed, we don't need
454 // to worry about the passed value.
455 if (!Solver.isBlockExecutable(CS.getParent()))
456 continue;
457
458 // Examine arguments and create specialization candidates from call sites
459 // with constant arguments.
460 bool Added = false;
461 for (Argument *A : Args) {
462 Constant *C = getCandidateConstant(CS.getArgOperand(A->getArgNo()));
463 if (!C)
464 continue;
465
466 if (!Added) {
467 Specializations[&CS] = {{}, 0 - Cost};
468 Added = true;
469 }
470
471 SpecializationInfo &S = Specializations.back().second;
472 S.Gain += getSpecializationBonus(A, C, Solver.getLoopInfo(*F));
473 S.Args.push_back({A, C});
474 }
475 Added = false;
Value stored to 'Added' is never read
476 }
477
478 // Remove unprofitable specializations.
479 if (!ForceFunctionSpecialization)
480 Specializations.remove_if(
481 [](const auto &Entry) { return Entry.second.Gain <= 0; });
482
483 // Clear the MapVector and return the underlying vector.
484 WorkList = Specializations.takeVector();
485
486 // Sort the candidates in descending order.
487 llvm::stable_sort(WorkList, [](const auto &L, const auto &R) {
488 return L.second.Gain > R.second.Gain;
489 });
490
491 // Truncate the worklist to 'MaxClonesThreshold' candidates if necessary.
492 if (WorkList.size() > MaxClonesThreshold) {
493 LLVM_DEBUG(dbgs() << "FnSpecialization: Number of candidates exceed "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Number of candidates exceed "
<< "the maximum number of clones threshold.\n" <<
"FnSpecialization: Truncating worklist to " << MaxClonesThreshold
<< " candidates.\n"; } } while (false)
494 << "the maximum number of clones threshold.\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Number of candidates exceed "
<< "the maximum number of clones threshold.\n" <<
"FnSpecialization: Truncating worklist to " << MaxClonesThreshold
<< " candidates.\n"; } } while (false)
495 << "FnSpecialization: Truncating worklist to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Number of candidates exceed "
<< "the maximum number of clones threshold.\n" <<
"FnSpecialization: Truncating worklist to " << MaxClonesThreshold
<< " candidates.\n"; } } while (false)
496 << MaxClonesThreshold << " candidates.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Number of candidates exceed "
<< "the maximum number of clones threshold.\n" <<
"FnSpecialization: Truncating worklist to " << MaxClonesThreshold
<< " candidates.\n"; } } while (false)
;
497 WorkList.erase(WorkList.begin() + MaxClonesThreshold, WorkList.end());
498 }
499
500 LLVM_DEBUG(dbgs() << "FnSpecialization: Specializations for function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
501 << F->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
502 for (const auto &Entrydo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
503 : WorkList) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
504 dbgs() << "FnSpecialization: Gain = " << Entry.second.Gaindo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
505 << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
506 for (const ArgInfo &Arg : Entry.second.Args)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
507 dbgs() << "FnSpecialization: FormalArg = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
508 << Arg.Formal->getNameOrAsOperand()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
509 << ", ActualArg = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
510 << Arg.Actual->getNameOrAsOperand() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
511 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Specializations for function "
<< F->getName() << "\n"; for (const auto &
Entry : WorkList) { dbgs() << "FnSpecialization: Gain = "
<< Entry.second.Gain << "\n"; for (const ArgInfo
&Arg : Entry.second.Args) dbgs() << "FnSpecialization: FormalArg = "
<< Arg.Formal->getNameOrAsOperand() << ", ActualArg = "
<< Arg.Actual->getNameOrAsOperand() << "\n"; }
; } } while (false)
;
512
513 return !WorkList.empty();
514 }
515
516 bool isCandidateFunction(Function *F) {
517 // Do not specialize the cloned function again.
518 if (SpecializedFuncs.contains(F))
519 return false;
520
521 // If we're optimizing the function for size, we shouldn't specialize it.
522 if (F->hasOptSize() ||
523 shouldOptimizeForSize(F, nullptr, nullptr, PGSOQueryType::IRPass))
524 return false;
525
526 // Exit if the function is not executable. There's no point in specializing
527 // a dead function.
528 if (!Solver.isBlockExecutable(&F->getEntryBlock()))
529 return false;
530
531 // It wastes time to specialize a function which would get inlined finally.
532 if (F->hasFnAttribute(Attribute::AlwaysInline))
533 return false;
534
535 LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Try function: "
<< F->getName() << "\n"; } } while (false)
536 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Try function: "
<< F->getName() << "\n"; } } while (false)
;
537 return true;
538 }
539
540 void specializeFunction(Function *F, SpecializationInfo &S,
541 FuncList &WorkList) {
542 ValueToValueMapTy Mappings;
543 Function *Clone = cloneCandidateFunction(F, Mappings);
544
545 // Rewrite calls to the function so that they call the clone instead.
546 rewriteCallSites(Clone, S.Args, Mappings);
547
548 // Initialize the lattice state of the arguments of the function clone,
549 // marking the argument on which we specialized the function constant
550 // with the given value.
551 Solver.markArgInFuncSpecialization(Clone, S.Args);
552
553 // Mark all the specialized functions
554 WorkList.push_back(Clone);
555 NbFunctionsSpecialized++;
556
557 // If the function has been completely specialized, the original function
558 // is no longer needed. Mark it unreachable.
559 if (F->getNumUses() == 0 || all_of(F->users(), [F](User *U) {
560 if (auto *CS = dyn_cast<CallBase>(U))
561 return CS->getFunction() == F;
562 return false;
563 })) {
564 Solver.markFunctionUnreachable(F);
565 FullySpecialized.insert(F);
566 }
567 }
568
569 /// Compute and return the cost of specializing function \p F.
570 InstructionCost getSpecializationCost(Function *F) {
571 CodeMetrics &Metrics = analyzeFunction(F);
572 // If the code metrics reveal that we shouldn't duplicate the function, we
573 // shouldn't specialize it. Set the specialization cost to Invalid.
574 // Or if the lines of codes implies that this function is easy to get
575 // inlined so that we shouldn't specialize it.
576 if (Metrics.notDuplicatable || !Metrics.NumInsts.isValid() ||
577 (!ForceFunctionSpecialization &&
578 !F->hasFnAttribute(Attribute::NoInline) &&
579 Metrics.NumInsts < SmallFunctionThreshold))
580 return InstructionCost::getInvalid();
581
582 // Otherwise, set the specialization cost to be the cost of all the
583 // instructions in the function and penalty for specializing more functions.
584 unsigned Penalty = NbFunctionsSpecialized + 1;
585 return Metrics.NumInsts * InlineConstants::getInstrCost() * Penalty;
586 }
587
588 InstructionCost getUserBonus(User *U, llvm::TargetTransformInfo &TTI,
589 const LoopInfo &LI) {
590 auto *I = dyn_cast_or_null<Instruction>(U);
591 // If not an instruction we do not know how to evaluate.
592 // Keep minimum possible cost for now so that it doesnt affect
593 // specialization.
594 if (!I)
595 return std::numeric_limits<unsigned>::min();
596
597 InstructionCost Cost =
598 TTI.getInstructionCost(U, TargetTransformInfo::TCK_SizeAndLatency);
599
600 // Increase the cost if it is inside the loop.
601 unsigned LoopDepth = LI.getLoopDepth(I->getParent());
602 Cost *= std::pow((double)AvgLoopIterationCount, LoopDepth);
603
604 // Traverse recursively if there are more uses.
605 // TODO: Any other instructions to be added here?
606 if (I->mayReadFromMemory() || I->isCast())
607 for (auto *User : I->users())
608 Cost += getUserBonus(User, TTI, LI);
609
610 return Cost;
611 }
612
613 /// Compute a bonus for replacing argument \p A with constant \p C.
614 InstructionCost getSpecializationBonus(Argument *A, Constant *C,
615 const LoopInfo &LI) {
616 Function *F = A->getParent();
617 auto &TTI = (GetTTI)(*F);
618 LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Analysing bonus for constant: "
<< C->getNameOrAsOperand() << "\n"; } } while
(false)
619 << C->getNameOrAsOperand() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Analysing bonus for constant: "
<< C->getNameOrAsOperand() << "\n"; } } while
(false)
;
620
621 InstructionCost TotalCost = 0;
622 for (auto *U : A->users()) {
623 TotalCost += getUserBonus(U, TTI, LI);
624 LLVM_DEBUG(dbgs() << "FnSpecialization: User cost ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: User cost "
; TotalCost.print(dbgs()); dbgs() << " for: " << *
U << "\n"; } } while (false)
625 TotalCost.print(dbgs()); dbgs() << " for: " << *U << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: User cost "
; TotalCost.print(dbgs()); dbgs() << " for: " << *
U << "\n"; } } while (false)
;
626 }
627
628 // The below heuristic is only concerned with exposing inlining
629 // opportunities via indirect call promotion. If the argument is not a
630 // (potentially casted) function pointer, give up.
631 Function *CalledFunction = dyn_cast<Function>(C->stripPointerCasts());
632 if (!CalledFunction)
633 return TotalCost;
634
635 // Get TTI for the called function (used for the inline cost).
636 auto &CalleeTTI = (GetTTI)(*CalledFunction);
637
638 // Look at all the call sites whose called value is the argument.
639 // Specializing the function on the argument would allow these indirect
640 // calls to be promoted to direct calls. If the indirect call promotion
641 // would likely enable the called function to be inlined, specializing is a
642 // good idea.
643 int Bonus = 0;
644 for (User *U : A->users()) {
645 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
646 continue;
647 auto *CS = cast<CallBase>(U);
648 if (CS->getCalledOperand() != A)
649 continue;
650
651 // Get the cost of inlining the called function at this call site. Note
652 // that this is only an estimate. The called function may eventually
653 // change in a way that leads to it not being inlined here, even though
654 // inlining looks profitable now. For example, one of its called
655 // functions may be inlined into it, making the called function too large
656 // to be inlined into this call site.
657 //
658 // We apply a boost for performing indirect call promotion by increasing
659 // the default threshold by the threshold for indirect calls.
660 auto Params = getInlineParams();
661 Params.DefaultThreshold += InlineConstants::IndirectCallThreshold;
662 InlineCost IC =
663 getInlineCost(*CS, CalledFunction, Params, CalleeTTI, GetAC, GetTLI);
664
665 // We clamp the bonus for this call to be between zero and the default
666 // threshold.
667 if (IC.isAlways())
668 Bonus += Params.DefaultThreshold;
669 else if (IC.isVariable() && IC.getCostDelta() > 0)
670 Bonus += IC.getCostDelta();
671
672 LLVM_DEBUG(dbgs() << "FnSpecialization: Inlining bonus " << Bonusdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Inlining bonus "
<< Bonus << " for user " << *U << "\n"
; } } while (false)
673 << " for user " << *U << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Inlining bonus "
<< Bonus << " for user " << *U << "\n"
; } } while (false)
;
674 }
675
676 return TotalCost + Bonus;
677 }
678
679 /// Determine if it is possible to specialise the function for constant values
680 /// of the formal parameter \p A.
681 bool isArgumentInteresting(Argument *A) {
682 // No point in specialization if the argument is unused.
683 if (A->user_empty())
684 return false;
685
686 // For now, don't attempt to specialize functions based on the values of
687 // composite types.
688 Type *ArgTy = A->getType();
689 if (!ArgTy->isSingleValueType())
690 return false;
691
692 // Specialization of integer and floating point types needs to be explicitly
693 // enabled.
694 if (!EnableSpecializationForLiteralConstant &&
695 (ArgTy->isIntegerTy() || ArgTy->isFloatingPointTy()))
696 return false;
697
698 // SCCP solver does not record an argument that will be constructed on
699 // stack.
700 if (A->hasByValAttr() && !A->getParent()->onlyReadsMemory())
701 return false;
702
703 // Check the lattice value and decide if we should attemt to specialize,
704 // based on this argument. No point in specialization, if the lattice value
705 // is already a constant.
706 const ValueLatticeElement &LV = Solver.getLatticeValueFor(A);
707 if (LV.isUnknownOrUndef() || LV.isConstant() ||
708 (LV.isConstantRange() && LV.getConstantRange().isSingleElement())) {
709 LLVM_DEBUG(dbgs() << "FnSpecialization: Nothing to do, argument "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Nothing to do, argument "
<< A->getNameOrAsOperand() << " is already constant\n"
; } } while (false)
710 << A->getNameOrAsOperand() << " is already constant\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Nothing to do, argument "
<< A->getNameOrAsOperand() << " is already constant\n"
; } } while (false)
;
711 return false;
712 }
713
714 return true;
715 }
716
717 /// Check if the valuy \p V (an actual argument) is a constant or can only
718 /// have a constant value. Return that constant.
719 Constant *getCandidateConstant(Value *V) {
720 if (isa<PoisonValue>(V))
721 return nullptr;
722
723 // TrackValueOfGlobalVariable only tracks scalar global variables.
724 if (auto *GV = dyn_cast<GlobalVariable>(V)) {
725 // Check if we want to specialize on the address of non-constant
726 // global values.
727 if (!GV->isConstant() && !SpecializeOnAddresses)
728 return nullptr;
729
730 if (!GV->getValueType()->isSingleValueType())
731 return nullptr;
732 }
733
734 // Select for possible specialisation values that are constants or
735 // are deduced to be constants or constant ranges with a single element.
736 Constant *C = dyn_cast<Constant>(V);
737 if (!C) {
738 const ValueLatticeElement &LV = Solver.getLatticeValueFor(V);
739 if (LV.isConstant())
740 C = LV.getConstant();
741 else if (LV.isConstantRange() &&
742 LV.getConstantRange().isSingleElement()) {
743 assert(V->getType()->isIntegerTy() && "Non-integral constant range")(static_cast <bool> (V->getType()->isIntegerTy() &&
"Non-integral constant range") ? void (0) : __assert_fail ("V->getType()->isIntegerTy() && \"Non-integral constant range\""
, "llvm/lib/Transforms/IPO/FunctionSpecialization.cpp", 743, __extension__
__PRETTY_FUNCTION__))
;
744 C = Constant::getIntegerValue(
745 V->getType(), *LV.getConstantRange().getSingleElement());
746 } else
747 return nullptr;
748 }
749
750 LLVM_DEBUG(dbgs() << "FnSpecialization: Found interesting argument "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Found interesting argument "
<< V->getNameOrAsOperand() << "\n"; } } while
(false)
751 << V->getNameOrAsOperand() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Found interesting argument "
<< V->getNameOrAsOperand() << "\n"; } } while
(false)
;
752
753 return C;
754 }
755
756 /// Rewrite calls to function \p F to call function \p Clone instead.
757 ///
758 /// This function modifies calls to function \p F as long as the actual
759 /// arguments match those in \p Args. Note that for recursive calls we
760 /// need to compare against the cloned formal arguments.
761 ///
762 /// Callsites that have been marked with the MinSize function attribute won't
763 /// be specialized and rewritten.
764 void rewriteCallSites(Function *Clone, const SmallVectorImpl<ArgInfo> &Args,
765 ValueToValueMapTy &Mappings) {
766 assert(!Args.empty() && "Specialization without arguments")(static_cast <bool> (!Args.empty() && "Specialization without arguments"
) ? void (0) : __assert_fail ("!Args.empty() && \"Specialization without arguments\""
, "llvm/lib/Transforms/IPO/FunctionSpecialization.cpp", 766, __extension__
__PRETTY_FUNCTION__))
;
767 Function *F = Args[0].Formal->getParent();
768
769 SmallVector<CallBase *, 8> CallSitesToRewrite;
770 for (auto *U : F->users()) {
771 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
772 continue;
773 auto &CS = *cast<CallBase>(U);
774 if (!CS.getCalledFunction() || CS.getCalledFunction() != F)
775 continue;
776 CallSitesToRewrite.push_back(&CS);
777 }
778
779 LLVM_DEBUG(dbgs() << "FnSpecialization: Replacing call sites of "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Replacing call sites of "
<< F->getName() << " with " << Clone->
getName() << "\n"; } } while (false)
780 << F->getName() << " with " << Clone->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Replacing call sites of "
<< F->getName() << " with " << Clone->
getName() << "\n"; } } while (false)
;
781
782 for (auto *CS : CallSitesToRewrite) {
783 LLVM_DEBUG(dbgs() << "FnSpecialization: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: "
<< CS->getFunction()->getName() << " ->"
<< *CS << "\n"; } } while (false)
784 << CS->getFunction()->getName() << " ->" << *CSdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: "
<< CS->getFunction()->getName() << " ->"
<< *CS << "\n"; } } while (false)
785 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: "
<< CS->getFunction()->getName() << " ->"
<< *CS << "\n"; } } while (false)
;
786 if (/* recursive call */
787 (CS->getFunction() == Clone &&
788 all_of(Args,
789 [CS, &Mappings](const ArgInfo &Arg) {
790 unsigned ArgNo = Arg.Formal->getArgNo();
791 return CS->getArgOperand(ArgNo) == Mappings[Arg.Formal];
792 })) ||
793 /* normal call */
794 all_of(Args, [CS](const ArgInfo &Arg) {
795 unsigned ArgNo = Arg.Formal->getArgNo();
796 return CS->getArgOperand(ArgNo) == Arg.Actual;
797 })) {
798 CS->setCalledFunction(Clone);
799 Solver.markOverdefined(CS);
800 }
801 }
802 }
803
804 void updateSpecializedFuncs(FuncList &Candidates, FuncList &WorkList) {
805 for (auto *F : WorkList) {
806 SpecializedFuncs.insert(F);
807
808 // Initialize the state of the newly created functions, marking them
809 // argument-tracked and executable.
810 if (F->hasExactDefinition() && !F->hasFnAttribute(Attribute::Naked))
811 Solver.addTrackedFunction(F);
812
813 Solver.addArgumentTrackedFunction(F);
814 Candidates.push_back(F);
815 Solver.markBlockExecutable(&F->front());
816
817 // Replace the function arguments for the specialized functions.
818 for (Argument &Arg : F->args())
819 if (!Arg.use_empty() && tryToReplaceWithConstant(&Arg))
820 LLVM_DEBUG(dbgs() << "FnSpecialization: Replaced constant argument: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Replaced constant argument: "
<< Arg.getNameOrAsOperand() << "\n"; } } while (
false)
821 << Arg.getNameOrAsOperand() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Replaced constant argument: "
<< Arg.getNameOrAsOperand() << "\n"; } } while (
false)
;
822 }
823 }
824};
825} // namespace
826
827bool llvm::runFunctionSpecialization(
828 Module &M, FunctionAnalysisManager *FAM, const DataLayout &DL,
829 std::function<TargetLibraryInfo &(Function &)> GetTLI,
830 std::function<TargetTransformInfo &(Function &)> GetTTI,
831 std::function<AssumptionCache &(Function &)> GetAC,
832 function_ref<AnalysisResultsForFn(Function &)> GetAnalysis) {
833 SCCPSolver Solver(DL, GetTLI, M.getContext());
834 FunctionSpecializer FS(Solver, FAM, GetAC, GetTTI, GetTLI);
835 bool Changed = false;
836
837 // Loop over all functions, marking arguments to those with their addresses
838 // taken or that are external as overdefined.
839 for (Function &F : M) {
840 if (F.isDeclaration())
841 continue;
842 if (F.hasFnAttribute(Attribute::NoDuplicate))
843 continue;
844
845 LLVM_DEBUG(dbgs() << "\nFnSpecialization: Analysing decl: " << F.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "\nFnSpecialization: Analysing decl: "
<< F.getName() << "\n"; } } while (false)
846 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "\nFnSpecialization: Analysing decl: "
<< F.getName() << "\n"; } } while (false)
;
847 Solver.addAnalysis(F, GetAnalysis(F));
848
849 // Determine if we can track the function's arguments. If so, add the
850 // function to the solver's set of argument-tracked functions.
851 if (canTrackArgumentsInterprocedurally(&F)) {
852 LLVM_DEBUG(dbgs() << "FnSpecialization: Can track arguments\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Can track arguments\n"
; } } while (false)
;
853 Solver.addArgumentTrackedFunction(&F);
854 continue;
855 } else {
856 LLVM_DEBUG(dbgs() << "FnSpecialization: Can't track arguments!\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Can't track arguments!\n"
<< "FnSpecialization: Doesn't have local linkage, or "
<< "has its address taken\n"; } } while (false)
857 << "FnSpecialization: Doesn't have local linkage, or "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Can't track arguments!\n"
<< "FnSpecialization: Doesn't have local linkage, or "
<< "has its address taken\n"; } } while (false)
858 << "has its address taken\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Can't track arguments!\n"
<< "FnSpecialization: Doesn't have local linkage, or "
<< "has its address taken\n"; } } while (false)
;
859 }
860
861 // Assume the function is called.
862 Solver.markBlockExecutable(&F.front());
863
864 // Assume nothing about the incoming arguments.
865 for (Argument &AI : F.args())
866 Solver.markOverdefined(&AI);
867 }
868
869 // Determine if we can track any of the module's global variables. If so, add
870 // the global variables we can track to the solver's set of tracked global
871 // variables.
872 for (GlobalVariable &G : M.globals()) {
873 G.removeDeadConstantUsers();
874 if (canTrackGlobalVariableInterprocedurally(&G))
875 Solver.trackValueOfGlobalVariable(&G);
876 }
877
878 auto &TrackedFuncs = Solver.getArgumentTrackedFunctions();
879 SmallVector<Function *, 16> FuncDecls(TrackedFuncs.begin(),
880 TrackedFuncs.end());
881
882 // No tracked functions, so nothing to do: don't run the solver and remove
883 // the ssa_copy intrinsics that may have been introduced.
884 if (TrackedFuncs.empty()) {
885 removeSSACopy(M);
886 return false;
887 }
888
889 // Solve for constants.
890 auto RunSCCPSolver = [&](auto &WorkList) {
891 bool ResolvedUndefs = true;
892
893 while (ResolvedUndefs) {
894 // Not running the solver unnecessary is checked in regression test
895 // nothing-to-do.ll, so if this debug message is changed, this regression
896 // test needs updating too.
897 LLVM_DEBUG(dbgs() << "FnSpecialization: Running solver\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Running solver\n"
; } } while (false)
;
898
899 Solver.solve();
900 LLVM_DEBUG(dbgs() << "FnSpecialization: Resolving undefs\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Resolving undefs\n"
; } } while (false)
;
901 ResolvedUndefs = false;
902 for (Function *F : WorkList)
903 if (Solver.resolvedUndefsIn(*F))
904 ResolvedUndefs = true;
905 }
906
907 for (auto *F : WorkList) {
908 for (BasicBlock &BB : *F) {
909 if (!Solver.isBlockExecutable(&BB))
910 continue;
911 // FIXME: The solver may make changes to the function here, so set
912 // Changed, even if later function specialization does not trigger.
913 for (auto &I : make_early_inc_range(BB))
914 Changed |= FS.tryToReplaceWithConstant(&I);
915 }
916 }
917 };
918
919#ifndef NDEBUG
920 LLVM_DEBUG(dbgs() << "FnSpecialization: Worklist fn decls:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Worklist fn decls:\n"
; } } while (false)
;
921 for (auto *F : FuncDecls)
922 LLVM_DEBUG(dbgs() << "FnSpecialization: *) " << F->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: *) "
<< F->getName() << "\n"; } } while (false)
;
923#endif
924
925 // Initially resolve the constants in all the argument tracked functions.
926 RunSCCPSolver(FuncDecls);
927
928 SmallVector<Function *, 8> WorkList;
929 unsigned I = 0;
930 while (FuncSpecializationMaxIters != I++ &&
931 FS.specializeFunctions(FuncDecls, WorkList)) {
932 LLVM_DEBUG(dbgs() << "FnSpecialization: Finished iteration " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Finished iteration "
<< I << "\n"; } } while (false)
;
933
934 // Run the solver for the specialized functions.
935 RunSCCPSolver(WorkList);
936
937 // Replace some unresolved constant arguments.
938 constantArgPropagation(FuncDecls, M, Solver);
939
940 WorkList.clear();
941 Changed = true;
942 }
943
944 LLVM_DEBUG(dbgs() << "FnSpecialization: Number of specializations = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Number of specializations = "
<< NumFuncSpecialized << "\n"; } } while (false)
945 << NumFuncSpecialized << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("function-specialization")) { dbgs() << "FnSpecialization: Number of specializations = "
<< NumFuncSpecialized << "\n"; } } while (false)
;
946
947 // Remove any ssa_copy intrinsics that may have been introduced.
948 removeSSACopy(M);
949 return Changed;
950}