LLVM 20.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
10#include "llvm/ADT/Statistic.h"
24#include <cmath>
25
26using namespace llvm;
27
28#define DEBUG_TYPE "function-specialization"
29
30STATISTIC(NumSpecsCreated, "Number of specializations created");
31
33 "force-specialization", cl::init(false), cl::Hidden, cl::desc(
34 "Force function specialization for every call site with a constant "
35 "argument"));
36
38 "funcspec-max-clones", cl::init(3), cl::Hidden, cl::desc(
39 "The maximum number of clones allowed for a single function "
40 "specialization"));
41
43 MaxDiscoveryIterations("funcspec-max-discovery-iterations", cl::init(100),
45 cl::desc("The maximum number of iterations allowed "
46 "when searching for transitive "
47 "phis"));
48
50 "funcspec-max-incoming-phi-values", cl::init(8), cl::Hidden,
51 cl::desc("The maximum number of incoming values a PHI node can have to be "
52 "considered during the specialization bonus estimation"));
53
55 "funcspec-max-block-predecessors", cl::init(2), cl::Hidden, cl::desc(
56 "The maximum number of predecessors a basic block can have to be "
57 "considered during the estimation of dead code"));
58
60 "funcspec-min-function-size", cl::init(300), cl::Hidden, cl::desc(
61 "Don't specialize functions that have less than this number of "
62 "instructions"));
63
65 "funcspec-max-codesize-growth", cl::init(3), cl::Hidden, cl::desc(
66 "Maximum codesize growth allowed per function"));
67
69 "funcspec-min-codesize-savings", cl::init(20), cl::Hidden, cl::desc(
70 "Reject specializations whose codesize savings are less than this"
71 "much percent of the original function size"));
72
74 "funcspec-min-latency-savings", cl::init(40), cl::Hidden,
75 cl::desc("Reject specializations whose latency savings are less than this"
76 "much percent of the original function size"));
77
79 "funcspec-min-inlining-bonus", cl::init(300), cl::Hidden, cl::desc(
80 "Reject specializations whose inlining bonus is less than this"
81 "much percent of the original function size"));
82
84 "funcspec-on-address", cl::init(false), cl::Hidden, cl::desc(
85 "Enable function specialization on the address of global values"));
86
87// Disabled by default as it can significantly increase compilation times.
88//
89// https://llvm-compile-time-tracker.com
90// https://github.com/nikic/llvm-compile-time-tracker
92 "funcspec-for-literal-constant", cl::init(false), cl::Hidden, cl::desc(
93 "Enable specialization of functions that take a literal constant as an "
94 "argument"));
95
96bool InstCostVisitor::canEliminateSuccessor(BasicBlock *BB, BasicBlock *Succ,
97 DenseSet<BasicBlock *> &DeadBlocks) {
98 unsigned I = 0;
99 return all_of(predecessors(Succ),
100 [&I, BB, Succ, &DeadBlocks] (BasicBlock *Pred) {
101 return I++ < MaxBlockPredecessors &&
102 (Pred == BB || Pred == Succ || DeadBlocks.contains(Pred));
103 });
104}
105
106// Estimates the codesize savings due to dead code after constant propagation.
107// \p WorkList represents the basic blocks of a specialization which will
108// eventually become dead once we replace instructions that are known to be
109// constants. The successors of such blocks are added to the list as long as
110// the \p Solver found they were executable prior to specialization, and only
111// if all their predecessors are dead.
112Cost InstCostVisitor::estimateBasicBlocks(
114 Cost CodeSize = 0;
115 // Accumulate the instruction cost of each basic block weighted by frequency.
116 while (!WorkList.empty()) {
117 BasicBlock *BB = WorkList.pop_back_val();
118
119 // These blocks are considered dead as far as the InstCostVisitor
120 // is concerned. They haven't been proven dead yet by the Solver,
121 // but may become if we propagate the specialization arguments.
122 if (!DeadBlocks.insert(BB).second)
123 continue;
124
125 for (Instruction &I : *BB) {
126 // Disregard SSA copies.
127 if (auto *II = dyn_cast<IntrinsicInst>(&I))
128 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
129 continue;
130 // If it's a known constant we have already accounted for it.
131 if (KnownConstants.contains(&I))
132 continue;
133
135
136 LLVM_DEBUG(dbgs() << "FnSpecialization: CodeSize " << C
137 << " for user " << I << "\n");
138 CodeSize += C;
139 }
140
141 // Keep adding dead successors to the list as long as they are
142 // executable and only reachable from dead blocks.
143 for (BasicBlock *SuccBB : successors(BB))
144 if (isBlockExecutable(SuccBB) &&
145 canEliminateSuccessor(BB, SuccBB, DeadBlocks))
146 WorkList.push_back(SuccBB);
147 }
148 return CodeSize;
149}
150
151static Constant *findConstantFor(Value *V, ConstMap &KnownConstants) {
152 if (auto *C = dyn_cast<Constant>(V))
153 return C;
154 return KnownConstants.lookup(V);
155}
156
158 Bonus B;
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 B += getUserBonus(Phi);
164 }
165 return B;
166}
167
168/// Compute a bonus for replacing argument \p A with constant \p C.
170 LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "
171 << C->getNameOrAsOperand() << "\n");
172 Bonus B;
173 for (auto *U : A->users())
174 if (auto *UI = dyn_cast<Instruction>(U))
175 if (isBlockExecutable(UI->getParent()))
176 B += getUserBonus(UI, A, C);
177
178 LLVM_DEBUG(dbgs() << "FnSpecialization: Accumulated bonus {CodeSize = "
179 << B.CodeSize << ", Latency = " << B.Latency
180 << "} for argument " << *A << "\n");
181 return B;
182}
183
184Bonus InstCostVisitor::getUserBonus(Instruction *User, Value *Use, Constant *C) {
185 // We have already propagated a constant for this user.
186 if (KnownConstants.contains(User))
187 return {0, 0};
188
189 // Cache the iterator before visiting.
190 LastVisited = Use ? KnownConstants.insert({Use, C}).first
191 : KnownConstants.end();
192
193 Cost CodeSize = 0;
194 if (auto *I = dyn_cast<SwitchInst>(User)) {
195 CodeSize = estimateSwitchInst(*I);
196 } else if (auto *I = dyn_cast<BranchInst>(User)) {
197 CodeSize = estimateBranchInst(*I);
198 } else {
199 C = visit(*User);
200 if (!C)
201 return {0, 0};
202 }
203
204 // Even though it doesn't make sense to bind switch and branch instructions
205 // with a constant, unlike any other instruction type, it prevents estimating
206 // their bonus multiple times.
207 KnownConstants.insert({User, C});
208
210
211 uint64_t Weight = BFI.getBlockFreq(User->getParent()).getFrequency() /
213
214 Cost Latency = Weight *
216
217 LLVM_DEBUG(dbgs() << "FnSpecialization: {CodeSize = " << CodeSize
218 << ", Latency = " << Latency << "} for user "
219 << *User << "\n");
220
221 Bonus B(CodeSize, Latency);
222 for (auto *U : User->users())
223 if (auto *UI = dyn_cast<Instruction>(U))
224 if (UI != User && isBlockExecutable(UI->getParent()))
225 B += getUserBonus(UI, User, C);
226
227 return B;
228}
229
230Cost InstCostVisitor::estimateSwitchInst(SwitchInst &I) {
231 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
232
233 if (I.getCondition() != LastVisited->first)
234 return 0;
235
236 auto *C = dyn_cast<ConstantInt>(LastVisited->second);
237 if (!C)
238 return 0;
239
240 BasicBlock *Succ = I.findCaseValue(C)->getCaseSuccessor();
241 // Initialize the worklist with the dead basic blocks. These are the
242 // destination labels which are different from the one corresponding
243 // to \p C. They should be executable and have a unique predecessor.
245 for (const auto &Case : I.cases()) {
246 BasicBlock *BB = Case.getCaseSuccessor();
247 if (BB != Succ && isBlockExecutable(BB) &&
248 canEliminateSuccessor(I.getParent(), BB, DeadBlocks))
249 WorkList.push_back(BB);
250 }
251
252 return estimateBasicBlocks(WorkList);
253}
254
255Cost InstCostVisitor::estimateBranchInst(BranchInst &I) {
256 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
257
258 if (I.getCondition() != LastVisited->first)
259 return 0;
260
261 BasicBlock *Succ = I.getSuccessor(LastVisited->second->isOneValue());
262 // Initialize the worklist with the dead successor as long as
263 // it is executable and has a unique predecessor.
265 if (isBlockExecutable(Succ) &&
266 canEliminateSuccessor(I.getParent(), Succ, DeadBlocks))
267 WorkList.push_back(Succ);
268
269 return estimateBasicBlocks(WorkList);
270}
271
272bool InstCostVisitor::discoverTransitivelyIncomingValues(
273 Constant *Const, PHINode *Root, DenseSet<PHINode *> &TransitivePHIs) {
274
276 WorkList.push_back(Root);
277 unsigned Iter = 0;
278
279 while (!WorkList.empty()) {
280 PHINode *PN = WorkList.pop_back_val();
281
282 if (++Iter > MaxDiscoveryIterations ||
284 return false;
285
286 if (!TransitivePHIs.insert(PN).second)
287 continue;
288
289 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
290 Value *V = PN->getIncomingValue(I);
291
292 // Disregard self-references and dead incoming values.
293 if (auto *Inst = dyn_cast<Instruction>(V))
294 if (Inst == PN || DeadBlocks.contains(PN->getIncomingBlock(I)))
295 continue;
296
297 if (Constant *C = findConstantFor(V, KnownConstants)) {
298 // Not all incoming values are the same constant. Bail immediately.
299 if (C != Const)
300 return false;
301 continue;
302 }
303
304 if (auto *Phi = dyn_cast<PHINode>(V)) {
305 WorkList.push_back(Phi);
306 continue;
307 }
308
309 // We can't reason about anything else.
310 return false;
311 }
312 }
313 return true;
314}
315
316Constant *InstCostVisitor::visitPHINode(PHINode &I) {
317 if (I.getNumIncomingValues() > MaxIncomingPhiValues)
318 return nullptr;
319
320 bool Inserted = VisitedPHIs.insert(&I).second;
321 Constant *Const = nullptr;
322 bool HaveSeenIncomingPHI = false;
323
324 for (unsigned Idx = 0, E = I.getNumIncomingValues(); Idx != E; ++Idx) {
325 Value *V = I.getIncomingValue(Idx);
326
327 // Disregard self-references and dead incoming values.
328 if (auto *Inst = dyn_cast<Instruction>(V))
329 if (Inst == &I || DeadBlocks.contains(I.getIncomingBlock(Idx)))
330 continue;
331
332 if (Constant *C = findConstantFor(V, KnownConstants)) {
333 if (!Const)
334 Const = C;
335 // Not all incoming values are the same constant. Bail immediately.
336 if (C != Const)
337 return nullptr;
338 continue;
339 }
340
341 if (Inserted) {
342 // First time we are seeing this phi. We will retry later, after
343 // all the constant arguments have been propagated. Bail for now.
344 PendingPHIs.push_back(&I);
345 return nullptr;
346 }
347
348 if (isa<PHINode>(V)) {
349 // Perhaps it is a Transitive Phi. We will confirm later.
350 HaveSeenIncomingPHI = true;
351 continue;
352 }
353
354 // We can't reason about anything else.
355 return nullptr;
356 }
357
358 if (!Const)
359 return nullptr;
360
361 if (!HaveSeenIncomingPHI)
362 return Const;
363
364 DenseSet<PHINode *> TransitivePHIs;
365 if (!discoverTransitivelyIncomingValues(Const, &I, TransitivePHIs))
366 return nullptr;
367
368 return Const;
369}
370
371Constant *InstCostVisitor::visitFreezeInst(FreezeInst &I) {
372 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
373
374 if (isGuaranteedNotToBeUndefOrPoison(LastVisited->second))
375 return LastVisited->second;
376 return nullptr;
377}
378
379Constant *InstCostVisitor::visitCallBase(CallBase &I) {
380 Function *F = I.getCalledFunction();
381 if (!F || !canConstantFoldCallTo(&I, F))
382 return nullptr;
383
385 Operands.reserve(I.getNumOperands());
386
387 for (unsigned Idx = 0, E = I.getNumOperands() - 1; Idx != E; ++Idx) {
388 Value *V = I.getOperand(Idx);
389 Constant *C = findConstantFor(V, KnownConstants);
390 if (!C)
391 return nullptr;
392 Operands.push_back(C);
393 }
394
395 auto Ops = ArrayRef(Operands.begin(), Operands.end());
396 return ConstantFoldCall(&I, F, Ops);
397}
398
399Constant *InstCostVisitor::visitLoadInst(LoadInst &I) {
400 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
401
402 if (isa<ConstantPointerNull>(LastVisited->second))
403 return nullptr;
404 return ConstantFoldLoadFromConstPtr(LastVisited->second, I.getType(), DL);
405}
406
407Constant *InstCostVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {
409 Operands.reserve(I.getNumOperands());
410
411 for (unsigned Idx = 0, E = I.getNumOperands(); Idx != E; ++Idx) {
412 Value *V = I.getOperand(Idx);
413 Constant *C = findConstantFor(V, KnownConstants);
414 if (!C)
415 return nullptr;
416 Operands.push_back(C);
417 }
418
419 auto Ops = ArrayRef(Operands.begin(), Operands.end());
420 return ConstantFoldInstOperands(&I, Ops, DL);
421}
422
423Constant *InstCostVisitor::visitSelectInst(SelectInst &I) {
424 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
425
426 if (I.getCondition() != LastVisited->first)
427 return nullptr;
428
429 Value *V = LastVisited->second->isZeroValue() ? I.getFalseValue()
430 : I.getTrueValue();
431 Constant *C = findConstantFor(V, KnownConstants);
432 return C;
433}
434
435Constant *InstCostVisitor::visitCastInst(CastInst &I) {
436 return ConstantFoldCastOperand(I.getOpcode(), LastVisited->second,
437 I.getType(), DL);
438}
439
440Constant *InstCostVisitor::visitCmpInst(CmpInst &I) {
441 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
442
443 bool Swap = I.getOperand(1) == LastVisited->first;
444 Value *V = Swap ? I.getOperand(0) : I.getOperand(1);
445 Constant *Other = findConstantFor(V, KnownConstants);
446 if (!Other)
447 return nullptr;
448
449 Constant *Const = LastVisited->second;
450 return Swap ?
451 ConstantFoldCompareInstOperands(I.getPredicate(), Other, Const, DL)
453}
454
455Constant *InstCostVisitor::visitUnaryOperator(UnaryOperator &I) {
456 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
457
458 return ConstantFoldUnaryOpOperand(I.getOpcode(), LastVisited->second, DL);
459}
460
461Constant *InstCostVisitor::visitBinaryOperator(BinaryOperator &I) {
462 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");
463
464 bool Swap = I.getOperand(1) == LastVisited->first;
465 Value *V = Swap ? I.getOperand(0) : I.getOperand(1);
466 Constant *Other = findConstantFor(V, KnownConstants);
467 if (!Other)
468 return nullptr;
469
470 Constant *Const = LastVisited->second;
471 return dyn_cast_or_null<Constant>(Swap ?
472 simplifyBinOp(I.getOpcode(), Other, Const, SimplifyQuery(DL))
473 : simplifyBinOp(I.getOpcode(), Const, Other, SimplifyQuery(DL)));
474}
475
476Constant *FunctionSpecializer::getPromotableAlloca(AllocaInst *Alloca,
477 CallInst *Call) {
478 Value *StoreValue = nullptr;
479 for (auto *User : Alloca->users()) {
480 // We can't use llvm::isAllocaPromotable() as that would fail because of
481 // the usage in the CallInst, which is what we check here.
482 if (User == Call)
483 continue;
484
485 if (auto *Store = dyn_cast<StoreInst>(User)) {
486 // This is a duplicate store, bail out.
487 if (StoreValue || Store->isVolatile())
488 return nullptr;
489 StoreValue = Store->getValueOperand();
490 continue;
491 }
492 // Bail if there is any other unknown usage.
493 return nullptr;
494 }
495
496 if (!StoreValue)
497 return nullptr;
498
499 return getCandidateConstant(StoreValue);
500}
501
502// A constant stack value is an AllocaInst that has a single constant
503// value stored to it. Return this constant if such an alloca stack value
504// is a function argument.
505Constant *FunctionSpecializer::getConstantStackValue(CallInst *Call,
506 Value *Val) {
507 if (!Val)
508 return nullptr;
509 Val = Val->stripPointerCasts();
510 if (auto *ConstVal = dyn_cast<ConstantInt>(Val))
511 return ConstVal;
512 auto *Alloca = dyn_cast<AllocaInst>(Val);
513 if (!Alloca || !Alloca->getAllocatedType()->isIntegerTy())
514 return nullptr;
515 return getPromotableAlloca(Alloca, Call);
516}
517
518// To support specializing recursive functions, it is important to propagate
519// constant arguments because after a first iteration of specialisation, a
520// reduced example may look like this:
521//
522// define internal void @RecursiveFn(i32* arg1) {
523// %temp = alloca i32, align 4
524// store i32 2 i32* %temp, align 4
525// call void @RecursiveFn.1(i32* nonnull %temp)
526// ret void
527// }
528//
529// Before a next iteration, we need to propagate the constant like so
530// which allows further specialization in next iterations.
531//
532// @funcspec.arg = internal constant i32 2
533//
534// define internal void @someFunc(i32* arg1) {
535// call void @otherFunc(i32* nonnull @funcspec.arg)
536// ret void
537// }
538//
539// See if there are any new constant values for the callers of \p F via
540// stack variables and promote them to global variables.
541void FunctionSpecializer::promoteConstantStackValues(Function *F) {
542 for (User *U : F->users()) {
543
544 auto *Call = dyn_cast<CallInst>(U);
545 if (!Call)
546 continue;
547
548 if (!Solver.isBlockExecutable(Call->getParent()))
549 continue;
550
551 for (const Use &U : Call->args()) {
552 unsigned Idx = Call->getArgOperandNo(&U);
553 Value *ArgOp = Call->getArgOperand(Idx);
554 Type *ArgOpType = ArgOp->getType();
555
556 if (!Call->onlyReadsMemory(Idx) || !ArgOpType->isPointerTy())
557 continue;
558
559 auto *ConstVal = getConstantStackValue(Call, ArgOp);
560 if (!ConstVal)
561 continue;
562
563 Value *GV = new GlobalVariable(M, ConstVal->getType(), true,
565 "specialized.arg." + Twine(++NGlobals));
566 Call->setArgOperand(Idx, GV);
567 }
568 }
569}
570
571// ssa_copy intrinsics are introduced by the SCCP solver. These intrinsics
572// interfere with the promoteConstantStackValues() optimization.
573static void removeSSACopy(Function &F) {
574 for (BasicBlock &BB : F) {
575 for (Instruction &Inst : llvm::make_early_inc_range(BB)) {
576 auto *II = dyn_cast<IntrinsicInst>(&Inst);
577 if (!II)
578 continue;
579 if (II->getIntrinsicID() != Intrinsic::ssa_copy)
580 continue;
581 Inst.replaceAllUsesWith(II->getOperand(0));
582 Inst.eraseFromParent();
583 }
584 }
585}
586
587/// Remove any ssa_copy intrinsics that may have been introduced.
588void FunctionSpecializer::cleanUpSSA() {
589 for (Function *F : Specializations)
591}
592
593
594template <> struct llvm::DenseMapInfo<SpecSig> {
595 static inline SpecSig getEmptyKey() { return {~0U, {}}; }
596
597 static inline SpecSig getTombstoneKey() { return {~1U, {}}; }
598
599 static unsigned getHashValue(const SpecSig &S) {
600 return static_cast<unsigned>(hash_value(S));
601 }
602
603 static bool isEqual(const SpecSig &LHS, const SpecSig &RHS) {
604 return LHS == RHS;
605 }
606};
607
610 if (NumSpecsCreated > 0)
611 dbgs() << "FnSpecialization: Created " << NumSpecsCreated
612 << " specializations in module " << M.getName() << "\n");
613 // Eliminate dead code.
614 removeDeadFunctions();
615 cleanUpSSA();
616}
617
618/// Attempt to specialize functions in the module to enable constant
619/// propagation across function boundaries.
620///
621/// \returns true if at least one function is specialized.
623 // Find possible specializations for each function.
624 SpecMap SM;
625 SmallVector<Spec, 32> AllSpecs;
626 unsigned NumCandidates = 0;
627 for (Function &F : M) {
628 if (!isCandidateFunction(&F))
629 continue;
630
631 auto [It, Inserted] = FunctionMetrics.try_emplace(&F);
632 CodeMetrics &Metrics = It->second;
633 //Analyze the function.
634 if (Inserted) {
636 CodeMetrics::collectEphemeralValues(&F, &GetAC(F), EphValues);
637 for (BasicBlock &BB : F)
638 Metrics.analyzeBasicBlock(&BB, GetTTI(F), EphValues);
639 }
640
641 // If the code metrics reveal that we shouldn't duplicate the function,
642 // or if the code size implies that this function is easy to get inlined,
643 // then we shouldn't specialize it.
644 if (Metrics.notDuplicatable || !Metrics.NumInsts.isValid() ||
645 (!ForceSpecialization && !F.hasFnAttribute(Attribute::NoInline) &&
646 Metrics.NumInsts < MinFunctionSize))
647 continue;
648
649 // TODO: For now only consider recursive functions when running multiple
650 // times. This should change if specialization on literal constants gets
651 // enabled.
652 if (!Inserted && !Metrics.isRecursive && !SpecializeLiteralConstant)
653 continue;
654
655 int64_t Sz = *Metrics.NumInsts.getValue();
656 assert(Sz > 0 && "CodeSize should be positive");
657 // It is safe to down cast from int64_t, NumInsts is always positive.
658 unsigned FuncSize = static_cast<unsigned>(Sz);
659
660 LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for "
661 << F.getName() << " is " << FuncSize << "\n");
662
663 if (Inserted && Metrics.isRecursive)
664 promoteConstantStackValues(&F);
665
666 if (!findSpecializations(&F, FuncSize, AllSpecs, SM)) {
668 dbgs() << "FnSpecialization: No possible specializations found for "
669 << F.getName() << "\n");
670 continue;
671 }
672
673 ++NumCandidates;
674 }
675
676 if (!NumCandidates) {
678 dbgs()
679 << "FnSpecialization: No possible specializations found in module\n");
680 return false;
681 }
682
683 // Choose the most profitable specialisations, which fit in the module
684 // specialization budget, which is derived from maximum number of
685 // specializations per specialization candidate function.
686 auto CompareScore = [&AllSpecs](unsigned I, unsigned J) {
687 if (AllSpecs[I].Score != AllSpecs[J].Score)
688 return AllSpecs[I].Score > AllSpecs[J].Score;
689 return I > J;
690 };
691 const unsigned NSpecs =
692 std::min(NumCandidates * MaxClones, unsigned(AllSpecs.size()));
693 SmallVector<unsigned> BestSpecs(NSpecs + 1);
694 std::iota(BestSpecs.begin(), BestSpecs.begin() + NSpecs, 0);
695 if (AllSpecs.size() > NSpecs) {
696 LLVM_DEBUG(dbgs() << "FnSpecialization: Number of candidates exceed "
697 << "the maximum number of clones threshold.\n"
698 << "FnSpecialization: Specializing the "
699 << NSpecs
700 << " most profitable candidates.\n");
701 std::make_heap(BestSpecs.begin(), BestSpecs.begin() + NSpecs, CompareScore);
702 for (unsigned I = NSpecs, N = AllSpecs.size(); I < N; ++I) {
703 BestSpecs[NSpecs] = I;
704 std::push_heap(BestSpecs.begin(), BestSpecs.end(), CompareScore);
705 std::pop_heap(BestSpecs.begin(), BestSpecs.end(), CompareScore);
706 }
707 }
708
709 LLVM_DEBUG(dbgs() << "FnSpecialization: List of specializations \n";
710 for (unsigned I = 0; I < NSpecs; ++I) {
711 const Spec &S = AllSpecs[BestSpecs[I]];
712 dbgs() << "FnSpecialization: Function " << S.F->getName()
713 << " , score " << S.Score << "\n";
714 for (const ArgInfo &Arg : S.Sig.Args)
715 dbgs() << "FnSpecialization: FormalArg = "
716 << Arg.Formal->getNameOrAsOperand()
717 << ", ActualArg = " << Arg.Actual->getNameOrAsOperand()
718 << "\n";
719 });
720
721 // Create the chosen specializations.
722 SmallPtrSet<Function *, 8> OriginalFuncs;
724 for (unsigned I = 0; I < NSpecs; ++I) {
725 Spec &S = AllSpecs[BestSpecs[I]];
726 S.Clone = createSpecialization(S.F, S.Sig);
727
728 // Update the known call sites to call the clone.
729 for (CallBase *Call : S.CallSites) {
730 LLVM_DEBUG(dbgs() << "FnSpecialization: Redirecting " << *Call
731 << " to call " << S.Clone->getName() << "\n");
732 Call->setCalledFunction(S.Clone);
733 }
734
735 Clones.push_back(S.Clone);
736 OriginalFuncs.insert(S.F);
737 }
738
739 Solver.solveWhileResolvedUndefsIn(Clones);
740
741 // Update the rest of the call sites - these are the recursive calls, calls
742 // to discarded specialisations and calls that may match a specialisation
743 // after the solver runs.
744 for (Function *F : OriginalFuncs) {
745 auto [Begin, End] = SM[F];
746 updateCallSites(F, AllSpecs.begin() + Begin, AllSpecs.begin() + End);
747 }
748
749 for (Function *F : Clones) {
750 if (F->getReturnType()->isVoidTy())
751 continue;
752 if (F->getReturnType()->isStructTy()) {
753 auto *STy = cast<StructType>(F->getReturnType());
754 if (!Solver.isStructLatticeConstant(F, STy))
755 continue;
756 } else {
757 auto It = Solver.getTrackedRetVals().find(F);
758 assert(It != Solver.getTrackedRetVals().end() &&
759 "Return value ought to be tracked");
760 if (SCCPSolver::isOverdefined(It->second))
761 continue;
762 }
763 for (User *U : F->users()) {
764 if (auto *CS = dyn_cast<CallBase>(U)) {
765 //The user instruction does not call our function.
766 if (CS->getCalledFunction() != F)
767 continue;
768 Solver.resetLatticeValueFor(CS);
769 }
770 }
771 }
772
773 // Rerun the solver to notify the users of the modified callsites.
775
776 for (Function *F : OriginalFuncs)
777 if (FunctionMetrics[F].isRecursive)
778 promoteConstantStackValues(F);
779
780 return true;
781}
782
783void FunctionSpecializer::removeDeadFunctions() {
784 for (Function *F : FullySpecialized) {
785 LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "
786 << F->getName() << "\n");
787 if (FAM)
788 FAM->clear(*F, F->getName());
789 F->eraseFromParent();
790 }
791 FullySpecialized.clear();
792}
793
794/// Clone the function \p F and remove the ssa_copy intrinsics added by
795/// the SCCPSolver in the cloned version.
796static Function *cloneCandidateFunction(Function *F, unsigned NSpecs) {
797 ValueToValueMapTy Mappings;
798 Function *Clone = CloneFunction(F, Mappings);
799 Clone->setName(F->getName() + ".specialized." + Twine(NSpecs));
800 removeSSACopy(*Clone);
801 return Clone;
802}
803
804bool FunctionSpecializer::findSpecializations(Function *F, unsigned FuncSize,
805 SmallVectorImpl<Spec> &AllSpecs,
806 SpecMap &SM) {
807 // A mapping from a specialisation signature to the index of the respective
808 // entry in the all specialisation array. Used to ensure uniqueness of
809 // specialisations.
810 DenseMap<SpecSig, unsigned> UniqueSpecs;
811
812 // Get a list of interesting arguments.
814 for (Argument &Arg : F->args())
815 if (isArgumentInteresting(&Arg))
816 Args.push_back(&Arg);
817
818 if (Args.empty())
819 return false;
820
821 for (User *U : F->users()) {
822 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
823 continue;
824 auto &CS = *cast<CallBase>(U);
825
826 // The user instruction does not call our function.
827 if (CS.getCalledFunction() != F)
828 continue;
829
830 // If the call site has attribute minsize set, that callsite won't be
831 // specialized.
832 if (CS.hasFnAttr(Attribute::MinSize))
833 continue;
834
835 // If the parent of the call site will never be executed, we don't need
836 // to worry about the passed value.
837 if (!Solver.isBlockExecutable(CS.getParent()))
838 continue;
839
840 // Examine arguments and create a specialisation candidate from the
841 // constant operands of this call site.
842 SpecSig S;
843 for (Argument *A : Args) {
844 Constant *C = getCandidateConstant(CS.getArgOperand(A->getArgNo()));
845 if (!C)
846 continue;
847 LLVM_DEBUG(dbgs() << "FnSpecialization: Found interesting argument "
848 << A->getName() << " : " << C->getNameOrAsOperand()
849 << "\n");
850 S.Args.push_back({A, C});
851 }
852
853 if (S.Args.empty())
854 continue;
855
856 // Check if we have encountered the same specialisation already.
857 if (auto It = UniqueSpecs.find(S); It != UniqueSpecs.end()) {
858 // Existing specialisation. Add the call to the list to rewrite, unless
859 // it's a recursive call. A specialisation, generated because of a
860 // recursive call may end up as not the best specialisation for all
861 // the cloned instances of this call, which result from specialising
862 // functions. Hence we don't rewrite the call directly, but match it with
863 // the best specialisation once all specialisations are known.
864 if (CS.getFunction() == F)
865 continue;
866 const unsigned Index = It->second;
867 AllSpecs[Index].CallSites.push_back(&CS);
868 } else {
869 // Calculate the specialisation gain.
870 Bonus B;
871 unsigned Score = 0;
873 for (ArgInfo &A : S.Args) {
874 B += Visitor.getSpecializationBonus(A.Formal, A.Actual);
875 Score += getInliningBonus(A.Formal, A.Actual);
876 }
877 B += Visitor.getBonusFromPendingPHIs();
878
879
880 LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization bonus {CodeSize = "
881 << B.CodeSize << ", Latency = " << B.Latency
882 << ", Inlining = " << Score << "}\n");
883
884 FunctionGrowth[F] += FuncSize - B.CodeSize;
885
886 auto IsProfitable = [](Bonus &B, unsigned Score, unsigned FuncSize,
887 unsigned FuncGrowth) -> bool {
888 // No check required.
890 return true;
891 // Minimum inlining bonus.
892 if (Score > MinInliningBonus * FuncSize / 100)
893 return true;
894 // Minimum codesize savings.
895 if (B.CodeSize < MinCodeSizeSavings * FuncSize / 100)
896 return false;
897 // Minimum latency savings.
898 if (B.Latency < MinLatencySavings * FuncSize / 100)
899 return false;
900 // Maximum codesize growth.
901 if (FuncGrowth / FuncSize > MaxCodeSizeGrowth)
902 return false;
903 return true;
904 };
905
906 // Discard unprofitable specialisations.
907 if (!IsProfitable(B, Score, FuncSize, FunctionGrowth[F]))
908 continue;
909
910 // Create a new specialisation entry.
911 Score += std::max(B.CodeSize, B.Latency);
912 auto &Spec = AllSpecs.emplace_back(F, S, Score);
913 if (CS.getFunction() != F)
914 Spec.CallSites.push_back(&CS);
915 const unsigned Index = AllSpecs.size() - 1;
916 UniqueSpecs[S] = Index;
917 if (auto [It, Inserted] = SM.try_emplace(F, Index, Index + 1); !Inserted)
918 It->second.second = Index + 1;
919 }
920 }
921
922 return !UniqueSpecs.empty();
923}
924
925bool FunctionSpecializer::isCandidateFunction(Function *F) {
926 if (F->isDeclaration() || F->arg_empty())
927 return false;
928
929 if (F->hasFnAttribute(Attribute::NoDuplicate))
930 return false;
931
932 // Do not specialize the cloned function again.
933 if (Specializations.contains(F))
934 return false;
935
936 // If we're optimizing the function for size, we shouldn't specialize it.
937 if (F->hasOptSize() ||
939 return false;
940
941 // Exit if the function is not executable. There's no point in specializing
942 // a dead function.
943 if (!Solver.isBlockExecutable(&F->getEntryBlock()))
944 return false;
945
946 // It wastes time to specialize a function which would get inlined finally.
947 if (F->hasFnAttribute(Attribute::AlwaysInline))
948 return false;
949
950 LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()
951 << "\n");
952 return true;
953}
954
955Function *FunctionSpecializer::createSpecialization(Function *F,
956 const SpecSig &S) {
957 Function *Clone = cloneCandidateFunction(F, Specializations.size() + 1);
958
959 // The original function does not neccessarily have internal linkage, but the
960 // clone must.
962
963 // Initialize the lattice state of the arguments of the function clone,
964 // marking the argument on which we specialized the function constant
965 // with the given value.
967 Solver.markBlockExecutable(&Clone->front());
968 Solver.addArgumentTrackedFunction(Clone);
969 Solver.addTrackedFunction(Clone);
970
971 // Mark all the specialized functions
972 Specializations.insert(Clone);
973 ++NumSpecsCreated;
974
975 return Clone;
976}
977
978/// Compute the inlining bonus for replacing argument \p A with constant \p C.
979/// The below heuristic is only concerned with exposing inlining
980/// opportunities via indirect call promotion. If the argument is not a
981/// (potentially casted) function pointer, give up.
982unsigned FunctionSpecializer::getInliningBonus(Argument *A, Constant *C) {
983 Function *CalledFunction = dyn_cast<Function>(C->stripPointerCasts());
984 if (!CalledFunction)
985 return 0;
986
987 // Get TTI for the called function (used for the inline cost).
988 auto &CalleeTTI = (GetTTI)(*CalledFunction);
989
990 // Look at all the call sites whose called value is the argument.
991 // Specializing the function on the argument would allow these indirect
992 // calls to be promoted to direct calls. If the indirect call promotion
993 // would likely enable the called function to be inlined, specializing is a
994 // good idea.
995 int InliningBonus = 0;
996 for (User *U : A->users()) {
997 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
998 continue;
999 auto *CS = cast<CallBase>(U);
1000 if (CS->getCalledOperand() != A)
1001 continue;
1002 if (CS->getFunctionType() != CalledFunction->getFunctionType())
1003 continue;
1004
1005 // Get the cost of inlining the called function at this call site. Note
1006 // that this is only an estimate. The called function may eventually
1007 // change in a way that leads to it not being inlined here, even though
1008 // inlining looks profitable now. For example, one of its called
1009 // functions may be inlined into it, making the called function too large
1010 // to be inlined into this call site.
1011 //
1012 // We apply a boost for performing indirect call promotion by increasing
1013 // the default threshold by the threshold for indirect calls.
1014 auto Params = getInlineParams();
1015 Params.DefaultThreshold += InlineConstants::IndirectCallThreshold;
1016 InlineCost IC =
1017 getInlineCost(*CS, CalledFunction, Params, CalleeTTI, GetAC, GetTLI);
1018
1019 // We clamp the bonus for this call to be between zero and the default
1020 // threshold.
1021 if (IC.isAlways())
1022 InliningBonus += Params.DefaultThreshold;
1023 else if (IC.isVariable() && IC.getCostDelta() > 0)
1024 InliningBonus += IC.getCostDelta();
1025
1026 LLVM_DEBUG(dbgs() << "FnSpecialization: Inlining bonus " << InliningBonus
1027 << " for user " << *U << "\n");
1028 }
1029
1030 return InliningBonus > 0 ? static_cast<unsigned>(InliningBonus) : 0;
1031}
1032
1033/// Determine if it is possible to specialise the function for constant values
1034/// of the formal parameter \p A.
1035bool FunctionSpecializer::isArgumentInteresting(Argument *A) {
1036 // No point in specialization if the argument is unused.
1037 if (A->user_empty())
1038 return false;
1039
1040 Type *Ty = A->getType();
1041 if (!Ty->isPointerTy() && (!SpecializeLiteralConstant ||
1042 (!Ty->isIntegerTy() && !Ty->isFloatingPointTy() && !Ty->isStructTy())))
1043 return false;
1044
1045 // SCCP solver does not record an argument that will be constructed on
1046 // stack.
1047 if (A->hasByValAttr() && !A->getParent()->onlyReadsMemory())
1048 return false;
1049
1050 // For non-argument-tracked functions every argument is overdefined.
1051 if (!Solver.isArgumentTrackedFunction(A->getParent()))
1052 return true;
1053
1054 // Check the lattice value and decide if we should attemt to specialize,
1055 // based on this argument. No point in specialization, if the lattice value
1056 // is already a constant.
1057 bool IsOverdefined = Ty->isStructTy()
1059 : SCCPSolver::isOverdefined(Solver.getLatticeValueFor(A));
1060
1061 LLVM_DEBUG(
1062 if (IsOverdefined)
1063 dbgs() << "FnSpecialization: Found interesting parameter "
1064 << A->getNameOrAsOperand() << "\n";
1065 else
1066 dbgs() << "FnSpecialization: Nothing to do, parameter "
1067 << A->getNameOrAsOperand() << " is already constant\n";
1068 );
1069 return IsOverdefined;
1070}
1071
1072/// Check if the value \p V (an actual argument) is a constant or can only
1073/// have a constant value. Return that constant.
1074Constant *FunctionSpecializer::getCandidateConstant(Value *V) {
1075 if (isa<PoisonValue>(V))
1076 return nullptr;
1077
1078 // Select for possible specialisation values that are constants or
1079 // are deduced to be constants or constant ranges with a single element.
1080 Constant *C = dyn_cast<Constant>(V);
1081 if (!C)
1082 C = Solver.getConstantOrNull(V);
1083
1084 // Don't specialize on (anything derived from) the address of a non-constant
1085 // global variable, unless explicitly enabled.
1086 if (C && C->getType()->isPointerTy() && !C->isNullValue())
1087 if (auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(C));
1088 GV && !(GV->isConstant() || SpecializeOnAddress))
1089 return nullptr;
1090
1091 return C;
1092}
1093
1094void FunctionSpecializer::updateCallSites(Function *F, const Spec *Begin,
1095 const Spec *End) {
1096 // Collect the call sites that need updating.
1097 SmallVector<CallBase *> ToUpdate;
1098 for (User *U : F->users())
1099 if (auto *CS = dyn_cast<CallBase>(U);
1100 CS && CS->getCalledFunction() == F &&
1101 Solver.isBlockExecutable(CS->getParent()))
1102 ToUpdate.push_back(CS);
1103
1104 unsigned NCallsLeft = ToUpdate.size();
1105 for (CallBase *CS : ToUpdate) {
1106 bool ShouldDecrementCount = CS->getFunction() == F;
1107
1108 // Find the best matching specialisation.
1109 const Spec *BestSpec = nullptr;
1110 for (const Spec &S : make_range(Begin, End)) {
1111 if (!S.Clone || (BestSpec && S.Score <= BestSpec->Score))
1112 continue;
1113
1114 if (any_of(S.Sig.Args, [CS, this](const ArgInfo &Arg) {
1115 unsigned ArgNo = Arg.Formal->getArgNo();
1116 return getCandidateConstant(CS->getArgOperand(ArgNo)) != Arg.Actual;
1117 }))
1118 continue;
1119
1120 BestSpec = &S;
1121 }
1122
1123 if (BestSpec) {
1124 LLVM_DEBUG(dbgs() << "FnSpecialization: Redirecting " << *CS
1125 << " to call " << BestSpec->Clone->getName() << "\n");
1126 CS->setCalledFunction(BestSpec->Clone);
1127 ShouldDecrementCount = true;
1128 }
1129
1130 if (ShouldDecrementCount)
1131 --NCallsLeft;
1132 }
1133
1134 // If the function has been completely specialized, the original function
1135 // is no longer needed. Mark it unreachable.
1136 if (NCallsLeft == 0 && Solver.isArgumentTrackedFunction(F)) {
1137 Solver.markFunctionUnreachable(F);
1138 FullySpecialized.insert(F);
1139 }
1140}
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:480
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 > MinLatencySavings("funcspec-min-latency-savings", cl::init(40), cl::Hidden, cl::desc("Reject specializations whose latency savings are less than this" "much percent of the original function size"))
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"))
static Constant * findConstantFor(Value *V, ConstMap &KnownConstants)
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"))
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 cl::opt< unsigned > MaxCodeSizeGrowth("funcspec-max-codesize-growth", cl::init(3), cl::Hidden, cl::desc("Maximum codesize growth allowed per function"))
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"))
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"))
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< 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"))
static cl::opt< unsigned > MinFunctionSize("funcspec-min-function-size", cl::init(300), cl::Hidden, cl::desc("Don't specialize functions that have less than this number of " "instructions"))
static cl::opt< bool > SpecializeOnAddress("funcspec-on-address", cl::init(false), cl::Hidden, cl::desc("Enable function specialization on the address of global values"))
static cl::opt< bool > SpecializeLiteralConstant("funcspec-for-literal-constant", cl::init(false), cl::Hidden, cl::desc("Enable specialization of functions that take a literal constant as an " "argument"))
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
mir Rename Register Operands
Machine Trace Metrics
uint64_t IntrinsicInst * II
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:166
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
an instruction to allocate memory on the stack
Definition: Instructions.h:61
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
Definition: Instructions.h:115
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
This class represents an incoming formal argument to a Function.
Definition: Argument.h:31
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
BlockFrequency getEntryFreq() const
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Conditional or Unconditional Branch instruction.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1236
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:530
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:747
This is an important base class in LLVM.
Definition: Constant.h:42
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:194
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:226
bool empty() const
Definition: DenseMap.h:98
iterator end()
Definition: DenseMap.h:84
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:146
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
This class represents a freeze function that returns random concrete value if an operand is either a ...
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:214
const BasicBlock & front() const
Definition: Function.h:858
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:915
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:537
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:59
Represents the cost of inlining a function.
Definition: InlineCost.h:90
bool isAlways() const
Definition: InlineCost.h:139
int getCostDelta() const
Get the cost delta from the threshold for inlining.
Definition: InlineCost.h:175
bool isVariable() const
Definition: InlineCost.h:141
bool isBlockExecutable(BasicBlock *BB)
Bonus getSpecializationBonus(Argument *A, Constant *C)
Compute a bonus for replacing argument A with constant C.
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:87
An instruction for reading from memory.
Definition: Instructions.h:174
StringRef getName() const
Get a short "name" for the module.
Definition: Module.h:282
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.
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:65
void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
bool isStructLatticeConstant(Function *F, StructType *STy)
void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
void solveWhileResolvedUndefsIn(Module &M)
void addArgumentTrackedFunction(Function *F)
void solveWhileResolvedUndefs()
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
Constant * getConstantOrNull(Value *V) const
Return either a Constant or nullptr for a given Value.
bool isBlockExecutable(BasicBlock *BB) const
bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Set the Lattice Value for the arguments of a specialization F.
static bool isOverdefined(const ValueLatticeElement &LV)
Definition: SCCPSolver.cpp:52
void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
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:502
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Multiway switch.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
@ TCK_CodeSize
Instruction code size.
@ TCK_Latency
The latency of instruction.
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:251
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:245
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:224
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:377
std::string getNameOrAsOperand() const
Definition: Value.cpp:445
iterator_range< user_iterator > users()
Definition: Value.h:421
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:694
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
const int IndirectCallThreshold
Definition: InlineCost.h:48
Predicate getPredicate(unsigned Condition, unsigned Hint)
Return predicate consisting of specified condition and hint bits.
Definition: PPCPredicates.h:87
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1722
hash_code hash_value(const FixedPointSemantics &Val)
Definition: APFixedPoint.h:127
bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
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.
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:656
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...
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)
Get an InlineCost object representing the cost of inlining this callsite.
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:1729
Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Constant * ConstantFoldInstOperands(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.
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
@ Other
Any other memory.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
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.
InlineParams getInlineParams()
Generate the parameters to tune the inline cost analysis based only on the commandline options.
auto predecessors(const MachineBasicBlock *BB)
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...
Function * CloneFunction(Function *F, ValueToValueMapTy &VMap, ClonedCodeInfo *CodeInfo=nullptr)
Return a copy of the specified function and add it to that function's module.
#define N
Helper struct shared between Function Specialization and SCCP Solver.
Definition: SCCPSolver.h:41
Argument * Formal
Definition: SCCPSolver.h:42
Constant * Actual
Definition: SCCPSolver.h:43
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition: CodeMetrics.h:33
static 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:52
SmallVector< ArgInfo, 4 > Args
SmallVector< CallBase * > CallSites