LLVM API Documentation
00001 //===-- StructRetPromotion.cpp - Promote sret arguments ------------------===// 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 functions that return a struct (using a pointer to the struct 00011 // as the first argument of the function, marked with the 'sret' attribute) and 00012 // replaces them with a new function that simply returns each of the elements of 00013 // that struct (using multiple return values). 00014 // 00015 // This pass works under a number of conditions: 00016 // 1. The returned struct must not contain other structs 00017 // 2. The returned struct must only be used to load values from 00018 // 3. The placeholder struct passed in is the result of an alloca 00019 // 00020 //===----------------------------------------------------------------------===// 00021 00022 #define DEBUG_TYPE "sretpromotion" 00023 #include "llvm/Transforms/IPO.h" 00024 #include "llvm/Constants.h" 00025 #include "llvm/DerivedTypes.h" 00026 #include "llvm/LLVMContext.h" 00027 #include "llvm/Module.h" 00028 #include "llvm/CallGraphSCCPass.h" 00029 #include "llvm/Instructions.h" 00030 #include "llvm/Analysis/CallGraph.h" 00031 #include "llvm/Support/CallSite.h" 00032 #include "llvm/Support/CFG.h" 00033 #include "llvm/Support/Debug.h" 00034 #include "llvm/ADT/Statistic.h" 00035 #include "llvm/ADT/SmallVector.h" 00036 #include "llvm/ADT/Statistic.h" 00037 #include "llvm/Support/Compiler.h" 00038 #include "llvm/Support/raw_ostream.h" 00039 using namespace llvm; 00040 00041 STATISTIC(NumRejectedSRETUses , "Number of sret rejected due to unexpected uses"); 00042 STATISTIC(NumSRET , "Number of sret promoted"); 00043 namespace { 00044 /// SRETPromotion - This pass removes sret parameter and updates 00045 /// function to use multiple return value. 00046 /// 00047 struct VISIBILITY_HIDDEN SRETPromotion : public CallGraphSCCPass { 00048 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00049 CallGraphSCCPass::getAnalysisUsage(AU); 00050 } 00051 00052 virtual bool runOnSCC(const std::vector<CallGraphNode *> &SCC); 00053 static char ID; // Pass identification, replacement for typeid 00054 SRETPromotion() : CallGraphSCCPass(&ID) {} 00055 00056 private: 00057 bool PromoteReturn(CallGraphNode *CGN); 00058 bool isSafeToUpdateAllCallers(Function *F); 00059 Function *cloneFunctionBody(Function *F, const StructType *STy); 00060 void updateCallSites(Function *F, Function *NF); 00061 bool nestedStructType(const StructType *STy); 00062 }; 00063 } 00064 00065 char SRETPromotion::ID = 0; 00066 static RegisterPass<SRETPromotion> 00067 X("sretpromotion", "Promote sret arguments to multiple ret values"); 00068 00069 Pass *llvm::createStructRetPromotionPass() { 00070 return new SRETPromotion(); 00071 } 00072 00073 bool SRETPromotion::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 00074 bool Changed = false; 00075 00076 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 00077 Changed |= PromoteReturn(SCC[i]); 00078 00079 return Changed; 00080 } 00081 00082 /// PromoteReturn - This method promotes function that uses StructRet paramater 00083 /// into a function that uses mulitple return value. 00084 bool SRETPromotion::PromoteReturn(CallGraphNode *CGN) { 00085 Function *F = CGN->getFunction(); 00086 00087 if (!F || F->isDeclaration() || !F->hasLocalLinkage()) 00088 return false; 00089 00090 // Make sure that function returns struct. 00091 if (F->arg_size() == 0 || !F->hasStructRetAttr() || F->doesNotReturn()) 00092 return false; 00093 00094 DEBUG(errs() << "SretPromotion: Looking at sret function " 00095 << F->getName() << "\n"); 00096 00097 assert (F->getReturnType() == Type::getVoidTy(F->getContext()) && 00098 "Invalid function return type"); 00099 Function::arg_iterator AI = F->arg_begin(); 00100 const llvm::PointerType *FArgType = dyn_cast<PointerType>(AI->getType()); 00101 assert (FArgType && "Invalid sret parameter type"); 00102 const llvm::StructType *STy = 00103 dyn_cast<StructType>(FArgType->getElementType()); 00104 assert (STy && "Invalid sret parameter element type"); 00105 00106 // Check if it is ok to perform this promotion. 00107 if (isSafeToUpdateAllCallers(F) == false) { 00108 DOUT << "SretPromotion: Not all callers can be updated\n"; 00109 NumRejectedSRETUses++; 00110 return false; 00111 } 00112 00113 DOUT << "SretPromotion: sret argument will be promoted\n"; 00114 NumSRET++; 00115 // [1] Replace use of sret parameter 00116 AllocaInst *TheAlloca = new AllocaInst(STy, NULL, "mrv", 00117 F->getEntryBlock().begin()); 00118 Value *NFirstArg = F->arg_begin(); 00119 NFirstArg->replaceAllUsesWith(TheAlloca); 00120 00121 // [2] Find and replace ret instructions 00122 for (Function::iterator FI = F->begin(), FE = F->end(); FI != FE; ++FI) 00123 for(BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) { 00124 Instruction *I = BI; 00125 ++BI; 00126 if (isa<ReturnInst>(I)) { 00127 Value *NV = new LoadInst(TheAlloca, "mrv.ld", I); 00128 ReturnInst *NR = ReturnInst::Create(F->getContext(), NV, I); 00129 I->replaceAllUsesWith(NR); 00130 I->eraseFromParent(); 00131 } 00132 } 00133 00134 // [3] Create the new function body and insert it into the module. 00135 Function *NF = cloneFunctionBody(F, STy); 00136 00137 // [4] Update all call sites to use new function 00138 updateCallSites(F, NF); 00139 00140 F->eraseFromParent(); 00141 getAnalysis<CallGraph>().changeFunction(F, NF); 00142 return true; 00143 } 00144 00145 // Check if it is ok to perform this promotion. 00146 bool SRETPromotion::isSafeToUpdateAllCallers(Function *F) { 00147 00148 if (F->use_empty()) 00149 // No users. OK to modify signature. 00150 return true; 00151 00152 for (Value::use_iterator FnUseI = F->use_begin(), FnUseE = F->use_end(); 00153 FnUseI != FnUseE; ++FnUseI) { 00154 // The function is passed in as an argument to (possibly) another function, 00155 // we can't change it! 00156 CallSite CS = CallSite::get(*FnUseI); 00157 Instruction *Call = CS.getInstruction(); 00158 // The function is used by something else than a call or invoke instruction, 00159 // we can't change it! 00160 if (!Call || !CS.isCallee(FnUseI)) 00161 return false; 00162 CallSite::arg_iterator AI = CS.arg_begin(); 00163 Value *FirstArg = *AI; 00164 00165 if (!isa<AllocaInst>(FirstArg)) 00166 return false; 00167 00168 // Check FirstArg's users. 00169 for (Value::use_iterator ArgI = FirstArg->use_begin(), 00170 ArgE = FirstArg->use_end(); ArgI != ArgE; ++ArgI) { 00171 00172 // If FirstArg user is a CallInst that does not correspond to current 00173 // call site then this function F is not suitable for sret promotion. 00174 if (CallInst *CI = dyn_cast<CallInst>(ArgI)) { 00175 if (CI != Call) 00176 return false; 00177 } 00178 // If FirstArg user is a GEP whose all users are not LoadInst then 00179 // this function F is not suitable for sret promotion. 00180 else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(ArgI)) { 00181 // TODO : Use dom info and insert PHINodes to collect get results 00182 // from multiple call sites for this GEP. 00183 if (GEP->getParent() != Call->getParent()) 00184 return false; 00185 for (Value::use_iterator GEPI = GEP->use_begin(), GEPE = GEP->use_end(); 00186 GEPI != GEPE; ++GEPI) 00187 if (!isa<LoadInst>(GEPI)) 00188 return false; 00189 } 00190 // Any other FirstArg users make this function unsuitable for sret 00191 // promotion. 00192 else 00193 return false; 00194 } 00195 } 00196 00197 return true; 00198 } 00199 00200 /// cloneFunctionBody - Create a new function based on F and 00201 /// insert it into module. Remove first argument. Use STy as 00202 /// the return type for new function. 00203 Function *SRETPromotion::cloneFunctionBody(Function *F, 00204 const StructType *STy) { 00205 00206 const FunctionType *FTy = F->getFunctionType(); 00207 std::vector<const Type*> Params; 00208 00209 // Attributes - Keep track of the parameter attributes for the arguments. 00210 SmallVector<AttributeWithIndex, 8> AttributesVec; 00211 const AttrListPtr &PAL = F->getAttributes(); 00212 00213 // Add any return attributes. 00214 if (Attributes attrs = PAL.getRetAttributes()) 00215 AttributesVec.push_back(AttributeWithIndex::get(0, attrs)); 00216 00217 // Skip first argument. 00218 Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00219 ++I; 00220 // 0th parameter attribute is reserved for return type. 00221 // 1th parameter attribute is for first 1st sret argument. 00222 unsigned ParamIndex = 2; 00223 while (I != E) { 00224 Params.push_back(I->getType()); 00225 if (Attributes Attrs = PAL.getParamAttributes(ParamIndex)) 00226 AttributesVec.push_back(AttributeWithIndex::get(ParamIndex - 1, Attrs)); 00227 ++I; 00228 ++ParamIndex; 00229 } 00230 00231 // Add any fn attributes. 00232 if (Attributes attrs = PAL.getFnAttributes()) 00233 AttributesVec.push_back(AttributeWithIndex::get(~0, attrs)); 00234 00235 00236 FunctionType *NFTy = FunctionType::get(STy, Params, FTy->isVarArg()); 00237 Function *NF = Function::Create(NFTy, F->getLinkage()); 00238 NF->takeName(F); 00239 NF->copyAttributesFrom(F); 00240 NF->setAttributes(AttrListPtr::get(AttributesVec.begin(), AttributesVec.end())); 00241 F->getParent()->getFunctionList().insert(F, NF); 00242 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 00243 00244 // Replace arguments 00245 I = F->arg_begin(); 00246 E = F->arg_end(); 00247 Function::arg_iterator NI = NF->arg_begin(); 00248 ++I; 00249 while (I != E) { 00250 I->replaceAllUsesWith(NI); 00251 NI->takeName(I); 00252 ++I; 00253 ++NI; 00254 } 00255 00256 return NF; 00257 } 00258 00259 /// updateCallSites - Update all sites that call F to use NF. 00260 void SRETPromotion::updateCallSites(Function *F, Function *NF) { 00261 CallGraph &CG = getAnalysis<CallGraph>(); 00262 SmallVector<Value*, 16> Args; 00263 00264 // Attributes - Keep track of the parameter attributes for the arguments. 00265 SmallVector<AttributeWithIndex, 8> ArgAttrsVec; 00266 00267 while (!F->use_empty()) { 00268 CallSite CS = CallSite::get(*F->use_begin()); 00269 Instruction *Call = CS.getInstruction(); 00270 00271 const AttrListPtr &PAL = F->getAttributes(); 00272 // Add any return attributes. 00273 if (Attributes attrs = PAL.getRetAttributes()) 00274 ArgAttrsVec.push_back(AttributeWithIndex::get(0, attrs)); 00275 00276 // Copy arguments, however skip first one. 00277 CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 00278 Value *FirstCArg = *AI; 00279 ++AI; 00280 // 0th parameter attribute is reserved for return type. 00281 // 1th parameter attribute is for first 1st sret argument. 00282 unsigned ParamIndex = 2; 00283 while (AI != AE) { 00284 Args.push_back(*AI); 00285 if (Attributes Attrs = PAL.getParamAttributes(ParamIndex)) 00286 ArgAttrsVec.push_back(AttributeWithIndex::get(ParamIndex - 1, Attrs)); 00287 ++ParamIndex; 00288 ++AI; 00289 } 00290 00291 // Add any function attributes. 00292 if (Attributes attrs = PAL.getFnAttributes()) 00293 ArgAttrsVec.push_back(AttributeWithIndex::get(~0, attrs)); 00294 00295 AttrListPtr NewPAL = AttrListPtr::get(ArgAttrsVec.begin(), ArgAttrsVec.end()); 00296 00297 // Build new call instruction. 00298 Instruction *New; 00299 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 00300 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 00301 Args.begin(), Args.end(), "", Call); 00302 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 00303 cast<InvokeInst>(New)->setAttributes(NewPAL); 00304 } else { 00305 New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call); 00306 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 00307 cast<CallInst>(New)->setAttributes(NewPAL); 00308 if (cast<CallInst>(Call)->isTailCall()) 00309 cast<CallInst>(New)->setTailCall(); 00310 } 00311 Args.clear(); 00312 ArgAttrsVec.clear(); 00313 New->takeName(Call); 00314 00315 // Update the callgraph to know that the callsite has been transformed. 00316 CG[Call->getParent()->getParent()]->replaceCallSite(Call, New); 00317 00318 // Update all users of sret parameter to extract value using extractvalue. 00319 for (Value::use_iterator UI = FirstCArg->use_begin(), 00320 UE = FirstCArg->use_end(); UI != UE; ) { 00321 User *U2 = *UI++; 00322 CallInst *C2 = dyn_cast<CallInst>(U2); 00323 if (C2 && (C2 == Call)) 00324 continue; 00325 else if (GetElementPtrInst *UGEP = dyn_cast<GetElementPtrInst>(U2)) { 00326 ConstantInt *Idx = dyn_cast<ConstantInt>(UGEP->getOperand(2)); 00327 assert (Idx && "Unexpected getelementptr index!"); 00328 Value *GR = ExtractValueInst::Create(New, Idx->getZExtValue(), 00329 "evi", UGEP); 00330 while(!UGEP->use_empty()) { 00331 // isSafeToUpdateAllCallers has checked that all GEP uses are 00332 // LoadInsts 00333 LoadInst *L = cast<LoadInst>(*UGEP->use_begin()); 00334 L->replaceAllUsesWith(GR); 00335 L->eraseFromParent(); 00336 } 00337 UGEP->eraseFromParent(); 00338 } 00339 else assert( 0 && "Unexpected sret parameter use"); 00340 } 00341 Call->eraseFromParent(); 00342 } 00343 } 00344 00345 /// nestedStructType - Return true if STy includes any 00346 /// other aggregate types 00347 bool SRETPromotion::nestedStructType(const StructType *STy) { 00348 unsigned Num = STy->getNumElements(); 00349 for (unsigned i = 0; i < Num; i++) { 00350 const Type *Ty = STy->getElementType(i); 00351 if (!Ty->isSingleValueType() && Ty != Type::getVoidTy(STy->getContext())) 00352 return true; 00353 } 00354 return false; 00355 }