lib/Transforms/Scalar/SimplifyLibCalls.cpp

   1 //===- SimplifyLibCalls.cpp - Optimize specific well-known library calls --===//
   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 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.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  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"
  35 using namespace llvm;
  36
  37
  38 //===----------------------------------------------------------------------===//
  39 // Optimizer Base Class
  40 //===----------------------------------------------------------------------===//
  41
  42 /// This class is the abstract base class for the set of optimizations that
  43 /// corresponds to one library call.
  44 namespace {
  45 class LibCallOptimization {
  46 protected:
  47   Function *Caller;
  48   const DataLayout *TD;
  49   const TargetLibraryInfo *TLI;
  50   LLVMContext* Context;
  51 public:
  52   LibCallOptimization() { }
  53   virtual ~LibCallOptimization() {}
  54
  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
  59   /// delete CI.
  60   virtual Value *CallOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B)
  61     =0;
  62
  63   Value *OptimizeCall(CallInst *CI, const DataLayout *TD,
  64                       const TargetLibraryInfo *TLI, IRBuilder<> &B) {
  65     Caller = CI->getParent()->getParent();
  66     this->TD = TD;
  67     this->TLI = TLI;
  68     if (CI->getCalledFunction())
  69       Context = &CI->getCalledFunction()->getContext();
  70
  71     // We never change the calling convention.
  72     if (CI->getCallingConv() != llvm::CallingConv::C)
  73       return NULL;
  74
  75     return CallOptimizer(CI->getCalledFunction(), CI, B);
  76   }
  77 };
  78 } // End anonymous namespace.
  79
  80
  81 //===----------------------------------------------------------------------===//
  82 // SimplifyLibCalls Pass Implementation
  83 //===----------------------------------------------------------------------===//
  84
  85 namespace {
  86   /// This pass optimizes well known library functions from libc and libm.
  87   ///
  88   class SimplifyLibCalls : public FunctionPass {
  89     TargetLibraryInfo *TLI;
  90
  91     StringMap<LibCallOptimization*> Optimizations;
  92
  93     bool Modified;  // This is only used by doInitialization.
  94   public:
  95     static char ID; // Pass identification
  96     SimplifyLibCalls() : FunctionPass(ID) {
  97       initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
  98     }
  99     void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
 100     void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
 101
 102     void InitOptimizations();
 103     bool runOnFunction(Function &F);
 104
 105     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 106       AU.addRequired<TargetLibraryInfo>();
 107     }
 108   };
 109 } // end anonymous namespace.
 110
 111 char SimplifyLibCalls::ID = 0;
 112
 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)
 118
 119 // Public interface to the Simplify LibCalls pass.
 120 FunctionPass *llvm::createSimplifyLibCallsPass() {
 121   return new SimplifyLibCalls();
 122 }
 123
 124 void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
 125   if (TLI->has(F))
 126     Optimizations[TLI->getName(F)] = Opt;
 127 }
 128
 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;
 133 }
 134
 135 /// Optimizations - Populate the Optimizations map with all the optimizations
 136 /// we know.
 137 void SimplifyLibCalls::InitOptimizations() {
 138 }
 139
 140
 141 /// runOnFunction - Top level algorithm.
 142 ///
 143 bool SimplifyLibCalls::runOnFunction(Function &F) {
 144   TLI = &getAnalysis<TargetLibraryInfo>();
 145
 146   if (Optimizations.empty())
 147     InitOptimizations();
 148
 149   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
 150
 151   IRBuilder<> Builder(F.getContext());
 152
 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; ) {
 156       // Ignore non-calls.
 157       CallInst *CI = dyn_cast<CallInst>(I++);
 158       if (!CI || CI->hasFnAttr(Attribute::NoBuiltin)) continue;
 159
 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()))
 164         continue;
 165
 166       // Ignore unknown calls.
 167       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
 168       if (!LCO) continue;
 169
 170       // Set the builder to the instruction after the call.
 171       Builder.SetInsertPoint(BB, I);
 172
 173       // Use debug location of CI for all new instructions.
 174       Builder.SetCurrentDebugLocation(CI->getDebugLoc());
 175
 176       // Try to optimize this call.
 177       Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
 178       if (Result == 0) continue;
 179
 180       DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
 181             dbgs() << "  into: " << *Result << "\n");
 182
 183       // Something changed!
 184       Changed = true;
 185
 186       // Inspect the instruction after the call (which was potentially just
 187       // added) next.
 188       I = CI; ++I;
 189
 190       if (CI != Result && !CI->use_empty()) {
 191         CI->replaceAllUsesWith(Result);
 192         if (!Result->hasName())
 193           Result->takeName(CI);
 194       }
 195       CI->eraseFromParent();
 196     }
 197   }
 198   return Changed;
 199 }
 200
 201 // TODO:
 202 //   Additional cases that we need to add to this file:
 203 //
 204 // cbrt:
 205 //   * cbrt(expN(X))  -> expN(x/3)
 206 //   * cbrt(sqrt(x))  -> pow(x,1/6)
 207 //   * cbrt(sqrt(x))  -> pow(x,1/9)
 208 //
 209 // exp, expf, expl:
 210 //   * exp(log(x))  -> x
 211 //
 212 // log, logf, logl:
 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)
 220 //
 221 // lround, lroundf, lroundl:
 222 //   * lround(cnst) -> cnst'
 223 //
 224 // pow, powf, powl:
 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)
 228 //
 229 // round, roundf, roundl:
 230 //   * round(cnst) -> cnst'
 231 //
 232 // signbit:
 233 //   * signbit(cnst) -> cnst'
 234 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
 235 //
 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)
 240 //
 241 // strchr:
 242 //   * strchr(p, 0) -> strlen(p)
 243 // tan, tanf, tanl:
 244 //   * tan(atan(x)) -> x
 245 //
 246 // trunc, truncf, truncl:
 247 //   * trunc(cnst) -> cnst'
 248 //
 249 //