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