1 //===-- LibCallsShrinkWrap.cpp ----------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass shrink-wraps a call to function if the result is not used. 11 // The call can set errno but is otherwise side effect free. For example: 12 // sqrt(val); 13 // is transformed to 14 // if (val < 0) 15 // sqrt(val); 16 // Even if the result of library call is not being used, the compiler cannot 17 // safely delete the call because the function can set errno on error 18 // conditions. 19 // Note in many functions, the error condition solely depends on the incoming 20 // parameter. In this optimization, we can generate the condition can lead to 21 // the errno to shrink-wrap the call. Since the chances of hitting the error 22 // condition is low, the runtime call is effectively eliminated. 23 // 24 // These partially dead calls are usually results of C++ abstraction penalty 25 // exposed by inlining. 26 // 27 //===----------------------------------------------------------------------===// 28 29 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h" 30 #include "llvm/ADT/SmallVector.h" 31 #include "llvm/ADT/Statistic.h" 32 #include "llvm/Analysis/TargetLibraryInfo.h" 33 #include "llvm/IR/CFG.h" 34 #include "llvm/IR/Constants.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/LLVMContext.h" 40 #include "llvm/IR/MDBuilder.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 static cl::opt<bool> LibCallsShrinkWrapDoDomainError( 51 "libcalls-shrinkwrap-domain-error", cl::init(true), cl::Hidden, 52 cl::desc("Perform shrink-wrap on lib calls with domain errors")); 53 static cl::opt<bool> LibCallsShrinkWrapDoRangeError( 54 "libcalls-shrinkwrap-range-error", cl::init(true), cl::Hidden, 55 cl::desc("Perform shrink-wrap on lib calls with range errors")); 56 static cl::opt<bool> LibCallsShrinkWrapDoPoleError( 57 "libcalls-shrinkwrap-pole-error", cl::init(true), cl::Hidden, 58 cl::desc("Perform shrink-wrap on lib calls with pole errors")); 59 60 namespace { 61 class LibCallsShrinkWrapLegacyPass : public FunctionPass { 62 public: 63 static char ID; // Pass identification, replacement for typeid 64 explicit LibCallsShrinkWrapLegacyPass() : FunctionPass(ID) { 65 initializeLibCallsShrinkWrapLegacyPassPass( 66 *PassRegistry::getPassRegistry()); 67 } 68 void getAnalysisUsage(AnalysisUsage &AU) const override; 69 bool runOnFunction(Function &F) override; 70 }; 71 } 72 73 char LibCallsShrinkWrapLegacyPass::ID = 0; 74 INITIALIZE_PASS_BEGIN(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap", 75 "Conditionally eliminate dead library calls", false, 76 false) 77 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 78 INITIALIZE_PASS_END(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap", 79 "Conditionally eliminate dead library calls", false, false) 80 81 class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> { 82 public: 83 LibCallsShrinkWrap(const TargetLibraryInfo &TLI) : TLI(TLI), Changed(false){}; 84 bool isChanged() const { return Changed; } 85 void visitCallInst(CallInst &CI) { checkCandidate(CI); } 86 void perform() { 87 for (auto &CI : WorkList) { 88 DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName() 89 << "\n"); 90 if (perform(CI)) { 91 Changed = true; 92 DEBUG(dbgs() << "Transformed\n"); 93 } 94 } 95 } 96 97 private: 98 bool perform(CallInst *CI); 99 void checkCandidate(CallInst &CI); 100 void shrinkWrapCI(CallInst *CI, Value *Cond); 101 bool performCallDomainErrorOnly(CallInst *CI, const LibFunc::Func &Func); 102 bool performCallErrors(CallInst *CI, const LibFunc::Func &Func); 103 bool performCallRangeErrorOnly(CallInst *CI, const LibFunc::Func &Func); 104 Value *generateOneRangeCond(CallInst *CI, const LibFunc::Func &Func); 105 Value *generateTwoRangeCond(CallInst *CI, const LibFunc::Func &Func); 106 Value *generateCondForPow(CallInst *CI, const LibFunc::Func &Func); 107 108 // Create an OR of two conditions. 109 Value *createOrCond(CallInst *CI, CmpInst::Predicate Cmp, float Val, 110 CmpInst::Predicate Cmp2, float Val2) { 111 IRBuilder<> BBBuilder(CI); 112 Value *Arg = CI->getArgOperand(0); 113 auto Cond2 = createCond(BBBuilder, Arg, Cmp2, Val2); 114 auto Cond1 = createCond(BBBuilder, Arg, Cmp, Val); 115 return BBBuilder.CreateOr(Cond1, Cond2); 116 } 117 118 // Create a single condition using IRBuilder. 119 Value *createCond(IRBuilder<> &BBBuilder, Value *Arg, CmpInst::Predicate Cmp, 120 float Val) { 121 Constant *V = ConstantFP::get(BBBuilder.getContext(), APFloat(Val)); 122 if (!Arg->getType()->isFloatTy()) 123 V = ConstantExpr::getFPExtend(V, Arg->getType()); 124 return BBBuilder.CreateFCmp(Cmp, Arg, V); 125 } 126 127 // Create a single condition. 128 Value *createCond(CallInst *CI, CmpInst::Predicate Cmp, float Val) { 129 IRBuilder<> BBBuilder(CI); 130 Value *Arg = CI->getArgOperand(0); 131 return createCond(BBBuilder, Arg, Cmp, Val); 132 } 133 134 const TargetLibraryInfo &TLI; 135 SmallVector<CallInst *, 16> WorkList; 136 bool Changed; 137 }; 138 139 // Perform the transformation to calls with errno set by domain error. 140 bool LibCallsShrinkWrap::performCallDomainErrorOnly(CallInst *CI, 141 const LibFunc::Func &Func) { 142 Value *Cond = nullptr; 143 144 switch (Func) { 145 case LibFunc::acos: // DomainError: (x < -1 || x > 1) 146 case LibFunc::acosf: // Same as acos 147 case LibFunc::acosl: // Same as acos 148 case LibFunc::asin: // DomainError: (x < -1 || x > 1) 149 case LibFunc::asinf: // Same as asin 150 case LibFunc::asinl: // Same as asin 151 { 152 ++NumWrappedTwoCond; 153 Cond = createOrCond(CI, CmpInst::FCMP_OLT, -1.0f, CmpInst::FCMP_OGT, 1.0f); 154 break; 155 } 156 case LibFunc::cos: // DomainError: (x == +inf || x == -inf) 157 case LibFunc::cosf: // Same as cos 158 case LibFunc::cosl: // Same as cos 159 case LibFunc::sin: // DomainError: (x == +inf || x == -inf) 160 case LibFunc::sinf: // Same as sin 161 case LibFunc::sinl: // Same as sin 162 { 163 ++NumWrappedTwoCond; 164 Cond = createOrCond(CI, CmpInst::FCMP_OEQ, INFINITY, CmpInst::FCMP_OEQ, 165 -INFINITY); 166 break; 167 } 168 case LibFunc::acosh: // DomainError: (x < 1) 169 case LibFunc::acoshf: // Same as acosh 170 case LibFunc::acoshl: // Same as acosh 171 { 172 ++NumWrappedOneCond; 173 Cond = createCond(CI, CmpInst::FCMP_OLT, 1.0f); 174 break; 175 } 176 case LibFunc::sqrt: // DomainError: (x < 0) 177 case LibFunc::sqrtf: // Same as sqrt 178 case LibFunc::sqrtl: // Same as sqrt 179 { 180 ++NumWrappedOneCond; 181 Cond = createCond(CI, CmpInst::FCMP_OLT, 0.0f); 182 break; 183 } 184 default: 185 return false; 186 } 187 shrinkWrapCI(CI, Cond); 188 return true; 189 } 190 191 // Perform the transformation to calls with errno set by range error. 192 bool LibCallsShrinkWrap::performCallRangeErrorOnly(CallInst *CI, 193 const LibFunc::Func &Func) { 194 Value *Cond = nullptr; 195 196 switch (Func) { 197 case LibFunc::cosh: 198 case LibFunc::coshf: 199 case LibFunc::coshl: 200 case LibFunc::exp: 201 case LibFunc::expf: 202 case LibFunc::expl: 203 case LibFunc::exp10: 204 case LibFunc::exp10f: 205 case LibFunc::exp10l: 206 case LibFunc::exp2: 207 case LibFunc::exp2f: 208 case LibFunc::exp2l: 209 case LibFunc::sinh: 210 case LibFunc::sinhf: 211 case LibFunc::sinhl: { 212 Cond = generateTwoRangeCond(CI, Func); 213 break; 214 } 215 case LibFunc::expm1: // RangeError: (709, inf) 216 case LibFunc::expm1f: // RangeError: (88, inf) 217 case LibFunc::expm1l: // RangeError: (11356, inf) 218 { 219 Cond = generateOneRangeCond(CI, Func); 220 break; 221 } 222 default: 223 return false; 224 } 225 shrinkWrapCI(CI, Cond); 226 return true; 227 } 228 229 // Perform the transformation to calls with errno set by combination of errors. 230 bool LibCallsShrinkWrap::performCallErrors(CallInst *CI, 231 const LibFunc::Func &Func) { 232 Value *Cond = nullptr; 233 234 switch (Func) { 235 case LibFunc::atanh: // DomainError: (x < -1 || x > 1) 236 // PoleError: (x == -1 || x == 1) 237 // Overall Cond: (x <= -1 || x >= 1) 238 case LibFunc::atanhf: // Same as atanh 239 case LibFunc::atanhl: // Same as atanh 240 { 241 if (!LibCallsShrinkWrapDoDomainError || !LibCallsShrinkWrapDoPoleError) 242 return false; 243 ++NumWrappedTwoCond; 244 Cond = createOrCond(CI, CmpInst::FCMP_OLE, -1.0f, CmpInst::FCMP_OGE, 1.0f); 245 break; 246 } 247 case LibFunc::log: // DomainError: (x < 0) 248 // PoleError: (x == 0) 249 // Overall Cond: (x <= 0) 250 case LibFunc::logf: // Same as log 251 case LibFunc::logl: // Same as log 252 case LibFunc::log10: // Same as log 253 case LibFunc::log10f: // Same as log 254 case LibFunc::log10l: // Same as log 255 case LibFunc::log2: // Same as log 256 case LibFunc::log2f: // Same as log 257 case LibFunc::log2l: // Same as log 258 case LibFunc::logb: // Same as log 259 case LibFunc::logbf: // Same as log 260 case LibFunc::logbl: // Same as log 261 { 262 if (!LibCallsShrinkWrapDoDomainError || !LibCallsShrinkWrapDoPoleError) 263 return false; 264 ++NumWrappedOneCond; 265 Cond = createCond(CI, CmpInst::FCMP_OLE, 0.0f); 266 break; 267 } 268 case LibFunc::log1p: // DomainError: (x < -1) 269 // PoleError: (x == -1) 270 // Overall Cond: (x <= -1) 271 case LibFunc::log1pf: // Same as log1p 272 case LibFunc::log1pl: // Same as log1p 273 { 274 if (!LibCallsShrinkWrapDoDomainError || !LibCallsShrinkWrapDoPoleError) 275 return false; 276 ++NumWrappedOneCond; 277 Cond = createCond(CI, CmpInst::FCMP_OLE, -1.0f); 278 break; 279 } 280 case LibFunc::pow: // DomainError: x < 0 and y is noninteger 281 // PoleError: x == 0 and y < 0 282 // RangeError: overflow or underflow 283 case LibFunc::powf: 284 case LibFunc::powl: { 285 if (!LibCallsShrinkWrapDoDomainError || !LibCallsShrinkWrapDoPoleError || 286 !LibCallsShrinkWrapDoRangeError) 287 return false; 288 Cond = generateCondForPow(CI, Func); 289 if (Cond == nullptr) 290 return false; 291 break; 292 } 293 default: 294 return false; 295 } 296 assert(Cond && "performCallErrors should not see an empty condition"); 297 shrinkWrapCI(CI, Cond); 298 return true; 299 } 300 301 // Checks if CI is a candidate for shrinkwrapping and put it into work list if 302 // true. 303 void LibCallsShrinkWrap::checkCandidate(CallInst &CI) { 304 if (CI.isNoBuiltin()) 305 return; 306 // A possible improvement is to handle the calls with the return value being 307 // used. If there is API for fast libcall implementation without setting 308 // errno, we can use the same framework to direct/wrap the call to the fast 309 // API in the error free path, and leave the original call in the slow path. 310 if (!CI.use_empty()) 311 return; 312 313 LibFunc::Func Func; 314 Function *Callee = CI.getCalledFunction(); 315 if (!Callee) 316 return; 317 if (!TLI.getLibFunc(*Callee, Func) || !TLI.has(Func)) 318 return; 319 320 // TODO: Handle long double in other formats. 321 Type *ArgType = CI.getArgOperand(0)->getType(); 322 if (!(ArgType->isFloatTy() || ArgType->isDoubleTy() || 323 ArgType->isX86_FP80Ty())) 324 return; 325 326 WorkList.push_back(&CI); 327 } 328 329 // Generate the upper bound condition for RangeError. 330 Value *LibCallsShrinkWrap::generateOneRangeCond(CallInst *CI, 331 const LibFunc::Func &Func) { 332 float UpperBound; 333 switch (Func) { 334 case LibFunc::expm1: // RangeError: (709, inf) 335 UpperBound = 709.0f; 336 break; 337 case LibFunc::expm1f: // RangeError: (88, inf) 338 UpperBound = 88.0f; 339 break; 340 case LibFunc::expm1l: // RangeError: (11356, inf) 341 UpperBound = 11356.0f; 342 break; 343 default: 344 llvm_unreachable("Should be reach here"); 345 } 346 347 ++NumWrappedOneCond; 348 return createCond(CI, CmpInst::FCMP_OGT, UpperBound); 349 } 350 351 // Generate the lower and upper bound condition for RangeError. 352 Value *LibCallsShrinkWrap::generateTwoRangeCond(CallInst *CI, 353 const LibFunc::Func &Func) { 354 float UpperBound, LowerBound; 355 switch (Func) { 356 case LibFunc::cosh: // RangeError: (x < -710 || x > 710) 357 case LibFunc::sinh: // Same as cosh 358 LowerBound = -710.0f; 359 UpperBound = 710.0f; 360 break; 361 case LibFunc::coshf: // RangeError: (x < -89 || x > 89) 362 case LibFunc::sinhf: // Same as coshf 363 LowerBound = -89.0f; 364 UpperBound = 89.0f; 365 break; 366 case LibFunc::coshl: // RangeError: (x < -11357 || x > 11357) 367 case LibFunc::sinhl: // Same as coshl 368 LowerBound = -11357.0f; 369 UpperBound = 11357.0f; 370 break; 371 case LibFunc::exp: // RangeError: (x < -745 || x > 709) 372 LowerBound = -745.0f; 373 UpperBound = 709.0f; 374 break; 375 case LibFunc::expf: // RangeError: (x < -103 || x > 88) 376 LowerBound = -103.0f; 377 UpperBound = 88.0f; 378 break; 379 case LibFunc::expl: // RangeError: (x < -11399 || x > 11356) 380 LowerBound = -11399.0f; 381 UpperBound = 11356.0f; 382 break; 383 case LibFunc::exp10: // RangeError: (x < -323 || x > 308) 384 LowerBound = -323.0f; 385 UpperBound = 308.0f; 386 break; 387 case LibFunc::exp10f: // RangeError: (x < -45 || x > 38) 388 LowerBound = -45.0f; 389 UpperBound = 38.0f; 390 break; 391 case LibFunc::exp10l: // RangeError: (x < -4950 || x > 4932) 392 LowerBound = -4950.0f; 393 UpperBound = 4932.0f; 394 break; 395 case LibFunc::exp2: // RangeError: (x < -1074 || x > 1023) 396 LowerBound = -1074.0f; 397 UpperBound = 1023.0f; 398 break; 399 case LibFunc::exp2f: // RangeError: (x < -149 || x > 127) 400 LowerBound = -149.0f; 401 UpperBound = 127.0f; 402 break; 403 case LibFunc::exp2l: // RangeError: (x < -16445 || x > 11383) 404 LowerBound = -16445.0f; 405 UpperBound = 11383.0f; 406 break; 407 default: 408 llvm_unreachable("Should be reach here"); 409 } 410 411 ++NumWrappedTwoCond; 412 return createOrCond(CI, CmpInst::FCMP_OGT, UpperBound, CmpInst::FCMP_OLT, 413 LowerBound); 414 } 415 416 // For pow(x,y), We only handle the following cases: 417 // (1) x is a constant && (x >= 1) && (x < MaxUInt8) 418 // Cond is: (y > 127) 419 // (2) x is a value coming from an integer type. 420 // (2.1) if x's bit_size == 8 421 // Cond: (x <= 0 || y > 128) 422 // (2.2) if x's bit_size is 16 423 // Cond: (x <= 0 || y > 64) 424 // (2.3) if x's bit_size is 32 425 // Cond: (x <= 0 || y > 32) 426 // Support for powl(x,y) and powf(x,y) are TBD. 427 // 428 // Note that condition can be more conservative than the actual condition 429 // (i.e. we might invoke the calls that will not set the errno.). 430 // 431 Value *LibCallsShrinkWrap::generateCondForPow(CallInst *CI, 432 const LibFunc::Func &Func) { 433 // FIXME: LibFunc::powf and powl TBD. 434 if (Func != LibFunc::pow) { 435 DEBUG(dbgs() << "Not handled powf() and powl()\n"); 436 return nullptr; 437 } 438 439 Value *Base = CI->getArgOperand(0); 440 Value *Exp = CI->getArgOperand(1); 441 IRBuilder<> BBBuilder(CI); 442 443 // Constant Base case. 444 if (ConstantFP *CF = dyn_cast<ConstantFP>(Base)) { 445 double D = CF->getValueAPF().convertToDouble(); 446 if (D < 1.0f || D > APInt::getMaxValue(8).getZExtValue()) { 447 DEBUG(dbgs() << "Not handled pow(): constant base out of range\n"); 448 return nullptr; 449 } 450 451 ++NumWrappedOneCond; 452 Constant *V = ConstantFP::get(CI->getContext(), APFloat(127.0f)); 453 if (!Exp->getType()->isFloatTy()) 454 V = ConstantExpr::getFPExtend(V, Exp->getType()); 455 return BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V); 456 } 457 458 // If the Base value coming from an integer type. 459 Instruction *I = dyn_cast<Instruction>(Base); 460 if (!I) { 461 DEBUG(dbgs() << "Not handled pow(): FP type base\n"); 462 return nullptr; 463 } 464 unsigned Opcode = I->getOpcode(); 465 if (Opcode == Instruction::UIToFP || Opcode == Instruction::SIToFP) { 466 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits(); 467 float UpperV = 0.0f; 468 if (BW == 8) 469 UpperV = 128.0f; 470 else if (BW == 16) 471 UpperV = 64.0f; 472 else if (BW == 32) 473 UpperV = 32.0f; 474 else { 475 DEBUG(dbgs() << "Not handled pow(): type too wide\n"); 476 return nullptr; 477 } 478 479 ++NumWrappedTwoCond; 480 Constant *V = ConstantFP::get(CI->getContext(), APFloat(UpperV)); 481 Constant *V0 = ConstantFP::get(CI->getContext(), APFloat(0.0f)); 482 if (!Exp->getType()->isFloatTy()) 483 V = ConstantExpr::getFPExtend(V, Exp->getType()); 484 if (!Base->getType()->isFloatTy()) 485 V0 = ConstantExpr::getFPExtend(V0, Exp->getType()); 486 487 Value *Cond = BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V); 488 Value *Cond0 = BBBuilder.CreateFCmp(CmpInst::FCMP_OLE, Base, V0); 489 return BBBuilder.CreateOr(Cond0, Cond); 490 } 491 DEBUG(dbgs() << "Not handled pow(): base not from integer convert\n"); 492 return nullptr; 493 } 494 495 // Wrap conditions that can potentially generate errno to the library call. 496 void LibCallsShrinkWrap::shrinkWrapCI(CallInst *CI, Value *Cond) { 497 assert(Cond != nullptr && "hrinkWrapCI is not expecting an empty call inst"); 498 MDNode *BranchWeights = 499 MDBuilder(CI->getContext()).createBranchWeights(1, 2000); 500 TerminatorInst *NewInst = 501 SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights); 502 BasicBlock *CallBB = NewInst->getParent(); 503 CallBB->setName("cdce.call"); 504 CallBB->getSingleSuccessor()->setName("cdce.end"); 505 CI->removeFromParent(); 506 CallBB->getInstList().insert(CallBB->getFirstInsertionPt(), CI); 507 DEBUG(dbgs() << "== Basic Block After =="); 508 DEBUG(dbgs() << *CallBB->getSinglePredecessor() << *CallBB 509 << *CallBB->getSingleSuccessor() << "\n"); 510 } 511 512 // Perform the transformation to a single candidate. 513 bool LibCallsShrinkWrap::perform(CallInst *CI) { 514 LibFunc::Func Func; 515 Function *Callee = CI->getCalledFunction(); 516 assert(Callee && "perform() should apply to a non-empty callee"); 517 TLI.getLibFunc(*Callee, Func); 518 assert(Func && "perform() is not expecting an empty function"); 519 520 if (LibCallsShrinkWrapDoDomainError && performCallDomainErrorOnly(CI, Func)) 521 return true; 522 523 if (LibCallsShrinkWrapDoRangeError && performCallRangeErrorOnly(CI, Func)) 524 return true; 525 526 return performCallErrors(CI, Func); 527 } 528 529 void LibCallsShrinkWrapLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { 530 AU.setPreservesCFG(); 531 AU.addRequired<TargetLibraryInfoWrapperPass>(); 532 } 533 534 bool runImpl(Function &F, const TargetLibraryInfo &TLI) { 535 if (F.hasFnAttribute(Attribute::OptimizeForSize)) 536 return false; 537 LibCallsShrinkWrap CCDCE(TLI); 538 CCDCE.visit(F); 539 CCDCE.perform(); 540 return CCDCE.isChanged(); 541 } 542 543 bool LibCallsShrinkWrapLegacyPass::runOnFunction(Function &F) { 544 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 545 return runImpl(F, TLI); 546 } 547 548 namespace llvm { 549 char &LibCallsShrinkWrapPassID = LibCallsShrinkWrapLegacyPass::ID; 550 551 // Public interface to LibCallsShrinkWrap pass. 552 FunctionPass *createLibCallsShrinkWrapPass() { 553 return new LibCallsShrinkWrapLegacyPass(); 554 } 555 556 PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F, 557 FunctionAnalysisManager &FAM) { 558 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F); 559 bool Changed = runImpl(F, TLI); 560 if (!Changed) 561 return PreservedAnalyses::all(); 562 return PreservedAnalyses::none(); 563 } 564 } 565