1 //===-- LibCallsShrinkWrap.cpp ----------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This pass shrink-wraps a call to function if the result is not used.
10 // The call can set errno but is otherwise side effect free. For example:
15 // Even if the result of library call is not being used, the compiler cannot
16 // safely delete the call because the function can set errno on error
18 // Note in many functions, the error condition solely depends on the incoming
19 // parameter. In this optimization, we can generate the condition can lead to
20 // the errno to shrink-wrap the call. Since the chances of hitting the error
21 // condition is low, the runtime call is effectively eliminated.
23 // These partially dead calls are usually results of C++ abstraction penalty
24 // exposed by inlining.
26 //===----------------------------------------------------------------------===//
28 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Analysis/GlobalsModRef.h"
32 #include "llvm/Analysis/TargetLibraryInfo.h"
33 #include "llvm/IR/CFG.h"
34 #include "llvm/IR/Constants.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/IRBuilder.h"
38 #include "llvm/IR/InstVisitor.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/LLVMContext.h"
41 #include "llvm/IR/MDBuilder.h"
42 #include "llvm/InitializePasses.h"
43 #include "llvm/Pass.h"
44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
47 #define DEBUG_TYPE "libcalls-shrinkwrap"
49 STATISTIC(NumWrappedOneCond, "Number of One-Condition Wrappers Inserted");
50 STATISTIC(NumWrappedTwoCond, "Number of Two-Condition Wrappers Inserted");
53 class LibCallsShrinkWrapLegacyPass : public FunctionPass {
55 static char ID; // Pass identification, replacement for typeid
56 explicit LibCallsShrinkWrapLegacyPass() : FunctionPass(ID) {
57 initializeLibCallsShrinkWrapLegacyPassPass(
58 *PassRegistry::getPassRegistry());
60 void getAnalysisUsage(AnalysisUsage &AU) const override;
61 bool runOnFunction(Function &F) override;
65 char LibCallsShrinkWrapLegacyPass::ID = 0;
66 INITIALIZE_PASS_BEGIN(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap",
67 "Conditionally eliminate dead library calls", false,
69 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
70 INITIALIZE_PASS_END(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap",
71 "Conditionally eliminate dead library calls", false, false)
74 class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> {
76 LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DominatorTree *DT)
78 void visitCallInst(CallInst &CI) { checkCandidate(CI); }
81 for (auto &CI : WorkList) {
82 LLVM_DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName()
86 LLVM_DEBUG(dbgs() << "Transformed\n");
93 bool perform(CallInst *CI);
94 void checkCandidate(CallInst &CI);
95 void shrinkWrapCI(CallInst *CI, Value *Cond);
96 bool performCallDomainErrorOnly(CallInst *CI, const LibFunc &Func);
97 bool performCallErrors(CallInst *CI, const LibFunc &Func);
98 bool performCallRangeErrorOnly(CallInst *CI, const LibFunc &Func);
99 Value *generateOneRangeCond(CallInst *CI, const LibFunc &Func);
100 Value *generateTwoRangeCond(CallInst *CI, const LibFunc &Func);
101 Value *generateCondForPow(CallInst *CI, const LibFunc &Func);
103 // Create an OR of two conditions.
104 Value *createOrCond(CallInst *CI, CmpInst::Predicate Cmp, float Val,
105 CmpInst::Predicate Cmp2, float Val2) {
106 IRBuilder<> BBBuilder(CI);
107 Value *Arg = CI->getArgOperand(0);
108 auto Cond2 = createCond(BBBuilder, Arg, Cmp2, Val2);
109 auto Cond1 = createCond(BBBuilder, Arg, Cmp, Val);
110 return BBBuilder.CreateOr(Cond1, Cond2);
113 // Create a single condition using IRBuilder.
114 Value *createCond(IRBuilder<> &BBBuilder, Value *Arg, CmpInst::Predicate Cmp,
116 Constant *V = ConstantFP::get(BBBuilder.getContext(), APFloat(Val));
117 if (!Arg->getType()->isFloatTy())
118 V = ConstantExpr::getFPExtend(V, Arg->getType());
119 return BBBuilder.CreateFCmp(Cmp, Arg, V);
122 // Create a single condition.
123 Value *createCond(CallInst *CI, CmpInst::Predicate Cmp, float Val) {
124 IRBuilder<> BBBuilder(CI);
125 Value *Arg = CI->getArgOperand(0);
126 return createCond(BBBuilder, Arg, Cmp, Val);
129 const TargetLibraryInfo &TLI;
131 SmallVector<CallInst *, 16> WorkList;
133 } // end anonymous namespace
135 // Perform the transformation to calls with errno set by domain error.
136 bool LibCallsShrinkWrap::performCallDomainErrorOnly(CallInst *CI,
137 const LibFunc &Func) {
138 Value *Cond = nullptr;
141 case LibFunc_acos: // DomainError: (x < -1 || x > 1)
142 case LibFunc_acosf: // Same as acos
143 case LibFunc_acosl: // Same as acos
144 case LibFunc_asin: // DomainError: (x < -1 || x > 1)
145 case LibFunc_asinf: // Same as asin
146 case LibFunc_asinl: // Same as asin
149 Cond = createOrCond(CI, CmpInst::FCMP_OLT, -1.0f, CmpInst::FCMP_OGT, 1.0f);
152 case LibFunc_cos: // DomainError: (x == +inf || x == -inf)
153 case LibFunc_cosf: // Same as cos
154 case LibFunc_cosl: // Same as cos
155 case LibFunc_sin: // DomainError: (x == +inf || x == -inf)
156 case LibFunc_sinf: // Same as sin
157 case LibFunc_sinl: // Same as sin
160 Cond = createOrCond(CI, CmpInst::FCMP_OEQ, INFINITY, CmpInst::FCMP_OEQ,
164 case LibFunc_acosh: // DomainError: (x < 1)
165 case LibFunc_acoshf: // Same as acosh
166 case LibFunc_acoshl: // Same as acosh
169 Cond = createCond(CI, CmpInst::FCMP_OLT, 1.0f);
172 case LibFunc_sqrt: // DomainError: (x < 0)
173 case LibFunc_sqrtf: // Same as sqrt
174 case LibFunc_sqrtl: // Same as sqrt
177 Cond = createCond(CI, CmpInst::FCMP_OLT, 0.0f);
183 shrinkWrapCI(CI, Cond);
187 // Perform the transformation to calls with errno set by range error.
188 bool LibCallsShrinkWrap::performCallRangeErrorOnly(CallInst *CI,
189 const LibFunc &Func) {
190 Value *Cond = nullptr;
207 case LibFunc_sinhl: {
208 Cond = generateTwoRangeCond(CI, Func);
211 case LibFunc_expm1: // RangeError: (709, inf)
212 case LibFunc_expm1f: // RangeError: (88, inf)
213 case LibFunc_expm1l: // RangeError: (11356, inf)
215 Cond = generateOneRangeCond(CI, Func);
221 shrinkWrapCI(CI, Cond);
225 // Perform the transformation to calls with errno set by combination of errors.
226 bool LibCallsShrinkWrap::performCallErrors(CallInst *CI,
227 const LibFunc &Func) {
228 Value *Cond = nullptr;
231 case LibFunc_atanh: // DomainError: (x < -1 || x > 1)
232 // PoleError: (x == -1 || x == 1)
233 // Overall Cond: (x <= -1 || x >= 1)
234 case LibFunc_atanhf: // Same as atanh
235 case LibFunc_atanhl: // Same as atanh
238 Cond = createOrCond(CI, CmpInst::FCMP_OLE, -1.0f, CmpInst::FCMP_OGE, 1.0f);
241 case LibFunc_log: // DomainError: (x < 0)
242 // PoleError: (x == 0)
243 // Overall Cond: (x <= 0)
244 case LibFunc_logf: // Same as log
245 case LibFunc_logl: // Same as log
246 case LibFunc_log10: // Same as log
247 case LibFunc_log10f: // Same as log
248 case LibFunc_log10l: // Same as log
249 case LibFunc_log2: // Same as log
250 case LibFunc_log2f: // Same as log
251 case LibFunc_log2l: // Same as log
252 case LibFunc_logb: // Same as log
253 case LibFunc_logbf: // Same as log
254 case LibFunc_logbl: // Same as log
257 Cond = createCond(CI, CmpInst::FCMP_OLE, 0.0f);
260 case LibFunc_log1p: // DomainError: (x < -1)
261 // PoleError: (x == -1)
262 // Overall Cond: (x <= -1)
263 case LibFunc_log1pf: // Same as log1p
264 case LibFunc_log1pl: // Same as log1p
267 Cond = createCond(CI, CmpInst::FCMP_OLE, -1.0f);
270 case LibFunc_pow: // DomainError: x < 0 and y is noninteger
271 // PoleError: x == 0 and y < 0
272 // RangeError: overflow or underflow
275 Cond = generateCondForPow(CI, Func);
283 assert(Cond && "performCallErrors should not see an empty condition");
284 shrinkWrapCI(CI, Cond);
288 // Checks if CI is a candidate for shrinkwrapping and put it into work list if
290 void LibCallsShrinkWrap::checkCandidate(CallInst &CI) {
291 if (CI.isNoBuiltin())
293 // A possible improvement is to handle the calls with the return value being
294 // used. If there is API for fast libcall implementation without setting
295 // errno, we can use the same framework to direct/wrap the call to the fast
296 // API in the error free path, and leave the original call in the slow path.
301 Function *Callee = CI.getCalledFunction();
304 if (!TLI.getLibFunc(*Callee, Func) || !TLI.has(Func))
307 if (CI.getNumArgOperands() == 0)
309 // TODO: Handle long double in other formats.
310 Type *ArgType = CI.getArgOperand(0)->getType();
311 if (!(ArgType->isFloatTy() || ArgType->isDoubleTy() ||
312 ArgType->isX86_FP80Ty()))
315 WorkList.push_back(&CI);
318 // Generate the upper bound condition for RangeError.
319 Value *LibCallsShrinkWrap::generateOneRangeCond(CallInst *CI,
320 const LibFunc &Func) {
323 case LibFunc_expm1: // RangeError: (709, inf)
326 case LibFunc_expm1f: // RangeError: (88, inf)
329 case LibFunc_expm1l: // RangeError: (11356, inf)
330 UpperBound = 11356.0f;
333 llvm_unreachable("Unhandled library call!");
337 return createCond(CI, CmpInst::FCMP_OGT, UpperBound);
340 // Generate the lower and upper bound condition for RangeError.
341 Value *LibCallsShrinkWrap::generateTwoRangeCond(CallInst *CI,
342 const LibFunc &Func) {
343 float UpperBound, LowerBound;
345 case LibFunc_cosh: // RangeError: (x < -710 || x > 710)
346 case LibFunc_sinh: // Same as cosh
347 LowerBound = -710.0f;
350 case LibFunc_coshf: // RangeError: (x < -89 || x > 89)
351 case LibFunc_sinhf: // Same as coshf
355 case LibFunc_coshl: // RangeError: (x < -11357 || x > 11357)
356 case LibFunc_sinhl: // Same as coshl
357 LowerBound = -11357.0f;
358 UpperBound = 11357.0f;
360 case LibFunc_exp: // RangeError: (x < -745 || x > 709)
361 LowerBound = -745.0f;
364 case LibFunc_expf: // RangeError: (x < -103 || x > 88)
365 LowerBound = -103.0f;
368 case LibFunc_expl: // RangeError: (x < -11399 || x > 11356)
369 LowerBound = -11399.0f;
370 UpperBound = 11356.0f;
372 case LibFunc_exp10: // RangeError: (x < -323 || x > 308)
373 LowerBound = -323.0f;
376 case LibFunc_exp10f: // RangeError: (x < -45 || x > 38)
380 case LibFunc_exp10l: // RangeError: (x < -4950 || x > 4932)
381 LowerBound = -4950.0f;
382 UpperBound = 4932.0f;
384 case LibFunc_exp2: // RangeError: (x < -1074 || x > 1023)
385 LowerBound = -1074.0f;
386 UpperBound = 1023.0f;
388 case LibFunc_exp2f: // RangeError: (x < -149 || x > 127)
389 LowerBound = -149.0f;
392 case LibFunc_exp2l: // RangeError: (x < -16445 || x > 11383)
393 LowerBound = -16445.0f;
394 UpperBound = 11383.0f;
397 llvm_unreachable("Unhandled library call!");
401 return createOrCond(CI, CmpInst::FCMP_OGT, UpperBound, CmpInst::FCMP_OLT,
405 // For pow(x,y), We only handle the following cases:
406 // (1) x is a constant && (x >= 1) && (x < MaxUInt8)
407 // Cond is: (y > 127)
408 // (2) x is a value coming from an integer type.
409 // (2.1) if x's bit_size == 8
410 // Cond: (x <= 0 || y > 128)
411 // (2.2) if x's bit_size is 16
412 // Cond: (x <= 0 || y > 64)
413 // (2.3) if x's bit_size is 32
414 // Cond: (x <= 0 || y > 32)
415 // Support for powl(x,y) and powf(x,y) are TBD.
417 // Note that condition can be more conservative than the actual condition
418 // (i.e. we might invoke the calls that will not set the errno.).
420 Value *LibCallsShrinkWrap::generateCondForPow(CallInst *CI,
421 const LibFunc &Func) {
422 // FIXME: LibFunc_powf and powl TBD.
423 if (Func != LibFunc_pow) {
424 LLVM_DEBUG(dbgs() << "Not handled powf() and powl()\n");
428 Value *Base = CI->getArgOperand(0);
429 Value *Exp = CI->getArgOperand(1);
430 IRBuilder<> BBBuilder(CI);
432 // Constant Base case.
433 if (ConstantFP *CF = dyn_cast<ConstantFP>(Base)) {
434 double D = CF->getValueAPF().convertToDouble();
435 if (D < 1.0f || D > APInt::getMaxValue(8).getZExtValue()) {
436 LLVM_DEBUG(dbgs() << "Not handled pow(): constant base out of range\n");
441 Constant *V = ConstantFP::get(CI->getContext(), APFloat(127.0f));
442 if (!Exp->getType()->isFloatTy())
443 V = ConstantExpr::getFPExtend(V, Exp->getType());
444 return BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V);
447 // If the Base value coming from an integer type.
448 Instruction *I = dyn_cast<Instruction>(Base);
450 LLVM_DEBUG(dbgs() << "Not handled pow(): FP type base\n");
453 unsigned Opcode = I->getOpcode();
454 if (Opcode == Instruction::UIToFP || Opcode == Instruction::SIToFP) {
455 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
464 LLVM_DEBUG(dbgs() << "Not handled pow(): type too wide\n");
469 Constant *V = ConstantFP::get(CI->getContext(), APFloat(UpperV));
470 Constant *V0 = ConstantFP::get(CI->getContext(), APFloat(0.0f));
471 if (!Exp->getType()->isFloatTy())
472 V = ConstantExpr::getFPExtend(V, Exp->getType());
473 if (!Base->getType()->isFloatTy())
474 V0 = ConstantExpr::getFPExtend(V0, Exp->getType());
476 Value *Cond = BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V);
477 Value *Cond0 = BBBuilder.CreateFCmp(CmpInst::FCMP_OLE, Base, V0);
478 return BBBuilder.CreateOr(Cond0, Cond);
480 LLVM_DEBUG(dbgs() << "Not handled pow(): base not from integer convert\n");
484 // Wrap conditions that can potentially generate errno to the library call.
485 void LibCallsShrinkWrap::shrinkWrapCI(CallInst *CI, Value *Cond) {
486 assert(Cond != nullptr && "ShrinkWrapCI is not expecting an empty call inst");
487 MDNode *BranchWeights =
488 MDBuilder(CI->getContext()).createBranchWeights(1, 2000);
490 Instruction *NewInst =
491 SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights, DT);
492 BasicBlock *CallBB = NewInst->getParent();
493 CallBB->setName("cdce.call");
494 BasicBlock *SuccBB = CallBB->getSingleSuccessor();
495 assert(SuccBB && "The split block should have a single successor");
496 SuccBB->setName("cdce.end");
497 CI->removeFromParent();
498 CallBB->getInstList().insert(CallBB->getFirstInsertionPt(), CI);
499 LLVM_DEBUG(dbgs() << "== Basic Block After ==");
500 LLVM_DEBUG(dbgs() << *CallBB->getSinglePredecessor() << *CallBB
501 << *CallBB->getSingleSuccessor() << "\n");
504 // Perform the transformation to a single candidate.
505 bool LibCallsShrinkWrap::perform(CallInst *CI) {
507 Function *Callee = CI->getCalledFunction();
508 assert(Callee && "perform() should apply to a non-empty callee");
509 TLI.getLibFunc(*Callee, Func);
510 assert(Func && "perform() is not expecting an empty function");
512 if (performCallDomainErrorOnly(CI, Func) || performCallRangeErrorOnly(CI, Func))
514 return performCallErrors(CI, Func);
517 void LibCallsShrinkWrapLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
518 AU.addPreserved<DominatorTreeWrapperPass>();
519 AU.addPreserved<GlobalsAAWrapperPass>();
520 AU.addRequired<TargetLibraryInfoWrapperPass>();
523 static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
525 if (F.hasFnAttribute(Attribute::OptimizeForSize))
527 LibCallsShrinkWrap CCDCE(TLI, DT);
529 bool Changed = CCDCE.perform();
531 // Verify the dominator after we've updated it locally.
532 assert(!DT || DT->verify(DominatorTree::VerificationLevel::Fast));
536 bool LibCallsShrinkWrapLegacyPass::runOnFunction(Function &F) {
537 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
538 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
539 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
540 return runImpl(F, TLI, DT);
544 char &LibCallsShrinkWrapPassID = LibCallsShrinkWrapLegacyPass::ID;
546 // Public interface to LibCallsShrinkWrap pass.
547 FunctionPass *createLibCallsShrinkWrapPass() {
548 return new LibCallsShrinkWrapLegacyPass();
551 PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F,
552 FunctionAnalysisManager &FAM) {
553 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
554 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
555 if (!runImpl(F, TLI, DT))
556 return PreservedAnalyses::all();
557 auto PA = PreservedAnalyses();
558 PA.preserve<GlobalsAA>();
559 PA.preserve<DominatorTreeAnalysis>();