LLVM API Documentation

PartialSpecialization.cpp

Go to the documentation of this file.
00001 //===-- PartialSpecialization.cpp - Specialize for common constants--------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass finds function arguments that are often a common constant and 
00011 // specializes a version of the called function for that constant.
00012 //
00013 // This pass simply does the cloning for functions it specializes.  It depends
00014 // on IPSCCP and DAE to clean up the results.
00015 //
00016 // The initial heuristic favors constant arguments that are used in control 
00017 // flow.
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #define DEBUG_TYPE "partialspecialization"
00022 #include "llvm/Transforms/IPO.h"
00023 #include "llvm/Constant.h"
00024 #include "llvm/Instructions.h"
00025 #include "llvm/Module.h"
00026 #include "llvm/Pass.h"
00027 #include "llvm/ADT/Statistic.h"
00028 #include "llvm/Transforms/Utils/Cloning.h"
00029 #include "llvm/Support/CallSite.h"
00030 #include "llvm/Support/Compiler.h"
00031 #include "llvm/ADT/DenseSet.h"
00032 #include <map>
00033 using namespace llvm;
00034 
00035 STATISTIC(numSpecialized, "Number of specialized functions created");
00036 
00037 // Call must be used at least occasionally
00038 static const int CallsMin = 5;
00039 
00040 // Must have 10% of calls having the same constant to specialize on
00041 static const double ConstValPercent = .1;
00042 
00043 namespace {
00044   class VISIBILITY_HIDDEN PartSpec : public ModulePass {
00045     void scanForInterest(Function&, SmallVector<int, 6>&);
00046     int scanDistribution(Function&, int, std::map<Constant*, int>&);
00047   public :
00048     static char ID; // Pass identification, replacement for typeid
00049     PartSpec() : ModulePass(&ID) {}
00050     bool runOnModule(Module &M);
00051   };
00052 }
00053 
00054 char PartSpec::ID = 0;
00055 static RegisterPass<PartSpec>
00056 X("partialspecialization", "Partial Specialization");
00057 
00058 // Specialize F by replacing the arguments (keys) in replacements with the 
00059 // constants (values).  Replace all calls to F with those constants with
00060 // a call to the specialized function.  Returns the specialized function
00061 static Function* 
00062 SpecializeFunction(Function* F, 
00063                    DenseMap<const Value*, Value*>& replacements) {
00064   // arg numbers of deleted arguments
00065   DenseSet<unsigned> deleted;
00066   for (DenseMap<const Value*, Value*>::iterator 
00067          repb = replacements.begin(), repe = replacements.end();
00068        repb != repe; ++repb)
00069     deleted.insert(cast<Argument>(repb->first)->getArgNo());
00070 
00071   Function* NF = CloneFunction(F, replacements);
00072   NF->setLinkage(GlobalValue::InternalLinkage);
00073   F->getParent()->getFunctionList().push_back(NF);
00074 
00075   for (Value::use_iterator ii = F->use_begin(), ee = F->use_end(); 
00076        ii != ee; ) {
00077     Value::use_iterator i = ii;
00078     ++ii;
00079     if (isa<CallInst>(i) || isa<InvokeInst>(i)) {
00080       CallSite CS(cast<Instruction>(i));
00081       if (CS.getCalledFunction() == F) {
00082         
00083         SmallVector<Value*, 6> args;
00084         for (unsigned x = 0; x < CS.arg_size(); ++x)
00085           if (!deleted.count(x))
00086             args.push_back(CS.getArgument(x));
00087         Value* NCall;
00088         if (CallInst *CI = dyn_cast<CallInst>(i)) {
00089           NCall = CallInst::Create(NF, args.begin(), args.end(), 
00090                                    CI->getName(), CI);
00091           cast<CallInst>(NCall)->setTailCall(CI->isTailCall());
00092           cast<CallInst>(NCall)->setCallingConv(CI->getCallingConv());
00093         } else {
00094           InvokeInst *II = cast<InvokeInst>(i);
00095           NCall = InvokeInst::Create(NF, II->getNormalDest(),
00096                                      II->getUnwindDest(),
00097                                      args.begin(), args.end(), 
00098                                      II->getName(), II);
00099           cast<InvokeInst>(NCall)->setCallingConv(II->getCallingConv());
00100         }
00101         CS.getInstruction()->replaceAllUsesWith(NCall);
00102         CS.getInstruction()->eraseFromParent();
00103       }
00104     }
00105   }
00106   return NF;
00107 }
00108 
00109 
00110 bool PartSpec::runOnModule(Module &M) {
00111   bool Changed = false;
00112   for (Module::iterator I = M.begin(); I != M.end(); ++I) {
00113     Function &F = *I;
00114     if (F.isDeclaration() || F.mayBeOverridden()) continue;
00115     SmallVector<int, 6> interestingArgs;
00116     scanForInterest(F, interestingArgs);
00117 
00118     // Find the first interesting Argument that we can specialize on
00119     // If there are multiple interesting Arguments, then those will be found
00120     // when processing the cloned function.
00121     bool breakOuter = false;
00122     for (unsigned int x = 0; !breakOuter && x < interestingArgs.size(); ++x) {
00123       std::map<Constant*, int> distribution;
00124       int total = scanDistribution(F, interestingArgs[x], distribution);
00125       if (total > CallsMin) 
00126         for (std::map<Constant*, int>::iterator ii = distribution.begin(),
00127                ee = distribution.end(); ii != ee; ++ii)
00128           if (total > ii->second && ii->first &&
00129                ii->second > total * ConstValPercent) {
00130             DenseMap<const Value*, Value*> m;
00131             Function::arg_iterator arg = F.arg_begin();
00132             for (int y = 0; y < interestingArgs[x]; ++y)
00133               ++arg;
00134             m[&*arg] = ii->first;
00135             SpecializeFunction(&F, m);
00136             ++numSpecialized;
00137             breakOuter = true;
00138             Changed = true;
00139           }
00140     }
00141   }
00142   return Changed;
00143 }
00144 
00145 /// scanForInterest - This function decides which arguments would be worth
00146 /// specializing on.
00147 void PartSpec::scanForInterest(Function& F, SmallVector<int, 6>& args) {
00148   for(Function::arg_iterator ii = F.arg_begin(), ee = F.arg_end();
00149       ii != ee; ++ii) {
00150     for(Value::use_iterator ui = ii->use_begin(), ue = ii->use_end();
00151         ui != ue; ++ui) {
00152 
00153       bool interesting = false;
00154 
00155       if (isa<CmpInst>(ui)) interesting = true;
00156       else if (isa<CallInst>(ui))
00157         interesting = ui->getOperand(0) == ii;
00158       else if (isa<InvokeInst>(ui))
00159         interesting = ui->getOperand(0) == ii;
00160       else if (isa<SwitchInst>(ui)) interesting = true;
00161       else if (isa<BranchInst>(ui)) interesting = true;
00162 
00163       if (interesting) {
00164         args.push_back(std::distance(F.arg_begin(), ii));
00165         break;
00166       }
00167     }
00168   }
00169 }
00170 
00171 /// scanDistribution - Construct a histogram of constants for arg of F at arg.
00172 int PartSpec::scanDistribution(Function& F, int arg, 
00173                                std::map<Constant*, int>& dist) {
00174   bool hasIndirect = false;
00175   int total = 0;
00176   for(Value::use_iterator ii = F.use_begin(), ee = F.use_end();
00177       ii != ee; ++ii)
00178     if ((isa<CallInst>(ii) || isa<InvokeInst>(ii))
00179         && ii->getOperand(0) == &F) {
00180       ++dist[dyn_cast<Constant>(ii->getOperand(arg + 1))];
00181       ++total;
00182     } else
00183       hasIndirect = true;
00184 
00185   // Preserve the original address taken function even if all other uses
00186   // will be specialized.
00187   if (hasIndirect) ++total;
00188   return total;
00189 }
00190 
00191 ModulePass* llvm::createPartialSpecializationPass() { return new PartSpec(); }