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/Pass.h"
43 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
46 #define DEBUG_TYPE "libcalls-shrinkwrap"
48 STATISTIC(NumWrappedOneCond, "Number of One-Condition Wrappers Inserted");
49 STATISTIC(NumWrappedTwoCond, "Number of Two-Condition Wrappers Inserted");
52 class LibCallsShrinkWrapLegacyPass : public FunctionPass {
54 static char ID; // Pass identification, replacement for typeid
55 explicit LibCallsShrinkWrapLegacyPass() : FunctionPass(ID) {
56 initializeLibCallsShrinkWrapLegacyPassPass(
57 *PassRegistry::getPassRegistry());
59 void getAnalysisUsage(AnalysisUsage &AU) const override;
60 bool runOnFunction(Function &F) override;
64 char LibCallsShrinkWrapLegacyPass::ID = 0;
65 INITIALIZE_PASS_BEGIN(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap",
66 "Conditionally eliminate dead library calls", false,
68 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
69 INITIALIZE_PASS_END(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap",
70 "Conditionally eliminate dead library calls", false, false)
73 class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> {
75 LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DominatorTree *DT)
77 void visitCallInst(CallInst &CI) { checkCandidate(CI); }
80 for (auto &CI : WorkList) {
81 LLVM_DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName()
85 LLVM_DEBUG(dbgs() << "Transformed\n");
92 bool perform(CallInst *CI);
93 void checkCandidate(CallInst &CI);
94 void shrinkWrapCI(CallInst *CI, Value *Cond);
95 bool performCallDomainErrorOnly(CallInst *CI, const LibFunc &Func);
96 bool performCallErrors(CallInst *CI, const LibFunc &Func);
97 bool performCallRangeErrorOnly(CallInst *CI, const LibFunc &Func);
98 Value *generateOneRangeCond(CallInst *CI, const LibFunc &Func);
99 Value *generateTwoRangeCond(CallInst *CI, const LibFunc &Func);
100 Value *generateCondForPow(CallInst *CI, const LibFunc &Func);
102 // Create an OR of two conditions.
103 Value *createOrCond(CallInst *CI, CmpInst::Predicate Cmp, float Val,
104 CmpInst::Predicate Cmp2, float Val2) {
105 IRBuilder<> BBBuilder(CI);
106 Value *Arg = CI->getArgOperand(0);
107 auto Cond2 = createCond(BBBuilder, Arg, Cmp2, Val2);
108 auto Cond1 = createCond(BBBuilder, Arg, Cmp, Val);
109 return BBBuilder.CreateOr(Cond1, Cond2);
112 // Create a single condition using IRBuilder.
113 Value *createCond(IRBuilder<> &BBBuilder, Value *Arg, CmpInst::Predicate Cmp,
115 Constant *V = ConstantFP::get(BBBuilder.getContext(), APFloat(Val));
116 if (!Arg->getType()->isFloatTy())
117 V = ConstantExpr::getFPExtend(V, Arg->getType());
118 return BBBuilder.CreateFCmp(Cmp, Arg, V);
121 // Create a single condition.
122 Value *createCond(CallInst *CI, CmpInst::Predicate Cmp, float Val) {
123 IRBuilder<> BBBuilder(CI);
124 Value *Arg = CI->getArgOperand(0);
125 return createCond(BBBuilder, Arg, Cmp, Val);
128 const TargetLibraryInfo &TLI;
130 SmallVector<CallInst *, 16> WorkList;
132 } // end anonymous namespace
134 // Perform the transformation to calls with errno set by domain error.
135 bool LibCallsShrinkWrap::performCallDomainErrorOnly(CallInst *CI,
136 const LibFunc &Func) {
137 Value *Cond = nullptr;
140 case LibFunc_acos: // DomainError: (x < -1 || x > 1)
141 case LibFunc_acosf: // Same as acos
142 case LibFunc_acosl: // Same as acos
143 case LibFunc_asin: // DomainError: (x < -1 || x > 1)
144 case LibFunc_asinf: // Same as asin
145 case LibFunc_asinl: // Same as asin
148 Cond = createOrCond(CI, CmpInst::FCMP_OLT, -1.0f, CmpInst::FCMP_OGT, 1.0f);
151 case LibFunc_cos: // DomainError: (x == +inf || x == -inf)
152 case LibFunc_cosf: // Same as cos
153 case LibFunc_cosl: // Same as cos
154 case LibFunc_sin: // DomainError: (x == +inf || x == -inf)
155 case LibFunc_sinf: // Same as sin
156 case LibFunc_sinl: // Same as sin
159 Cond = createOrCond(CI, CmpInst::FCMP_OEQ, INFINITY, CmpInst::FCMP_OEQ,
163 case LibFunc_acosh: // DomainError: (x < 1)
164 case LibFunc_acoshf: // Same as acosh
165 case LibFunc_acoshl: // Same as acosh
168 Cond = createCond(CI, CmpInst::FCMP_OLT, 1.0f);
171 case LibFunc_sqrt: // DomainError: (x < 0)
172 case LibFunc_sqrtf: // Same as sqrt
173 case LibFunc_sqrtl: // Same as sqrt
176 Cond = createCond(CI, CmpInst::FCMP_OLT, 0.0f);
182 shrinkWrapCI(CI, Cond);
186 // Perform the transformation to calls with errno set by range error.
187 bool LibCallsShrinkWrap::performCallRangeErrorOnly(CallInst *CI,
188 const LibFunc &Func) {
189 Value *Cond = nullptr;
206 case LibFunc_sinhl: {
207 Cond = generateTwoRangeCond(CI, Func);
210 case LibFunc_expm1: // RangeError: (709, inf)
211 case LibFunc_expm1f: // RangeError: (88, inf)
212 case LibFunc_expm1l: // RangeError: (11356, inf)
214 Cond = generateOneRangeCond(CI, Func);
220 shrinkWrapCI(CI, Cond);
224 // Perform the transformation to calls with errno set by combination of errors.
225 bool LibCallsShrinkWrap::performCallErrors(CallInst *CI,
226 const LibFunc &Func) {
227 Value *Cond = nullptr;
230 case LibFunc_atanh: // DomainError: (x < -1 || x > 1)
231 // PoleError: (x == -1 || x == 1)
232 // Overall Cond: (x <= -1 || x >= 1)
233 case LibFunc_atanhf: // Same as atanh
234 case LibFunc_atanhl: // Same as atanh
237 Cond = createOrCond(CI, CmpInst::FCMP_OLE, -1.0f, CmpInst::FCMP_OGE, 1.0f);
240 case LibFunc_log: // DomainError: (x < 0)
241 // PoleError: (x == 0)
242 // Overall Cond: (x <= 0)
243 case LibFunc_logf: // Same as log
244 case LibFunc_logl: // Same as log
245 case LibFunc_log10: // Same as log
246 case LibFunc_log10f: // Same as log
247 case LibFunc_log10l: // Same as log
248 case LibFunc_log2: // Same as log
249 case LibFunc_log2f: // Same as log
250 case LibFunc_log2l: // Same as log
251 case LibFunc_logb: // Same as log
252 case LibFunc_logbf: // Same as log
253 case LibFunc_logbl: // Same as log
256 Cond = createCond(CI, CmpInst::FCMP_OLE, 0.0f);
259 case LibFunc_log1p: // DomainError: (x < -1)
260 // PoleError: (x == -1)
261 // Overall Cond: (x <= -1)
262 case LibFunc_log1pf: // Same as log1p
263 case LibFunc_log1pl: // Same as log1p
266 Cond = createCond(CI, CmpInst::FCMP_OLE, -1.0f);
269 case LibFunc_pow: // DomainError: x < 0 and y is noninteger
270 // PoleError: x == 0 and y < 0
271 // RangeError: overflow or underflow
274 Cond = generateCondForPow(CI, Func);
282 assert(Cond && "performCallErrors should not see an empty condition");
283 shrinkWrapCI(CI, Cond);
287 // Checks if CI is a candidate for shrinkwrapping and put it into work list if
289 void LibCallsShrinkWrap::checkCandidate(CallInst &CI) {
290 if (CI.isNoBuiltin())
292 // A possible improvement is to handle the calls with the return value being
293 // used. If there is API for fast libcall implementation without setting
294 // errno, we can use the same framework to direct/wrap the call to the fast
295 // API in the error free path, and leave the original call in the slow path.
300 Function *Callee = CI.getCalledFunction();
303 if (!TLI.getLibFunc(*Callee, Func) || !TLI.has(Func))
306 if (CI.getNumArgOperands() == 0)
308 // TODO: Handle long double in other formats.
309 Type *ArgType = CI.getArgOperand(0)->getType();
310 if (!(ArgType->isFloatTy() || ArgType->isDoubleTy() ||
311 ArgType->isX86_FP80Ty()))
314 WorkList.push_back(&CI);
317 // Generate the upper bound condition for RangeError.
318 Value *LibCallsShrinkWrap::generateOneRangeCond(CallInst *CI,
319 const LibFunc &Func) {
322 case LibFunc_expm1: // RangeError: (709, inf)
325 case LibFunc_expm1f: // RangeError: (88, inf)
328 case LibFunc_expm1l: // RangeError: (11356, inf)
329 UpperBound = 11356.0f;
332 llvm_unreachable("Unhandled library call!");
336 return createCond(CI, CmpInst::FCMP_OGT, UpperBound);
339 // Generate the lower and upper bound condition for RangeError.
340 Value *LibCallsShrinkWrap::generateTwoRangeCond(CallInst *CI,
341 const LibFunc &Func) {
342 float UpperBound, LowerBound;
344 case LibFunc_cosh: // RangeError: (x < -710 || x > 710)
345 case LibFunc_sinh: // Same as cosh
346 LowerBound = -710.0f;
349 case LibFunc_coshf: // RangeError: (x < -89 || x > 89)
350 case LibFunc_sinhf: // Same as coshf
354 case LibFunc_coshl: // RangeError: (x < -11357 || x > 11357)
355 case LibFunc_sinhl: // Same as coshl
356 LowerBound = -11357.0f;
357 UpperBound = 11357.0f;
359 case LibFunc_exp: // RangeError: (x < -745 || x > 709)
360 LowerBound = -745.0f;
363 case LibFunc_expf: // RangeError: (x < -103 || x > 88)
364 LowerBound = -103.0f;
367 case LibFunc_expl: // RangeError: (x < -11399 || x > 11356)
368 LowerBound = -11399.0f;
369 UpperBound = 11356.0f;
371 case LibFunc_exp10: // RangeError: (x < -323 || x > 308)
372 LowerBound = -323.0f;
375 case LibFunc_exp10f: // RangeError: (x < -45 || x > 38)
379 case LibFunc_exp10l: // RangeError: (x < -4950 || x > 4932)
380 LowerBound = -4950.0f;
381 UpperBound = 4932.0f;
383 case LibFunc_exp2: // RangeError: (x < -1074 || x > 1023)
384 LowerBound = -1074.0f;
385 UpperBound = 1023.0f;
387 case LibFunc_exp2f: // RangeError: (x < -149 || x > 127)
388 LowerBound = -149.0f;
391 case LibFunc_exp2l: // RangeError: (x < -16445 || x > 11383)
392 LowerBound = -16445.0f;
393 UpperBound = 11383.0f;
396 llvm_unreachable("Unhandled library call!");
400 return createOrCond(CI, CmpInst::FCMP_OGT, UpperBound, CmpInst::FCMP_OLT,
404 // For pow(x,y), We only handle the following cases:
405 // (1) x is a constant && (x >= 1) && (x < MaxUInt8)
406 // Cond is: (y > 127)
407 // (2) x is a value coming from an integer type.
408 // (2.1) if x's bit_size == 8
409 // Cond: (x <= 0 || y > 128)
410 // (2.2) if x's bit_size is 16
411 // Cond: (x <= 0 || y > 64)
412 // (2.3) if x's bit_size is 32
413 // Cond: (x <= 0 || y > 32)
414 // Support for powl(x,y) and powf(x,y) are TBD.
416 // Note that condition can be more conservative than the actual condition
417 // (i.e. we might invoke the calls that will not set the errno.).
419 Value *LibCallsShrinkWrap::generateCondForPow(CallInst *CI,
420 const LibFunc &Func) {
421 // FIXME: LibFunc_powf and powl TBD.
422 if (Func != LibFunc_pow) {
423 LLVM_DEBUG(dbgs() << "Not handled powf() and powl()\n");
427 Value *Base = CI->getArgOperand(0);
428 Value *Exp = CI->getArgOperand(1);
429 IRBuilder<> BBBuilder(CI);
431 // Constant Base case.
432 if (ConstantFP *CF = dyn_cast<ConstantFP>(Base)) {
433 double D = CF->getValueAPF().convertToDouble();
434 if (D < 1.0f || D > APInt::getMaxValue(8).getZExtValue()) {
435 LLVM_DEBUG(dbgs() << "Not handled pow(): constant base out of range\n");
440 Constant *V = ConstantFP::get(CI->getContext(), APFloat(127.0f));
441 if (!Exp->getType()->isFloatTy())
442 V = ConstantExpr::getFPExtend(V, Exp->getType());
443 return BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V);
446 // If the Base value coming from an integer type.
447 Instruction *I = dyn_cast<Instruction>(Base);
449 LLVM_DEBUG(dbgs() << "Not handled pow(): FP type base\n");
452 unsigned Opcode = I->getOpcode();
453 if (Opcode == Instruction::UIToFP || Opcode == Instruction::SIToFP) {
454 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
463 LLVM_DEBUG(dbgs() << "Not handled pow(): type too wide\n");
468 Constant *V = ConstantFP::get(CI->getContext(), APFloat(UpperV));
469 Constant *V0 = ConstantFP::get(CI->getContext(), APFloat(0.0f));
470 if (!Exp->getType()->isFloatTy())
471 V = ConstantExpr::getFPExtend(V, Exp->getType());
472 if (!Base->getType()->isFloatTy())
473 V0 = ConstantExpr::getFPExtend(V0, Exp->getType());
475 Value *Cond = BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V);
476 Value *Cond0 = BBBuilder.CreateFCmp(CmpInst::FCMP_OLE, Base, V0);
477 return BBBuilder.CreateOr(Cond0, Cond);
479 LLVM_DEBUG(dbgs() << "Not handled pow(): base not from integer convert\n");
483 // Wrap conditions that can potentially generate errno to the library call.
484 void LibCallsShrinkWrap::shrinkWrapCI(CallInst *CI, Value *Cond) {
485 assert(Cond != nullptr && "ShrinkWrapCI is not expecting an empty call inst");
486 MDNode *BranchWeights =
487 MDBuilder(CI->getContext()).createBranchWeights(1, 2000);
489 Instruction *NewInst =
490 SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights, DT);
491 BasicBlock *CallBB = NewInst->getParent();
492 CallBB->setName("cdce.call");
493 BasicBlock *SuccBB = CallBB->getSingleSuccessor();
494 assert(SuccBB && "The split block should have a single successor");
495 SuccBB->setName("cdce.end");
496 CI->removeFromParent();
497 CallBB->getInstList().insert(CallBB->getFirstInsertionPt(), CI);
498 LLVM_DEBUG(dbgs() << "== Basic Block After ==");
499 LLVM_DEBUG(dbgs() << *CallBB->getSinglePredecessor() << *CallBB
500 << *CallBB->getSingleSuccessor() << "\n");
503 // Perform the transformation to a single candidate.
504 bool LibCallsShrinkWrap::perform(CallInst *CI) {
506 Function *Callee = CI->getCalledFunction();
507 assert(Callee && "perform() should apply to a non-empty callee");
508 TLI.getLibFunc(*Callee, Func);
509 assert(Func && "perform() is not expecting an empty function");
511 if (performCallDomainErrorOnly(CI, Func) || performCallRangeErrorOnly(CI, Func))
513 return performCallErrors(CI, Func);
516 void LibCallsShrinkWrapLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const {
517 AU.addPreserved<DominatorTreeWrapperPass>();
518 AU.addPreserved<GlobalsAAWrapperPass>();
519 AU.addRequired<TargetLibraryInfoWrapperPass>();
522 static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
524 if (F.hasFnAttribute(Attribute::OptimizeForSize))
526 LibCallsShrinkWrap CCDCE(TLI, DT);
528 bool Changed = CCDCE.perform();
530 // Verify the dominator after we've updated it locally.
531 assert(!DT || DT->verify(DominatorTree::VerificationLevel::Fast));
535 bool LibCallsShrinkWrapLegacyPass::runOnFunction(Function &F) {
536 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
537 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
538 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
539 return runImpl(F, TLI, DT);
543 char &LibCallsShrinkWrapPassID = LibCallsShrinkWrapLegacyPass::ID;
545 // Public interface to LibCallsShrinkWrap pass.
546 FunctionPass *createLibCallsShrinkWrapPass() {
547 return new LibCallsShrinkWrapLegacyPass();
550 PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F,
551 FunctionAnalysisManager &FAM) {
552 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
553 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
554 if (!runImpl(F, TLI, DT))
555 return PreservedAnalyses::all();
556 auto PA = PreservedAnalyses();
557 PA.preserve<GlobalsAA>();
558 PA.preserve<DominatorTreeAnalysis>();