blob: e28fc42ed248fd8526b1573032512b68c8080943 [file] [log] [blame]
Gordon Henriksena8a118b2008-05-08 17:46:35 +00001//===-- StructRetPromotion.cpp - Promote sret arguments ------------------===//
Devang Patelca891ec2008-02-29 23:34:08 +00002//
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//
Gordon Henriksena8a118b2008-05-08 17:46:35 +000010// This pass finds functions that return a struct (using a pointer to the struct
11// as the first argument of the function, marked with the 'sret' attribute) and
12// replaces them with a new function that simply returns each of the elements of
13// that struct (using multiple return values).
14//
15// This pass works under a number of conditions:
16// 1. The returned struct must not contain other structs
17// 2. The returned struct must only be used to load values from
18// 3. The placeholder struct passed in is the result of an alloca
19//
Devang Patelca891ec2008-02-29 23:34:08 +000020//===----------------------------------------------------------------------===//
21
22#define DEBUG_TYPE "sretpromotion"
23#include "llvm/Transforms/IPO.h"
24#include "llvm/Constants.h"
25#include "llvm/DerivedTypes.h"
Owen Anderson14ce9ef2009-07-06 01:34:54 +000026#include "llvm/LLVMContext.h"
Devang Patelca891ec2008-02-29 23:34:08 +000027#include "llvm/Module.h"
28#include "llvm/CallGraphSCCPass.h"
29#include "llvm/Instructions.h"
30#include "llvm/Analysis/CallGraph.h"
31#include "llvm/Support/CallSite.h"
32#include "llvm/Support/CFG.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/ADT/SmallVector.h"
Devang Patel98a6e062008-03-04 17:44:37 +000036#include "llvm/ADT/Statistic.h"
Devang Patelca891ec2008-02-29 23:34:08 +000037#include "llvm/Support/Compiler.h"
Daniel Dunbar460f6562009-07-26 09:48:23 +000038#include "llvm/Support/raw_ostream.h"
Devang Patelca891ec2008-02-29 23:34:08 +000039using namespace llvm;
40
Devang Patel98a6e062008-03-04 17:44:37 +000041STATISTIC(NumRejectedSRETUses , "Number of sret rejected due to unexpected uses");
42STATISTIC(NumSRET , "Number of sret promoted");
Devang Patelca891ec2008-02-29 23:34:08 +000043namespace {
44 /// SRETPromotion - This pass removes sret parameter and updates
45 /// function to use multiple return value.
46 ///
47 struct VISIBILITY_HIDDEN SRETPromotion : public CallGraphSCCPass {
48 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
49 CallGraphSCCPass::getAnalysisUsage(AU);
50 }
51
52 virtual bool runOnSCC(const std::vector<CallGraphNode *> &SCC);
53 static char ID; // Pass identification, replacement for typeid
Dan Gohmanae73dc12008-09-04 17:05:41 +000054 SRETPromotion() : CallGraphSCCPass(&ID) {}
Devang Patelca891ec2008-02-29 23:34:08 +000055
56 private:
57 bool PromoteReturn(CallGraphNode *CGN);
58 bool isSafeToUpdateAllCallers(Function *F);
59 Function *cloneFunctionBody(Function *F, const StructType *STy);
60 void updateCallSites(Function *F, Function *NF);
Devang Patela9fe8bb2008-03-04 21:32:09 +000061 bool nestedStructType(const StructType *STy);
Devang Patelca891ec2008-02-29 23:34:08 +000062 };
Devang Patelca891ec2008-02-29 23:34:08 +000063}
64
Dan Gohman844731a2008-05-13 00:00:25 +000065char SRETPromotion::ID = 0;
66static RegisterPass<SRETPromotion>
67X("sretpromotion", "Promote sret arguments to multiple ret values");
68
Devang Patelca891ec2008-02-29 23:34:08 +000069Pass *llvm::createStructRetPromotionPass() {
70 return new SRETPromotion();
71}
72
73bool SRETPromotion::runOnSCC(const std::vector<CallGraphNode *> &SCC) {
74 bool Changed = false;
75
76 for (unsigned i = 0, e = SCC.size(); i != e; ++i)
77 Changed |= PromoteReturn(SCC[i]);
78
79 return Changed;
80}
81
82/// PromoteReturn - This method promotes function that uses StructRet paramater
83/// into a function that uses mulitple return value.
84bool SRETPromotion::PromoteReturn(CallGraphNode *CGN) {
85 Function *F = CGN->getFunction();
86
Rafael Espindolabb46f522009-01-15 20:18:42 +000087 if (!F || F->isDeclaration() || !F->hasLocalLinkage())
Devang Patelca891ec2008-02-29 23:34:08 +000088 return false;
89
90 // Make sure that function returns struct.
Devang Patel41e23972008-03-03 21:46:28 +000091 if (F->arg_size() == 0 || !F->hasStructRetAttr() || F->doesNotReturn())
Devang Patelca891ec2008-02-29 23:34:08 +000092 return false;
93
Daniel Dunbar460f6562009-07-26 09:48:23 +000094 DEBUG(errs() << "SretPromotion: Looking at sret function "
95 << F->getName() << "\n");
Matthijs Kooijman81ec2482008-08-07 15:14:04 +000096
Owen Anderson1d0be152009-08-13 21:58:54 +000097 assert (F->getReturnType() == Type::getVoidTy(F->getContext()) &&
98 "Invalid function return type");
Devang Patelca891ec2008-02-29 23:34:08 +000099 Function::arg_iterator AI = F->arg_begin();
100 const llvm::PointerType *FArgType = dyn_cast<PointerType>(AI->getType());
Duncan Sands33af59d2008-05-09 12:20:10 +0000101 assert (FArgType && "Invalid sret parameter type");
Devang Patelca891ec2008-02-29 23:34:08 +0000102 const llvm::StructType *STy =
103 dyn_cast<StructType>(FArgType->getElementType());
104 assert (STy && "Invalid sret parameter element type");
105
106 // Check if it is ok to perform this promotion.
Devang Patel98a6e062008-03-04 17:44:37 +0000107 if (isSafeToUpdateAllCallers(F) == false) {
Chris Lattnerbbbfa992009-08-23 06:35:02 +0000108 DEBUG(errs() << "SretPromotion: Not all callers can be updated\n");
Devang Patel98a6e062008-03-04 17:44:37 +0000109 NumRejectedSRETUses++;
Devang Patelca891ec2008-02-29 23:34:08 +0000110 return false;
Devang Patel98a6e062008-03-04 17:44:37 +0000111 }
Devang Patelca891ec2008-02-29 23:34:08 +0000112
Chris Lattnerbbbfa992009-08-23 06:35:02 +0000113 DEBUG(errs() << "SretPromotion: sret argument will be promoted\n");
Devang Pateldf1d15c2008-03-04 17:48:11 +0000114 NumSRET++;
Devang Patelca891ec2008-02-29 23:34:08 +0000115 // [1] Replace use of sret parameter
Owen Anderson50dead02009-07-15 23:53:25 +0000116 AllocaInst *TheAlloca = new AllocaInst(STy, NULL, "mrv",
117 F->getEntryBlock().begin());
Devang Patelca891ec2008-02-29 23:34:08 +0000118 Value *NFirstArg = F->arg_begin();
119 NFirstArg->replaceAllUsesWith(TheAlloca);
120
Devang Patel98a6e062008-03-04 17:44:37 +0000121 // [2] Find and replace ret instructions
Devang Patelca891ec2008-02-29 23:34:08 +0000122 for (Function::iterator FI = F->begin(), FE = F->end(); FI != FE; ++FI)
123 for(BasicBlock::iterator BI = FI->begin(), BE = FI->end(); BI != BE; ) {
124 Instruction *I = BI;
125 ++BI;
126 if (isa<ReturnInst>(I)) {
Dan Gohmanfc74abf2008-07-23 00:34:11 +0000127 Value *NV = new LoadInst(TheAlloca, "mrv.ld", I);
Owen Anderson1d0be152009-08-13 21:58:54 +0000128 ReturnInst *NR = ReturnInst::Create(F->getContext(), NV, I);
Devang Patelca891ec2008-02-29 23:34:08 +0000129 I->replaceAllUsesWith(NR);
130 I->eraseFromParent();
131 }
132 }
133
Devang Patel98a6e062008-03-04 17:44:37 +0000134 // [3] Create the new function body and insert it into the module.
Devang Patelca891ec2008-02-29 23:34:08 +0000135 Function *NF = cloneFunctionBody(F, STy);
136
Devang Patel98a6e062008-03-04 17:44:37 +0000137 // [4] Update all call sites to use new function
Devang Patelca891ec2008-02-29 23:34:08 +0000138 updateCallSites(F, NF);
139
140 F->eraseFromParent();
141 getAnalysis<CallGraph>().changeFunction(F, NF);
142 return true;
143}
144
Duncan Sands33af59d2008-05-09 12:20:10 +0000145// Check if it is ok to perform this promotion.
Devang Patelca891ec2008-02-29 23:34:08 +0000146bool SRETPromotion::isSafeToUpdateAllCallers(Function *F) {
147
148 if (F->use_empty())
149 // No users. OK to modify signature.
150 return true;
151
152 for (Value::use_iterator FnUseI = F->use_begin(), FnUseE = F->use_end();
153 FnUseI != FnUseE; ++FnUseI) {
Matthijs Kooijman257da0a2008-06-05 08:48:32 +0000154 // The function is passed in as an argument to (possibly) another function,
155 // we can't change it!
Devang Patelca891ec2008-02-29 23:34:08 +0000156 CallSite CS = CallSite::get(*FnUseI);
157 Instruction *Call = CS.getInstruction();
Matthijs Kooijman47c6fd72008-06-05 08:57:20 +0000158 // The function is used by something else than a call or invoke instruction,
159 // we can't change it!
Gabor Greifedc4d692009-01-22 21:35:57 +0000160 if (!Call || !CS.isCallee(FnUseI))
Matthijs Kooijman47c6fd72008-06-05 08:57:20 +0000161 return false;
Devang Patelca891ec2008-02-29 23:34:08 +0000162 CallSite::arg_iterator AI = CS.arg_begin();
163 Value *FirstArg = *AI;
164
165 if (!isa<AllocaInst>(FirstArg))
166 return false;
167
168 // Check FirstArg's users.
169 for (Value::use_iterator ArgI = FirstArg->use_begin(),
170 ArgE = FirstArg->use_end(); ArgI != ArgE; ++ArgI) {
171
172 // If FirstArg user is a CallInst that does not correspond to current
173 // call site then this function F is not suitable for sret promotion.
174 if (CallInst *CI = dyn_cast<CallInst>(ArgI)) {
175 if (CI != Call)
176 return false;
177 }
178 // If FirstArg user is a GEP whose all users are not LoadInst then
179 // this function F is not suitable for sret promotion.
180 else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(ArgI)) {
Devang Patele0a6a3f2008-03-05 23:39:23 +0000181 // TODO : Use dom info and insert PHINodes to collect get results
182 // from multiple call sites for this GEP.
183 if (GEP->getParent() != Call->getParent())
184 return false;
Devang Patelca891ec2008-02-29 23:34:08 +0000185 for (Value::use_iterator GEPI = GEP->use_begin(), GEPE = GEP->use_end();
186 GEPI != GEPE; ++GEPI)
187 if (!isa<LoadInst>(GEPI))
188 return false;
189 }
190 // Any other FirstArg users make this function unsuitable for sret
191 // promotion.
192 else
193 return false;
194 }
195 }
196
197 return true;
198}
199
200/// cloneFunctionBody - Create a new function based on F and
201/// insert it into module. Remove first argument. Use STy as
202/// the return type for new function.
203Function *SRETPromotion::cloneFunctionBody(Function *F,
204 const StructType *STy) {
205
Devang Patelca891ec2008-02-29 23:34:08 +0000206 const FunctionType *FTy = F->getFunctionType();
207 std::vector<const Type*> Params;
208
Devang Patel05988662008-09-25 21:00:45 +0000209 // Attributes - Keep track of the parameter attributes for the arguments.
210 SmallVector<AttributeWithIndex, 8> AttributesVec;
211 const AttrListPtr &PAL = F->getAttributes();
Devang Patel2a4821b2008-03-03 18:36:03 +0000212
213 // Add any return attributes.
Devang Patel19c87462008-09-26 22:53:05 +0000214 if (Attributes attrs = PAL.getRetAttributes())
Devang Patel05988662008-09-25 21:00:45 +0000215 AttributesVec.push_back(AttributeWithIndex::get(0, attrs));
Devang Patel2a4821b2008-03-03 18:36:03 +0000216
Devang Patelca891ec2008-02-29 23:34:08 +0000217 // Skip first argument.
218 Function::arg_iterator I = F->arg_begin(), E = F->arg_end();
219 ++I;
Devang Patel8f9b5512008-03-12 00:07:03 +0000220 // 0th parameter attribute is reserved for return type.
221 // 1th parameter attribute is for first 1st sret argument.
222 unsigned ParamIndex = 2;
Devang Patelca891ec2008-02-29 23:34:08 +0000223 while (I != E) {
224 Params.push_back(I->getType());
Devang Patel19c87462008-09-26 22:53:05 +0000225 if (Attributes Attrs = PAL.getParamAttributes(ParamIndex))
Devang Patel05988662008-09-25 21:00:45 +0000226 AttributesVec.push_back(AttributeWithIndex::get(ParamIndex - 1, Attrs));
Devang Patelca891ec2008-02-29 23:34:08 +0000227 ++I;
Devang Patel2a4821b2008-03-03 18:36:03 +0000228 ++ParamIndex;
Devang Patelca891ec2008-02-29 23:34:08 +0000229 }
230
Devang Patel19c87462008-09-26 22:53:05 +0000231 // Add any fn attributes.
232 if (Attributes attrs = PAL.getFnAttributes())
233 AttributesVec.push_back(AttributeWithIndex::get(~0, attrs));
234
235
Owen Andersondebcb012009-07-29 22:17:13 +0000236 FunctionType *NFTy = FunctionType::get(STy, Params, FTy->isVarArg());
Matthijs Kooijman7d942002008-08-07 16:01:23 +0000237 Function *NF = Function::Create(NFTy, F->getLinkage());
238 NF->takeName(F);
Duncan Sands28c3cff2008-05-26 19:58:59 +0000239 NF->copyAttributesFrom(F);
Devang Patel05988662008-09-25 21:00:45 +0000240 NF->setAttributes(AttrListPtr::get(AttributesVec.begin(), AttributesVec.end()));
Devang Patelca891ec2008-02-29 23:34:08 +0000241 F->getParent()->getFunctionList().insert(F, NF);
242 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
243
244 // Replace arguments
245 I = F->arg_begin();
246 E = F->arg_end();
247 Function::arg_iterator NI = NF->arg_begin();
248 ++I;
249 while (I != E) {
250 I->replaceAllUsesWith(NI);
251 NI->takeName(I);
252 ++I;
253 ++NI;
254 }
255
256 return NF;
257}
258
259/// updateCallSites - Update all sites that call F to use NF.
260void SRETPromotion::updateCallSites(Function *F, Function *NF) {
Duncan Sandsa9c32512008-09-08 11:08:09 +0000261 CallGraph &CG = getAnalysis<CallGraph>();
Devang Patelca891ec2008-02-29 23:34:08 +0000262 SmallVector<Value*, 16> Args;
263
Devang Patel05988662008-09-25 21:00:45 +0000264 // Attributes - Keep track of the parameter attributes for the arguments.
265 SmallVector<AttributeWithIndex, 8> ArgAttrsVec;
Devang Patel2a4821b2008-03-03 18:36:03 +0000266
Matthijs Kooijmanc1f1d462008-08-14 15:03:05 +0000267 while (!F->use_empty()) {
268 CallSite CS = CallSite::get(*F->use_begin());
Devang Patelca891ec2008-02-29 23:34:08 +0000269 Instruction *Call = CS.getInstruction();
270
Devang Patel05988662008-09-25 21:00:45 +0000271 const AttrListPtr &PAL = F->getAttributes();
Devang Patel2a4821b2008-03-03 18:36:03 +0000272 // Add any return attributes.
Devang Patel19c87462008-09-26 22:53:05 +0000273 if (Attributes attrs = PAL.getRetAttributes())
Devang Patel05988662008-09-25 21:00:45 +0000274 ArgAttrsVec.push_back(AttributeWithIndex::get(0, attrs));
Devang Patel2a4821b2008-03-03 18:36:03 +0000275
Devang Patelca891ec2008-02-29 23:34:08 +0000276 // Copy arguments, however skip first one.
277 CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end();
278 Value *FirstCArg = *AI;
279 ++AI;
Devang Patel8f9b5512008-03-12 00:07:03 +0000280 // 0th parameter attribute is reserved for return type.
281 // 1th parameter attribute is for first 1st sret argument.
282 unsigned ParamIndex = 2;
Devang Patelca891ec2008-02-29 23:34:08 +0000283 while (AI != AE) {
284 Args.push_back(*AI);
Devang Patel19c87462008-09-26 22:53:05 +0000285 if (Attributes Attrs = PAL.getParamAttributes(ParamIndex))
Devang Patel05988662008-09-25 21:00:45 +0000286 ArgAttrsVec.push_back(AttributeWithIndex::get(ParamIndex - 1, Attrs));
Devang Patel2a4821b2008-03-03 18:36:03 +0000287 ++ParamIndex;
Devang Patelca891ec2008-02-29 23:34:08 +0000288 ++AI;
289 }
290
Devang Patel19c87462008-09-26 22:53:05 +0000291 // Add any function attributes.
292 if (Attributes attrs = PAL.getFnAttributes())
293 ArgAttrsVec.push_back(AttributeWithIndex::get(~0, attrs));
Chris Lattner58d74912008-03-12 17:45:29 +0000294
Devang Patel05988662008-09-25 21:00:45 +0000295 AttrListPtr NewPAL = AttrListPtr::get(ArgAttrsVec.begin(), ArgAttrsVec.end());
Chris Lattner58d74912008-03-12 17:45:29 +0000296
Devang Patelca891ec2008-02-29 23:34:08 +0000297 // Build new call instruction.
298 Instruction *New;
299 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
Gabor Greif051a9502008-04-06 20:25:17 +0000300 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
301 Args.begin(), Args.end(), "", Call);
Devang Patelca891ec2008-02-29 23:34:08 +0000302 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv());
Devang Patel05988662008-09-25 21:00:45 +0000303 cast<InvokeInst>(New)->setAttributes(NewPAL);
Devang Patelca891ec2008-02-29 23:34:08 +0000304 } else {
Gabor Greif051a9502008-04-06 20:25:17 +0000305 New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call);
Devang Patelca891ec2008-02-29 23:34:08 +0000306 cast<CallInst>(New)->setCallingConv(CS.getCallingConv());
Devang Patel05988662008-09-25 21:00:45 +0000307 cast<CallInst>(New)->setAttributes(NewPAL);
Devang Patelca891ec2008-02-29 23:34:08 +0000308 if (cast<CallInst>(Call)->isTailCall())
309 cast<CallInst>(New)->setTailCall();
310 }
311 Args.clear();
Devang Patel544b92b2008-03-04 19:12:58 +0000312 ArgAttrsVec.clear();
Devang Patelca891ec2008-02-29 23:34:08 +0000313 New->takeName(Call);
314
Duncan Sandsa9c32512008-09-08 11:08:09 +0000315 // Update the callgraph to know that the callsite has been transformed.
316 CG[Call->getParent()->getParent()]->replaceCallSite(Call, New);
317
Dan Gohmanfc74abf2008-07-23 00:34:11 +0000318 // Update all users of sret parameter to extract value using extractvalue.
Devang Patelca891ec2008-02-29 23:34:08 +0000319 for (Value::use_iterator UI = FirstCArg->use_begin(),
320 UE = FirstCArg->use_end(); UI != UE; ) {
321 User *U2 = *UI++;
322 CallInst *C2 = dyn_cast<CallInst>(U2);
323 if (C2 && (C2 == Call))
324 continue;
325 else if (GetElementPtrInst *UGEP = dyn_cast<GetElementPtrInst>(U2)) {
Devang Patel96f9cc02008-03-04 19:22:54 +0000326 ConstantInt *Idx = dyn_cast<ConstantInt>(UGEP->getOperand(2));
327 assert (Idx && "Unexpected getelementptr index!");
Dan Gohmanfc74abf2008-07-23 00:34:11 +0000328 Value *GR = ExtractValueInst::Create(New, Idx->getZExtValue(),
329 "evi", UGEP);
Matthijs Kooijmanc1f1d462008-08-14 15:03:05 +0000330 while(!UGEP->use_empty()) {
331 // isSafeToUpdateAllCallers has checked that all GEP uses are
332 // LoadInsts
333 LoadInst *L = cast<LoadInst>(*UGEP->use_begin());
334 L->replaceAllUsesWith(GR);
335 L->eraseFromParent();
Devang Patelca891ec2008-02-29 23:34:08 +0000336 }
337 UGEP->eraseFromParent();
338 }
339 else assert( 0 && "Unexpected sret parameter use");
340 }
341 Call->eraseFromParent();
342 }
343}
Devang Patela9fe8bb2008-03-04 21:32:09 +0000344
345/// nestedStructType - Return true if STy includes any
346/// other aggregate types
347bool SRETPromotion::nestedStructType(const StructType *STy) {
348 unsigned Num = STy->getNumElements();
349 for (unsigned i = 0; i < Num; i++) {
350 const Type *Ty = STy->getElementType(i);
Owen Anderson1d0be152009-08-13 21:58:54 +0000351 if (!Ty->isSingleValueType() && Ty != Type::getVoidTy(STy->getContext()))
Devang Patela9fe8bb2008-03-04 21:32:09 +0000352 return true;
353 }
354 return false;
355}