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 static char ID; // Pass identification
94 SimplifyLibCalls() : FunctionPass(ID) {
95 initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
97 void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
98 void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
100 void InitOptimizations();
101 bool runOnFunction(Function &F);
103 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
104 AU.addRequired<TargetLibraryInfo>();
107 } // end anonymous namespace.
109 char SimplifyLibCalls::ID = 0;
111 INITIALIZE_PASS_BEGIN(SimplifyLibCalls, "simplify-libcalls",
112 "Simplify well-known library calls", false, false)
113 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
114 INITIALIZE_PASS_END(SimplifyLibCalls, "simplify-libcalls",
115 "Simplify well-known library calls", false, false)
117 // Public interface to the Simplify LibCalls pass.
118 FunctionPass *llvm::createSimplifyLibCallsPass() {
119 return new SimplifyLibCalls();
122 void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
124 Optimizations[TLI->getName(F)] = Opt;
127 void SimplifyLibCalls::AddOpt(LibFunc::Func F1, LibFunc::Func F2,
128 LibCallOptimization* Opt) {
129 if (TLI->has(F1) && TLI->has(F2))
130 Optimizations[TLI->getName(F1)] = Opt;
133 /// Optimizations - Populate the Optimizations map with all the optimizations
135 void SimplifyLibCalls::InitOptimizations() {
139 /// runOnFunction - Top level algorithm.
141 bool SimplifyLibCalls::runOnFunction(Function &F) {
142 TLI = &getAnalysis<TargetLibraryInfo>();
144 if (Optimizations.empty())
147 const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
149 IRBuilder<> Builder(F.getContext());
151 bool Changed = false;
152 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
153 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
155 CallInst *CI = dyn_cast<CallInst>(I++);
156 if (!CI || CI->hasFnAttr(Attribute::NoBuiltin)) continue;
158 // Ignore indirect calls and calls to non-external functions.
159 Function *Callee = CI->getCalledFunction();
160 if (Callee == 0 || !Callee->isDeclaration() ||
161 !(Callee->hasExternalLinkage() || Callee->hasDLLImportLinkage()))
164 // Ignore unknown calls.
165 LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
168 // Set the builder to the instruction after the call.
169 Builder.SetInsertPoint(BB, I);
171 // Use debug location of CI for all new instructions.
172 Builder.SetCurrentDebugLocation(CI->getDebugLoc());
174 // Try to optimize this call.
175 Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
176 if (Result == 0) continue;
178 DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
179 dbgs() << " into: " << *Result << "\n");
181 // Something changed!
184 // Inspect the instruction after the call (which was potentially just
188 if (CI != Result && !CI->use_empty()) {
189 CI->replaceAllUsesWith(Result);
190 if (!Result->hasName())
191 Result->takeName(CI);
193 CI->eraseFromParent();
200 // Additional cases that we need to add to this file:
203 // * cbrt(expN(X)) -> expN(x/3)
204 // * cbrt(sqrt(x)) -> pow(x,1/6)
205 // * cbrt(sqrt(x)) -> pow(x,1/9)
208 // * exp(log(x)) -> x
211 // * log(exp(x)) -> x
212 // * log(x**y) -> y*log(x)
213 // * log(exp(y)) -> y*log(e)
214 // * log(exp2(y)) -> y*log(2)
215 // * log(exp10(y)) -> y*log(10)
216 // * log(sqrt(x)) -> 0.5*log(x)
217 // * log(pow(x,y)) -> y*log(x)
219 // lround, lroundf, lroundl:
220 // * lround(cnst) -> cnst'
223 // * pow(exp(x),y) -> exp(x*y)
224 // * pow(sqrt(x),y) -> pow(x,y*0.5)
225 // * pow(pow(x,y),z)-> pow(x,y*z)
227 // round, roundf, roundl:
228 // * round(cnst) -> cnst'
231 // * signbit(cnst) -> cnst'
232 // * signbit(nncst) -> 0 (if pstv is a non-negative constant)
234 // sqrt, sqrtf, sqrtl:
235 // * sqrt(expN(x)) -> expN(x*0.5)
236 // * sqrt(Nroot(x)) -> pow(x,1/(2*N))
237 // * sqrt(pow(x,y)) -> pow(|x|,y*0.5)
240 // * strchr(p, 0) -> strlen(p)
242 // * tan(atan(x)) -> x
244 // trunc, truncf, truncl:
245 // * trunc(cnst) -> cnst'