1 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a simple pass that applies a variety of small
11 // optimizations for calls to specific well-known function calls (e.g. runtime
12 // library functions). Any optimization that takes the very simple form
13 // "replace call to library function with simpler code that provides the same
14 // result" belongs in this file.
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "simplify-libcalls"
19 #include "llvm/Transforms/Scalar.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/StringMap.h"
23 #include "llvm/Analysis/ValueTracking.h"
24 #include "llvm/Config/config.h" // FIXME: Shouldn't depend on host!
25 #include "llvm/IR/DataLayout.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/LLVMContext.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include "llvm/Target/TargetLibraryInfo.h"
34 #include "llvm/Transforms/Utils/BuildLibCalls.h"
38 //===----------------------------------------------------------------------===//
39 // Optimizer Base Class
40 //===----------------------------------------------------------------------===//
42 /// This class is the abstract base class for the set of optimizations that
43 /// corresponds to one library call.
45 class LibCallOptimization {
49 const TargetLibraryInfo *TLI;
52 LibCallOptimization() { }
53 virtual ~LibCallOptimization() {}
55 /// CallOptimizer - This pure virtual method is implemented by base classes to
56 /// do various optimizations. If this returns null then no transformation was
57 /// performed. If it returns CI, then it transformed the call and CI is to be
58 /// deleted. If it returns something else, replace CI with the new value and
60 virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
63 Value *OptimizeCall(CallInst *CI, const DataLayout *TD,
64 const TargetLibraryInfo *TLI, IRBuilder<> &B) {
65 Caller = CI->getParent()->getParent();
68 if (CI->getCalledFunction())
69 Context = &CI->getCalledFunction()->getContext();
71 // We never change the calling convention.
72 if (CI->getCallingConv() != llvm::CallingConv::C)
75 return CallOptimizer(CI->getCalledFunction(), CI, B);
78 } // End anonymous namespace.
81 //===----------------------------------------------------------------------===//
82 // SimplifyLibCalls Pass Implementation
83 //===----------------------------------------------------------------------===//
86 /// This pass optimizes well known library functions from libc and libm.
88 class SimplifyLibCalls : public FunctionPass {
89 TargetLibraryInfo *TLI;
91 StringMap<LibCallOptimization*> Optimizations;
93 bool Modified; // This is only used by doInitialization.
95 static char ID; // Pass identification
96 SimplifyLibCalls() : FunctionPass(ID) {
97 initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
99 void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
100 void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
102 void InitOptimizations();
103 bool runOnFunction(Function &F);
105 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
106 AU.addRequired<TargetLibraryInfo>();
109 } // end anonymous namespace.
111 char SimplifyLibCalls::ID = 0;
113 INITIALIZE_PASS_BEGIN(SimplifyLibCalls, "simplify-libcalls",
114 "Simplify well-known library calls", false, false)
115 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
116 INITIALIZE_PASS_END(SimplifyLibCalls, "simplify-libcalls",
117 "Simplify well-known library calls", false, false)
119 // Public interface to the Simplify LibCalls pass.
120 FunctionPass *llvm::createSimplifyLibCallsPass() {
121 return new SimplifyLibCalls();
124 void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
126 Optimizations[TLI->getName(F)] = Opt;
129 void SimplifyLibCalls::AddOpt(LibFunc::Func F1, LibFunc::Func F2,
130 LibCallOptimization* Opt) {
131 if (TLI->has(F1) && TLI->has(F2))
132 Optimizations[TLI->getName(F1)] = Opt;
135 /// Optimizations - Populate the Optimizations map with all the optimizations
137 void SimplifyLibCalls::InitOptimizations() {
141 /// runOnFunction - Top level algorithm.
143 bool SimplifyLibCalls::runOnFunction(Function &F) {
144 TLI = &getAnalysis<TargetLibraryInfo>();
146 if (Optimizations.empty())
149 const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
151 IRBuilder<> Builder(F.getContext());
153 bool Changed = false;
154 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
155 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
157 CallInst *CI = dyn_cast<CallInst>(I++);
158 if (!CI || CI->hasFnAttr(Attribute::NoBuiltin)) continue;
160 // Ignore indirect calls and calls to non-external functions.
161 Function *Callee = CI->getCalledFunction();
162 if (Callee == 0 || !Callee->isDeclaration() ||
163 !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
166 // Ignore unknown calls.
167 LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
170 // Set the builder to the instruction after the call.
171 Builder.SetInsertPoint(BB, I);
173 // Use debug location of CI for all new instructions.
174 Builder.SetCurrentDebugLocation(CI->getDebugLoc());
176 // Try to optimize this call.
177 Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
178 if (Result == 0) continue;
180 DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
181 dbgs() << " into: " << *Result << "\n");
183 // Something changed!
186 // Inspect the instruction after the call (which was potentially just
190 if (CI != Result && !CI->use_empty()) {
191 CI->replaceAllUsesWith(Result);
192 if (!Result->hasName())
193 Result->takeName(CI);
195 CI->eraseFromParent();
202 // Additional cases that we need to add to this file:
205 // * cbrt(expN(X)) -> expN(x/3)
206 // * cbrt(sqrt(x)) -> pow(x,1/6)
207 // * cbrt(sqrt(x)) -> pow(x,1/9)
210 // * exp(log(x)) -> x
213 // * log(exp(x)) -> x
214 // * log(x**y) -> y*log(x)
215 // * log(exp(y)) -> y*log(e)
216 // * log(exp2(y)) -> y*log(2)
217 // * log(exp10(y)) -> y*log(10)
218 // * log(sqrt(x)) -> 0.5*log(x)
219 // * log(pow(x,y)) -> y*log(x)
221 // lround, lroundf, lroundl:
222 // * lround(cnst) -> cnst'
225 // * pow(exp(x),y) -> exp(x*y)
226 // * pow(sqrt(x),y) -> pow(x,y*0.5)
227 // * pow(pow(x,y),z)-> pow(x,y*z)
229 // round, roundf, roundl:
230 // * round(cnst) -> cnst'
233 // * signbit(cnst) -> cnst'
234 // * signbit(nncst) -> 0 (if pstv is a non-negative constant)
236 // sqrt, sqrtf, sqrtl:
237 // * sqrt(expN(x)) -> expN(x*0.5)
238 // * sqrt(Nroot(x)) -> pow(x,1/(2*N))
239 // * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
242 // * strchr(p, 0) -> strlen(p)
244 // * tan(atan(x)) -> x
246 // trunc, truncf, truncl:
247 // * trunc(cnst) -> cnst'