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