LLVM: lib/Transforms/IPO/FunctionSpecialization.cpp Source File

LLVM 22.0.0git
FunctionSpecialization.cpp
Go to the documentation of this file.
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#include <cmath>
24
25using namespace llvm;
26
27 #define DEBUG_TYPE "function-specialization"
28
29 STATISTIC(NumSpecsCreated, "Number of specializations created");
30
31namespace llvm {
32
33 static cl::opt<bool> ForceSpecialization(
34 "force-specialization", cl::init(false), cl::Hidden,
35 cl::desc(
36 "Force function specialization for every call site with a constant "
37 "argument"));
38
39 static cl::opt<unsigned> MaxClones(
40 "funcspec-max-clones", cl::init(3), cl::Hidden, cl::desc(
41 "The maximum number of clones allowed for a single function "
42 "specialization"));
43
44static cl::opt<unsigned>
45 MaxDiscoveryIterations("funcspec-max-discovery-iterations", cl::init(100),
46 cl::Hidden,
47 cl::desc("The maximum number of iterations allowed "
48 "when searching for transitive "
49 "phis"));
50
51 static cl::opt<unsigned> MaxIncomingPhiValues(
52 "funcspec-max-incoming-phi-values", cl::init(8), cl::Hidden,
53 cl::desc("The maximum number of incoming values a PHI node can have to be "
54 "considered during the specialization bonus estimation"));
55
56 static cl::opt<unsigned> MaxBlockPredecessors(
57 "funcspec-max-block-predecessors", cl::init(2), cl::Hidden, cl::desc(
58 "The maximum number of predecessors a basic block can have to be "
59 "considered during the estimation of dead code"));
60
61 static cl::opt<unsigned> MinFunctionSize(
62 "funcspec-min-function-size", cl::init(500), cl::Hidden,
63 cl::desc("Don't specialize functions that have less than this number of "
64 "instructions"));
65
66 static cl::opt<unsigned> MaxCodeSizeGrowth(
67 "funcspec-max-codesize-growth", cl::init(3), cl::Hidden, cl::desc(
68 "Maximum codesize growth allowed per function"));
69
70 static cl::opt<unsigned> MinCodeSizeSavings(
71 "funcspec-min-codesize-savings", cl::init(20), cl::Hidden,
72 cl::desc("Reject specializations whose codesize savings are less than this "
73 "much percent of the original function size"));
74
75 static cl::opt<unsigned> MinLatencySavings(
76 "funcspec-min-latency-savings", cl::init(20), cl::Hidden,
77 cl::desc("Reject specializations whose latency savings are less than this "
78 "much percent of the original function size"));
79
80 static cl::opt<unsigned> MinInliningBonus(
81 "funcspec-min-inlining-bonus", cl::init(300), cl::Hidden,
82 cl::desc("Reject specializations whose inlining bonus is less than this "
83 "much percent of the original function size"));
84
85 static cl::opt<bool> SpecializeOnAddress(
86 "funcspec-on-address", cl::init(false), cl::Hidden, cl::desc(
87 "Enable function specialization on the address of global values"));
88
89 static cl::opt<bool> SpecializeLiteralConstant(
90 "funcspec-for-literal-constant", cl::init(true), cl::Hidden,
91 cl::desc(
92 "Enable specialization of functions that take a literal constant as an "
93 "argument"));
94
95extern cl::opt<bool> ProfcheckDisableMetadataFixes;
96
97} // end namespace llvm
98
99bool InstCostVisitor::canEliminateSuccessor(BasicBlock *BB,
100 BasicBlock *Succ) const {
101 unsigned I = 0;
102 return all_of(predecessors(Succ), [&I, BB, Succ, this](BasicBlock *Pred) {
103 return I++ < MaxBlockPredecessors &&
104 (Pred == BB || Pred == Succ || !isBlockExecutable(Pred));
105 });
106}
107
108// Estimates the codesize savings due to dead code after constant propagation.
109// \p WorkList represents the basic blocks of a specialization which will
110// eventually become dead once we replace instructions that are known to be
111// constants. The successors of such blocks are added to the list as long as
112// the \p Solver found they were executable prior to specialization, and only
113// if all their predecessors are dead.
114Cost InstCostVisitor::estimateBasicBlocks(
115 SmallVectorImpl<BasicBlock *> &WorkList) {
116 Cost CodeSize = 0;
117 // Accumulate the codesize savings of each basic block.
118 while (!WorkList.empty()) {
119 BasicBlock *BB = WorkList.pop_back_val();
120
121 // These blocks are considered dead as far as the InstCostVisitor
122 // is concerned. They haven't been proven dead yet by the Solver,
123 // but may become if we propagate the specialization arguments.
124 assert(Solver.isBlockExecutable(BB) && "BB already found dead by IPSCCP!");
125 if (!DeadBlocks.insert(BB).second)
126 continue;
127
128 for (Instruction &I : *BB) {
129 // If it's a known constant we have already accounted for it.
130 if (KnownConstants.contains(&I))
131 continue;
132
133 Cost C = TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
134
135 LLVM_DEBUG(dbgs() << "FnSpecialization: CodeSize " << C
136 << " for user " << I << "\n");
137 CodeSize += C;
138 }
139
140 // Keep adding dead successors to the list as long as they are
141 // executable and only reachable from dead blocks.
142 for (BasicBlock *SuccBB : successors(BB))
143 if (isBlockExecutable(SuccBB) && canEliminateSuccessor(BB, SuccBB))
144 WorkList.push_back(SuccBB);
145 }
146 return CodeSize;
147}
148
149Constant *InstCostVisitor::findConstantFor(Value *V) const {
150 if (auto *C = dyn_cast<Constant>(V))
151 return C;
152 if (auto *C = Solver.getConstantOrNull(V))
153 return C;
154 return KnownConstants.lookup(V);
155}
156
159 while (!PendingPHIs.empty()) {
160 Instruction *Phi = PendingPHIs.pop_back_val();
161 // The pending PHIs could have been proven dead by now.
162 if (isBlockExecutable(Phi->getParent()))
163 CodeSize += getCodeSizeSavingsForUser(Phi);
164 }
165 return CodeSize;
166}
167
168/// Compute the codesize savings for replacing argument \p A with constant \p C.
170 LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "
171 << C->getNameOrAsOperand() << "\n");
173 for (auto *U : A->users())
174 if (auto *UI = dyn_cast<Instruction>(U))
175 if (isBlockExecutable(UI->getParent()))
176 CodeSize += getCodeSizeSavingsForUser(UI, A, C);
177
178 LLVM_DEBUG(dbgs() << "FnSpecialization: Accumulated bonus {CodeSize = "
179 << CodeSize << "} for argument " << *A << "\n");
180 return CodeSize;
181}
182
183/// Compute the latency savings from replacing all arguments with constants for
184/// a specialization candidate. As this function computes the latency savings
185/// for all Instructions in KnownConstants at once, it should be called only
186/// after every instruction has been visited, i.e. after:
187///
188/// * getCodeSizeSavingsForArg has been run for every constant argument of a
189/// specialization candidate
190///
191/// * getCodeSizeSavingsFromPendingPHIs has been run
192///
193/// to ensure that the latency savings are calculated for all Instructions we
194/// have visited and found to be constant.
196 auto &BFI = GetBFI(*F);
197 Cost TotalLatency = 0;
198
199 for (auto Pair : KnownConstants) {
200 Instruction *I = dyn_cast<Instruction>(Pair.first);
201 if (!I)
202 continue;
203
204 uint64_t Weight = BFI.getBlockFreq(I->getParent()).getFrequency() /
205 BFI.getEntryFreq().getFrequency();
206
207 Cost Latency =
208 Weight * TTI.getInstructionCost(I, TargetTransformInfo::TCK_Latency);
209
210 LLVM_DEBUG(dbgs() << "FnSpecialization: {Latency = " << Latency
211 << "} for instruction " << *I << "\n");
212
213 TotalLatency += Latency;
214 }
215
216 return TotalLatency;
217}
218
219Cost InstCostVisitor::getCodeSizeSavingsForUser(Instruction *User, Value *Use,
220 Constant *C) {
221 // We have already propagated a constant for this user.
222 if (KnownConstants.contains(User))
223 return 0;
224
225 // Cache the iterator before visiting.
226 LastVisited = Use ? KnownConstants.insert({Use, C}).first
227 : KnownConstants.end();
228
229 Cost CodeSize = 0;
230 if (auto *I = dyn_cast<SwitchInst>(User)) {
231 CodeSize = estimateSwitchInst(*I);
232 } else if (auto *I = dyn_cast<BranchInst>(User)) {
233 CodeSize = estimateBranchInst(*I);
234 } else {
235 C = visit(*User);
236 if (!C)
237 return 0;
238 }
239
240 // Even though it doesn't make sense to bind switch and branch instructions
241 // with a constant, unlike any other instruction type, it prevents estimating
242 // their bonus multiple times.
243 KnownConstants.insert({User, C});
244
245 CodeSize += TTI.getInstructionCost(User, TargetTransformInfo::TCK_CodeSize);
246
247 LLVM_DEBUG(dbgs() << "FnSpecialization: {CodeSize = " << CodeSize
248 << "} for user " << *User << "\n");
249
250 for (auto *U : User->users())
251 if (auto *UI = dyn_cast<Instruction>(U))
252 if (UI != User && isBlockExecutable(UI->getParent()))
253 CodeSize += getCodeSizeSavingsForUser(UI, User, C);
254
255 return CodeSize;
256}
257
258Cost InstCostVisitor::estimateSwitchInst(SwitchInst &I) {
259 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
260
261 if (I.getCondition() != LastVisited->first)
262 return 0;
263
264 auto *C = dyn_cast<ConstantInt>(LastVisited->second);
265 if (!C)
266 return 0;
267
268 BasicBlock *Succ = I.findCaseValue(C)->getCaseSuccessor();
269 // Initialize the worklist with the dead basic blocks. These are the
270 // destination labels which are different from the one corresponding
271 // to \p C. They should be executable and have a unique predecessor.
272 SmallVector<BasicBlock *> WorkList;
273 for (const auto &Case : I.cases()) {
274 BasicBlock *BB = Case.getCaseSuccessor();
275 if (BB != Succ && isBlockExecutable(BB) &&
276 canEliminateSuccessor(I.getParent(), BB))
277 WorkList.push_back(BB);
278 }
279
280 return estimateBasicBlocks(WorkList);
281}
282
283Cost InstCostVisitor::estimateBranchInst(BranchInst &I) {
284 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
285
286 if (I.getCondition() != LastVisited->first)
287 return 0;
288
289 BasicBlock *Succ = I.getSuccessor(LastVisited->second->isOneValue());
290 // Initialize the worklist with the dead successor as long as
291 // it is executable and has a unique predecessor.
292 SmallVector<BasicBlock *> WorkList;
293 if (isBlockExecutable(Succ) && canEliminateSuccessor(I.getParent(), Succ))
294 WorkList.push_back(Succ);
295
296 return estimateBasicBlocks(WorkList);
297}
298
299bool InstCostVisitor::discoverTransitivelyIncomingValues(
300 Constant *Const, PHINode *Root, DenseSet<PHINode *> &TransitivePHIs) {
301
302 SmallVector<PHINode *, 64> WorkList;
303 WorkList.push_back(Root);
304 unsigned Iter = 0;
305
306 while (!WorkList.empty()) {
307 PHINode *PN = WorkList.pop_back_val();
308
309 if (++Iter > MaxDiscoveryIterations ||
310 PN->getNumIncomingValues() > MaxIncomingPhiValues)
311 return false;
312
313 if (!TransitivePHIs.insert(PN).second)
314 continue;
315
316 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
317 Value *V = PN->getIncomingValue(I);
318
319 // Disregard self-references and dead incoming values.
320 if (auto *Inst = dyn_cast<Instruction>(V))
321 if (Inst == PN || !isBlockExecutable(PN->getIncomingBlock(I)))
322 continue;
323
324 if (Constant *C = findConstantFor(V)) {
325 // Not all incoming values are the same constant. Bail immediately.
326 if (C != Const)
327 return false;
328 continue;
329 }
330
331 if (auto *Phi = dyn_cast<PHINode>(V)) {
332 WorkList.push_back(Phi);
333 continue;
334 }
335
336 // We can't reason about anything else.
337 return false;
338 }
339 }
340 return true;
341}
342
343Constant *InstCostVisitor::visitPHINode(PHINode &I) {
344 if (I.getNumIncomingValues() > MaxIncomingPhiValues)
345 return nullptr;
346
347 bool Inserted = VisitedPHIs.insert(&I).second;
348 Constant *Const = nullptr;
349 bool HaveSeenIncomingPHI = false;
350
351 for (unsigned Idx = 0, E = I.getNumIncomingValues(); Idx != E; ++Idx) {
352 Value *V = I.getIncomingValue(Idx);
353
354 // Disregard self-references and dead incoming values.
355 if (auto *Inst = dyn_cast<Instruction>(V))
356 if (Inst == &I || !isBlockExecutable(I.getIncomingBlock(Idx)))
357 continue;
358
359 if (Constant *C = findConstantFor(V)) {
360 if (!Const)
361 Const = C;
362 // Not all incoming values are the same constant. Bail immediately.
363 if (C != Const)
364 return nullptr;
365 continue;
366 }
367
368 if (Inserted) {
369 // First time we are seeing this phi. We will retry later, after
370 // all the constant arguments have been propagated. Bail for now.
371 PendingPHIs.push_back(&I);
372 return nullptr;
373 }
374
375 if (isa<PHINode>(V)) {
376 // Perhaps it is a Transitive Phi. We will confirm later.
377 HaveSeenIncomingPHI = true;
378 continue;
379 }
380
381 // We can't reason about anything else.
382 return nullptr;
383 }
384
385 if (!Const)
386 return nullptr;
387
388 if (!HaveSeenIncomingPHI)
389 return Const;
390
391 DenseSet<PHINode *> TransitivePHIs;
392 if (!discoverTransitivelyIncomingValues(Const, &I, TransitivePHIs))
393 return nullptr;
394
395 return Const;
396}
397
398Constant *InstCostVisitor::visitFreezeInst(FreezeInst &I) {
399 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
400
401 if (isGuaranteedNotToBeUndefOrPoison(LastVisited->second))
402 return LastVisited->second;
403 return nullptr;
404}
405
406Constant *InstCostVisitor::visitCallBase(CallBase &I) {
407 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
408
409 Function *F = I.getCalledFunction();
410 if (!F || !canConstantFoldCallTo(&I, F))
411 return nullptr;
412
413 SmallVector<Constant *, 8> Operands;
414 Operands.reserve(I.getNumOperands());
415
416 for (unsigned Idx = 0, E = I.getNumOperands() - 1; Idx != E; ++Idx) {
417 Value *V = I.getOperand(Idx);
418 if (isa<MetadataAsValue>(V))
419 return nullptr;
420 Constant *C = findConstantFor(V);
421 if (!C)
422 return nullptr;
423 Operands.push_back(C);
424 }
425
426 auto Ops = ArrayRef(Operands.begin(), Operands.end());
427 return ConstantFoldCall(&I, F, Ops);
428}
429
430Constant *InstCostVisitor::visitLoadInst(LoadInst &I) {
431 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
432
433 if (isa<ConstantPointerNull>(LastVisited->second))
434 return nullptr;
435 return ConstantFoldLoadFromConstPtr(LastVisited->second, I.getType(), DL);
436}
437
438Constant *InstCostVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
439 SmallVector<Constant *, 8> Operands;
440 Operands.reserve(I.getNumOperands());
441
442 for (unsigned Idx = 0, E = I.getNumOperands(); Idx != E; ++Idx) {
443 Value *V = I.getOperand(Idx);
444 Constant *C = findConstantFor(V);
445 if (!C)
446 return nullptr;
447 Operands.push_back(C);
448 }
449
450 auto Ops = ArrayRef(Operands.begin(), Operands.end());
451 return ConstantFoldInstOperands(&I, Ops, DL);
452}
453
454Constant *InstCostVisitor::visitSelectInst(SelectInst &I) {
455 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
456
457 if (I.getCondition() == LastVisited->first) {
458 Value *V = LastVisited->second->isZeroValue() ? I.getFalseValue()
459 : I.getTrueValue();
460 return findConstantFor(V);
461 }
462 if (Constant *Condition = findConstantFor(I.getCondition()))
463 if ((I.getTrueValue() == LastVisited->first && Condition->isOneValue()) ||
464 (I.getFalseValue() == LastVisited->first && Condition->isZeroValue()))
465 return LastVisited->second;
466 return nullptr;
467}
468
469Constant *InstCostVisitor::visitCastInst(CastInst &I) {
470 return ConstantFoldCastOperand(I.getOpcode(), LastVisited->second,
471 I.getType(), DL);
472}
473
474Constant *InstCostVisitor::visitCmpInst(CmpInst &I) {
475 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
476
477 Constant *Const = LastVisited->second;
478 bool ConstOnRHS = I.getOperand(1) == LastVisited->first;
479 Value *V = ConstOnRHS ? I.getOperand(0) : I.getOperand(1);
480 Constant *Other = findConstantFor(V);
481
482 if (Other) {
483 if (ConstOnRHS)
484 std::swap(Const, Other);
485 return ConstantFoldCompareInstOperands(I.getPredicate(), Const, Other, DL);
486 }
487
488 // If we haven't found Other to be a specific constant value, we may still be
489 // able to constant fold using information from the lattice value.
490 const ValueLatticeElement &ConstLV = ValueLatticeElement::get(Const);
491 const ValueLatticeElement &OtherLV = Solver.getLatticeValueFor(V);
492 auto &V1State = ConstOnRHS ? OtherLV : ConstLV;
493 auto &V2State = ConstOnRHS ? ConstLV : OtherLV;
494 return V1State.getCompare(I.getPredicate(), I.getType(), V2State, DL);
495}
496
497Constant *InstCostVisitor::visitUnaryOperator(UnaryOperator &I) {
498 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
499
500 return ConstantFoldUnaryOpOperand(I.getOpcode(), LastVisited->second, DL);
501}
502
503Constant *InstCostVisitor::visitBinaryOperator(BinaryOperator &I) {
504 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
505
506 bool ConstOnRHS = I.getOperand(1) == LastVisited->first;
507 Value *V = ConstOnRHS ? I.getOperand(0) : I.getOperand(1);
508 Constant *Other = findConstantFor(V);
509 Value *OtherVal = Other ? Other : V;
510 Value *ConstVal = LastVisited->second;
511
512 if (ConstOnRHS)
513 std::swap(ConstVal, OtherVal);
514
515 return dyn_cast_or_null<Constant>(
516 simplifyBinOp(I.getOpcode(), ConstVal, OtherVal, SimplifyQuery(DL)));
517}
518
519Constant *FunctionSpecializer::getPromotableAlloca(AllocaInst *Alloca,
520 CallInst *Call) {
521 Value *StoreValue = nullptr;
522 for (auto *User : Alloca->users()) {
523 // We can't use llvm::isAllocaPromotable() as that would fail because of
524 // the usage in the CallInst, which is what we check here.
525 if (User == Call)
526 continue;
527
528 if (auto *Store = dyn_cast<StoreInst>(User)) {
529 // This is a duplicate store, bail out.
530 if (StoreValue || Store->isVolatile())
531 return nullptr;
532 StoreValue = Store->getValueOperand();
533 continue;
534 }
535 // Bail if there is any other unknown usage.
536 return nullptr;
537 }
538
539 if (!StoreValue)
540 return nullptr;
541
542 return getCandidateConstant(StoreValue);
543}
544
545// A constant stack value is an AllocaInst that has a single constant
546// value stored to it. Return this constant if such an alloca stack value
547// is a function argument.
548Constant *FunctionSpecializer::getConstantStackValue(CallInst *Call,
549 Value *Val) {
550 if (!Val)
551 return nullptr;
552 Val = Val->stripPointerCasts();
553 if (auto *ConstVal = dyn_cast<ConstantInt>(Val))
554 return ConstVal;
555 auto *Alloca = dyn_cast<AllocaInst>(Val);
556 if (!Alloca || !Alloca->getAllocatedType()->isIntegerTy())
557 return nullptr;
558 return getPromotableAlloca(Alloca, Call);
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>(U);
588 if (!Call)
589 continue;
590
591 if (!Solver.isBlockExecutable(Call->getParent()))
592 continue;
593
594 for (const Use &U : Call->args()) {
595 unsigned Idx = Call->getArgOperandNo(&U);
596 Value *ArgOp = Call->getArgOperand(Idx);
597 Type *ArgOpType = ArgOp->getType();
598
599 if (!Call->onlyReadsMemory(Idx) || !ArgOpType->isPointerTy())
600 continue;
601
602 auto *ConstVal = getConstantStackValue(Call, 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(Idx, GV);
610 }
611 }
612}
613
614// The SCCP solver inserts bitcasts for PredicateInfo. These interfere with the
615// promoteConstantStackValues() optimization.
616 static void removeSSACopy(Function &F) {
617 for (BasicBlock &BB : F) {
618 for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
619 auto *BC = dyn_cast<BitCastInst>(&Inst);
620 if (!BC || BC->getType() != BC->getOperand(0)->getType())
621 continue;
622 Inst.replaceAllUsesWith(BC->getOperand(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);
632}
633
634
635 template <> struct llvm::DenseMapInfo<SpecSig> {
636 static inline SpecSig getEmptyKey() { return {~0U, {}}; }
637
638 static inline SpecSig getTombstoneKey() { return {~1U, {}}; }
639
640 static unsigned getHashValue(const SpecSig &S) {
641 return static_cast<unsigned>(hash_value(S));
642 }
643
644 static bool isEqual(const SpecSig &LHS, const SpecSig &RHS) {
645 return LHS == RHS;
646 }
647};
648
651 if (NumSpecsCreated > 0)
652 dbgs() << "FnSpecialization: Created " << NumSpecsCreated
653 << " specializations in module " << M.getName() << "\n");
654 // Eliminate dead code.
655 removeDeadFunctions();
656 cleanUpSSA();
657}
658
659/// Get the unsigned Value of given Cost object. Assumes the Cost is always
660/// non-negative, which is true for both TCK_CodeSize and TCK_Latency, and
661/// always Valid.
662 static unsigned getCostValue(const Cost &C) {
663 int64_t Value = C.getValue();
664
665 assert(Value >= 0 && "CodeSize and Latency cannot be negative");
666 // It is safe to down cast since we know the arguments cannot be negative and
667 // Cost is of type int64_t.
668 return static_cast<unsigned>(Value);
669}
670
671/// Attempt to specialize functions in the module to enable constant
672/// propagation across function boundaries.
673///
674/// \returns true if at least one function is specialized.
676 // Find possible specializations for each function.
677 SpecMap SM;
678 SmallVector<Spec, 32> AllSpecs;
679 unsigned NumCandidates = 0;
680 for (Function &F : M) {
681 if (!isCandidateFunction(&F))
682 continue;
683
684 auto [It, Inserted] = FunctionMetrics.try_emplace(&F);
685 CodeMetrics &Metrics = It->second;
686 //Analyze the function.
687 if (Inserted) {
689 CodeMetrics::collectEphemeralValues(&F, &GetAC(F), EphValues);
690 for (BasicBlock &BB : F)
691 Metrics.analyzeBasicBlock(&BB, GetTTI(F), EphValues);
692 }
693
694 // When specializing literal constants is enabled, always require functions
695 // to be larger than MinFunctionSize, to prevent excessive specialization.
696 const bool RequireMinSize =
698 (SpecializeLiteralConstant || !F.hasFnAttribute(Attribute::NoInline));
699
700 // If the code metrics reveal that we shouldn't duplicate the function,
701 // or if the code size implies that this function is easy to get inlined,
702 // then we shouldn't specialize it.
703 if (Metrics.notDuplicatable || !Metrics.NumInsts.isValid() ||
704 (RequireMinSize && Metrics.NumInsts < MinFunctionSize))
705 continue;
706
707 // When specialization on literal constants is disabled, only consider
708 // recursive functions when running multiple times to save wasted analysis,
709 // as we will not be able to specialize on any newly found literal constant
710 // return values.
711 if (!SpecializeLiteralConstant && !Inserted && !Metrics.isRecursive)
712 continue;
713
714 int64_t Sz = Metrics.NumInsts.getValue();
715 assert(Sz > 0 && "CodeSize should be positive");
716 // It is safe to down cast from int64_t, NumInsts is always positive.
717 unsigned FuncSize = static_cast<unsigned>(Sz);
718
719 LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for "
720 << F.getName() << " is " << FuncSize << "\n");
721
722 if (Inserted && Metrics.isRecursive)
723 promoteConstantStackValues(&F);
724
725 if (!findSpecializations(&F, FuncSize, AllSpecs, SM)) {
727 dbgs() << "FnSpecialization: No possible specializations found for "
728 << F.getName() << "\n");
729 continue;
730 }
731
732 ++NumCandidates;
733 }
734
735 if (!NumCandidates) {
737 dbgs()
738 << "FnSpecialization: No possible specializations found in module\n");
739 return false;
740 }
741
742 // Choose the most profitable specialisations, which fit in the module
743 // specialization budget, which is derived from maximum number of
744 // specializations per specialization candidate function.
745 auto CompareScore = [&AllSpecs](unsigned I, unsigned J) {
746 if (AllSpecs[I].Score != AllSpecs[J].Score)
747 return AllSpecs[I].Score > AllSpecs[J].Score;
748 return I > J;
749 };
750 const unsigned NSpecs =
751 std::min(NumCandidates * MaxClones, unsigned(AllSpecs.size()));
752 SmallVector<unsigned> BestSpecs(NSpecs + 1);
753 std::iota(BestSpecs.begin(), BestSpecs.begin() + NSpecs, 0);
754 if (AllSpecs.size() > NSpecs) {
755 LLVM_DEBUG(dbgs() << "FnSpecialization: Number of candidates exceed "
756 << "the maximum number of clones threshold.\n"
757 << "FnSpecialization: Specializing the "
758 << NSpecs
759 << " most profitable candidates.\n");
760 std::make_heap(BestSpecs.begin(), BestSpecs.begin() + NSpecs, CompareScore);
761 for (unsigned I = NSpecs, N = AllSpecs.size(); I < N; ++I) {
762 BestSpecs[NSpecs] = I;
763 std::push_heap(BestSpecs.begin(), BestSpecs.end(), CompareScore);
764 std::pop_heap(BestSpecs.begin(), BestSpecs.end(), CompareScore);
765 }
766 }
767
768 LLVM_DEBUG(dbgs() << "FnSpecialization: List of specializations \n";
769 for (unsigned I = 0; I < NSpecs; ++I) {
770 const Spec &S = AllSpecs[BestSpecs[I]];
771 dbgs() << "FnSpecialization: Function " << S.F->getName()
772 << " , score " << S.Score << "\n";
773 for (const ArgInfo &Arg : S.Sig.Args)
774 dbgs() << "FnSpecialization: FormalArg = "
775 << Arg.Formal->getNameOrAsOperand()
776 << ", ActualArg = " << Arg.Actual->getNameOrAsOperand()
777 << "\n";
778 });
779
780 // Create the chosen specializations.
781 SmallPtrSet<Function *, 8> OriginalFuncs;
783 for (unsigned I = 0; I < NSpecs; ++I) {
784 Spec &S = AllSpecs[BestSpecs[I]];
785
786 // Accumulate the codesize growth for the function, now we are creating the
787 // specialization.
788 FunctionGrowth[S.F] += S.CodeSize;
789
790 S.Clone = createSpecialization(S.F, S.Sig);
791
792 // Update the known call sites to call the clone.
793 for (CallBase *Call : S.CallSites) {
794 Function *Clone = S.Clone;
795 LLVM_DEBUG(dbgs() << "FnSpecialization: Redirecting " << *Call
796 << " to call " << Clone->getName() << "\n");
797 Call->setCalledFunction(S.Clone);
798 auto &BFI = GetBFI(*Call->getFunction());
799 std::optional<uint64_t> Count =
800 BFI.getBlockProfileCount(Call->getParent());
802 std::optional<llvm::Function::ProfileCount> MaybeCloneCount =
803 Clone->getEntryCount();
804 if (MaybeCloneCount) {
805 uint64_t CallCount = *Count + MaybeCloneCount->getCount();
806 Clone->setEntryCount(CallCount);
807 if (std::optional<llvm::Function::ProfileCount> MaybeOriginalCount =
808 S.F->getEntryCount()) {
809 uint64_t OriginalCount = MaybeOriginalCount->getCount();
810 if (OriginalCount >= *Count) {
811 S.F->setEntryCount(OriginalCount - *Count);
812 } else {
813 // This should generally not happen as that would mean there are
814 // more computed calls to the function than what was recorded.
816 }
817 }
818 }
819 }
820 }
821
822 Clones.push_back(S.Clone);
823 OriginalFuncs.insert(S.F);
824 }
825
826 Solver.solveWhileResolvedUndefsIn(Clones);
827
828 // Update the rest of the call sites - these are the recursive calls, calls
829 // to discarded specialisations and calls that may match a specialisation
830 // after the solver runs.
831 for (Function *F : OriginalFuncs) {
832 auto [Begin, End] = SM[F];
833 updateCallSites(F, AllSpecs.begin() + Begin, AllSpecs.begin() + End);
834 }
835
836 for (Function *F : Clones) {
837 if (F->getReturnType()->isVoidTy())
838 continue;
839 if (F->getReturnType()->isStructTy()) {
840 auto *STy = cast<StructType>(F->getReturnType());
841 if (!Solver.isStructLatticeConstant(F, STy))
842 continue;
843 } else {
844 auto It = Solver.getTrackedRetVals().find(F);
845 assert(It != Solver.getTrackedRetVals().end() &&
846 "Return value ought to be tracked");
847 if (SCCPSolver::isOverdefined(It->second))
848 continue;
849 }
850 for (User *U : F->users()) {
851 if (auto *CS = dyn_cast<CallBase>(U)) {
852 //The user instruction does not call our function.
853 if (CS->getCalledFunction() != F)
854 continue;
855 Solver.resetLatticeValueFor(CS);
856 }
857 }
858 }
859
860 // Rerun the solver to notify the users of the modified callsites.
861 Solver.solveWhileResolvedUndefs();
862
863 for (Function *F : OriginalFuncs)
864 if (FunctionMetrics[F].isRecursive)
865 promoteConstantStackValues(F);
866
867 return true;
868}
869
870void FunctionSpecializer::removeDeadFunctions() {
871 for (Function *F : DeadFunctions) {
872 LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "
873 << F->getName() << "\n");
874 if (FAM)
875 FAM->clear(*F, F->getName());
876
877 // Remove all the callsites that were proven unreachable once, and replace
878 // them with poison.
879 for (User *U : make_early_inc_range(F->users())) {
880 assert((isa<CallInst>(U) || isa<InvokeInst>(U)) &&
881 "User of dead function must be call or invoke");
882 Instruction *CS = cast<Instruction>(U);
883 CS->replaceAllUsesWith(PoisonValue::get(CS->getType()));
884 CS->eraseFromParent();
885 }
886 F->eraseFromParent();
887 }
888 DeadFunctions.clear();
889}
890
891/// Clone the function \p F and remove the ssa_copy intrinsics added by
892/// the SCCPSolver in the cloned version.
893 static Function *cloneCandidateFunction(Function *F, unsigned NSpecs) {
894 ValueToValueMapTy Mappings;
895 Function *Clone = CloneFunction(F, Mappings);
896 Clone->setName(F->getName() + ".specialized." + Twine(NSpecs));
897 removeSSACopy(*Clone);
898 return Clone;
899}
900
901bool FunctionSpecializer::findSpecializations(Function *F, unsigned FuncSize,
902 SmallVectorImpl<Spec> &AllSpecs,
903 SpecMap &SM) {
904 // A mapping from a specialisation signature to the index of the respective
905 // entry in the all specialisation array. Used to ensure uniqueness of
906 // specialisations.
907 DenseMap<SpecSig, unsigned> UniqueSpecs;
908
909 // Get a list of interesting arguments.
910 SmallVector<Argument *> Args;
911 for (Argument &Arg : F->args())
912 if (isArgumentInteresting(&Arg))
913 Args.push_back(&Arg);
914
915 if (Args.empty())
916 return false;
917
918 for (User *U : F->users()) {
919 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
920 continue;
921 auto &CS = *cast<CallBase>(U);
922
923 // The user instruction does not call our function.
924 if (CS.getCalledFunction() != F)
925 continue;
926
927 // If the call site has attribute minsize set, that callsite won't be
928 // specialized.
929 if (CS.hasFnAttr(Attribute::MinSize))
930 continue;
931
932 // If the parent of the call site will never be executed, we don't need
933 // to worry about the passed value.
934 if (!Solver.isBlockExecutable(CS.getParent()))
935 continue;
936
937 // Examine arguments and create a specialisation candidate from the
938 // constant operands of this call site.
939 SpecSig S;
940 for (Argument *A : Args) {
941 Constant *C = getCandidateConstant(CS.getArgOperand(A->getArgNo()));
942 if (!C)
943 continue;
944 LLVM_DEBUG(dbgs() << "FnSpecialization: Found interesting argument "
945 << A->getName() << " : " << C->getNameOrAsOperand()
946 << "\n");
947 S.Args.push_back({A, C});
948 }
949
950 if (S.Args.empty())
951 continue;
952
953 // Check if we have encountered the same specialisation already.
954 if (auto It = UniqueSpecs.find(S); It != UniqueSpecs.end()) {
955 // Existing specialisation. Add the call to the list to rewrite, unless
956 // it's a recursive call. A specialisation, generated because of a
957 // recursive call may end up as not the best specialisation for all
958 // the cloned instances of this call, which result from specialising
959 // functions. Hence we don't rewrite the call directly, but match it with
960 // the best specialisation once all specialisations are known.
961 if (CS.getFunction() == F)
962 continue;
963 const unsigned Index = It->second;
964 AllSpecs[Index].CallSites.push_back(&CS);
965 } else {
966 // Calculate the specialisation gain.
967 Cost CodeSize;
968 unsigned Score = 0;
969 InstCostVisitor Visitor = getInstCostVisitorFor(F);
970 for (ArgInfo &A : S.Args) {
971 CodeSize += Visitor.getCodeSizeSavingsForArg(A.Formal, A.Actual);
972 Score += getInliningBonus(A.Formal, A.Actual);
973 }
974 CodeSize += Visitor.getCodeSizeSavingsFromPendingPHIs();
975
976 unsigned CodeSizeSavings = getCostValue(CodeSize);
977 unsigned SpecSize = FuncSize - CodeSizeSavings;
978
979 auto IsProfitable = [&]() -> bool {
980 // No check required.
981 if (ForceSpecialization)
982 return true;
983
984 LLVM_DEBUG(
985 dbgs() << "FnSpecialization: Specialization bonus {Inlining = "
986 << Score << " (" << (Score * 100 / FuncSize) << "%)}\n");
987
988 // Minimum inlining bonus.
989 if (Score > MinInliningBonus * FuncSize / 100)
990 return true;
991
992 LLVM_DEBUG(
993 dbgs() << "FnSpecialization: Specialization bonus {CodeSize = "
994 << CodeSizeSavings << " ("
995 << (CodeSizeSavings * 100 / FuncSize) << "%)}\n");
996
997 // Minimum codesize savings.
998 if (CodeSizeSavings < MinCodeSizeSavings * FuncSize / 100)
999 return false;
1000
1001 // Lazily compute the Latency, to avoid unnecessarily computing BFI.
1002 unsigned LatencySavings =
1003 getCostValue(Visitor.getLatencySavingsForKnownConstants());
1004
1005 LLVM_DEBUG(
1006 dbgs() << "FnSpecialization: Specialization bonus {Latency = "
1007 << LatencySavings << " ("
1008 << (LatencySavings * 100 / FuncSize) << "%)}\n");
1009
1010 // Minimum latency savings.
1011 if (LatencySavings < MinLatencySavings * FuncSize / 100)
1012 return false;
1013 // Maximum codesize growth.
1014 if ((FunctionGrowth[F] + SpecSize) / FuncSize > MaxCodeSizeGrowth)
1015 return false;
1016
1017 Score += std::max(CodeSizeSavings, LatencySavings);
1018 return true;
1019 };
1020
1021 // Discard unprofitable specialisations.
1022 if (!IsProfitable())
1023 continue;
1024
1025 // Create a new specialisation entry.
1026 auto &Spec = AllSpecs.emplace_back(F, S, Score, SpecSize);
1027 if (CS.getFunction() != F)
1028 Spec.CallSites.push_back(&CS);
1029 const unsigned Index = AllSpecs.size() - 1;
1030 UniqueSpecs[S] = Index;
1031 if (auto [It, Inserted] = SM.try_emplace(F, Index, Index + 1); !Inserted)
1032 It->second.second = Index + 1;
1033 }
1034 }
1035
1036 return !UniqueSpecs.empty();
1037}
1038
1039bool FunctionSpecializer::isCandidateFunction(Function *F) {
1040 if (F->isDeclaration() || F->arg_empty())
1041 return false;
1042
1043 if (F->hasFnAttribute(Attribute::NoDuplicate))
1044 return false;
1045
1046 // Do not specialize the cloned function again.
1047 if (Specializations.contains(F))
1048 return false;
1049
1050 // If we're optimizing the function for size, we shouldn't specialize it.
1051 if (shouldOptimizeForSize(F, nullptr, nullptr, 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(&F->getEntryBlock()))
1057 return false;
1058
1059 // It wastes time to specialize a function which would get inlined finally.
1060 if (F->hasFnAttribute(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, 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(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(Clone, S.Args);
1083 Solver.markBlockExecutable(&Clone->front());
1084 Solver.addArgumentTrackedFunction(Clone);
1085 Solver.addTrackedFunction(Clone);
1086
1087 // Mark all the specialized functions
1088 Specializations.insert(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>(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>(U) && !isa<InvokeInst>(U))
1114 continue;
1115 auto *CS = cast<CallBase>(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(*CS, CalledFunction, Params, CalleeTTI, 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(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(Solver.getStructLatticeValueFor(A), SCCPSolver::isOverdefined)
1175 : SCCPSolver::isOverdefined(Solver.getLatticeValueFor(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>(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>(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>(getUnderlyingObject(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>(U);
1216 CS && CS->getCalledFunction() == F &&
1217 Solver.isBlockExecutable(CS->getParent()))
1218 ToUpdate.push_back(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(Begin, End)) {
1227 if (!S.Clone || (BestSpec && S.Score <= BestSpec->Score))
1228 continue;
1229
1230 if (any_of(S.Sig.Args, [CS, this](const ArgInfo &Arg) {
1231 unsigned ArgNo = Arg.Formal->getArgNo();
1232 return getCandidateConstant(CS->getArgOperand(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(F);
1258 }
1259}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
A
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static Function * cloneCandidateFunction(Function *F, unsigned NSpecs)
Clone the function F and remove the ssa_copy intrinsics added by the SCCPSolver in the cloned version...
static void removeSSACopy(Function &F)
static unsigned getCostValue(const Cost &C)
Get the unsigned Value of given Cost object.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
F
#define F(x, y, z)
Definition MD5.cpp:55
I
#define I(x, y, z)
Definition MD5.cpp:58
Machine Trace Metrics
FunctionAnalysisManager FAM
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:114
This pass exposes codegen information to IR-level passes.
an instruction to allocate memory on the stack
Definition Instructions.h:65
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition Instructions.h:122
This class represents an incoming formal argument to a Function.
Definition Argument.h:32
LLVM Basic Block Representation.
Definition BasicBlock.h:62
Conditional or Unconditional Branch instruction.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition InstrTypes.h:1114
bool onlyReadsMemory(unsigned OpNo) const
Definition InstrTypes.h:1749
Value * getArgOperand(unsigned i) const
Definition InstrTypes.h:1290
void setArgOperand(unsigned i, Value *v)
Definition InstrTypes.h:1295
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition InstrTypes.h:1281
unsigned getArgOperandNo(const Use *U) const
Given a use for a arg operand, get the arg operand number that corresponds to it.
Definition InstrTypes.h:1321
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition InstrTypes.h:448
This class is the base class for the comparison instructions.
Definition InstrTypes.h:664
This is an important base class in LLVM.
Definition Constant.h:43
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:178
bool empty() const
Definition DenseMap.h:109
iterator end()
Definition DenseMap.h:81
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition DenseMap.h:169
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:233
Implements a dense probed hash-table based set.
Definition DenseSet.h:279
This class represents a freeze function that returns random concrete value if an operand is either a ...
LLVM_ABI bool run()
Attempt to specialize functions in the module to enable constant propagation across function boundari...
InstCostVisitor getInstCostVisitorFor(Function *F)
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition Function.h:209
const BasicBlock & front() const
Definition Function.h:858
std::optional< ProfileCount > getEntryCount(bool AllowSynthetic=false) const
Get the entry count for this function.
Definition Function.cpp:1121
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
Definition Function.cpp:1099
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition Instructions.h:950
void setLinkage(LinkageTypes LT)
Definition GlobalValue.h:539
@ InternalLinkage
Rename collisions when linking (static functions).
Definition GlobalValue.h:60
bool isAlways() const
Definition InlineCost.h:140
int getCostDelta() const
Get the cost delta from the threshold for inlining.
Definition InlineCost.h:176
bool isVariable() const
Definition InlineCost.h:142
LLVM_ABI Cost getLatencySavingsForKnownConstants()
Compute the latency savings from replacing all arguments with constants for a specialization candidat...
LLVM_ABI Cost getCodeSizeSavingsForArg(Argument *A, Constant *C)
Compute the codesize savings for replacing argument A with constant C.
LLVM_ABI Cost getCodeSizeSavingsFromPendingPHIs()
bool isBlockExecutable(BasicBlock *BB) const
void visit(Iterator Start, Iterator End)
Definition InstVisitor.h:87
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
Definition Instruction.cpp:86
An instruction for reading from memory.
Definition Instructions.h:181
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition Constants.cpp:1888
static LLVM_ABI bool isOverdefined(const ValueLatticeElement &LV)
Definition SCCPSolver.cpp:60
This class represents the LLVM 'select' instruction.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition SmallPtrSet.h:527
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition SmallVector.h:574
reference emplace_back(ArgTypes &&... Args)
Definition SmallVector.h:944
void reserve(size_type N)
Definition SmallVector.h:664
void push_back(const T &Elt)
Definition SmallVector.h:417
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition SmallVector.h:1203
Multiway switch.
@ TCK_CodeSize
Instruction code size.
@ TCK_Latency
The latency of instruction.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:267
bool isStructTy() const
True if this is an instance of StructType.
Definition Type.h:261
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition Type.h:184
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:240
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
Definition User.h:44
LLVM_ABI Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
static ValueLatticeElement get(Constant *C)
Definition ValueLattice.h:201
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:256
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
Definition Value.cpp:382
LLVM_ABI std::string getNameOrAsOperand() const
Definition Value.cpp:449
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:538
iterator_range< user_iterator > users()
Definition Value.h:426
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition Value.cpp:693
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:202
const ParentTy * getParent() const
Definition ilist_node.h:34
CallInst * Call
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ C
The default llvm calling convention, compatible with C.
Definition CallingConv.h:34
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:81
@ Constant
Definition ISDOpcodes.h:86
const int IndirectCallThreshold
Definition InlineCost.h:50
@ Const
Definition NVPTX.h:185
initializer< Ty > init(const Ty &Val)
Definition CommandLine.h:445
@ User
could "use" a pointer
This is an optimization pass for GlobalISel generic memory operations.
Definition AddressRanges.h:18
static cl::opt< unsigned > MinCodeSizeSavings("funcspec-min-codesize-savings", cl::init(20), cl::Hidden, cl::desc("Reject specializations whose codesize savings are less than this " "much percent of the original function size"))
FunctionAddr VTableAddr Value
Definition InstrProf.h:137
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1725
hash_code hash_value(const FixedPointSemantics &Val)
Definition APFixedPoint.h:137
static cl::opt< bool > SpecializeOnAddress("funcspec-on-address", cl::init(false), cl::Hidden, cl::desc("Enable function specialization on the address of global values"))
InstructionCost Cost
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
auto successors(const MachineBasicBlock *BB)
static cl::opt< unsigned > MaxIncomingPhiValues("funcspec-max-incoming-phi-values", cl::init(8), cl::Hidden, cl::desc("The maximum number of incoming values a PHI node can have to be " "considered during the specialization bonus estimation"))
static cl::opt< bool > SpecializeLiteralConstant("funcspec-for-literal-constant", cl::init(true), cl::Hidden, cl::desc("Enable specialization of functions that take a literal constant as an " "argument"))
DenseMap< Function *, std::pair< unsigned, unsigned > > SpecMap
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ABI bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
LLVM_ABI Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
static cl::opt< unsigned > MaxCodeSizeGrowth("funcspec-max-codesize-growth", cl::init(3), cl::Hidden, cl::desc("Maximum codesize growth allowed per function"))
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:632
static cl::opt< unsigned > MinLatencySavings("funcspec-min-latency-savings", cl::init(20), cl::Hidden, cl::desc("Reject specializations whose latency savings are less than this " "much percent of the original function size"))
LLVM_ABI Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
static cl::opt< unsigned > MinFunctionSize("funcspec-min-function-size", cl::init(500), cl::Hidden, cl::desc("Don't specialize functions that have less than this number of " "instructions"))
static cl::opt< unsigned > MaxDiscoveryIterations("funcspec-max-discovery-iterations", cl::init(100), cl::Hidden, cl::desc("The maximum number of iterations allowed " "when searching for transitive " "phis"))
auto dyn_cast_or_null(const Y &Val)
Definition Casting.h:753
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1732
LLVM_ABI Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
FunctionAddr VTableAddr Count
Definition InstrProf.h:139
LLVM_ABI Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
Definition SmallVector.h:1129
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI InlineCost getInlineCost(CallBase &Call, const InlineParams &Params, TargetTransformInfo &CalleeTTI, function_ref< AssumptionCache &(Function &)> GetAssumptionCache, function_ref< const TargetLibraryInfo &(Function &)> GetTLI, function_ref< BlockFrequencyInfo &(Function &)> GetBFI=nullptr, ProfileSummaryInfo *PSI=nullptr, OptimizationRemarkEmitter *ORE=nullptr, function_ref< EphemeralValuesCache &(Function &)> GetEphValuesCache=nullptr)
Get an InlineCost object representing the cost of inlining this callsite.
@ Other
Any other memory.
Definition ModRef.h:68
static cl::opt< unsigned > MaxClones("funcspec-max-clones", cl::init(3), cl::Hidden, cl::desc("The maximum number of clones allowed for a single function " "specialization"))
LLVM_ABI Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
static cl::opt< bool > ForceSpecialization("force-specialization", cl::init(false), cl::Hidden, cl::desc("Force function specialization for every call site with a constant " "argument"))
static cl::opt< unsigned > MaxBlockPredecessors("funcspec-max-block-predecessors", cl::init(2), cl::Hidden, cl::desc("The maximum number of predecessors a basic block can have to be " "considered during the estimation of dead code"))
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI InlineParams getInlineParams()
Generate the parameters to tune the inline cost analysis based only on the commandline options.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
auto predecessors(const MachineBasicBlock *BB)
cl::opt< bool > ProfcheckDisableMetadataFixes("profcheck-disable-metadata-fixes", cl::Hidden, cl::init(false), cl::desc("Disable metadata propagation fixes discovered through Issue #147390"))
LLVM_ABI Constant * ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty, APInt Offset, const DataLayout &DL)
Return the value that a load from C with offset Offset would produce if it is constant and determinab...
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
LLVM_ABI Function * CloneFunction(Function *F, ValueToValueMapTy &VMap, ClonedCodeInfo *CodeInfo=nullptr)
Return a copy of the specified function and add it to that function's module.
static cl::opt< unsigned > MinInliningBonus("funcspec-min-inlining-bonus", cl::init(300), cl::Hidden, cl::desc("Reject specializations whose inlining bonus is less than this " "much percent of the original function size"))
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:869
N
#define N
Helper struct shared between Function Specialization and SCCP Solver.
Definition SCCPSolver.h:42
Argument * Formal
Definition SCCPSolver.h:43
Constant * Actual
Definition SCCPSolver.h:44
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition CodeMetrics.h:34
static LLVM_ABI void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Definition CodeMetrics.cpp:71
static unsigned getHashValue(const SpecSig &S)
static bool isEqual(const SpecSig &LHS, const SpecSig &RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition DenseMapInfo.h:54
SmallVector< ArgInfo, 4 > Args
SmallVector< CallBase * > CallSites
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /