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