LLVM API Documentation

StructRetPromotion.cpp

Go to the documentation of this file.
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 }