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 (e.g. functions,
10 // globals). Constant parameters like function pointers and constant globals
11 // are propagated to the callee by specializing the function.
12 //
13 // Current limitations:
14 // - It does not handle specialization of recursive functions,
15 // - It does not yet handle integer ranges.
16 // - Only 1 argument per function is specialised,
17 // - The cost-model could be further looked into,
18 // - We are not yet caching analysis results.
19 //
20 // Ideas:
21 // - With a function specialization attribute for arguments, we could have
22 // a direct way to steer function specialization, avoiding the cost-model,
23 // and thus control compile-times / code-size.
24 //
25 //===----------------------------------------------------------------------===//
26
27 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Analysis/AssumptionCache.h"
29 #include "llvm/Analysis/CodeMetrics.h"
30 #include "llvm/Analysis/DomTreeUpdater.h"
31 #include "llvm/Analysis/InlineCost.h"
32 #include "llvm/Analysis/LoopInfo.h"
33 #include "llvm/Analysis/TargetLibraryInfo.h"
34 #include "llvm/Analysis/TargetTransformInfo.h"
35 #include "llvm/Transforms/Scalar/SCCP.h"
36 #include "llvm/Transforms/Utils/Cloning.h"
37 #include "llvm/Transforms/Utils/SizeOpts.h"
38 #include <cmath>
39
40 using namespace llvm;
41
42 #define DEBUG_TYPE "function-specialization"
43
44 STATISTIC(NumFuncSpecialized, "Number of functions specialized");
45
46 static cl::opt<bool> ForceFunctionSpecialization(
47 "force-function-specialization", cl::init(false), cl::Hidden,
48 cl::desc("Force function specialization for every call site with a "
49 "constant argument"));
50
51 static cl::opt<unsigned> FuncSpecializationMaxIters(
52 "func-specialization-max-iters", cl::Hidden,
53 cl::desc("The maximum number of iterations function specialization is run"),
54 cl::init(1));
55
56 static cl::opt<unsigned> MaxConstantsThreshold(
57 "func-specialization-max-constants", cl::Hidden,
58 cl::desc("The maximum number of clones allowed for a single function "
59 "specialization"),
60 cl::init(3));
61
62 static cl::opt<unsigned>
63 AvgLoopIterationCount("func-specialization-avg-iters-cost", cl::Hidden,
64 cl::desc("Average loop iteration count cost"),
65 cl::init(10));
66
67 static cl::opt<bool> EnableSpecializationForLiteralConstant(
68 "function-specialization-for-literal-constant", cl::init(false), cl::Hidden,
69 cl::desc("Make function specialization available for literal constant."));
70
71 // Helper to check if \p LV is either overdefined or a constant int.
isOverdefined(const ValueLatticeElement & LV)72 static bool isOverdefined(const ValueLatticeElement &LV) {
73 return !LV.isUnknownOrUndef() && !LV.isConstant();
74 }
75
76 class FunctionSpecializer {
77
78 /// The IPSCCP Solver.
79 SCCPSolver &Solver;
80
81 /// Analyses used to help determine if a function should be specialized.
82 std::function<AssumptionCache &(Function &)> GetAC;
83 std::function<TargetTransformInfo &(Function &)> GetTTI;
84 std::function<TargetLibraryInfo &(Function &)> GetTLI;
85
86 SmallPtrSet<Function *, 2> SpecializedFuncs;
87
88 public:
FunctionSpecializer(SCCPSolver & Solver,std::function<AssumptionCache & (Function &)> GetAC,std::function<TargetTransformInfo & (Function &)> GetTTI,std::function<TargetLibraryInfo & (Function &)> GetTLI)89 FunctionSpecializer(SCCPSolver &Solver,
90 std::function<AssumptionCache &(Function &)> GetAC,
91 std::function<TargetTransformInfo &(Function &)> GetTTI,
92 std::function<TargetLibraryInfo &(Function &)> GetTLI)
93 : Solver(Solver), GetAC(GetAC), GetTTI(GetTTI), GetTLI(GetTLI) {}
94
95 /// Attempt to specialize functions in the module to enable constant
96 /// propagation across function boundaries.
97 ///
98 /// \returns true if at least one function is specialized.
99 bool
specializeFunctions(SmallVectorImpl<Function * > & FuncDecls,SmallVectorImpl<Function * > & CurrentSpecializations)100 specializeFunctions(SmallVectorImpl<Function *> &FuncDecls,
101 SmallVectorImpl<Function *> &CurrentSpecializations) {
102
103 // Attempt to specialize the argument-tracked functions.
104 bool Changed = false;
105 for (auto *F : FuncDecls) {
106 if (specializeFunction(F, CurrentSpecializations)) {
107 Changed = true;
108 LLVM_DEBUG(dbgs() << "FnSpecialization: Can specialize this func.\n");
109 } else {
110 LLVM_DEBUG(
111 dbgs() << "FnSpecialization: Cannot specialize this func.\n");
112 }
113 }
114
115 for (auto *SpecializedFunc : CurrentSpecializations) {
116 SpecializedFuncs.insert(SpecializedFunc);
117
118 // TODO: If we want to support specializing specialized functions,
119 // initialize here the state of the newly created functions, marking
120 // them argument-tracked and executable.
121
122 // Replace the function arguments for the specialized functions.
123 for (Argument &Arg : SpecializedFunc->args())
124 if (!Arg.use_empty() && tryToReplaceWithConstant(&Arg))
125 LLVM_DEBUG(dbgs() << "FnSpecialization: Replaced constant argument: "
126 << Arg.getName() << "\n");
127 }
128
129 NumFuncSpecialized += NbFunctionsSpecialized;
130 return Changed;
131 }
132
tryToReplaceWithConstant(Value * V)133 bool tryToReplaceWithConstant(Value *V) {
134 if (!V->getType()->isSingleValueType() || isa<CallBase>(V) ||
135 V->user_empty())
136 return false;
137
138 const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
139 if (isOverdefined(IV))
140 return false;
141 auto *Const = IV.isConstant() ? Solver.getConstant(IV)
142 : UndefValue::get(V->getType());
143 V->replaceAllUsesWith(Const);
144
145 // TODO: Update the solver here if we want to specialize specialized
146 // functions.
147 return true;
148 }
149
150 private:
151 // The number of functions specialised, used for collecting statistics and
152 // also in the cost model.
153 unsigned NbFunctionsSpecialized = 0;
154
155 /// This function decides whether to specialize function \p F based on the
156 /// known constant values its arguments can take on. Specialization is
157 /// performed on the first interesting argument. Specializations based on
158 /// additional arguments will be evaluated on following iterations of the
159 /// main IPSCCP solve loop. \returns true if the function is specialized and
160 /// false otherwise.
specializeFunction(Function * F,SmallVectorImpl<Function * > & Specializations)161 bool specializeFunction(Function *F,
162 SmallVectorImpl<Function *> &Specializations) {
163
164 // Do not specialize the cloned function again.
165 if (SpecializedFuncs.contains(F)) {
166 return false;
167 }
168
169 // If we're optimizing the function for size, we shouldn't specialize it.
170 if (F->hasOptSize() ||
171 shouldOptimizeForSize(F, nullptr, nullptr, PGSOQueryType::IRPass))
172 return false;
173
174 // Exit if the function is not executable. There's no point in specializing
175 // a dead function.
176 if (!Solver.isBlockExecutable(&F->getEntryBlock()))
177 return false;
178
179 LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()
180 << "\n");
181 // Determine if we should specialize the function based on the values the
182 // argument can take on. If specialization is not profitable, we continue
183 // on to the next argument.
184 for (Argument &A : F->args()) {
185 LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing arg: " << A.getName()
186 << "\n");
187 // True if this will be a partial specialization. We will need to keep
188 // the original function around in addition to the added specializations.
189 bool IsPartial = true;
190
191 // Determine if this argument is interesting. If we know the argument can
192 // take on any constant values, they are collected in Constants. If the
193 // argument can only ever equal a constant value in Constants, the
194 // function will be completely specialized, and the IsPartial flag will
195 // be set to false by isArgumentInteresting (that function only adds
196 // values to the Constants list that are deemed profitable).
197 SmallVector<Constant *, 4> Constants;
198 if (!isArgumentInteresting(&A, Constants, IsPartial)) {
199 LLVM_DEBUG(dbgs() << "FnSpecialization: Argument is not interesting\n");
200 continue;
201 }
202
203 assert(!Constants.empty() && "No constants on which to specialize");
204 LLVM_DEBUG(dbgs() << "FnSpecialization: Argument is interesting!\n"
205 << "FnSpecialization: Specializing '" << F->getName()
206 << "' on argument: " << A << "\n"
207 << "FnSpecialization: Constants are:\n\n";
208 for (unsigned I = 0; I < Constants.size(); ++I) dbgs()
209 << *Constants[I] << "\n";
210 dbgs() << "FnSpecialization: End of constants\n\n");
211
212 // Create a version of the function in which the argument is marked
213 // constant with the given value.
214 for (auto *C : Constants) {
215 // Clone the function. We leave the ValueToValueMap empty to allow
216 // IPSCCP to propagate the constant arguments.
217 ValueToValueMapTy EmptyMap;
218 Function *Clone = CloneFunction(F, EmptyMap);
219 Argument *ClonedArg = Clone->arg_begin() + A.getArgNo();
220
221 // Rewrite calls to the function so that they call the clone instead.
222 rewriteCallSites(F, Clone, *ClonedArg, C);
223
224 // Initialize the lattice state of the arguments of the function clone,
225 // marking the argument on which we specialized the function constant
226 // with the given value.
227 Solver.markArgInFuncSpecialization(F, ClonedArg, C);
228
229 // Mark all the specialized functions
230 Specializations.push_back(Clone);
231 NbFunctionsSpecialized++;
232 }
233
234 // TODO: if we want to support specialize specialized functions, and if
235 // the function has been completely specialized, the original function is
236 // no longer needed, so we would need to mark it unreachable here.
237
238 // FIXME: Only one argument per function.
239 return true;
240 }
241
242 return false;
243 }
244
245 /// Compute the cost of specializing function \p F.
getSpecializationCost(Function * F)246 InstructionCost getSpecializationCost(Function *F) {
247 // Compute the code metrics for the function.
248 SmallPtrSet<const Value *, 32> EphValues;
249 CodeMetrics::collectEphemeralValues(F, &(GetAC)(*F), EphValues);
250 CodeMetrics Metrics;
251 for (BasicBlock &BB : *F)
252 Metrics.analyzeBasicBlock(&BB, (GetTTI)(*F), EphValues);
253
254 // If the code metrics reveal that we shouldn't duplicate the function, we
255 // shouldn't specialize it. Set the specialization cost to Invalid.
256 if (Metrics.notDuplicatable) {
257 InstructionCost C{};
258 C.setInvalid();
259 return C;
260 }
261
262 // Otherwise, set the specialization cost to be the cost of all the
263 // instructions in the function and penalty for specializing more functions.
264 unsigned Penalty = NbFunctionsSpecialized + 1;
265 return Metrics.NumInsts * InlineConstants::InstrCost * Penalty;
266 }
267
getUserBonus(User * U,llvm::TargetTransformInfo & TTI,LoopInfo & LI)268 InstructionCost getUserBonus(User *U, llvm::TargetTransformInfo &TTI,
269 LoopInfo &LI) {
270 auto *I = dyn_cast_or_null<Instruction>(U);
271 // If not an instruction we do not know how to evaluate.
272 // Keep minimum possible cost for now so that it doesnt affect
273 // specialization.
274 if (!I)
275 return std::numeric_limits<unsigned>::min();
276
277 auto Cost = TTI.getUserCost(U, TargetTransformInfo::TCK_SizeAndLatency);
278
279 // Traverse recursively if there are more uses.
280 // TODO: Any other instructions to be added here?
281 if (I->mayReadFromMemory() || I->isCast())
282 for (auto *User : I->users())
283 Cost += getUserBonus(User, TTI, LI);
284
285 // Increase the cost if it is inside the loop.
286 auto LoopDepth = LI.getLoopDepth(I->getParent());
287 Cost *= std::pow((double)AvgLoopIterationCount, LoopDepth);
288 return Cost;
289 }
290
291 /// Compute a bonus for replacing argument \p A with constant \p C.
getSpecializationBonus(Argument * A,Constant * C)292 InstructionCost getSpecializationBonus(Argument *A, Constant *C) {
293 Function *F = A->getParent();
294 DominatorTree DT(*F);
295 LoopInfo LI(DT);
296 auto &TTI = (GetTTI)(*F);
297 LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for: " << *A
298 << "\n");
299
300 InstructionCost TotalCost = 0;
301 for (auto *U : A->users()) {
302 TotalCost += getUserBonus(U, TTI, LI);
303 LLVM_DEBUG(dbgs() << "FnSpecialization: User cost ";
304 TotalCost.print(dbgs()); dbgs() << " for: " << *U << "\n");
305 }
306
307 // The below heuristic is only concerned with exposing inlining
308 // opportunities via indirect call promotion. If the argument is not a
309 // function pointer, give up.
310 if (!isa<PointerType>(A->getType()) ||
311 !isa<FunctionType>(A->getType()->getPointerElementType()))
312 return TotalCost;
313
314 // Since the argument is a function pointer, its incoming constant values
315 // should be functions or constant expressions. The code below attempts to
316 // look through cast expressions to find the function that will be called.
317 Value *CalledValue = C;
318 while (isa<ConstantExpr>(CalledValue) &&
319 cast<ConstantExpr>(CalledValue)->isCast())
320 CalledValue = cast<User>(CalledValue)->getOperand(0);
321 Function *CalledFunction = dyn_cast<Function>(CalledValue);
322 if (!CalledFunction)
323 return TotalCost;
324
325 // Get TTI for the called function (used for the inline cost).
326 auto &CalleeTTI = (GetTTI)(*CalledFunction);
327
328 // Look at all the call sites whose called value is the argument.
329 // Specializing the function on the argument would allow these indirect
330 // calls to be promoted to direct calls. If the indirect call promotion
331 // would likely enable the called function to be inlined, specializing is a
332 // good idea.
333 int Bonus = 0;
334 for (User *U : A->users()) {
335 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
336 continue;
337 auto *CS = cast<CallBase>(U);
338 if (CS->getCalledOperand() != A)
339 continue;
340
341 // Get the cost of inlining the called function at this call site. Note
342 // that this is only an estimate. The called function may eventually
343 // change in a way that leads to it not being inlined here, even though
344 // inlining looks profitable now. For example, one of its called
345 // functions may be inlined into it, making the called function too large
346 // to be inlined into this call site.
347 //
348 // We apply a boost for performing indirect call promotion by increasing
349 // the default threshold by the threshold for indirect calls.
350 auto Params = getInlineParams();
351 Params.DefaultThreshold += InlineConstants::IndirectCallThreshold;
352 InlineCost IC =
353 getInlineCost(*CS, CalledFunction, Params, CalleeTTI, GetAC, GetTLI);
354
355 // We clamp the bonus for this call to be between zero and the default
356 // threshold.
357 if (IC.isAlways())
358 Bonus += Params.DefaultThreshold;
359 else if (IC.isVariable() && IC.getCostDelta() > 0)
360 Bonus += IC.getCostDelta();
361 }
362
363 return TotalCost + Bonus;
364 }
365
366 /// Determine if we should specialize a function based on the incoming values
367 /// of the given argument.
368 ///
369 /// This function implements the goal-directed heuristic. It determines if
370 /// specializing the function based on the incoming values of argument \p A
371 /// would result in any significant optimization opportunities. If
372 /// optimization opportunities exist, the constant values of \p A on which to
373 /// specialize the function are collected in \p Constants. If the values in
374 /// \p Constants represent the complete set of values that \p A can take on,
375 /// the function will be completely specialized, and the \p IsPartial flag is
376 /// set to false.
377 ///
378 /// \returns true if the function should be specialized on the given
379 /// argument.
isArgumentInteresting(Argument * A,SmallVectorImpl<Constant * > & Constants,bool & IsPartial)380 bool isArgumentInteresting(Argument *A,
381 SmallVectorImpl<Constant *> &Constants,
382 bool &IsPartial) {
383 Function *F = A->getParent();
384
385 // For now, don't attempt to specialize functions based on the values of
386 // composite types.
387 if (!A->getType()->isSingleValueType() || A->user_empty())
388 return false;
389
390 // If the argument isn't overdefined, there's nothing to do. It should
391 // already be constant.
392 if (!Solver.getLatticeValueFor(A).isOverdefined()) {
393 LLVM_DEBUG(dbgs() << "FnSpecialization: nothing to do, arg is already "
394 << "constant?\n");
395 return false;
396 }
397
398 // Collect the constant values that the argument can take on. If the
399 // argument can't take on any constant values, we aren't going to
400 // specialize the function. While it's possible to specialize the function
401 // based on non-constant arguments, there's likely not much benefit to
402 // constant propagation in doing so.
403 //
404 // TODO 1: currently it won't specialize if there are over the threshold of
405 // calls using the same argument, e.g foo(a) x 4 and foo(b) x 1, but it
406 // might be beneficial to take the occurrences into account in the cost
407 // model, so we would need to find the unique constants.
408 //
409 // TODO 2: this currently does not support constants, i.e. integer ranges.
410 //
411 SmallVector<Constant *, 4> PossibleConstants;
412 bool AllConstant = getPossibleConstants(A, PossibleConstants);
413 if (PossibleConstants.empty()) {
414 LLVM_DEBUG(dbgs() << "FnSpecialization: no possible constants found\n");
415 return false;
416 }
417 if (PossibleConstants.size() > MaxConstantsThreshold) {
418 LLVM_DEBUG(dbgs() << "FnSpecialization: number of constants found exceed "
419 << "the maximum number of constants threshold.\n");
420 return false;
421 }
422
423 // Determine if it would be profitable to create a specialization of the
424 // function where the argument takes on the given constant value. If so,
425 // add the constant to Constants.
426 auto FnSpecCost = getSpecializationCost(F);
427 if (!FnSpecCost.isValid()) {
428 LLVM_DEBUG(dbgs() << "FnSpecialization: Invalid specialisation cost.\n");
429 return false;
430 }
431
432 LLVM_DEBUG(dbgs() << "FnSpecialization: func specialisation cost: ";
433 FnSpecCost.print(dbgs()); dbgs() << "\n");
434
435 for (auto *C : PossibleConstants) {
436 LLVM_DEBUG(dbgs() << "FnSpecialization: Constant: " << *C << "\n");
437 if (ForceFunctionSpecialization) {
438 LLVM_DEBUG(dbgs() << "FnSpecialization: Forced!\n");
439 Constants.push_back(C);
440 continue;
441 }
442 if (getSpecializationBonus(A, C) > FnSpecCost) {
443 LLVM_DEBUG(dbgs() << "FnSpecialization: profitable!\n");
444 Constants.push_back(C);
445 } else {
446 LLVM_DEBUG(dbgs() << "FnSpecialization: not profitable\n");
447 }
448 }
449
450 // None of the constant values the argument can take on were deemed good
451 // candidates on which to specialize the function.
452 if (Constants.empty())
453 return false;
454
455 // This will be a partial specialization if some of the constants were
456 // rejected due to their profitability.
457 IsPartial = !AllConstant || PossibleConstants.size() != Constants.size();
458
459 return true;
460 }
461
462 /// Collect in \p Constants all the constant values that argument \p A can
463 /// take on.
464 ///
465 /// \returns true if all of the values the argument can take on are constant
466 /// (e.g., the argument's parent function cannot be called with an
467 /// overdefined value).
getPossibleConstants(Argument * A,SmallVectorImpl<Constant * > & Constants)468 bool getPossibleConstants(Argument *A,
469 SmallVectorImpl<Constant *> &Constants) {
470 Function *F = A->getParent();
471 bool AllConstant = true;
472
473 // Iterate over all the call sites of the argument's parent function.
474 for (User *U : F->users()) {
475 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
476 continue;
477 auto &CS = *cast<CallBase>(U);
478
479 // If the parent of the call site will never be executed, we don't need
480 // to worry about the passed value.
481 if (!Solver.isBlockExecutable(CS.getParent()))
482 continue;
483
484 auto *V = CS.getArgOperand(A->getArgNo());
485 // TrackValueOfGlobalVariable only tracks scalar global variables.
486 if (auto *GV = dyn_cast<GlobalVariable>(V)) {
487 if (!GV->getValueType()->isSingleValueType()) {
488 return false;
489 }
490 }
491
492 if (isa<Constant>(V) && (Solver.getLatticeValueFor(V).isConstant() ||
493 EnableSpecializationForLiteralConstant))
494 Constants.push_back(cast<Constant>(V));
495 else
496 AllConstant = false;
497 }
498
499 // If the argument can only take on constant values, AllConstant will be
500 // true.
501 return AllConstant;
502 }
503
504 /// Rewrite calls to function \p F to call function \p Clone instead.
505 ///
506 /// This function modifies calls to function \p F whose argument at index \p
507 /// ArgNo is equal to constant \p C. The calls are rewritten to call function
508 /// \p Clone instead.
rewriteCallSites(Function * F,Function * Clone,Argument & Arg,Constant * C)509 void rewriteCallSites(Function *F, Function *Clone, Argument &Arg,
510 Constant *C) {
511 unsigned ArgNo = Arg.getArgNo();
512 SmallVector<CallBase *, 4> CallSitesToRewrite;
513 for (auto *U : F->users()) {
514 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
515 continue;
516 auto &CS = *cast<CallBase>(U);
517 if (!CS.getCalledFunction() || CS.getCalledFunction() != F)
518 continue;
519 CallSitesToRewrite.push_back(&CS);
520 }
521 for (auto *CS : CallSitesToRewrite) {
522 if ((CS->getFunction() == Clone && CS->getArgOperand(ArgNo) == &Arg) ||
523 CS->getArgOperand(ArgNo) == C) {
524 CS->setCalledFunction(Clone);
525 Solver.markOverdefined(CS);
526 }
527 }
528 }
529 };
530
531 /// Function to clean up the left over intrinsics from SCCP util.
cleanup(Module & M)532 static void cleanup(Module &M) {
533 for (Function &F : M) {
534 for (BasicBlock &BB : F) {
535 for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
536 Instruction *Inst = &*BI++;
537 if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
538 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
539 Value *Op = II->getOperand(0);
540 Inst->replaceAllUsesWith(Op);
541 Inst->eraseFromParent();
542 }
543 }
544 }
545 }
546 }
547 }
548
runFunctionSpecialization(Module & M,const DataLayout & DL,std::function<TargetLibraryInfo & (Function &)> GetTLI,std::function<TargetTransformInfo & (Function &)> GetTTI,std::function<AssumptionCache & (Function &)> GetAC,function_ref<AnalysisResultsForFn (Function &)> GetAnalysis)549 bool llvm::runFunctionSpecialization(
550 Module &M, const DataLayout &DL,
551 std::function<TargetLibraryInfo &(Function &)> GetTLI,
552 std::function<TargetTransformInfo &(Function &)> GetTTI,
553 std::function<AssumptionCache &(Function &)> GetAC,
554 function_ref<AnalysisResultsForFn(Function &)> GetAnalysis) {
555 SCCPSolver Solver(DL, GetTLI, M.getContext());
556 FunctionSpecializer FS(Solver, GetAC, GetTTI, GetTLI);
557 bool Changed = false;
558
559 // Loop over all functions, marking arguments to those with their addresses
560 // taken or that are external as overdefined.
561 for (Function &F : M) {
562 if (F.isDeclaration())
563 continue;
564 if (F.hasFnAttribute(Attribute::NoDuplicate))
565 continue;
566
567 LLVM_DEBUG(dbgs() << "\nFnSpecialization: Analysing decl: " << F.getName()
568 << "\n");
569 Solver.addAnalysis(F, GetAnalysis(F));
570
571 // Determine if we can track the function's arguments. If so, add the
572 // function to the solver's set of argument-tracked functions.
573 if (canTrackArgumentsInterprocedurally(&F)) {
574 LLVM_DEBUG(dbgs() << "FnSpecialization: Can track arguments\n");
575 Solver.addArgumentTrackedFunction(&F);
576 continue;
577 } else {
578 LLVM_DEBUG(dbgs() << "FnSpecialization: Can't track arguments!\n"
579 << "FnSpecialization: Doesn't have local linkage, or "
580 << "has its address taken\n");
581 }
582
583 // Assume the function is called.
584 Solver.markBlockExecutable(&F.front());
585
586 // Assume nothing about the incoming arguments.
587 for (Argument &AI : F.args())
588 Solver.markOverdefined(&AI);
589 }
590
591 // Determine if we can track any of the module's global variables. If so, add
592 // the global variables we can track to the solver's set of tracked global
593 // variables.
594 for (GlobalVariable &G : M.globals()) {
595 G.removeDeadConstantUsers();
596 if (canTrackGlobalVariableInterprocedurally(&G))
597 Solver.trackValueOfGlobalVariable(&G);
598 }
599
600 // Solve for constants.
601 auto RunSCCPSolver = [&](auto &WorkList) {
602 bool ResolvedUndefs = true;
603
604 while (ResolvedUndefs) {
605 LLVM_DEBUG(dbgs() << "FnSpecialization: Running solver\n");
606 Solver.solve();
607 LLVM_DEBUG(dbgs() << "FnSpecialization: Resolving undefs\n");
608 ResolvedUndefs = false;
609 for (Function *F : WorkList)
610 if (Solver.resolvedUndefsIn(*F))
611 ResolvedUndefs = true;
612 }
613
614 for (auto *F : WorkList) {
615 for (BasicBlock &BB : *F) {
616 if (!Solver.isBlockExecutable(&BB))
617 continue;
618 for (auto &I : make_early_inc_range(BB))
619 FS.tryToReplaceWithConstant(&I);
620 }
621 }
622 };
623
624 auto &TrackedFuncs = Solver.getArgumentTrackedFunctions();
625 SmallVector<Function *, 16> FuncDecls(TrackedFuncs.begin(),
626 TrackedFuncs.end());
627 #ifndef NDEBUG
628 LLVM_DEBUG(dbgs() << "FnSpecialization: Worklist fn decls:\n");
629 for (auto *F : FuncDecls)
630 LLVM_DEBUG(dbgs() << "FnSpecialization: *) " << F->getName() << "\n");
631 #endif
632
633 // Initially resolve the constants in all the argument tracked functions.
634 RunSCCPSolver(FuncDecls);
635
636 SmallVector<Function *, 2> CurrentSpecializations;
637 unsigned I = 0;
638 while (FuncSpecializationMaxIters != I++ &&
639 FS.specializeFunctions(FuncDecls, CurrentSpecializations)) {
640 // TODO: run the solver here for the specialized functions only if we want
641 // to specialize recursively.
642
643 CurrentSpecializations.clear();
644 Changed = true;
645 }
646
647 // Clean up the IR by removing ssa_copy intrinsics.
648 cleanup(M);
649 return Changed;
650 }
651