lib/Transforms/IPO/PartialSpecialization.cpp

   1 //===-- PartialSpecialization.cpp - Specialize for common constants--------===//
   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 pass finds function arguments that are often a common constant and
  11 // specializes a version of the called function for that constant.
  12 //
  13 // This pass simply does the cloning for functions it specializes.  It depends
  14 // on IPSCCP and DAE to clean up the results.
  15 //
  16 // The initial heuristic favors constant arguments that are used in control
  17 // flow.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #define DEBUG_TYPE "partialspecialization"
  22 #include "llvm/Transforms/IPO.h"
  23 #include "llvm/Constant.h"
  24 #include "llvm/Instructions.h"
  25 #include "llvm/Module.h"
  26 #include "llvm/Pass.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/Transforms/Utils/Cloning.h"
  29 #include "llvm/Support/Compiler.h"
  30 #include <map>
  31 using namespace llvm;
  32
  33 STATISTIC(numSpecialized, "Number of specialized functions created");
  34
  35 // Call must be used at least occasionally
  36 static const int CallsMin = 5;
  37
  38 // Must have 10% of calls having the same constant to specialize on
  39 static const double ConstValPercent = .1;
  40
  41 namespace {
  42   class VISIBILITY_HIDDEN PartSpec : public ModulePass {
  43     void scanForInterest(Function&, SmallVector<int, 6>&);
  44     void replaceUsersFor(Function&, int, Constant*, Function*);
  45     int scanDistribution(Function&, int, std::map<Constant*, int>&);
  46   public :
  47     static char ID; // Pass identification, replacement for typeid
  48     PartSpec() : ModulePass(&ID) {}
  49     bool runOnModule(Module &M);
  50   };
  51 }
  52
  53 char PartSpec::ID = 0;
  54 static RegisterPass<PartSpec>
  55 X("partialspecialization", "Partial Specialization");
  56
  57 bool PartSpec::runOnModule(Module &M) {
  58   bool Changed = false;
  59   for (Module::iterator I = M.begin(); I != M.end(); ++I) {
  60     Function &F = *I;
  61     if (F.isDeclaration()) continue;
  62     SmallVector<int, 6> interestingArgs;
  63     scanForInterest(F, interestingArgs);
  64
  65     // Find the first interesting Argument that we can specialize on
  66     // If there are multiple interesting Arguments, then those will be found
  67     // when processing the cloned function.
  68     bool breakOuter = false;
  69     for (unsigned int x = 0; !breakOuter && x < interestingArgs.size(); ++x) {
  70       std::map<Constant*, int> distribution;
  71       int total = scanDistribution(F, interestingArgs[x], distribution);
  72       if (total > CallsMin)
  73         for (std::map<Constant*, int>::iterator ii = distribution.begin(),
  74                ee = distribution.end(); ii != ee; ++ii)
  75           if (total > ii->second && ii->first &&
  76                ii->second > total * ConstValPercent) {
  77             Function* NF = CloneFunction(&F);
  78             NF->setLinkage(GlobalValue::InternalLinkage);
  79             M.getFunctionList().push_back(NF);
  80             replaceUsersFor(F, interestingArgs[x], ii->first, NF);
  81             breakOuter = true;
  82             Changed = true;
  83           }
  84     }
  85   }
  86   return Changed;
  87 }
  88
  89 /// scanForInterest - This function decides which arguments would be worth
  90 /// specializing on.
  91 void PartSpec::scanForInterest(Function& F, SmallVector<int, 6>& args) {
  92   for(Function::arg_iterator ii = F.arg_begin(), ee = F.arg_end();
  93       ii != ee; ++ii) {
  94     for(Value::use_iterator ui = ii->use_begin(), ue = ii->use_end();
  95         ui != ue; ++ui) {
  96       // As an initial proxy for control flow, specialize on arguments
  97       // that are used in comparisons.
  98       if (isa<CmpInst>(ui)) {
  99         args.push_back(std::distance(F.arg_begin(), ii));
 100         break;
 101       }
 102     }
 103   }
 104 }
 105
 106 /// replaceUsersFor - Replace direct calls to F with NF if the arg argnum is
 107 /// the constant val
 108 void PartSpec::replaceUsersFor(Function& F , int argnum, Constant* val,
 109                                Function* NF) {
 110   ++numSpecialized;
 111   for(Value::use_iterator ii = F.use_begin(), ee = F.use_end();
 112       ii != ee; ++ii)
 113     if (CallInst* CI = dyn_cast<CallInst>(ii))
 114       if (CI->getOperand(0) == &F && CI->getOperand(argnum + 1) == val)
 115         CI->setOperand(0, NF);
 116 }
 117
 118 int PartSpec::scanDistribution(Function& F, int arg,
 119                                std::map<Constant*, int>& dist) {
 120   bool hasIndirect = false;
 121   int total = 0;
 122   for(Value::use_iterator ii = F.use_begin(), ee = F.use_end();
 123       ii != ee; ++ii)
 124     if (CallInst* CI = dyn_cast<CallInst>(ii)) {
 125       ++dist[dyn_cast<Constant>(CI->getOperand(arg + 1))];
 126       ++total;
 127     } else
 128       hasIndirect = true;
 129
 130   // Preserve the original address taken function even if all other uses
 131   // will be specialized.
 132   if (hasIndirect) ++total;
 133   return total;
 134 }
 135
 136 ModulePass* llvm::createPartialSpecializationPass() { return new PartSpec(); }