contrib/llvm/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   public:
  93     static char ID; // Pass identification
  94     SimplifyLibCalls() : FunctionPass(ID) {
  95       initializeSimplifyLibCallsPass(*PassRegistry::getPassRegistry());
  96     }
  97     void AddOpt(LibFunc::Func F, LibCallOptimization* Opt);
  98     void AddOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
  99
 100     void InitOptimizations();
 101     bool runOnFunction(Function &F);
 102
 103     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 104       AU.addRequired<TargetLibraryInfo>();
 105     }
 106   };
 107 } // end anonymous namespace.
 108
 109 char SimplifyLibCalls::ID = 0;
 110
 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)
 116
 117 // Public interface to the Simplify LibCalls pass.
 118 FunctionPass *llvm::createSimplifyLibCallsPass() {
 119   return new SimplifyLibCalls();
 120 }
 121
 122 void SimplifyLibCalls::AddOpt(LibFunc::Func F, LibCallOptimization* Opt) {
 123   if (TLI->has(F))
 124     Optimizations[TLI->getName(F)] = Opt;
 125 }
 126
 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;
 131 }
 132
 133 /// Optimizations - Populate the Optimizations map with all the optimizations
 134 /// we know.
 135 void SimplifyLibCalls::InitOptimizations() {
 136 }
 137
 138
 139 /// runOnFunction - Top level algorithm.
 140 ///
 141 bool SimplifyLibCalls::runOnFunction(Function &F) {
 142   TLI = &getAnalysis<TargetLibraryInfo>();
 143
 144   if (Optimizations.empty())
 145     InitOptimizations();
 146
 147   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
 148
 149   IRBuilder<> Builder(F.getContext());
 150
 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; ) {
 154       // Ignore non-calls.
 155       CallInst *CI = dyn_cast<CallInst>(I++);
 156       if (!CI || CI->hasFnAttr(Attribute::NoBuiltin)) continue;
 157
 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()))
 162         continue;
 163
 164       // Ignore unknown calls.
 165       LibCallOptimization *LCO = Optimizations.lookup(Callee->getName());
 166       if (!LCO) continue;
 167
 168       // Set the builder to the instruction after the call.
 169       Builder.SetInsertPoint(BB, I);
 170
 171       // Use debug location of CI for all new instructions.
 172       Builder.SetCurrentDebugLocation(CI->getDebugLoc());
 173
 174       // Try to optimize this call.
 175       Value *Result = LCO->OptimizeCall(CI, TD, TLI, Builder);
 176       if (Result == 0) continue;
 177
 178       DEBUG(dbgs() << "SimplifyLibCalls simplified: " << *CI;
 179             dbgs() << "  into: " << *Result << "\n");
 180
 181       // Something changed!
 182       Changed = true;
 183
 184       // Inspect the instruction after the call (which was potentially just
 185       // added) next.
 186       I = CI; ++I;
 187
 188       if (CI != Result && !CI->use_empty()) {
 189         CI->replaceAllUsesWith(Result);
 190         if (!Result->hasName())
 191           Result->takeName(CI);
 192       }
 193       CI->eraseFromParent();
 194     }
 195   }
 196   return Changed;
 197 }
 198
 199 // TODO:
 200 //   Additional cases that we need to add to this file:
 201 //
 202 // cbrt:
 203 //   * cbrt(expN(X))  -> expN(x/3)
 204 //   * cbrt(sqrt(x))  -> pow(x,1/6)
 205 //   * cbrt(sqrt(x))  -> pow(x,1/9)
 206 //
 207 // exp, expf, expl:
 208 //   * exp(log(x))  -> x
 209 //
 210 // log, logf, logl:
 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)
 218 //
 219 // lround, lroundf, lroundl:
 220 //   * lround(cnst) -> cnst'
 221 //
 222 // pow, powf, powl:
 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)
 226 //
 227 // round, roundf, roundl:
 228 //   * round(cnst) -> cnst'
 229 //
 230 // signbit:
 231 //   * signbit(cnst) -> cnst'
 232 //   * signbit(nncst) -> 0 (if pstv is a non-negative constant)
 233 //
 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)
 238 //
 239 // strchr:
 240 //   * strchr(p, 0) -> strlen(p)
 241 // tan, tanf, tanl:
 242 //   * tan(atan(x)) -> x
 243 //
 244 // trunc, truncf, truncl:
 245 //   * trunc(cnst) -> cnst'
 246 //
 247 //