LLVM API Documentation
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(); }