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/CallSite.h"
  30 #include "llvm/ADT/DenseSet.h"
  31 #include <map>
  32 using namespace llvm;
  33
  34 STATISTIC(numSpecialized, "Number of specialized functions created");
  35 STATISTIC(numReplaced, "Number of callers replaced by specialization");
  36
  37 // Maximum number of arguments markable interested
  38 static const int MaxInterests = 6;
  39
  40 // Call must be used at least occasionally
  41 static const int CallsMin = 5;
  42
  43 // Must have 10% of calls having the same constant to specialize on
  44 static const double ConstValPercent = .1;
  45
  46 namespace {
  47   typedef SmallVector<int, MaxInterests> InterestingArgVector;
  48   class PartSpec : public ModulePass {
  49     void scanForInterest(Function&, InterestingArgVector&);
  50     int scanDistribution(Function&, int, std::map<Constant*, int>&);
  51   public :
  52     static char ID; // Pass identification, replacement for typeid
  53     PartSpec() : ModulePass(ID) {}
  54     bool runOnModule(Module &M);
  55   };
  56 }
  57
  58 char PartSpec::ID = 0;
  59 INITIALIZE_PASS(PartSpec, "partialspecialization",
  60                 "Partial Specialization", false, false);
  61
  62 // Specialize F by replacing the arguments (keys) in replacements with the
  63 // constants (values).  Replace all calls to F with those constants with
  64 // a call to the specialized function.  Returns the specialized function
  65 static Function*
  66 SpecializeFunction(Function* F,
  67                    ValueMap<const Value*, Value*>& replacements) {
  68   // arg numbers of deleted arguments
  69   DenseMap<unsigned, const Argument*> deleted;
  70   for (ValueMap<const Value*, Value*>::iterator
  71          repb = replacements.begin(), repe = replacements.end();
  72        repb != repe; ++repb) {
  73     Argument const *arg = cast<const Argument>(repb->first);
  74     deleted[arg->getArgNo()] = arg;
  75   }
  76
  77   Function* NF = CloneFunction(F, replacements,
  78                                /*ModuleLevelChanges=*/false);
  79   NF->setLinkage(GlobalValue::InternalLinkage);
  80   F->getParent()->getFunctionList().push_back(NF);
  81
  82   for (Value::use_iterator ii = F->use_begin(), ee = F->use_end();
  83        ii != ee; ) {
  84     Value::use_iterator i = ii;
  85     ++ii;
  86     User *U = *i;
  87     CallSite CS(U);
  88     if (CS) {
  89       if (CS.getCalledFunction() == F) {
  90         SmallVector<Value*, 6> args;
  91         // Assemble the non-specialized arguments for the updated callsite.
  92         // In the process, make sure that the specialized arguments are
  93         // constant and match the specialization.  If that's not the case,
  94         // this callsite needs to call the original or some other
  95         // specialization; don't change it here.
  96         CallSite::arg_iterator as = CS.arg_begin(), ae = CS.arg_end();
  97         for (CallSite::arg_iterator ai = as; ai != ae; ++ai) {
  98           DenseMap<unsigned, const Argument*>::iterator delit = deleted.find(
  99             std::distance(as, ai));
 100           if (delit == deleted.end())
 101             args.push_back(cast<Value>(ai));
 102           else {
 103             Constant *ci = dyn_cast<Constant>(ai);
 104             if (!(ci && ci == replacements[delit->second]))
 105               goto next_use;
 106           }
 107         }
 108         Value* NCall;
 109         if (CallInst *CI = dyn_cast<CallInst>(U)) {
 110           NCall = CallInst::Create(NF, args.begin(), args.end(),
 111                                    CI->getName(), CI);
 112           cast<CallInst>(NCall)->setTailCall(CI->isTailCall());
 113           cast<CallInst>(NCall)->setCallingConv(CI->getCallingConv());
 114         } else {
 115           InvokeInst *II = cast<InvokeInst>(U);
 116           NCall = InvokeInst::Create(NF, II->getNormalDest(),
 117                                      II->getUnwindDest(),
 118                                      args.begin(), args.end(),
 119                                      II->getName(), II);
 120           cast<InvokeInst>(NCall)->setCallingConv(II->getCallingConv());
 121         }
 122         CS.getInstruction()->replaceAllUsesWith(NCall);
 123         CS.getInstruction()->eraseFromParent();
 124         ++numReplaced;
 125       }
 126     }
 127     next_use:;
 128   }
 129   return NF;
 130 }
 131
 132
 133 bool PartSpec::runOnModule(Module &M) {
 134   bool Changed = false;
 135   for (Module::iterator I = M.begin(); I != M.end(); ++I) {
 136     Function &F = *I;
 137     if (F.isDeclaration() || F.mayBeOverridden()) continue;
 138     InterestingArgVector interestingArgs;
 139     scanForInterest(F, interestingArgs);
 140
 141     // Find the first interesting Argument that we can specialize on
 142     // If there are multiple interesting Arguments, then those will be found
 143     // when processing the cloned function.
 144     bool breakOuter = false;
 145     for (unsigned int x = 0; !breakOuter && x < interestingArgs.size(); ++x) {
 146       std::map<Constant*, int> distribution;
 147       int total = scanDistribution(F, interestingArgs[x], distribution);
 148       if (total > CallsMin)
 149         for (std::map<Constant*, int>::iterator ii = distribution.begin(),
 150                ee = distribution.end(); ii != ee; ++ii)
 151           if (total > ii->second && ii->first &&
 152                ii->second > total * ConstValPercent) {
 153             ValueMap<const Value*, Value*> m;
 154             Function::arg_iterator arg = F.arg_begin();
 155             for (int y = 0; y < interestingArgs[x]; ++y)
 156               ++arg;
 157             m[&*arg] = ii->first;
 158             SpecializeFunction(&F, m);
 159             ++numSpecialized;
 160             breakOuter = true;
 161             Changed = true;
 162           }
 163     }
 164   }
 165   return Changed;
 166 }
 167
 168 /// scanForInterest - This function decides which arguments would be worth
 169 /// specializing on.
 170 void PartSpec::scanForInterest(Function& F, InterestingArgVector& args) {
 171   for(Function::arg_iterator ii = F.arg_begin(), ee = F.arg_end();
 172       ii != ee; ++ii) {
 173     for(Value::use_iterator ui = ii->use_begin(), ue = ii->use_end();
 174         ui != ue; ++ui) {
 175
 176       bool interesting = false;
 177       User *U = *ui;
 178       if (isa<CmpInst>(U)) interesting = true;
 179       else if (isa<CallInst>(U))
 180         interesting = ui->getOperand(0) == ii;
 181       else if (isa<InvokeInst>(U))
 182         interesting = ui->getOperand(0) == ii;
 183       else if (isa<SwitchInst>(U)) interesting = true;
 184       else if (isa<BranchInst>(U)) interesting = true;
 185
 186       if (interesting) {
 187         args.push_back(std::distance(F.arg_begin(), ii));
 188         break;
 189       }
 190     }
 191   }
 192 }
 193
 194 /// scanDistribution - Construct a histogram of constants for arg of F at arg.
 195 int PartSpec::scanDistribution(Function& F, int arg,
 196                                std::map<Constant*, int>& dist) {
 197   bool hasIndirect = false;
 198   int total = 0;
 199   for (Value::use_iterator ii = F.use_begin(), ee = F.use_end();
 200       ii != ee; ++ii) {
 201     User *U = *ii;
 202     CallSite CS(U);
 203     if (CS && CS.getCalledFunction() == &F) {
 204       ++dist[dyn_cast<Constant>(CS.getArgument(arg))];
 205       ++total;
 206     } else
 207       hasIndirect = true;
 208   }
 209
 210   // Preserve the original address taken function even if all other uses
 211   // will be specialized.
 212   if (hasIndirect) ++total;
 213   return total;
 214 }
 215
 216 ModulePass* llvm::createPartialSpecializationPass() { return new PartSpec(); }