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/Constants.h" 34 #include "llvm/IR/Dominators.h" 35 #include "llvm/IR/Function.h" 36 #include "llvm/IR/IRBuilder.h" 37 #include "llvm/IR/InstVisitor.h" 38 #include "llvm/IR/Instructions.h" 39 #include "llvm/IR/MDBuilder.h" 40 #include "llvm/InitializePasses.h" 41 #include "llvm/Pass.h" 42 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 43 using namespace llvm; 44 45 #define DEBUG_TYPE "libcalls-shrinkwrap" 46 47 STATISTIC(NumWrappedOneCond, "Number of One-Condition Wrappers Inserted"); 48 STATISTIC(NumWrappedTwoCond, "Number of Two-Condition Wrappers Inserted"); 49 50 namespace { 51 class LibCallsShrinkWrapLegacyPass : public FunctionPass { 52 public: 53 static char ID; // Pass identification, replacement for typeid 54 explicit LibCallsShrinkWrapLegacyPass() : FunctionPass(ID) { 55 initializeLibCallsShrinkWrapLegacyPassPass( 56 *PassRegistry::getPassRegistry()); 57 } 58 void getAnalysisUsage(AnalysisUsage &AU) const override; 59 bool runOnFunction(Function &F) override; 60 }; 61 } 62 63 char LibCallsShrinkWrapLegacyPass::ID = 0; 64 INITIALIZE_PASS_BEGIN(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap", 65 "Conditionally eliminate dead library calls", false, 66 false) 67 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 68 INITIALIZE_PASS_END(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap", 69 "Conditionally eliminate dead library calls", false, false) 70 71 namespace { 72 class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> { 73 public: 74 LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DominatorTree *DT) 75 : TLI(TLI), DT(DT){}; 76 void visitCallInst(CallInst &CI) { checkCandidate(CI); } 77 bool perform() { 78 bool Changed = false; 79 for (auto &CI : WorkList) { 80 LLVM_DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName() 81 << "\n"); 82 if (perform(CI)) { 83 Changed = true; 84 LLVM_DEBUG(dbgs() << "Transformed\n"); 85 } 86 } 87 return Changed; 88 } 89 90 private: 91 bool perform(CallInst *CI); 92 void checkCandidate(CallInst &CI); 93 void shrinkWrapCI(CallInst *CI, Value *Cond); 94 bool performCallDomainErrorOnly(CallInst *CI, const LibFunc &Func); 95 bool performCallErrors(CallInst *CI, const LibFunc &Func); 96 bool performCallRangeErrorOnly(CallInst *CI, const LibFunc &Func); 97 Value *generateOneRangeCond(CallInst *CI, const LibFunc &Func); 98 Value *generateTwoRangeCond(CallInst *CI, const LibFunc &Func); 99 Value *generateCondForPow(CallInst *CI, const LibFunc &Func); 100 101 // Create an OR of two conditions. 102 Value *createOrCond(CallInst *CI, CmpInst::Predicate Cmp, float Val, 103 CmpInst::Predicate Cmp2, float Val2) { 104 IRBuilder<> BBBuilder(CI); 105 Value *Arg = CI->getArgOperand(0); 106 auto Cond2 = createCond(BBBuilder, Arg, Cmp2, Val2); 107 auto Cond1 = createCond(BBBuilder, Arg, Cmp, Val); 108 return BBBuilder.CreateOr(Cond1, Cond2); 109 } 110 111 // Create a single condition using IRBuilder. 112 Value *createCond(IRBuilder<> &BBBuilder, Value *Arg, CmpInst::Predicate Cmp, 113 float Val) { 114 Constant *V = ConstantFP::get(BBBuilder.getContext(), APFloat(Val)); 115 if (!Arg->getType()->isFloatTy()) 116 V = ConstantExpr::getFPExtend(V, Arg->getType()); 117 return BBBuilder.CreateFCmp(Cmp, Arg, V); 118 } 119 120 // Create a single condition. 121 Value *createCond(CallInst *CI, CmpInst::Predicate Cmp, float Val) { 122 IRBuilder<> BBBuilder(CI); 123 Value *Arg = CI->getArgOperand(0); 124 return createCond(BBBuilder, Arg, Cmp, Val); 125 } 126 127 const TargetLibraryInfo &TLI; 128 DominatorTree *DT; 129 SmallVector<CallInst *, 16> WorkList; 130 }; 131 } // end anonymous namespace 132 133 // Perform the transformation to calls with errno set by domain error. 134 bool LibCallsShrinkWrap::performCallDomainErrorOnly(CallInst *CI, 135 const LibFunc &Func) { 136 Value *Cond = nullptr; 137 138 switch (Func) { 139 case LibFunc_acos: // DomainError: (x < -1 || x > 1) 140 case LibFunc_acosf: // Same as acos 141 case LibFunc_acosl: // Same as acos 142 case LibFunc_asin: // DomainError: (x < -1 || x > 1) 143 case LibFunc_asinf: // Same as asin 144 case LibFunc_asinl: // Same as asin 145 { 146 ++NumWrappedTwoCond; 147 Cond = createOrCond(CI, CmpInst::FCMP_OLT, -1.0f, CmpInst::FCMP_OGT, 1.0f); 148 break; 149 } 150 case LibFunc_cos: // DomainError: (x == +inf || x == -inf) 151 case LibFunc_cosf: // Same as cos 152 case LibFunc_cosl: // Same as cos 153 case LibFunc_sin: // DomainError: (x == +inf || x == -inf) 154 case LibFunc_sinf: // Same as sin 155 case LibFunc_sinl: // Same as sin 156 { 157 ++NumWrappedTwoCond; 158 Cond = createOrCond(CI, CmpInst::FCMP_OEQ, INFINITY, CmpInst::FCMP_OEQ, 159 -INFINITY); 160 break; 161 } 162 case LibFunc_acosh: // DomainError: (x < 1) 163 case LibFunc_acoshf: // Same as acosh 164 case LibFunc_acoshl: // Same as acosh 165 { 166 ++NumWrappedOneCond; 167 Cond = createCond(CI, CmpInst::FCMP_OLT, 1.0f); 168 break; 169 } 170 case LibFunc_sqrt: // DomainError: (x < 0) 171 case LibFunc_sqrtf: // Same as sqrt 172 case LibFunc_sqrtl: // Same as sqrt 173 { 174 ++NumWrappedOneCond; 175 Cond = createCond(CI, CmpInst::FCMP_OLT, 0.0f); 176 break; 177 } 178 default: 179 return false; 180 } 181 shrinkWrapCI(CI, Cond); 182 return true; 183 } 184 185 // Perform the transformation to calls with errno set by range error. 186 bool LibCallsShrinkWrap::performCallRangeErrorOnly(CallInst *CI, 187 const LibFunc &Func) { 188 Value *Cond = nullptr; 189 190 switch (Func) { 191 case LibFunc_cosh: 192 case LibFunc_coshf: 193 case LibFunc_coshl: 194 case LibFunc_exp: 195 case LibFunc_expf: 196 case LibFunc_expl: 197 case LibFunc_exp10: 198 case LibFunc_exp10f: 199 case LibFunc_exp10l: 200 case LibFunc_exp2: 201 case LibFunc_exp2f: 202 case LibFunc_exp2l: 203 case LibFunc_sinh: 204 case LibFunc_sinhf: 205 case LibFunc_sinhl: { 206 Cond = generateTwoRangeCond(CI, Func); 207 break; 208 } 209 case LibFunc_expm1: // RangeError: (709, inf) 210 case LibFunc_expm1f: // RangeError: (88, inf) 211 case LibFunc_expm1l: // RangeError: (11356, inf) 212 { 213 Cond = generateOneRangeCond(CI, Func); 214 break; 215 } 216 default: 217 return false; 218 } 219 shrinkWrapCI(CI, Cond); 220 return true; 221 } 222 223 // Perform the transformation to calls with errno set by combination of errors. 224 bool LibCallsShrinkWrap::performCallErrors(CallInst *CI, 225 const LibFunc &Func) { 226 Value *Cond = nullptr; 227 228 switch (Func) { 229 case LibFunc_atanh: // DomainError: (x < -1 || x > 1) 230 // PoleError: (x == -1 || x == 1) 231 // Overall Cond: (x <= -1 || x >= 1) 232 case LibFunc_atanhf: // Same as atanh 233 case LibFunc_atanhl: // Same as atanh 234 { 235 ++NumWrappedTwoCond; 236 Cond = createOrCond(CI, CmpInst::FCMP_OLE, -1.0f, CmpInst::FCMP_OGE, 1.0f); 237 break; 238 } 239 case LibFunc_log: // DomainError: (x < 0) 240 // PoleError: (x == 0) 241 // Overall Cond: (x <= 0) 242 case LibFunc_logf: // Same as log 243 case LibFunc_logl: // Same as log 244 case LibFunc_log10: // Same as log 245 case LibFunc_log10f: // Same as log 246 case LibFunc_log10l: // Same as log 247 case LibFunc_log2: // Same as log 248 case LibFunc_log2f: // Same as log 249 case LibFunc_log2l: // Same as log 250 case LibFunc_logb: // Same as log 251 case LibFunc_logbf: // Same as log 252 case LibFunc_logbl: // Same as log 253 { 254 ++NumWrappedOneCond; 255 Cond = createCond(CI, CmpInst::FCMP_OLE, 0.0f); 256 break; 257 } 258 case LibFunc_log1p: // DomainError: (x < -1) 259 // PoleError: (x == -1) 260 // Overall Cond: (x <= -1) 261 case LibFunc_log1pf: // Same as log1p 262 case LibFunc_log1pl: // Same as log1p 263 { 264 ++NumWrappedOneCond; 265 Cond = createCond(CI, CmpInst::FCMP_OLE, -1.0f); 266 break; 267 } 268 case LibFunc_pow: // DomainError: x < 0 and y is noninteger 269 // PoleError: x == 0 and y < 0 270 // RangeError: overflow or underflow 271 case LibFunc_powf: 272 case LibFunc_powl: { 273 Cond = generateCondForPow(CI, Func); 274 if (Cond == nullptr) 275 return false; 276 break; 277 } 278 default: 279 return false; 280 } 281 assert(Cond && "performCallErrors should not see an empty condition"); 282 shrinkWrapCI(CI, Cond); 283 return true; 284 } 285 286 // Checks if CI is a candidate for shrinkwrapping and put it into work list if 287 // true. 288 void LibCallsShrinkWrap::checkCandidate(CallInst &CI) { 289 if (CI.isNoBuiltin()) 290 return; 291 // A possible improvement is to handle the calls with the return value being 292 // used. If there is API for fast libcall implementation without setting 293 // errno, we can use the same framework to direct/wrap the call to the fast 294 // API in the error free path, and leave the original call in the slow path. 295 if (!CI.use_empty()) 296 return; 297 298 LibFunc Func; 299 Function *Callee = CI.getCalledFunction(); 300 if (!Callee) 301 return; 302 if (!TLI.getLibFunc(*Callee, Func) || !TLI.has(Func)) 303 return; 304 305 if (CI.arg_empty()) 306 return; 307 // TODO: Handle long double in other formats. 308 Type *ArgType = CI.getArgOperand(0)->getType(); 309 if (!(ArgType->isFloatTy() || ArgType->isDoubleTy() || 310 ArgType->isX86_FP80Ty())) 311 return; 312 313 WorkList.push_back(&CI); 314 } 315 316 // Generate the upper bound condition for RangeError. 317 Value *LibCallsShrinkWrap::generateOneRangeCond(CallInst *CI, 318 const LibFunc &Func) { 319 float UpperBound; 320 switch (Func) { 321 case LibFunc_expm1: // RangeError: (709, inf) 322 UpperBound = 709.0f; 323 break; 324 case LibFunc_expm1f: // RangeError: (88, inf) 325 UpperBound = 88.0f; 326 break; 327 case LibFunc_expm1l: // RangeError: (11356, inf) 328 UpperBound = 11356.0f; 329 break; 330 default: 331 llvm_unreachable("Unhandled library call!"); 332 } 333 334 ++NumWrappedOneCond; 335 return createCond(CI, CmpInst::FCMP_OGT, UpperBound); 336 } 337 338 // Generate the lower and upper bound condition for RangeError. 339 Value *LibCallsShrinkWrap::generateTwoRangeCond(CallInst *CI, 340 const LibFunc &Func) { 341 float UpperBound, LowerBound; 342 switch (Func) { 343 case LibFunc_cosh: // RangeError: (x < -710 || x > 710) 344 case LibFunc_sinh: // Same as cosh 345 LowerBound = -710.0f; 346 UpperBound = 710.0f; 347 break; 348 case LibFunc_coshf: // RangeError: (x < -89 || x > 89) 349 case LibFunc_sinhf: // Same as coshf 350 LowerBound = -89.0f; 351 UpperBound = 89.0f; 352 break; 353 case LibFunc_coshl: // RangeError: (x < -11357 || x > 11357) 354 case LibFunc_sinhl: // Same as coshl 355 LowerBound = -11357.0f; 356 UpperBound = 11357.0f; 357 break; 358 case LibFunc_exp: // RangeError: (x < -745 || x > 709) 359 LowerBound = -745.0f; 360 UpperBound = 709.0f; 361 break; 362 case LibFunc_expf: // RangeError: (x < -103 || x > 88) 363 LowerBound = -103.0f; 364 UpperBound = 88.0f; 365 break; 366 case LibFunc_expl: // RangeError: (x < -11399 || x > 11356) 367 LowerBound = -11399.0f; 368 UpperBound = 11356.0f; 369 break; 370 case LibFunc_exp10: // RangeError: (x < -323 || x > 308) 371 LowerBound = -323.0f; 372 UpperBound = 308.0f; 373 break; 374 case LibFunc_exp10f: // RangeError: (x < -45 || x > 38) 375 LowerBound = -45.0f; 376 UpperBound = 38.0f; 377 break; 378 case LibFunc_exp10l: // RangeError: (x < -4950 || x > 4932) 379 LowerBound = -4950.0f; 380 UpperBound = 4932.0f; 381 break; 382 case LibFunc_exp2: // RangeError: (x < -1074 || x > 1023) 383 LowerBound = -1074.0f; 384 UpperBound = 1023.0f; 385 break; 386 case LibFunc_exp2f: // RangeError: (x < -149 || x > 127) 387 LowerBound = -149.0f; 388 UpperBound = 127.0f; 389 break; 390 case LibFunc_exp2l: // RangeError: (x < -16445 || x > 11383) 391 LowerBound = -16445.0f; 392 UpperBound = 11383.0f; 393 break; 394 default: 395 llvm_unreachable("Unhandled library call!"); 396 } 397 398 ++NumWrappedTwoCond; 399 return createOrCond(CI, CmpInst::FCMP_OGT, UpperBound, CmpInst::FCMP_OLT, 400 LowerBound); 401 } 402 403 // For pow(x,y), We only handle the following cases: 404 // (1) x is a constant && (x >= 1) && (x < MaxUInt8) 405 // Cond is: (y > 127) 406 // (2) x is a value coming from an integer type. 407 // (2.1) if x's bit_size == 8 408 // Cond: (x <= 0 || y > 128) 409 // (2.2) if x's bit_size is 16 410 // Cond: (x <= 0 || y > 64) 411 // (2.3) if x's bit_size is 32 412 // Cond: (x <= 0 || y > 32) 413 // Support for powl(x,y) and powf(x,y) are TBD. 414 // 415 // Note that condition can be more conservative than the actual condition 416 // (i.e. we might invoke the calls that will not set the errno.). 417 // 418 Value *LibCallsShrinkWrap::generateCondForPow(CallInst *CI, 419 const LibFunc &Func) { 420 // FIXME: LibFunc_powf and powl TBD. 421 if (Func != LibFunc_pow) { 422 LLVM_DEBUG(dbgs() << "Not handled powf() and powl()\n"); 423 return nullptr; 424 } 425 426 Value *Base = CI->getArgOperand(0); 427 Value *Exp = CI->getArgOperand(1); 428 IRBuilder<> BBBuilder(CI); 429 430 // Constant Base case. 431 if (ConstantFP *CF = dyn_cast<ConstantFP>(Base)) { 432 double D = CF->getValueAPF().convertToDouble(); 433 if (D < 1.0f || D > APInt::getMaxValue(8).getZExtValue()) { 434 LLVM_DEBUG(dbgs() << "Not handled pow(): constant base out of range\n"); 435 return nullptr; 436 } 437 438 ++NumWrappedOneCond; 439 Constant *V = ConstantFP::get(CI->getContext(), APFloat(127.0f)); 440 if (!Exp->getType()->isFloatTy()) 441 V = ConstantExpr::getFPExtend(V, Exp->getType()); 442 return BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V); 443 } 444 445 // If the Base value coming from an integer type. 446 Instruction *I = dyn_cast<Instruction>(Base); 447 if (!I) { 448 LLVM_DEBUG(dbgs() << "Not handled pow(): FP type base\n"); 449 return nullptr; 450 } 451 unsigned Opcode = I->getOpcode(); 452 if (Opcode == Instruction::UIToFP || Opcode == Instruction::SIToFP) { 453 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits(); 454 float UpperV = 0.0f; 455 if (BW == 8) 456 UpperV = 128.0f; 457 else if (BW == 16) 458 UpperV = 64.0f; 459 else if (BW == 32) 460 UpperV = 32.0f; 461 else { 462 LLVM_DEBUG(dbgs() << "Not handled pow(): type too wide\n"); 463 return nullptr; 464 } 465 466 ++NumWrappedTwoCond; 467 Constant *V = ConstantFP::get(CI->getContext(), APFloat(UpperV)); 468 Constant *V0 = ConstantFP::get(CI->getContext(), APFloat(0.0f)); 469 if (!Exp->getType()->isFloatTy()) 470 V = ConstantExpr::getFPExtend(V, Exp->getType()); 471 if (!Base->getType()->isFloatTy()) 472 V0 = ConstantExpr::getFPExtend(V0, Exp->getType()); 473 474 Value *Cond = BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V); 475 Value *Cond0 = BBBuilder.CreateFCmp(CmpInst::FCMP_OLE, Base, V0); 476 return BBBuilder.CreateOr(Cond0, Cond); 477 } 478 LLVM_DEBUG(dbgs() << "Not handled pow(): base not from integer convert\n"); 479 return nullptr; 480 } 481 482 // Wrap conditions that can potentially generate errno to the library call. 483 void LibCallsShrinkWrap::shrinkWrapCI(CallInst *CI, Value *Cond) { 484 assert(Cond != nullptr && "ShrinkWrapCI is not expecting an empty call inst"); 485 MDNode *BranchWeights = 486 MDBuilder(CI->getContext()).createBranchWeights(1, 2000); 487 488 Instruction *NewInst = 489 SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights, DT); 490 BasicBlock *CallBB = NewInst->getParent(); 491 CallBB->setName("cdce.call"); 492 BasicBlock *SuccBB = CallBB->getSingleSuccessor(); 493 assert(SuccBB && "The split block should have a single successor"); 494 SuccBB->setName("cdce.end"); 495 CI->removeFromParent(); 496 CallBB->getInstList().insert(CallBB->getFirstInsertionPt(), CI); 497 LLVM_DEBUG(dbgs() << "== Basic Block After =="); 498 LLVM_DEBUG(dbgs() << *CallBB->getSinglePredecessor() << *CallBB 499 << *CallBB->getSingleSuccessor() << "\n"); 500 } 501 502 // Perform the transformation to a single candidate. 503 bool LibCallsShrinkWrap::perform(CallInst *CI) { 504 LibFunc Func; 505 Function *Callee = CI->getCalledFunction(); 506 assert(Callee && "perform() should apply to a non-empty callee"); 507 TLI.getLibFunc(*Callee, Func); 508 assert(Func && "perform() is not expecting an empty function"); 509 510 if (performCallDomainErrorOnly(CI, Func) || performCallRangeErrorOnly(CI, Func)) 511 return true; 512 return performCallErrors(CI, Func); 513 } 514 515 void LibCallsShrinkWrapLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { 516 AU.addPreserved<DominatorTreeWrapperPass>(); 517 AU.addPreserved<GlobalsAAWrapperPass>(); 518 AU.addRequired<TargetLibraryInfoWrapperPass>(); 519 } 520 521 static bool runImpl(Function &F, const TargetLibraryInfo &TLI, 522 DominatorTree *DT) { 523 if (F.hasFnAttribute(Attribute::OptimizeForSize)) 524 return false; 525 LibCallsShrinkWrap CCDCE(TLI, DT); 526 CCDCE.visit(F); 527 bool Changed = CCDCE.perform(); 528 529 // Verify the dominator after we've updated it locally. 530 assert(!DT || DT->verify(DominatorTree::VerificationLevel::Fast)); 531 return Changed; 532 } 533 534 bool LibCallsShrinkWrapLegacyPass::runOnFunction(Function &F) { 535 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 536 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 537 auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; 538 return runImpl(F, TLI, DT); 539 } 540 541 namespace llvm { 542 char &LibCallsShrinkWrapPassID = LibCallsShrinkWrapLegacyPass::ID; 543 544 // Public interface to LibCallsShrinkWrap pass. 545 FunctionPass *createLibCallsShrinkWrapPass() { 546 return new LibCallsShrinkWrapLegacyPass(); 547 } 548 549 PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F, 550 FunctionAnalysisManager &FAM) { 551 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F); 552 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F); 553 if (!runImpl(F, TLI, DT)) 554 return PreservedAnalyses::all(); 555 auto PA = PreservedAnalyses(); 556 PA.preserve<DominatorTreeAnalysis>(); 557 return PA; 558 } 559 } 560