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#include "llvm/Transforms/IPO/FunctionSpecialization.h"
10#include "llvm/ADT/Statistic.h"
11#include "llvm/Analysis/CodeMetrics.h"
12#include "llvm/Analysis/ConstantFolding.h"
13#include "llvm/Analysis/InlineCost.h"
14#include "llvm/Analysis/InstructionSimplify.h"
15#include "llvm/Analysis/TargetTransformInfo.h"
16#include "llvm/Analysis/ValueLattice.h"
17#include "llvm/Analysis/ValueLatticeUtils.h"
18#include "llvm/Analysis/ValueTracking.h"
19#include "llvm/Transforms/Scalar/SCCP.h"
20#include "llvm/Transforms/Utils/Cloning.h"
21#include "llvm/Transforms/Utils/SCCPSolver.h"
22#include "llvm/Transforms/Utils/SizeOpts.h"
23
24using namespace llvm;
25
26#define DEBUG_TYPE "function-specialization"
27
28STATISTIC(NumSpecsCreated, "Number of specializations created");
29
30namespace llvm {
31
32static cl::opt<bool> ForceSpecialization(
33 "force-specialization", cl::init(Val: false), cl::Hidden,
34 cl::desc(
35 "Force function specialization for every call site with a constant "
36 "argument"));
37
38static cl::opt<unsigned> MaxClones(
39 "funcspec-max-clones", cl::init(Val: 3), cl::Hidden, cl::desc(
40 "The maximum number of clones allowed for a single function "
41 "specialization"));
42
43static cl::opt<unsigned>
44 MaxDiscoveryIterations("funcspec-max-discovery-iterations", cl::init(Val: 100),
45 cl::Hidden,
46 cl::desc("The maximum number of iterations allowed "
47 "when searching for transitive "
48 "phis"));
49
50static cl::opt<unsigned> MaxIncomingPhiValues(
51 "funcspec-max-incoming-phi-values", cl::init(Val: 8), cl::Hidden,
52 cl::desc("The maximum number of incoming values a PHI node can have to be "
53 "considered during the specialization bonus estimation"));
54
55static cl::opt<unsigned> MaxBlockPredecessors(
56 "funcspec-max-block-predecessors", cl::init(Val: 2), cl::Hidden, cl::desc(
57 "The maximum number of predecessors a basic block can have to be "
58 "considered during the estimation of dead code"));
59
60static cl::opt<unsigned> MinFunctionSize(
61 "funcspec-min-function-size", cl::init(Val: 500), cl::Hidden,
62 cl::desc("Don't specialize functions that have less than this number of "
63 "instructions"));
64
65static cl::opt<unsigned> MaxCodeSizeGrowth(
66 "funcspec-max-codesize-growth", cl::init(Val: 3), cl::Hidden, cl::desc(
67 "Maximum codesize growth allowed per function"));
68
69static cl::opt<unsigned> MinCodeSizeSavings(
70 "funcspec-min-codesize-savings", cl::init(Val: 20), cl::Hidden,
71 cl::desc("Reject specializations whose codesize savings are less than this "
72 "much percent of the original function size"));
73
74static cl::opt<unsigned> MinLatencySavings(
75 "funcspec-min-latency-savings", cl::init(Val: 20), cl::Hidden,
76 cl::desc("Reject specializations whose latency savings are less than this "
77 "much percent of the original function size"));
78
79static cl::opt<unsigned> MinInliningBonus(
80 "funcspec-min-inlining-bonus", cl::init(Val: 300), cl::Hidden,
81 cl::desc("Reject specializations whose inlining bonus is less than this "
82 "much percent of the original function size"));
83
84static cl::opt<bool> SpecializeOnAddress(
85 "funcspec-on-address", cl::init(Val: false), cl::Hidden, cl::desc(
86 "Enable function specialization on the address of global values"));
87
88static cl::opt<bool> SpecializeLiteralConstant(
89 "funcspec-for-literal-constant", cl::init(Val: true), cl::Hidden,
90 cl::desc(
91 "Enable specialization of functions that take a literal constant as an "
92 "argument"));
93
94extern cl::opt<bool> ProfcheckDisableMetadataFixes;
95
96} // end namespace llvm
97
98bool InstCostVisitor::canEliminateSuccessor(BasicBlock *BB,
99 BasicBlock *Succ) const {
100 unsigned I = 0;
101 return all_of(Range: predecessors(BB: Succ), P: [&I, BB, Succ, this](BasicBlock *Pred) {
102 return I++ < MaxBlockPredecessors &&
103 (Pred == BB || Pred == Succ || !isBlockExecutable(BB: Pred));
104 });
105}
106
107// Estimates the codesize savings due to dead code after constant propagation.
108// \p WorkList represents the basic blocks of a specialization which will
109// eventually become dead once we replace instructions that are known to be
110// constants. The successors of such blocks are added to the list as long as
111// the \p Solver found they were executable prior to specialization, and only
112// if all their predecessors are dead.
113Cost InstCostVisitor::estimateBasicBlocks(
114 SmallVectorImpl<BasicBlock *> &WorkList) {
115 Cost CodeSize = 0;
116 // Accumulate the codesize savings of each basic block.
117 while (!WorkList.empty()) {
118 BasicBlock *BB = WorkList.pop_back_val();
119
120 // These blocks are considered dead as far as the InstCostVisitor
121 // is concerned. They haven't been proven dead yet by the Solver,
122 // but may become if we propagate the specialization arguments.
123 assert(Solver.isBlockExecutable(BB) && "BB already found dead by IPSCCP!");
124 if (!DeadBlocks.insert(V: BB).second)
125 continue;
126
127 for (Instruction &I : *BB) {
128 // If it's a known constant we have already accounted for it.
129 if (KnownConstants.contains(Val: &I))
130 continue;
131
132 Cost C = TTI.getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_CodeSize);
133
134 LLVM_DEBUG(dbgs() << "FnSpecialization: CodeSize " << C
135 << " for user " << I << "\n");
136 CodeSize += C;
137 }
138
139 // Keep adding dead successors to the list as long as they are
140 // executable and only reachable from dead blocks.
141 for (BasicBlock *SuccBB : successors(BB))
142 if (isBlockExecutable(BB: SuccBB) && canEliminateSuccessor(BB, Succ: SuccBB))
143 WorkList.push_back(Elt: SuccBB);
144 }
145 return CodeSize;
146}
147
148Constant *InstCostVisitor::findConstantFor(Value *V) const {
149 if (auto *C = dyn_cast<Constant>(Val: V))
150 return C;
151 if (auto *C = Solver.getConstantOrNull(V))
152 return C;
153 return KnownConstants.lookup(Val: V);
154}
155
156Cost InstCostVisitor::getCodeSizeSavingsFromPendingPHIs() {
157 Cost CodeSize;
158 while (!PendingPHIs.empty()) {
159 Instruction *Phi = PendingPHIs.pop_back_val();
160 // The pending PHIs could have been proven dead by now.
161 if (isBlockExecutable(BB: Phi->getParent()))
162 CodeSize += getCodeSizeSavingsForUser(User: Phi);
163 }
164 return CodeSize;
165}
166
167/// Compute the codesize savings for replacing argument \p A with constant \p C.
168Cost InstCostVisitor::getCodeSizeSavingsForArg(Argument *A, Constant *C) {
169 LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "
170 << C->getNameOrAsOperand() << "\n");
171 Cost CodeSize;
172 for (auto *U : A->users())
173 if (auto *UI = dyn_cast<Instruction>(Val: U))
174 if (isBlockExecutable(BB: UI->getParent()))
175 CodeSize += getCodeSizeSavingsForUser(User: UI, Use: A, C);
176
177 LLVM_DEBUG(dbgs() << "FnSpecialization: Accumulated bonus {CodeSize = "
178 << CodeSize << "} for argument " << *A << "\n");
179 return CodeSize;
180}
181
182/// Compute the latency savings from replacing all arguments with constants for
183/// a specialization candidate. As this function computes the latency savings
184/// for all Instructions in KnownConstants at once, it should be called only
185/// after every instruction has been visited, i.e. after:
186///
187/// * getCodeSizeSavingsForArg has been run for every constant argument of a
188/// specialization candidate
189///
190/// * getCodeSizeSavingsFromPendingPHIs has been run
191///
192/// to ensure that the latency savings are calculated for all Instructions we
193/// have visited and found to be constant.
194Cost InstCostVisitor::getLatencySavingsForKnownConstants() {
195 auto &BFI = GetBFI(*F);
196 Cost TotalLatency = 0;
197
198 for (auto Pair : KnownConstants) {
199 Instruction *I = dyn_cast<Instruction>(Val: Pair.first);
200 if (!I)
201 continue;
202
203 uint64_t Weight = BFI.getBlockFreq(BB: I->getParent()).getFrequency() /
204 BFI.getEntryFreq().getFrequency();
205
206 Cost Latency =
207 Weight * TTI.getInstructionCost(U: I, CostKind: TargetTransformInfo::TCK_Latency);
208
209 LLVM_DEBUG(dbgs() << "FnSpecialization: {Latency = " << Latency
210 << "} for instruction " << *I << "\n");
211
212 TotalLatency += Latency;
213 }
214
215 return TotalLatency;
216}
217
218Cost InstCostVisitor::getCodeSizeSavingsForUser(Instruction *User, Value *Use,
219 Constant *C) {
220 // We have already propagated a constant for this user.
221 if (KnownConstants.contains(Val: User))
222 return 0;
223
224 // Cache the iterator before visiting.
225 LastVisited = Use ? KnownConstants.insert(KV: {Use, C}).first
226 : KnownConstants.end();
227
228 Cost CodeSize = 0;
229 if (auto *I = dyn_cast<SwitchInst>(Val: User)) {
230 CodeSize = estimateSwitchInst(I&: *I);
231 } else if (auto *I = dyn_cast<CondBrInst>(Val: User)) {
232 CodeSize = estimateCondBrInst(I&: *I);
233 } else {
234 C = visit(I&: *User);
235 if (!C)
236 return 0;
237 }
238
239 // Even though it doesn't make sense to bind switch and branch instructions
240 // with a constant, unlike any other instruction type, it prevents estimating
241 // their bonus multiple times.
242 KnownConstants.insert(KV: {User, C});
243
244 CodeSize += TTI.getInstructionCost(U: User, CostKind: TargetTransformInfo::TCK_CodeSize);
245
246 LLVM_DEBUG(dbgs() << "FnSpecialization: {CodeSize = " << CodeSize
247 << "} for user " << *User << "\n");
248
249 for (auto *U : User->users())
250 if (auto *UI = dyn_cast<Instruction>(Val: U))
251 if (UI != User && isBlockExecutable(BB: UI->getParent()))
252 CodeSize += getCodeSizeSavingsForUser(User: UI, Use: User, C);
253
254 return CodeSize;
255}
256
257Cost InstCostVisitor::estimateSwitchInst(SwitchInst &I) {
258 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
259
260 if (I.getCondition() != LastVisited->first)
261 return 0;
262
263 auto *C = dyn_cast<ConstantInt>(Val: LastVisited->second);
264 if (!C)
265 return 0;
266
267 BasicBlock *Succ = I.findCaseValue(C)->getCaseSuccessor();
268 // Initialize the worklist with the dead basic blocks. These are the
269 // destination labels which are different from the one corresponding
270 // to \p C. They should be executable and have a unique predecessor.
271 SmallVector<BasicBlock *> WorkList;
272 for (const auto &Case : I.cases()) {
273 BasicBlock *BB = Case.getCaseSuccessor();
274 if (BB != Succ && isBlockExecutable(BB) &&
275 canEliminateSuccessor(BB: I.getParent(), Succ: BB))
276 WorkList.push_back(Elt: BB);
277 }
278
279 return estimateBasicBlocks(WorkList);
280}
281
282Cost InstCostVisitor::estimateCondBrInst(CondBrInst &I) {
283 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
284
285 if (I.getCondition() != LastVisited->first)
286 return 0;
287
288 BasicBlock *Succ = I.getSuccessor(i: LastVisited->second->isOneValue());
289 // Initialize the worklist with the dead successor as long as
290 // it is executable and has a unique predecessor.
291 SmallVector<BasicBlock *> WorkList;
292 if (isBlockExecutable(BB: Succ) && canEliminateSuccessor(BB: I.getParent(), Succ))
293 WorkList.push_back(Elt: Succ);
294
295 return estimateBasicBlocks(WorkList);
296}
297
298bool InstCostVisitor::discoverTransitivelyIncomingValues(
299 Constant *Const, PHINode *Root, DenseSet<PHINode *> &TransitivePHIs) {
300
301 SmallVector<PHINode *, 64> WorkList;
302 WorkList.push_back(Elt: Root);
303 unsigned Iter = 0;
304
305 while (!WorkList.empty()) {
306 PHINode *PN = WorkList.pop_back_val();
307
308 if (++Iter > MaxDiscoveryIterations ||
309 PN->getNumIncomingValues() > MaxIncomingPhiValues)
310 return false;
311
312 if (!TransitivePHIs.insert(V: PN).second)
313 continue;
314
315 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
316 Value *V = PN->getIncomingValue(i: I);
317
318 // Disregard self-references and dead incoming values.
319 if (auto *Inst = dyn_cast<Instruction>(Val: V))
320 if (Inst == PN || !isBlockExecutable(BB: PN->getIncomingBlock(i: I)))
321 continue;
322
323 if (Constant *C = findConstantFor(V)) {
324 // Not all incoming values are the same constant. Bail immediately.
325 if (C != Const)
326 return false;
327 continue;
328 }
329
330 if (auto *Phi = dyn_cast<PHINode>(Val: V)) {
331 WorkList.push_back(Elt: Phi);
332 continue;
333 }
334
335 // We can't reason about anything else.
336 return false;
337 }
338 }
339 return true;
340}
341
342Constant *InstCostVisitor::visitPHINode(PHINode &I) {
343 if (I.getNumIncomingValues() > MaxIncomingPhiValues)
344 return nullptr;
345
346 bool Inserted = VisitedPHIs.insert(V: &I).second;
347 Constant *Const = nullptr;
348 bool HaveSeenIncomingPHI = false;
349
350 for (unsigned Idx = 0, E = I.getNumIncomingValues(); Idx != E; ++Idx) {
351 Value *V = I.getIncomingValue(i: Idx);
352
353 // Disregard self-references and dead incoming values.
354 if (auto *Inst = dyn_cast<Instruction>(Val: V))
355 if (Inst == &I || !isBlockExecutable(BB: I.getIncomingBlock(i: Idx)))
356 continue;
357
358 if (Constant *C = findConstantFor(V)) {
359 if (!Const)
360 Const = C;
361 // Not all incoming values are the same constant. Bail immediately.
362 if (C != Const)
363 return nullptr;
364 continue;
365 }
366
367 if (Inserted) {
368 // First time we are seeing this phi. We will retry later, after
369 // all the constant arguments have been propagated. Bail for now.
370 PendingPHIs.push_back(Elt: &I);
371 return nullptr;
372 }
373
374 if (isa<PHINode>(Val: V)) {
375 // Perhaps it is a Transitive Phi. We will confirm later.
376 HaveSeenIncomingPHI = true;
377 continue;
378 }
379
380 // We can't reason about anything else.
381 return nullptr;
382 }
383
384 if (!Const)
385 return nullptr;
386
387 if (!HaveSeenIncomingPHI)
388 return Const;
389
390 DenseSet<PHINode *> TransitivePHIs;
391 if (!discoverTransitivelyIncomingValues(Const, Root: &I, TransitivePHIs))
392 return nullptr;
393
394 return Const;
395}
396
397Constant *InstCostVisitor::visitFreezeInst(FreezeInst &I) {
398 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
399
400 if (isGuaranteedNotToBeUndefOrPoison(V: LastVisited->second))
401 return LastVisited->second;
402 return nullptr;
403}
404
405Constant *InstCostVisitor::visitCallBase(CallBase &I) {
406 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
407
408 Function *F = I.getCalledFunction();
409 if (!F || !canConstantFoldCallTo(Call: &I, F))
410 return nullptr;
411
412 SmallVector<Constant *, 8> Operands;
413 Operands.reserve(N: I.getNumOperands());
414
415 for (unsigned Idx = 0, E = I.getNumOperands() - 1; Idx != E; ++Idx) {
416 Value *V = I.getOperand(i_nocapture: Idx);
417 if (isa<MetadataAsValue>(Val: V))
418 return nullptr;
419 Constant *C = findConstantFor(V);
420 if (!C)
421 return nullptr;
422 Operands.push_back(Elt: C);
423 }
424
425 auto Ops = ArrayRef(Operands.begin(), Operands.end());
426 return ConstantFoldCall(Call: &I, F, Operands: Ops);
427}
428
429Constant *InstCostVisitor::visitLoadInst(LoadInst &I) {
430 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
431
432 if (isa<ConstantPointerNull>(Val: LastVisited->second))
433 return nullptr;
434 return ConstantFoldLoadFromConstPtr(C: LastVisited->second, Ty: I.getType(), DL);
435}
436
437Constant *InstCostVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
438 SmallVector<Constant *, 8> Operands;
439 Operands.reserve(N: I.getNumOperands());
440
441 for (unsigned Idx = 0, E = I.getNumOperands(); Idx != E; ++Idx) {
442 Value *V = I.getOperand(i_nocapture: Idx);
443 Constant *C = findConstantFor(V);
444 if (!C)
445 return nullptr;
446 Operands.push_back(Elt: C);
447 }
448
449 auto Ops = ArrayRef(Operands.begin(), Operands.end());
450 return ConstantFoldInstOperands(I: &I, Ops, DL);
451}
452
453Constant *InstCostVisitor::visitSelectInst(SelectInst &I) {
454 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
455
456 if (I.getCondition() == LastVisited->first) {
457 Value *V = LastVisited->second->isNullValue() ? I.getFalseValue()
458 : I.getTrueValue();
459 return findConstantFor(V);
460 }
461 if (Constant *Condition = findConstantFor(V: I.getCondition()))
462 if ((I.getTrueValue() == LastVisited->first && Condition->isOneValue()) ||
463 (I.getFalseValue() == LastVisited->first && Condition->isNullValue()))
464 return LastVisited->second;
465 return nullptr;
466}
467
468Constant *InstCostVisitor::visitCastInst(CastInst &I) {
469 return ConstantFoldCastOperand(Opcode: I.getOpcode(), C: LastVisited->second,
470 DestTy: I.getType(), DL);
471}
472
473Constant *InstCostVisitor::visitCmpInst(CmpInst &I) {
474 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
475
476 Constant *Const = LastVisited->second;
477 bool ConstOnRHS = I.getOperand(i_nocapture: 1) == LastVisited->first;
478 Value *V = ConstOnRHS ? I.getOperand(i_nocapture: 0) : I.getOperand(i_nocapture: 1);
479 Constant *Other = findConstantFor(V);
480
481 if (Other) {
482 if (ConstOnRHS)
483 std::swap(a&: Const, b&: Other);
484 return ConstantFoldCompareInstOperands(Predicate: I.getPredicate(), LHS: Const, RHS: Other, DL);
485 }
486
487 // If we haven't found Other to be a specific constant value, we may still be
488 // able to constant fold using information from the lattice value.
489 const ValueLatticeElement &ConstLV = ValueLatticeElement::get(C: Const);
490 const ValueLatticeElement &OtherLV = Solver.getLatticeValueFor(V);
491 auto &V1State = ConstOnRHS ? OtherLV : ConstLV;
492 auto &V2State = ConstOnRHS ? ConstLV : OtherLV;
493 return V1State.getCompare(Pred: I.getPredicate(), Ty: I.getType(), Other: V2State, DL);
494}
495
496Constant *InstCostVisitor::visitUnaryOperator(UnaryOperator &I) {
497 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
498
499 return ConstantFoldUnaryOpOperand(Opcode: I.getOpcode(), Op: LastVisited->second, DL);
500}
501
502Constant *InstCostVisitor::visitBinaryOperator(BinaryOperator &I) {
503 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
504
505 bool ConstOnRHS = I.getOperand(i_nocapture: 1) == LastVisited->first;
506 Value *V = ConstOnRHS ? I.getOperand(i_nocapture: 0) : I.getOperand(i_nocapture: 1);
507 Constant *Other = findConstantFor(V);
508 Value *OtherVal = Other ? Other : V;
509 Value *ConstVal = LastVisited->second;
510
511 if (ConstOnRHS)
512 std::swap(a&: ConstVal, b&: OtherVal);
513
514 return dyn_cast_or_null<Constant>(
515 Val: simplifyBinOp(Opcode: I.getOpcode(), LHS: ConstVal, RHS: OtherVal, Q: SimplifyQuery(DL)));
516}
517
518Constant *FunctionSpecializer::getPromotableAlloca(AllocaInst *Alloca,
519 CallInst *Call) {
520 Value *StoreValue = nullptr;
521 for (auto *User : Alloca->users()) {
522 // We can't use llvm::isAllocaPromotable() as that would fail because of
523 // the usage in the CallInst, which is what we check here.
524 if (User == Call)
525 continue;
526
527 if (auto *Store = dyn_cast<StoreInst>(Val: User)) {
528 // This is a duplicate store, bail out.
529 if (StoreValue || Store->isVolatile())
530 return nullptr;
531 StoreValue = Store->getValueOperand();
532 continue;
533 }
534 // Bail if there is any other unknown usage.
535 return nullptr;
536 }
537
538 if (!StoreValue)
539 return nullptr;
540
541 return getCandidateConstant(V: StoreValue);
542}
543
544// A constant stack value is an AllocaInst that has a single constant
545// value stored to it. Return this constant if such an alloca stack value
546// is a function argument and the value is an integer.
547Constant *FunctionSpecializer::getConstantStackValue(CallInst *Call,
548 Value *Val) {
549 if (!Val)
550 return nullptr;
551 Val = Val->stripPointerCasts();
552 auto *Alloca = dyn_cast<AllocaInst>(Val);
553 if (!Alloca)
554 return nullptr;
555 Constant *C = getPromotableAlloca(Alloca, Call);
556 if (!C || !C->getType()->isIntegerTy())
557 return nullptr;
558 return C;
559}
560
561// To support specializing recursive functions, it is important to propagate
562// constant arguments because after a first iteration of specialisation, a
563// reduced example may look like this:
564//
565// define internal void @RecursiveFn(i32* arg1) {
566// %temp = alloca i32, align 4
567// store i32 2 i32* %temp, align 4
568// call void @RecursiveFn.1(i32* nonnull %temp)
569// ret void
570// }
571//
572// Before a next iteration, we need to propagate the constant like so
573// which allows further specialization in next iterations.
574//
575// @funcspec.arg = internal constant i32 2
576//
577// define internal void @someFunc(i32* arg1) {
578// call void @otherFunc(i32* nonnull @funcspec.arg)
579// ret void
580// }
581//
582// See if there are any new constant values for the callers of \p F via
583// stack variables and promote them to global variables.
584void FunctionSpecializer::promoteConstantStackValues(Function *F) {
585 for (User *U : F->users()) {
586
587 auto *Call = dyn_cast<CallInst>(Val: U);
588 if (!Call)
589 continue;
590
591 if (!Solver.isBlockExecutable(BB: Call->getParent()))
592 continue;
593
594 for (const Use &U : Call->args()) {
595 unsigned Idx = Call->getArgOperandNo(U: &U);
596 Value *ArgOp = Call->getArgOperand(i: Idx);
597 Type *ArgOpType = ArgOp->getType();
598
599 if (!Call->onlyReadsMemory(OpNo: Idx) || !ArgOpType->isPointerTy())
600 continue;
601
602 auto *ConstVal = getConstantStackValue(Call, Val: ArgOp);
603 if (!ConstVal)
604 continue;
605
606 Value *GV = new GlobalVariable(M, ConstVal->getType(), true,
607 GlobalValue::InternalLinkage, ConstVal,
608 "specialized.arg." + Twine(++NGlobals));
609 Call->setArgOperand(i: Idx, v: GV);
610 }
611 }
612}
613
614// The SCCP solver inserts bitcasts for PredicateInfo. These interfere with the
615// promoteConstantStackValues() optimization.
616static void removeSSACopy(Function &F) {
617 for (BasicBlock &BB : F) {
618 for (Instruction &Inst : llvm::make_early_inc_range(Range&: BB)) {
619 auto *BC = dyn_cast<BitCastInst>(Val: &Inst);
620 if (!BC || BC->getType() != BC->getOperand(i_nocapture: 0)->getType())
621 continue;
622 Inst.replaceAllUsesWith(V: BC->getOperand(i_nocapture: 0));
623 Inst.eraseFromParent();
624 }
625 }
626}
627
628/// Remove any ssa_copy intrinsics that may have been introduced.
629void FunctionSpecializer::cleanUpSSA() {
630 for (Function *F : Specializations)
631 removeSSACopy(F&: *F);
632}
633
634template <> struct llvm::DenseMapInfo<SpecSig> {
635 static unsigned getHashValue(const SpecSig &S) {
636 return static_cast<unsigned>(hash_value(S));
637 }
638
639 static bool isEqual(const SpecSig &LHS, const SpecSig &RHS) {
640 return LHS == RHS;
641 }
642};
643
644FunctionSpecializer::~FunctionSpecializer() {
645 LLVM_DEBUG(
646 if (NumSpecsCreated > 0)
647 dbgs() << "FnSpecialization: Created " << NumSpecsCreated
648 << " specializations in module " << M.getName() << "\n");
649 // Eliminate dead code.
650 removeDeadFunctions();
651 cleanUpSSA();
652}
653
654/// Get the unsigned Value of given Cost object. Assumes the Cost is always
655/// non-negative, which is true for both TCK_CodeSize and TCK_Latency, and
656/// always Valid.
657static unsigned getCostValue(const Cost &C) {
658 int64_t Value = C.getValue();
659
660 assert(Value >= 0 && "CodeSize and Latency cannot be negative");
661 // It is safe to down cast since we know the arguments cannot be negative and
662 // Cost is of type int64_t.
663 return static_cast<unsigned>(Value);
664}
665
666/// Attempt to specialize functions in the module to enable constant
667/// propagation across function boundaries.
668///
669/// \returns true if at least one function is specialized.
670bool FunctionSpecializer::run() {
671 // Find possible specializations for each function.
672 SpecMap SM;
673 SmallVector<Spec, 32> AllSpecs;
674 unsigned NumCandidates = 0;
675 for (Function &F : M) {
676 if (!isCandidateFunction(F: &F))
677 continue;
678
679 auto [It, Inserted] = FunctionMetrics.try_emplace(Key: &F);
680 CodeMetrics &Metrics = It->second;
681 //Analyze the function.
682 if (Inserted) {
683 SmallPtrSet<const Value *, 32> EphValues;
684 CodeMetrics::collectEphemeralValues(L: &F, AC: &GetAC(F), EphValues);
685 for (BasicBlock &BB : F)
686 Metrics.analyzeBasicBlock(BB: &BB, TTI: GetTTI(F), EphValues);
687 }
688
689 // When specializing literal constants is enabled, always require functions
690 // to be larger than MinFunctionSize, to prevent excessive specialization.
691 const bool RequireMinSize =
692 !ForceSpecialization &&
693 (SpecializeLiteralConstant || !F.hasFnAttribute(Kind: Attribute::NoInline));
694
695 // If the code metrics reveal that we shouldn't duplicate the function,
696 // or if the code size implies that this function is easy to get inlined,
697 // then we shouldn't specialize it.
698 if (Metrics.notDuplicatable || !Metrics.NumInsts.isValid() ||
699 (RequireMinSize && Metrics.NumInsts < MinFunctionSize))
700 continue;
701
702 // When specialization on literal constants is disabled, only consider
703 // recursive functions when running multiple times to save wasted analysis,
704 // as we will not be able to specialize on any newly found literal constant
705 // return values.
706 if (!SpecializeLiteralConstant && !Inserted && !Metrics.isRecursive)
707 continue;
708
709 int64_t Sz = Metrics.NumInsts.getValue();
710 assert(Sz > 0 && "CodeSize should be positive");
711 // It is safe to down cast from int64_t, NumInsts is always positive.
712 unsigned FuncSize = static_cast<unsigned>(Sz);
713
714 LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for "
715 << F.getName() << " is " << FuncSize << "\n");
716
717 if (Inserted && Metrics.isRecursive)
718 promoteConstantStackValues(F: &F);
719
720 if (!findSpecializations(F: &F, FuncSize, AllSpecs, SM)) {
721 LLVM_DEBUG(
722 dbgs() << "FnSpecialization: No possible specializations found for "
723 << F.getName() << "\n");
724 continue;
725 }
726
727 ++NumCandidates;
728 }
729
730 if (!NumCandidates) {
731 LLVM_DEBUG(
732 dbgs()
733 << "FnSpecialization: No possible specializations found in module\n");
734 return false;
735 }
736
737 // Choose the most profitable specialisations, which fit in the module
738 // specialization budget, which is derived from maximum number of
739 // specializations per specialization candidate function.
740 auto CompareScore = [&AllSpecs](unsigned I, unsigned J) {
741 if (AllSpecs[I].Score != AllSpecs[J].Score)
742 return AllSpecs[I].Score > AllSpecs[J].Score;
743 return I > J;
744 };
745 const unsigned NSpecs =
746 std::min(a: NumCandidates * MaxClones, b: unsigned(AllSpecs.size()));
747 SmallVector<unsigned> BestSpecs(NSpecs + 1);
748 std::iota(first: BestSpecs.begin(), last: BestSpecs.begin() + NSpecs, value: 0);
749 if (AllSpecs.size() > NSpecs) {
750 LLVM_DEBUG(dbgs() << "FnSpecialization: Number of candidates exceed "
751 << "the maximum number of clones threshold.\n"
752 << "FnSpecialization: Specializing the "
753 << NSpecs
754 << " most profitable candidates.\n");
755 std::make_heap(first: BestSpecs.begin(), last: BestSpecs.begin() + NSpecs, comp: CompareScore);
756 for (unsigned I = NSpecs, N = AllSpecs.size(); I < N; ++I) {
757 BestSpecs[NSpecs] = I;
758 std::push_heap(first: BestSpecs.begin(), last: BestSpecs.end(), comp: CompareScore);
759 std::pop_heap(first: BestSpecs.begin(), last: BestSpecs.end(), comp: CompareScore);
760 }
761 }
762
763 LLVM_DEBUG(dbgs() << "FnSpecialization: List of specializations \n";
764 for (unsigned I = 0; I < NSpecs; ++I) {
765 const Spec &S = AllSpecs[BestSpecs[I]];
766 dbgs() << "FnSpecialization: Function " << S.F->getName()
767 << " , score " << S.Score << "\n";
768 for (const ArgInfo &Arg : S.Sig.Args)
769 dbgs() << "FnSpecialization: FormalArg = "
770 << Arg.Formal->getNameOrAsOperand()
771 << ", ActualArg = " << Arg.Actual->getNameOrAsOperand()
772 << "\n";
773 });
774
775 // Create the chosen specializations.
776 SmallPtrSet<Function *, 8> OriginalFuncs;
777 SmallVector<Function *> Clones;
778 for (unsigned I = 0; I < NSpecs; ++I) {
779 Spec &S = AllSpecs[BestSpecs[I]];
780
781 // Accumulate the codesize growth for the function, now we are creating the
782 // specialization.
783 FunctionGrowth[S.F] += S.CodeSize;
784
785 S.Clone = createSpecialization(F: S.F, S: S.Sig);
786
787 // Update the known call sites to call the clone.
788 for (CallBase *Call : S.CallSites) {
789 Function *Clone = S.Clone;
790 LLVM_DEBUG(dbgs() << "FnSpecialization: Redirecting " << *Call
791 << " to call " << Clone->getName() << "\n");
792 Call->setCalledFunction(S.Clone);
793 auto &BFI = GetBFI(*Call->getFunction());
794 std::optional<uint64_t> Count =
795 BFI.getBlockProfileCount(BB: Call->getParent());
796 if (Count && !ProfcheckDisableMetadataFixes) {
797 std::optional<uint64_t> MaybeCloneCount = Clone->getEntryCount();
798 if (MaybeCloneCount) {
799 uint64_t CallCount = *Count + *MaybeCloneCount;
800 Clone->setEntryCount(Count: CallCount);
801 if (std::optional<uint64_t> MaybeOriginalCount =
802 S.F->getEntryCount()) {
803 uint64_t OriginalCount = *MaybeOriginalCount;
804 if (OriginalCount >= *Count) {
805 S.F->setEntryCount(Count: OriginalCount - *Count);
806 } else {
807 // This should generally not happen as that would mean there are
808 // more computed calls to the function than what was recorded.
809 LLVM_DEBUG(S.F->setEntryCount(0));
810 }
811 }
812 }
813 }
814 }
815
816 Clones.push_back(Elt: S.Clone);
817 OriginalFuncs.insert(Ptr: S.F);
818 }
819
820 Solver.solveWhileResolvedUndefsIn(WorkList&: Clones);
821
822 // Update the rest of the call sites - these are the recursive calls, calls
823 // to discarded specialisations and calls that may match a specialisation
824 // after the solver runs.
825 for (Function *F : OriginalFuncs) {
826 auto [Begin, End] = SM[F];
827 updateCallSites(F, Begin: AllSpecs.begin() + Begin, End: AllSpecs.begin() + End);
828 }
829
830 for (Function *F : Clones) {
831 if (F->getReturnType()->isVoidTy())
832 continue;
833 if (F->getReturnType()->isStructTy()) {
834 auto *STy = cast<StructType>(Val: F->getReturnType());
835 if (!Solver.isStructLatticeConstant(F, STy))
836 continue;
837 } else {
838 auto It = Solver.getTrackedRetVals().find(Key: F);
839 assert(It != Solver.getTrackedRetVals().end() &&
840 "Return value ought to be tracked");
841 if (SCCPSolver::isOverdefined(LV: It->second))
842 continue;
843 }
844 for (User *U : F->users()) {
845 if (auto *CS = dyn_cast<CallBase>(Val: U)) {
846 //The user instruction does not call our function.
847 if (CS->getCalledFunction() != F)
848 continue;
849 Solver.resetLatticeValueFor(Call: CS);
850 }
851 }
852 }
853
854 // Rerun the solver to notify the users of the modified callsites.
855 Solver.solveWhileResolvedUndefs();
856
857 for (Function *F : OriginalFuncs)
858 if (FunctionMetrics[F].isRecursive)
859 promoteConstantStackValues(F);
860
861 return true;
862}
863
864void FunctionSpecializer::removeDeadFunctions() {
865 for (Function *F : DeadFunctions) {
866 LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "
867 << F->getName() << "\n");
868 if (FAM)
869 FAM->clear(IR&: *F, Name: F->getName());
870
871 // Remove all the callsites that were proven unreachable once, and replace
872 // them with poison.
873 for (User *U : make_early_inc_range(Range: F->users())) {
874 assert((isa<CallInst>(U) || isa<InvokeInst>(U)) &&
875 "User of dead function must be call or invoke");
876 Instruction *CS = cast<Instruction>(Val: U);
877 CS->replaceAllUsesWith(V: PoisonValue::get(T: CS->getType()));
878 CS->eraseFromParent();
879 }
880 F->eraseFromParent();
881 }
882 DeadFunctions.clear();
883}
884
885/// Clone the function \p F and remove the ssa_copy intrinsics added by
886/// the SCCPSolver in the cloned version.
887static Function *cloneCandidateFunction(Function *F, unsigned NSpecs) {
888 ValueToValueMapTy Mappings;
889 Function *Clone = CloneFunction(F, VMap&: Mappings);
890 Clone->setName(F->getName() + ".specialized." + Twine(NSpecs));
891 removeSSACopy(F&: *Clone);
892 return Clone;
893}
894
895bool FunctionSpecializer::findSpecializations(Function *F, unsigned FuncSize,
896 SmallVectorImpl<Spec> &AllSpecs,
897 SpecMap &SM) {
898 // A mapping from a specialisation signature to the index of the respective
899 // entry in the all specialisation array. Used to ensure uniqueness of
900 // specialisations.
901 DenseMap<SpecSig, unsigned> UniqueSpecs;
902
903 // Get a list of interesting arguments.
904 SmallVector<Argument *> Args;
905 for (Argument &Arg : F->args())
906 if (isArgumentInteresting(A: &Arg))
907 Args.push_back(Elt: &Arg);
908
909 if (Args.empty())
910 return false;
911
912 for (User *U : F->users()) {
913 if (!isa<CallInst>(Val: U) && !isa<InvokeInst>(Val: U))
914 continue;
915 auto &CS = *cast<CallBase>(Val: U);
916
917 // The user instruction does not call our function.
918 if (CS.getCalledFunction() != F)
919 continue;
920
921 // If the call site has attribute minsize set, that callsite won't be
922 // specialized.
923 if (CS.hasFnAttr(Kind: Attribute::MinSize))
924 continue;
925
926 // If the parent of the call site will never be executed, we don't need
927 // to worry about the passed value.
928 if (!Solver.isBlockExecutable(BB: CS.getParent()))
929 continue;
930
931 // Examine arguments and create a specialisation candidate from the
932 // constant operands of this call site.
933 SpecSig S;
934 for (Argument *A : Args) {
935 Constant *C = getCandidateConstant(V: CS.getArgOperand(i: A->getArgNo()));
936 if (!C)
937 continue;
938 LLVM_DEBUG(dbgs() << "FnSpecialization: Found interesting argument "
939 << A->getName() << " : " << C->getNameOrAsOperand()
940 << "\n");
941 S.Args.push_back(Elt: {A, C});
942 }
943
944 if (S.Args.empty())
945 continue;
946
947 // Check if we have encountered the same specialisation already.
948 if (auto It = UniqueSpecs.find(Val: S); It != UniqueSpecs.end()) {
949 // Existing specialisation. Add the call to the list to rewrite, unless
950 // it's a recursive call. A specialisation, generated because of a
951 // recursive call may end up as not the best specialisation for all
952 // the cloned instances of this call, which result from specialising
953 // functions. Hence we don't rewrite the call directly, but match it with
954 // the best specialisation once all specialisations are known.
955 if (CS.getFunction() == F)
956 continue;
957 const unsigned Index = It->second;
958 AllSpecs[Index].CallSites.push_back(Elt: &CS);
959 } else {
960 // Calculate the specialisation gain.
961 Cost CodeSize;
962 unsigned Score = 0;
963 InstCostVisitor Visitor = getInstCostVisitorFor(F);
964 for (ArgInfo &A : S.Args) {
965 CodeSize += Visitor.getCodeSizeSavingsForArg(A: A.Formal, C: A.Actual);
966 Score += getInliningBonus(A: A.Formal, C: A.Actual);
967 }
968 CodeSize += Visitor.getCodeSizeSavingsFromPendingPHIs();
969
970 unsigned CodeSizeSavings = getCostValue(C: CodeSize);
971 unsigned SpecSize = FuncSize - CodeSizeSavings;
972
973 auto IsProfitable = [&]() -> bool {
974 // No check required.
975 if (ForceSpecialization)
976 return true;
977
978 LLVM_DEBUG(
979 dbgs() << "FnSpecialization: Specialization bonus {Inlining = "
980 << Score << " (" << (Score * 100 / FuncSize) << "%)}\n");
981
982 // Minimum inlining bonus.
983 if (Score > MinInliningBonus * FuncSize / 100)
984 return true;
985
986 LLVM_DEBUG(
987 dbgs() << "FnSpecialization: Specialization bonus {CodeSize = "
988 << CodeSizeSavings << " ("
989 << (CodeSizeSavings * 100 / FuncSize) << "%)}\n");
990
991 // Minimum codesize savings.
992 if (CodeSizeSavings < MinCodeSizeSavings * FuncSize / 100)
993 return false;
994
995 // Lazily compute the Latency, to avoid unnecessarily computing BFI.
996 unsigned LatencySavings =
997 getCostValue(C: Visitor.getLatencySavingsForKnownConstants());
998
999 LLVM_DEBUG(
1000 dbgs() << "FnSpecialization: Specialization bonus {Latency = "
1001 << LatencySavings << " ("
1002 << (LatencySavings * 100 / FuncSize) << "%)}\n");
1003
1004 // Minimum latency savings.
1005 if (LatencySavings < MinLatencySavings * FuncSize / 100)
1006 return false;
1007 // Maximum codesize growth.
1008 if ((FunctionGrowth[F] + SpecSize) / FuncSize > MaxCodeSizeGrowth)
1009 return false;
1010
1011 Score += std::max(a: CodeSizeSavings, b: LatencySavings);
1012 return true;
1013 };
1014
1015 // Discard unprofitable specialisations.
1016 if (!IsProfitable())
1017 continue;
1018
1019 // Create a new specialisation entry.
1020 auto &Spec = AllSpecs.emplace_back(Args&: F, Args&: S, Args&: Score, Args&: SpecSize);
1021 if (CS.getFunction() != F)
1022 Spec.CallSites.push_back(Elt: &CS);
1023 const unsigned Index = AllSpecs.size() - 1;
1024 UniqueSpecs[S] = Index;
1025 if (auto [It, Inserted] = SM.try_emplace(Key: F, Args: Index, Args: Index + 1); !Inserted)
1026 It->second.second = Index + 1;
1027 }
1028 }
1029
1030 return !UniqueSpecs.empty();
1031}
1032
1033bool FunctionSpecializer::isCandidateFunction(Function *F) {
1034 if (F->isDeclaration() || F->arg_empty())
1035 return false;
1036
1037 if (F->isInterposable())
1038 return false;
1039
1040 if (F->hasFnAttribute(Kind: Attribute::NoDuplicate))
1041 return false;
1042
1043 if (F->hasOptSize())
1044 return false;
1045
1046 // Do not specialize the cloned function again.
1047 if (Specializations.contains(Ptr: F))
1048 return false;
1049
1050 // If we're optimizing the function for size, we shouldn't specialize it.
1051 if (shouldOptimizeForSize(F, PSI: nullptr, BFI: nullptr, QueryType: PGSOQueryType::IRPass))
1052 return false;
1053
1054 // Exit if the function is not executable. There's no point in specializing
1055 // a dead function.
1056 if (!Solver.isBlockExecutable(BB: &F->getEntryBlock()))
1057 return false;
1058
1059 // It wastes time to specialize a function which would get inlined finally.
1060 if (F->hasFnAttribute(Kind: Attribute::AlwaysInline))
1061 return false;
1062
1063 LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()
1064 << "\n");
1065 return true;
1066}
1067
1068Function *FunctionSpecializer::createSpecialization(Function *F,
1069 const SpecSig &S) {
1070 Function *Clone = cloneCandidateFunction(F, NSpecs: Specializations.size() + 1);
1071
1072 // The original function does not neccessarily have internal linkage, but the
1073 // clone must.
1074 Clone->setLinkage(GlobalValue::InternalLinkage);
1075
1076 if (F->getEntryCount() && !ProfcheckDisableMetadataFixes)
1077 Clone->setEntryCount(Count: 0);
1078
1079 // Initialize the lattice state of the arguments of the function clone,
1080 // marking the argument on which we specialized the function constant
1081 // with the given value.
1082 Solver.setLatticeValueForSpecializationArguments(F: Clone, Args: S.Args);
1083 Solver.markBlockExecutable(BB: &Clone->front());
1084 Solver.addArgumentTrackedFunction(F: Clone);
1085 Solver.addTrackedFunction(F: Clone);
1086
1087 // Mark all the specialized functions
1088 Specializations.insert(Ptr: Clone);
1089 ++NumSpecsCreated;
1090
1091 return Clone;
1092}
1093
1094/// Compute the inlining bonus for replacing argument \p A with constant \p C.
1095/// The below heuristic is only concerned with exposing inlining
1096/// opportunities via indirect call promotion. If the argument is not a
1097/// (potentially casted) function pointer, give up.
1098unsigned FunctionSpecializer::getInliningBonus(Argument *A, Constant *C) {
1099 Function *CalledFunction = dyn_cast<Function>(Val: C->stripPointerCasts());
1100 if (!CalledFunction)
1101 return 0;
1102
1103 // Get TTI for the called function (used for the inline cost).
1104 auto &CalleeTTI = (GetTTI)(*CalledFunction);
1105
1106 // Look at all the call sites whose called value is the argument.
1107 // Specializing the function on the argument would allow these indirect
1108 // calls to be promoted to direct calls. If the indirect call promotion
1109 // would likely enable the called function to be inlined, specializing is a
1110 // good idea.
1111 int InliningBonus = 0;
1112 for (User *U : A->users()) {
1113 if (!isa<CallInst>(Val: U) && !isa<InvokeInst>(Val: U))
1114 continue;
1115 auto *CS = cast<CallBase>(Val: U);
1116 if (CS->getCalledOperand() != A)
1117 continue;
1118 if (CS->getFunctionType() != CalledFunction->getFunctionType())
1119 continue;
1120
1121 // Get the cost of inlining the called function at this call site. Note
1122 // that this is only an estimate. The called function may eventually
1123 // change in a way that leads to it not being inlined here, even though
1124 // inlining looks profitable now. For example, one of its called
1125 // functions may be inlined into it, making the called function too large
1126 // to be inlined into this call site.
1127 //
1128 // We apply a boost for performing indirect call promotion by increasing
1129 // the default threshold by the threshold for indirect calls.
1130 auto Params = getInlineParams();
1131 Params.DefaultThreshold += InlineConstants::IndirectCallThreshold;
1132 InlineCost IC =
1133 getInlineCost(Call&: *CS, Callee: CalledFunction, Params, CalleeTTI, GetAssumptionCache: GetAC, GetTLI);
1134
1135 // We clamp the bonus for this call to be between zero and the default
1136 // threshold.
1137 if (IC.isAlways())
1138 InliningBonus += Params.DefaultThreshold;
1139 else if (IC.isVariable() && IC.getCostDelta() > 0)
1140 InliningBonus += IC.getCostDelta();
1141
1142 LLVM_DEBUG(dbgs() << "FnSpecialization: Inlining bonus " << InliningBonus
1143 << " for user " << *U << "\n");
1144 }
1145
1146 return InliningBonus > 0 ? static_cast<unsigned>(InliningBonus) : 0;
1147}
1148
1149/// Determine if it is possible to specialise the function for constant values
1150/// of the formal parameter \p A.
1151bool FunctionSpecializer::isArgumentInteresting(Argument *A) {
1152 // No point in specialization if the argument is unused.
1153 if (A->user_empty())
1154 return false;
1155
1156 Type *Ty = A->getType();
1157 if (!Ty->isPointerTy() && (!SpecializeLiteralConstant ||
1158 (!Ty->isIntegerTy() && !Ty->isFloatingPointTy() && !Ty->isStructTy())))
1159 return false;
1160
1161 // SCCP solver does not record an argument that will be constructed on
1162 // stack.
1163 if (A->hasByValAttr() && !A->getParent()->onlyReadsMemory())
1164 return false;
1165
1166 // For non-argument-tracked functions every argument is overdefined.
1167 if (!Solver.isArgumentTrackedFunction(F: A->getParent()))
1168 return true;
1169
1170 // Check the lattice value and decide if we should attemt to specialize,
1171 // based on this argument. No point in specialization, if the lattice value
1172 // is already a constant.
1173 bool IsOverdefined = Ty->isStructTy()
1174 ? any_of(Range: Solver.getStructLatticeValueFor(V: A), P: SCCPSolver::isOverdefined)
1175 : SCCPSolver::isOverdefined(LV: Solver.getLatticeValueFor(V: A));
1176
1177 LLVM_DEBUG(
1178 if (IsOverdefined)
1179 dbgs() << "FnSpecialization: Found interesting parameter "
1180 << A->getNameOrAsOperand() << "\n";
1181 else
1182 dbgs() << "FnSpecialization: Nothing to do, parameter "
1183 << A->getNameOrAsOperand() << " is already constant\n";
1184 );
1185 return IsOverdefined;
1186}
1187
1188/// Check if the value \p V (an actual argument) is a constant or can only
1189/// have a constant value. Return that constant.
1190Constant *FunctionSpecializer::getCandidateConstant(Value *V) {
1191 if (isa<PoisonValue>(Val: V))
1192 return nullptr;
1193
1194 // Select for possible specialisation values that are constants or
1195 // are deduced to be constants or constant ranges with a single element.
1196 Constant *C = dyn_cast<Constant>(Val: V);
1197 if (!C)
1198 C = Solver.getConstantOrNull(V);
1199
1200 // Don't specialize on (anything derived from) the address of a non-constant
1201 // global variable, unless explicitly enabled.
1202 if (C && C->getType()->isPointerTy() && !C->isNullValue())
1203 if (auto *GV = dyn_cast<GlobalVariable>(Val: getUnderlyingObject(V: C));
1204 GV && !(GV->isConstant() || SpecializeOnAddress))
1205 return nullptr;
1206
1207 return C;
1208}
1209
1210void FunctionSpecializer::updateCallSites(Function *F, const Spec *Begin,
1211 const Spec *End) {
1212 // Collect the call sites that need updating.
1213 SmallVector<CallBase *> ToUpdate;
1214 for (User *U : F->users())
1215 if (auto *CS = dyn_cast<CallBase>(Val: U);
1216 CS && CS->getCalledFunction() == F &&
1217 Solver.isBlockExecutable(BB: CS->getParent()))
1218 ToUpdate.push_back(Elt: CS);
1219
1220 unsigned NCallsLeft = ToUpdate.size();
1221 for (CallBase *CS : ToUpdate) {
1222 bool ShouldDecrementCount = CS->getFunction() == F;
1223
1224 // Find the best matching specialisation.
1225 const Spec *BestSpec = nullptr;
1226 for (const Spec &S : make_range(x: Begin, y: End)) {
1227 if (!S.Clone || (BestSpec && S.Score <= BestSpec->Score))
1228 continue;
1229
1230 if (any_of(Range: S.Sig.Args, P: [CS, this](const ArgInfo &Arg) {
1231 unsigned ArgNo = Arg.Formal->getArgNo();
1232 return getCandidateConstant(V: CS->getArgOperand(i: ArgNo)) != Arg.Actual;
1233 }))
1234 continue;
1235
1236 BestSpec = &S;
1237 }
1238
1239 if (BestSpec) {
1240 LLVM_DEBUG(dbgs() << "FnSpecialization: Redirecting " << *CS
1241 << " to call " << BestSpec->Clone->getName() << "\n");
1242 CS->setCalledFunction(BestSpec->Clone);
1243 ShouldDecrementCount = true;
1244 }
1245
1246 if (ShouldDecrementCount)
1247 --NCallsLeft;
1248 }
1249
1250 // If the function has been completely specialized, the original function
1251 // is no longer needed. Mark it unreachable.
1252 // NOTE: If the address of a function is taken, we cannot treat it as dead
1253 // function.
1254 if (NCallsLeft == 0 && Solver.isArgumentTrackedFunction(F) &&
1255 !F->hasAddressTaken()) {
1256 Solver.markFunctionUnreachable(F);
1257 DeadFunctions.insert(Ptr: F);
1258 }
1259}
1260