diff options
Diffstat (limited to 'llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp')
-rw-r--r-- | llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp | 561 |
1 files changed, 561 insertions, 0 deletions
diff --git a/llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp b/llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp new file mode 100644 index 000000000000..ed28fffc22b5 --- /dev/null +++ b/llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp @@ -0,0 +1,561 @@ +//===-- LibCallsShrinkWrap.cpp ----------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This pass shrink-wraps a call to function if the result is not used. +// The call can set errno but is otherwise side effect free. For example: +// sqrt(val); +// is transformed to +// if (val < 0) +// sqrt(val); +// Even if the result of library call is not being used, the compiler cannot +// safely delete the call because the function can set errno on error +// conditions. +// Note in many functions, the error condition solely depends on the incoming +// parameter. In this optimization, we can generate the condition can lead to +// the errno to shrink-wrap the call. Since the chances of hitting the error +// condition is low, the runtime call is effectively eliminated. +// +// These partially dead calls are usually results of C++ abstraction penalty +// exposed by inlining. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/LibCallsShrinkWrap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstVisitor.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/MDBuilder.h" +#include "llvm/Pass.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +using namespace llvm; + +#define DEBUG_TYPE "libcalls-shrinkwrap" + +STATISTIC(NumWrappedOneCond, "Number of One-Condition Wrappers Inserted"); +STATISTIC(NumWrappedTwoCond, "Number of Two-Condition Wrappers Inserted"); + +namespace { +class LibCallsShrinkWrapLegacyPass : public FunctionPass { +public: + static char ID; // Pass identification, replacement for typeid + explicit LibCallsShrinkWrapLegacyPass() : FunctionPass(ID) { + initializeLibCallsShrinkWrapLegacyPassPass( + *PassRegistry::getPassRegistry()); + } + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnFunction(Function &F) override; +}; +} + +char LibCallsShrinkWrapLegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap", + "Conditionally eliminate dead library calls", false, + false) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_END(LibCallsShrinkWrapLegacyPass, "libcalls-shrinkwrap", + "Conditionally eliminate dead library calls", false, false) + +namespace { +class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> { +public: + LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DominatorTree *DT) + : TLI(TLI), DT(DT){}; + void visitCallInst(CallInst &CI) { checkCandidate(CI); } + bool perform() { + bool Changed = false; + for (auto &CI : WorkList) { + LLVM_DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName() + << "\n"); + if (perform(CI)) { + Changed = true; + LLVM_DEBUG(dbgs() << "Transformed\n"); + } + } + return Changed; + } + +private: + bool perform(CallInst *CI); + void checkCandidate(CallInst &CI); + void shrinkWrapCI(CallInst *CI, Value *Cond); + bool performCallDomainErrorOnly(CallInst *CI, const LibFunc &Func); + bool performCallErrors(CallInst *CI, const LibFunc &Func); + bool performCallRangeErrorOnly(CallInst *CI, const LibFunc &Func); + Value *generateOneRangeCond(CallInst *CI, const LibFunc &Func); + Value *generateTwoRangeCond(CallInst *CI, const LibFunc &Func); + Value *generateCondForPow(CallInst *CI, const LibFunc &Func); + + // Create an OR of two conditions. + Value *createOrCond(CallInst *CI, CmpInst::Predicate Cmp, float Val, + CmpInst::Predicate Cmp2, float Val2) { + IRBuilder<> BBBuilder(CI); + Value *Arg = CI->getArgOperand(0); + auto Cond2 = createCond(BBBuilder, Arg, Cmp2, Val2); + auto Cond1 = createCond(BBBuilder, Arg, Cmp, Val); + return BBBuilder.CreateOr(Cond1, Cond2); + } + + // Create a single condition using IRBuilder. + Value *createCond(IRBuilder<> &BBBuilder, Value *Arg, CmpInst::Predicate Cmp, + float Val) { + Constant *V = ConstantFP::get(BBBuilder.getContext(), APFloat(Val)); + if (!Arg->getType()->isFloatTy()) + V = ConstantExpr::getFPExtend(V, Arg->getType()); + return BBBuilder.CreateFCmp(Cmp, Arg, V); + } + + // Create a single condition. + Value *createCond(CallInst *CI, CmpInst::Predicate Cmp, float Val) { + IRBuilder<> BBBuilder(CI); + Value *Arg = CI->getArgOperand(0); + return createCond(BBBuilder, Arg, Cmp, Val); + } + + const TargetLibraryInfo &TLI; + DominatorTree *DT; + SmallVector<CallInst *, 16> WorkList; +}; +} // end anonymous namespace + +// Perform the transformation to calls with errno set by domain error. +bool LibCallsShrinkWrap::performCallDomainErrorOnly(CallInst *CI, + const LibFunc &Func) { + Value *Cond = nullptr; + + switch (Func) { + case LibFunc_acos: // DomainError: (x < -1 || x > 1) + case LibFunc_acosf: // Same as acos + case LibFunc_acosl: // Same as acos + case LibFunc_asin: // DomainError: (x < -1 || x > 1) + case LibFunc_asinf: // Same as asin + case LibFunc_asinl: // Same as asin + { + ++NumWrappedTwoCond; + Cond = createOrCond(CI, CmpInst::FCMP_OLT, -1.0f, CmpInst::FCMP_OGT, 1.0f); + break; + } + case LibFunc_cos: // DomainError: (x == +inf || x == -inf) + case LibFunc_cosf: // Same as cos + case LibFunc_cosl: // Same as cos + case LibFunc_sin: // DomainError: (x == +inf || x == -inf) + case LibFunc_sinf: // Same as sin + case LibFunc_sinl: // Same as sin + { + ++NumWrappedTwoCond; + Cond = createOrCond(CI, CmpInst::FCMP_OEQ, INFINITY, CmpInst::FCMP_OEQ, + -INFINITY); + break; + } + case LibFunc_acosh: // DomainError: (x < 1) + case LibFunc_acoshf: // Same as acosh + case LibFunc_acoshl: // Same as acosh + { + ++NumWrappedOneCond; + Cond = createCond(CI, CmpInst::FCMP_OLT, 1.0f); + break; + } + case LibFunc_sqrt: // DomainError: (x < 0) + case LibFunc_sqrtf: // Same as sqrt + case LibFunc_sqrtl: // Same as sqrt + { + ++NumWrappedOneCond; + Cond = createCond(CI, CmpInst::FCMP_OLT, 0.0f); + break; + } + default: + return false; + } + shrinkWrapCI(CI, Cond); + return true; +} + +// Perform the transformation to calls with errno set by range error. +bool LibCallsShrinkWrap::performCallRangeErrorOnly(CallInst *CI, + const LibFunc &Func) { + Value *Cond = nullptr; + + switch (Func) { + case LibFunc_cosh: + case LibFunc_coshf: + case LibFunc_coshl: + case LibFunc_exp: + case LibFunc_expf: + case LibFunc_expl: + case LibFunc_exp10: + case LibFunc_exp10f: + case LibFunc_exp10l: + case LibFunc_exp2: + case LibFunc_exp2f: + case LibFunc_exp2l: + case LibFunc_sinh: + case LibFunc_sinhf: + case LibFunc_sinhl: { + Cond = generateTwoRangeCond(CI, Func); + break; + } + case LibFunc_expm1: // RangeError: (709, inf) + case LibFunc_expm1f: // RangeError: (88, inf) + case LibFunc_expm1l: // RangeError: (11356, inf) + { + Cond = generateOneRangeCond(CI, Func); + break; + } + default: + return false; + } + shrinkWrapCI(CI, Cond); + return true; +} + +// Perform the transformation to calls with errno set by combination of errors. +bool LibCallsShrinkWrap::performCallErrors(CallInst *CI, + const LibFunc &Func) { + Value *Cond = nullptr; + + switch (Func) { + case LibFunc_atanh: // DomainError: (x < -1 || x > 1) + // PoleError: (x == -1 || x == 1) + // Overall Cond: (x <= -1 || x >= 1) + case LibFunc_atanhf: // Same as atanh + case LibFunc_atanhl: // Same as atanh + { + ++NumWrappedTwoCond; + Cond = createOrCond(CI, CmpInst::FCMP_OLE, -1.0f, CmpInst::FCMP_OGE, 1.0f); + break; + } + case LibFunc_log: // DomainError: (x < 0) + // PoleError: (x == 0) + // Overall Cond: (x <= 0) + case LibFunc_logf: // Same as log + case LibFunc_logl: // Same as log + case LibFunc_log10: // Same as log + case LibFunc_log10f: // Same as log + case LibFunc_log10l: // Same as log + case LibFunc_log2: // Same as log + case LibFunc_log2f: // Same as log + case LibFunc_log2l: // Same as log + case LibFunc_logb: // Same as log + case LibFunc_logbf: // Same as log + case LibFunc_logbl: // Same as log + { + ++NumWrappedOneCond; + Cond = createCond(CI, CmpInst::FCMP_OLE, 0.0f); + break; + } + case LibFunc_log1p: // DomainError: (x < -1) + // PoleError: (x == -1) + // Overall Cond: (x <= -1) + case LibFunc_log1pf: // Same as log1p + case LibFunc_log1pl: // Same as log1p + { + ++NumWrappedOneCond; + Cond = createCond(CI, CmpInst::FCMP_OLE, -1.0f); + break; + } + case LibFunc_pow: // DomainError: x < 0 and y is noninteger + // PoleError: x == 0 and y < 0 + // RangeError: overflow or underflow + case LibFunc_powf: + case LibFunc_powl: { + Cond = generateCondForPow(CI, Func); + if (Cond == nullptr) + return false; + break; + } + default: + return false; + } + assert(Cond && "performCallErrors should not see an empty condition"); + shrinkWrapCI(CI, Cond); + return true; +} + +// Checks if CI is a candidate for shrinkwrapping and put it into work list if +// true. +void LibCallsShrinkWrap::checkCandidate(CallInst &CI) { + if (CI.isNoBuiltin()) + return; + // A possible improvement is to handle the calls with the return value being + // used. If there is API for fast libcall implementation without setting + // errno, we can use the same framework to direct/wrap the call to the fast + // API in the error free path, and leave the original call in the slow path. + if (!CI.use_empty()) + return; + + LibFunc Func; + Function *Callee = CI.getCalledFunction(); + if (!Callee) + return; + if (!TLI.getLibFunc(*Callee, Func) || !TLI.has(Func)) + return; + + if (CI.getNumArgOperands() == 0) + return; + // TODO: Handle long double in other formats. + Type *ArgType = CI.getArgOperand(0)->getType(); + if (!(ArgType->isFloatTy() || ArgType->isDoubleTy() || + ArgType->isX86_FP80Ty())) + return; + + WorkList.push_back(&CI); +} + +// Generate the upper bound condition for RangeError. +Value *LibCallsShrinkWrap::generateOneRangeCond(CallInst *CI, + const LibFunc &Func) { + float UpperBound; + switch (Func) { + case LibFunc_expm1: // RangeError: (709, inf) + UpperBound = 709.0f; + break; + case LibFunc_expm1f: // RangeError: (88, inf) + UpperBound = 88.0f; + break; + case LibFunc_expm1l: // RangeError: (11356, inf) + UpperBound = 11356.0f; + break; + default: + llvm_unreachable("Unhandled library call!"); + } + + ++NumWrappedOneCond; + return createCond(CI, CmpInst::FCMP_OGT, UpperBound); +} + +// Generate the lower and upper bound condition for RangeError. +Value *LibCallsShrinkWrap::generateTwoRangeCond(CallInst *CI, + const LibFunc &Func) { + float UpperBound, LowerBound; + switch (Func) { + case LibFunc_cosh: // RangeError: (x < -710 || x > 710) + case LibFunc_sinh: // Same as cosh + LowerBound = -710.0f; + UpperBound = 710.0f; + break; + case LibFunc_coshf: // RangeError: (x < -89 || x > 89) + case LibFunc_sinhf: // Same as coshf + LowerBound = -89.0f; + UpperBound = 89.0f; + break; + case LibFunc_coshl: // RangeError: (x < -11357 || x > 11357) + case LibFunc_sinhl: // Same as coshl + LowerBound = -11357.0f; + UpperBound = 11357.0f; + break; + case LibFunc_exp: // RangeError: (x < -745 || x > 709) + LowerBound = -745.0f; + UpperBound = 709.0f; + break; + case LibFunc_expf: // RangeError: (x < -103 || x > 88) + LowerBound = -103.0f; + UpperBound = 88.0f; + break; + case LibFunc_expl: // RangeError: (x < -11399 || x > 11356) + LowerBound = -11399.0f; + UpperBound = 11356.0f; + break; + case LibFunc_exp10: // RangeError: (x < -323 || x > 308) + LowerBound = -323.0f; + UpperBound = 308.0f; + break; + case LibFunc_exp10f: // RangeError: (x < -45 || x > 38) + LowerBound = -45.0f; + UpperBound = 38.0f; + break; + case LibFunc_exp10l: // RangeError: (x < -4950 || x > 4932) + LowerBound = -4950.0f; + UpperBound = 4932.0f; + break; + case LibFunc_exp2: // RangeError: (x < -1074 || x > 1023) + LowerBound = -1074.0f; + UpperBound = 1023.0f; + break; + case LibFunc_exp2f: // RangeError: (x < -149 || x > 127) + LowerBound = -149.0f; + UpperBound = 127.0f; + break; + case LibFunc_exp2l: // RangeError: (x < -16445 || x > 11383) + LowerBound = -16445.0f; + UpperBound = 11383.0f; + break; + default: + llvm_unreachable("Unhandled library call!"); + } + + ++NumWrappedTwoCond; + return createOrCond(CI, CmpInst::FCMP_OGT, UpperBound, CmpInst::FCMP_OLT, + LowerBound); +} + +// For pow(x,y), We only handle the following cases: +// (1) x is a constant && (x >= 1) && (x < MaxUInt8) +// Cond is: (y > 127) +// (2) x is a value coming from an integer type. +// (2.1) if x's bit_size == 8 +// Cond: (x <= 0 || y > 128) +// (2.2) if x's bit_size is 16 +// Cond: (x <= 0 || y > 64) +// (2.3) if x's bit_size is 32 +// Cond: (x <= 0 || y > 32) +// Support for powl(x,y) and powf(x,y) are TBD. +// +// Note that condition can be more conservative than the actual condition +// (i.e. we might invoke the calls that will not set the errno.). +// +Value *LibCallsShrinkWrap::generateCondForPow(CallInst *CI, + const LibFunc &Func) { + // FIXME: LibFunc_powf and powl TBD. + if (Func != LibFunc_pow) { + LLVM_DEBUG(dbgs() << "Not handled powf() and powl()\n"); + return nullptr; + } + + Value *Base = CI->getArgOperand(0); + Value *Exp = CI->getArgOperand(1); + IRBuilder<> BBBuilder(CI); + + // Constant Base case. + if (ConstantFP *CF = dyn_cast<ConstantFP>(Base)) { + double D = CF->getValueAPF().convertToDouble(); + if (D < 1.0f || D > APInt::getMaxValue(8).getZExtValue()) { + LLVM_DEBUG(dbgs() << "Not handled pow(): constant base out of range\n"); + return nullptr; + } + + ++NumWrappedOneCond; + Constant *V = ConstantFP::get(CI->getContext(), APFloat(127.0f)); + if (!Exp->getType()->isFloatTy()) + V = ConstantExpr::getFPExtend(V, Exp->getType()); + return BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V); + } + + // If the Base value coming from an integer type. + Instruction *I = dyn_cast<Instruction>(Base); + if (!I) { + LLVM_DEBUG(dbgs() << "Not handled pow(): FP type base\n"); + return nullptr; + } + unsigned Opcode = I->getOpcode(); + if (Opcode == Instruction::UIToFP || Opcode == Instruction::SIToFP) { + unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits(); + float UpperV = 0.0f; + if (BW == 8) + UpperV = 128.0f; + else if (BW == 16) + UpperV = 64.0f; + else if (BW == 32) + UpperV = 32.0f; + else { + LLVM_DEBUG(dbgs() << "Not handled pow(): type too wide\n"); + return nullptr; + } + + ++NumWrappedTwoCond; + Constant *V = ConstantFP::get(CI->getContext(), APFloat(UpperV)); + Constant *V0 = ConstantFP::get(CI->getContext(), APFloat(0.0f)); + if (!Exp->getType()->isFloatTy()) + V = ConstantExpr::getFPExtend(V, Exp->getType()); + if (!Base->getType()->isFloatTy()) + V0 = ConstantExpr::getFPExtend(V0, Exp->getType()); + + Value *Cond = BBBuilder.CreateFCmp(CmpInst::FCMP_OGT, Exp, V); + Value *Cond0 = BBBuilder.CreateFCmp(CmpInst::FCMP_OLE, Base, V0); + return BBBuilder.CreateOr(Cond0, Cond); + } + LLVM_DEBUG(dbgs() << "Not handled pow(): base not from integer convert\n"); + return nullptr; +} + +// Wrap conditions that can potentially generate errno to the library call. +void LibCallsShrinkWrap::shrinkWrapCI(CallInst *CI, Value *Cond) { + assert(Cond != nullptr && "ShrinkWrapCI is not expecting an empty call inst"); + MDNode *BranchWeights = + MDBuilder(CI->getContext()).createBranchWeights(1, 2000); + + Instruction *NewInst = + SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights, DT); + BasicBlock *CallBB = NewInst->getParent(); + CallBB->setName("cdce.call"); + BasicBlock *SuccBB = CallBB->getSingleSuccessor(); + assert(SuccBB && "The split block should have a single successor"); + SuccBB->setName("cdce.end"); + CI->removeFromParent(); + CallBB->getInstList().insert(CallBB->getFirstInsertionPt(), CI); + LLVM_DEBUG(dbgs() << "== Basic Block After =="); + LLVM_DEBUG(dbgs() << *CallBB->getSinglePredecessor() << *CallBB + << *CallBB->getSingleSuccessor() << "\n"); +} + +// Perform the transformation to a single candidate. +bool LibCallsShrinkWrap::perform(CallInst *CI) { + LibFunc Func; + Function *Callee = CI->getCalledFunction(); + assert(Callee && "perform() should apply to a non-empty callee"); + TLI.getLibFunc(*Callee, Func); + assert(Func && "perform() is not expecting an empty function"); + + if (performCallDomainErrorOnly(CI, Func) || performCallRangeErrorOnly(CI, Func)) + return true; + return performCallErrors(CI, Func); +} + +void LibCallsShrinkWrapLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addPreserved<DominatorTreeWrapperPass>(); + AU.addPreserved<GlobalsAAWrapperPass>(); + AU.addRequired<TargetLibraryInfoWrapperPass>(); +} + +static bool runImpl(Function &F, const TargetLibraryInfo &TLI, + DominatorTree *DT) { + if (F.hasFnAttribute(Attribute::OptimizeForSize)) + return false; + LibCallsShrinkWrap CCDCE(TLI, DT); + CCDCE.visit(F); + bool Changed = CCDCE.perform(); + +// Verify the dominator after we've updated it locally. + assert(!DT || DT->verify(DominatorTree::VerificationLevel::Fast)); + return Changed; +} + +bool LibCallsShrinkWrapLegacyPass::runOnFunction(Function &F) { + auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); + auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); + auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; + return runImpl(F, TLI, DT); +} + +namespace llvm { +char &LibCallsShrinkWrapPassID = LibCallsShrinkWrapLegacyPass::ID; + +// Public interface to LibCallsShrinkWrap pass. +FunctionPass *createLibCallsShrinkWrapPass() { + return new LibCallsShrinkWrapLegacyPass(); +} + +PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F, + FunctionAnalysisManager &FAM) { + auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F); + auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F); + if (!runImpl(F, TLI, DT)) + return PreservedAnalyses::all(); + auto PA = PreservedAnalyses(); + PA.preserve<GlobalsAA>(); + PA.preserve<DominatorTreeAnalysis>(); + return PA; +} +} |