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