1 //===-- LibCallsShrinkWrap.cpp ----------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // 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: 11 // sqrt(val); 12 // is transformed to 13 // if (val < 0) 14 // sqrt(val); 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 17 // conditions. 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. 22 // 23 // These partially dead calls are usually results of C++ abstraction penalty 24 // exposed by inlining. 25 // 26 //===----------------------------------------------------------------------===// 27 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" 44 using namespace llvm; 45 46 #define DEBUG_TYPE "libcalls-shrinkwrap" 47 48 STATISTIC(NumWrappedOneCond, "Number of One-Condition Wrappers Inserted"); 49 STATISTIC(NumWrappedTwoCond, "Number of Two-Condition Wrappers Inserted"); 50 51 namespace { 52 class LibCallsShrinkWrapLegacyPass : public FunctionPass { 53 public: 54 static char ID; // Pass identification, replacement for typeid 55 explicit LibCallsShrinkWrapLegacyPass() : FunctionPass(ID) { 56 initializeLibCallsShrinkWrapLegacyPassPass( 57 *PassRegistry::getPassRegistry()); 58 } 59 void getAnalysisUsage(AnalysisUsage &AU) const override; 60 bool runOnFunction(Function &F) override; 61 }; 62 } 63 64 char LibCallsShrinkWrapLegacyPass::ID = 0; 65 INITIALIZE_PASS_BEGIN(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap", 66 "Conditionally eliminate dead library calls", false, 67 false) 68 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 69 INITIALIZE_PASS_END(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap", 70 "Conditionally eliminate dead library calls", false, false) 71 72 namespace { 73 class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> { 74 public: 75 LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DominatorTree *DT) 76 : TLI(TLI), DT(DT){}; 77 void visitCallInst(CallInst &CI) { checkCandidate(CI); } 78 bool perform() { 79 bool Changed = false; 80 for (auto &CI : WorkList) { 81 LLVM_DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName() 82 << "\n"); 83 if (perform(CI)) { 84 Changed = true; 85 LLVM_DEBUG(dbgs() << "Transformed\n"); 86 } 87 } 88 return Changed; 89 } 90 91 private: 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); 101 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); 110 } 111 112 // Create a single condition using IRBuilder. 113 Value *createCond(IRBuilder<> &BBBuilder, Value *Arg, CmpInst::Predicate Cmp, 114 float Val) { 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); 119 } 120 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); 126 } 127 128 const TargetLibraryInfo &TLI; 129 DominatorTree *DT; 130 SmallVector<CallInst *, 16> WorkList; 131 }; 132 } // end anonymous namespace 133 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; 138 139 switch (Func) { 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 146 { 147 ++NumWrappedTwoCond; 148 Cond = createOrCond(CI, CmpInst::FCMP_OLT, -1.0f, CmpInst::FCMP_OGT, 1.0f); 149 break; 150 } 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 157 { 158 ++NumWrappedTwoCond; 159 Cond = createOrCond(CI, CmpInst::FCMP_OEQ, INFINITY, CmpInst::FCMP_OEQ, 160 -INFINITY); 161 break; 162 } 163 case LibFunc_acosh: // DomainError: (x < 1) 164 case LibFunc_acoshf: // Same as acosh 165 case LibFunc_acoshl: // Same as acosh 166 { 167 ++NumWrappedOneCond; 168 Cond = createCond(CI, CmpInst::FCMP_OLT, 1.0f); 169 break; 170 } 171 case LibFunc_sqrt: // DomainError: (x < 0) 172 case LibFunc_sqrtf: // Same as sqrt 173 case LibFunc_sqrtl: // Same as sqrt 174 { 175 ++NumWrappedOneCond; 176 Cond = createCond(CI, CmpInst::FCMP_OLT, 0.0f); 177 break; 178 } 179 default: 180 return false; 181 } 182 shrinkWrapCI(CI, Cond); 183 return true; 184 } 185 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; 190 191 switch (Func) { 192 case LibFunc_cosh: 193 case LibFunc_coshf: 194 case LibFunc_coshl: 195 case LibFunc_exp: 196 case LibFunc_expf: 197 case LibFunc_expl: 198 case LibFunc_exp10: 199 case LibFunc_exp10f: 200 case LibFunc_exp10l: 201 case LibFunc_exp2: 202 case LibFunc_exp2f: 203 case LibFunc_exp2l: 204 case LibFunc_sinh: 205 case LibFunc_sinhf: 206 case LibFunc_sinhl: { 207 Cond = generateTwoRangeCond(CI, Func); 208 break; 209 } 210 case LibFunc_expm1: // RangeError: (709, inf) 211 case LibFunc_expm1f: // RangeError: (88, inf) 212 case LibFunc_expm1l: // RangeError: (11356, inf) 213 { 214 Cond = generateOneRangeCond(CI, Func); 215 break; 216 } 217 default: 218 return false; 219 } 220 shrinkWrapCI(CI, Cond); 221 return true; 222 } 223 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; 228 229 switch (Func) { 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 235 { 236 ++NumWrappedTwoCond; 237 Cond = createOrCond(CI, CmpInst::FCMP_OLE, -1.0f, CmpInst::FCMP_OGE, 1.0f); 238 break; 239 } 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 254 { 255 ++NumWrappedOneCond; 256 Cond = createCond(CI, CmpInst::FCMP_OLE, 0.0f); 257 break; 258 } 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 264 { 265 ++NumWrappedOneCond; 266 Cond = createCond(CI, CmpInst::FCMP_OLE, -1.0f); 267 break; 268 } 269 case LibFunc_pow: // DomainError: x < 0 and y is noninteger 270 // PoleError: x == 0 and y < 0 271 // RangeError: overflow or underflow 272 case LibFunc_powf: 273 case LibFunc_powl: { 274 Cond = generateCondForPow(CI, Func); 275 if (Cond == nullptr) 276 return false; 277 break; 278 } 279 default: 280 return false; 281 } 282 assert(Cond && "performCallErrors should not see an empty condition"); 283 shrinkWrapCI(CI, Cond); 284 return true; 285 } 286 287 // Checks if CI is a candidate for shrinkwrapping and put it into work list if 288 // true. 289 void LibCallsShrinkWrap::checkCandidate(CallInst &CI) { 290 if (CI.isNoBuiltin()) 291 return; 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. 296 if (!CI.use_empty()) 297 return; 298 299 LibFunc Func; 300 Function *Callee = CI.getCalledFunction(); 301 if (!Callee) 302 return; 303 if (!TLI.getLibFunc(*Callee, Func) || !TLI.has(Func)) 304 return; 305 306 if (CI.getNumArgOperands() == 0) 307 return; 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())) 312 return; 313 314 WorkList.push_back(&CI); 315 } 316 317 // Generate the upper bound condition for RangeError. 318 Value *LibCallsShrinkWrap::generateOneRangeCond(CallInst *CI, 319 const LibFunc &Func) { 320 float UpperBound; 321 switch (Func) { 322 case LibFunc_expm1: // RangeError: (709, inf) 323 UpperBound = 709.0f; 324 break; 325 case LibFunc_expm1f: // RangeError: (88, inf) 326 UpperBound = 88.0f; 327 break; 328 case LibFunc_expm1l: // RangeError: (11356, inf) 329 UpperBound = 11356.0f; 330 break; 331 default: 332 llvm_unreachable("Unhandled library call!"); 333 } 334 335 ++NumWrappedOneCond; 336 return createCond(CI, CmpInst::FCMP_OGT, UpperBound); 337 } 338 339 // Generate the lower and upper bound condition for RangeError. 340 Value *LibCallsShrinkWrap::generateTwoRangeCond(CallInst *CI, 341 const LibFunc &Func) { 342 float UpperBound, LowerBound; 343 switch (Func) { 344 case LibFunc_cosh: // RangeError: (x < -710 || x > 710) 345 case LibFunc_sinh: // Same as cosh 346 LowerBound = -710.0f; 347 UpperBound = 710.0f; 348 break; 349 case LibFunc_coshf: // RangeError: (x < -89 || x > 89) 350 case LibFunc_sinhf: // Same as coshf 351 LowerBound = -89.0f; 352 UpperBound = 89.0f; 353 break; 354 case LibFunc_coshl: // RangeError: (x < -11357 || x > 11357) 355 case LibFunc_sinhl: // Same as coshl 356 LowerBound = -11357.0f; 357 UpperBound = 11357.0f; 358 break; 359 case LibFunc_exp: // RangeError: (x < -745 || x > 709) 360 LowerBound = -745.0f; 361 UpperBound = 709.0f; 362 break; 363 case LibFunc_expf: // RangeError: (x < -103 || x > 88) 364 LowerBound = -103.0f; 365 UpperBound = 88.0f; 366 break; 367 case LibFunc_expl: // RangeError: (x < -11399 || x > 11356) 368 LowerBound = -11399.0f; 369 UpperBound = 11356.0f; 370 break; 371 case LibFunc_exp10: // RangeError: (x < -323 || x > 308) 372 LowerBound = -323.0f; 373 UpperBound = 308.0f; 374 break; 375 case LibFunc_exp10f: // RangeError: (x < -45 || x > 38) 376 LowerBound = -45.0f; 377 UpperBound = 38.0f; 378 break; 379 case LibFunc_exp10l: // RangeError: (x < -4950 || x > 4932) 380 LowerBound = -4950.0f; 381 UpperBound = 4932.0f; 382 break; 383 case LibFunc_exp2: // RangeError: (x < -1074 || x > 1023) 384 LowerBound = -1074.0f; 385 UpperBound = 1023.0f; 386 break; 387 case LibFunc_exp2f: // RangeError: (x < -149 || x > 127) 388 LowerBound = -149.0f; 389 UpperBound = 127.0f; 390 break; 391 case LibFunc_exp2l: // RangeError: (x < -16445 || x > 11383) 392 LowerBound = -16445.0f; 393 UpperBound = 11383.0f; 394 break; 395 default: 396 llvm_unreachable("Unhandled library call!"); 397 } 398 399 ++NumWrappedTwoCond; 400 return createOrCond(CI, CmpInst::FCMP_OGT, UpperBound, CmpInst::FCMP_OLT, 401 LowerBound); 402 } 403 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. 415 // 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.). 418 // 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"); 424 return nullptr; 425 } 426 427 Value *Base = CI->getArgOperand(0); 428 Value *Exp = CI->getArgOperand(1); 429 IRBuilder<> BBBuilder(CI); 430 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"); 436 return nullptr; 437 } 438 439 ++NumWrappedOneCond; 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); 444 } 445 446 // If the Base value coming from an integer type. 447 Instruction *I = dyn_cast<Instruction>(Base); 448 if (!I) { 449 LLVM_DEBUG(dbgs() << "Not handled pow(): FP type base\n"); 450 return nullptr; 451 } 452 unsigned Opcode = I->getOpcode(); 453 if (Opcode == Instruction::UIToFP || Opcode == Instruction::SIToFP) { 454 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits(); 455 float UpperV = 0.0f; 456 if (BW == 8) 457 UpperV = 128.0f; 458 else if (BW == 16) 459 UpperV = 64.0f; 460 else if (BW == 32) 461 UpperV = 32.0f; 462 else { 463 LLVM_DEBUG(dbgs() << "Not handled pow(): type too wide\n"); 464 return nullptr; 465 } 466 467 ++NumWrappedTwoCond; 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()); 474 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); 478 } 479 LLVM_DEBUG(dbgs() << "Not handled pow(): base not from integer convert\n"); 480 return nullptr; 481 } 482 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); 488 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"); 501 } 502 503 // Perform the transformation to a single candidate. 504 bool LibCallsShrinkWrap::perform(CallInst *CI) { 505 LibFunc Func; 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"); 510 511 if (performCallDomainErrorOnly(CI, Func) || performCallRangeErrorOnly(CI, Func)) 512 return true; 513 return performCallErrors(CI, Func); 514 } 515 516 void LibCallsShrinkWrapLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { 517 AU.addPreserved<DominatorTreeWrapperPass>(); 518 AU.addPreserved<GlobalsAAWrapperPass>(); 519 AU.addRequired<TargetLibraryInfoWrapperPass>(); 520 } 521 522 static bool runImpl(Function &F, const TargetLibraryInfo &TLI, 523 DominatorTree *DT) { 524 if (F.hasFnAttribute(Attribute::OptimizeForSize)) 525 return false; 526 LibCallsShrinkWrap CCDCE(TLI, DT); 527 CCDCE.visit(F); 528 bool Changed = CCDCE.perform(); 529 530 // Verify the dominator after we've updated it locally. 531 assert(!DT || DT->verify(DominatorTree::VerificationLevel::Fast)); 532 return Changed; 533 } 534 535 bool LibCallsShrinkWrapLegacyPass::runOnFunction(Function &F) { 536 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 537 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 538 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; 539 return runImpl(F, TLI, DT); 540 } 541 542 namespace llvm { 543 char &LibCallsShrinkWrapPassID = LibCallsShrinkWrapLegacyPass::ID; 544 545 // Public interface to LibCallsShrinkWrap pass. 546 FunctionPass *createLibCallsShrinkWrapPass() { 547 return new LibCallsShrinkWrapLegacyPass(); 548 } 549 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>(); 559 return PA; 560 } 561 } 562