1 //===-- ArgumentPromotion.cpp - Promote 'by reference' arguments ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass promotes "by reference" arguments to be "by value" arguments. In
11 // practice, this means looking for internal functions that have pointer
12 // arguments. If we can prove, through the use of alias analysis, that that an
13 // argument is *only* loaded, then we can pass the value into the function
14 // instead of the address of the value. This can cause recursive simplification
15 // of code, and lead to the elimination of allocas, especially in C++ template
18 // This pass also handles aggregate arguments that are passed into a function,
19 // scalarizing them if the elements of the aggregate are only loaded. Note that
20 // we refuse to scalarize aggregates which would require passing in more than
21 // three operands to the function, because we don't want to pass thousands of
22 // operands for a large array or something!
24 // Note that this transformation could also be done for arguments that are only
25 // stored to (returning the value instead), but we do not currently handle that
26 // case. This case would be best handled when and if we start supporting
27 // multiple return values from functions.
29 //===----------------------------------------------------------------------===//
31 #include "llvm/Transforms/IPO.h"
32 #include "llvm/Constants.h"
33 #include "llvm/DerivedTypes.h"
34 #include "llvm/Module.h"
35 #include "llvm/Pass.h"
36 #include "llvm/Instructions.h"
37 #include "llvm/Analysis/AliasAnalysis.h"
38 #include "llvm/Target/TargetData.h"
39 #include "llvm/Support/CallSite.h"
40 #include "llvm/Support/CFG.h"
41 #include "Support/Debug.h"
42 #include "Support/DepthFirstIterator.h"
43 #include "Support/Statistic.h"
44 #include "Support/StringExtras.h"
49 Statistic<> NumArgumentsPromoted("argpromotion",
50 "Number of pointer arguments promoted");
51 Statistic<> NumAggregatesPromoted("argpromotion",
52 "Number of aggregate arguments promoted");
53 Statistic<> NumArgumentsDead("argpromotion",
54 "Number of dead pointer args eliminated");
56 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
58 class ArgPromotion : public Pass {
59 // WorkList - The set of internal functions that we have yet to process. As
60 // we eliminate arguments from a function, we push all callers into this set
61 // so that the by reference argument can be bubbled out as far as possible.
62 // This set contains only internal functions.
63 std::set<Function*> WorkList;
65 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
66 AU.addRequired<AliasAnalysis>();
67 AU.addRequired<TargetData>();
70 virtual bool run(Module &M);
72 bool PromoteArguments(Function *F);
73 bool isSafeToPromoteArgument(Argument *Arg) const;
74 void DoPromotion(Function *F, std::vector<Argument*> &ArgsToPromote);
77 RegisterOpt<ArgPromotion> X("argpromotion",
78 "Promote 'by reference' arguments to scalars");
81 Pass *llvm::createArgumentPromotionPass() {
82 return new ArgPromotion();
85 bool ArgPromotion::run(Module &M) {
87 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
88 if (I->hasInternalLinkage()) {
91 // If there are any constant pointer refs pointing to this function,
92 // eliminate them now if possible.
93 ConstantPointerRef *CPR = 0;
94 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
96 if ((CPR = dyn_cast<ConstantPointerRef>(*UI)))
99 // See if we can transform all users to use the function directly.
100 while (!CPR->use_empty()) {
101 User *TheUser = CPR->use_back();
102 if (!isa<Constant>(TheUser) && !isa<GlobalVariable>(TheUser)) {
104 TheUser->replaceUsesOfWith(CPR, I);
106 // We won't be able to eliminate all users. :(
107 WorkList.erase(I); // Minor efficiency win.
112 // If we nuked all users of the CPR, kill the CPR now!
113 if (CPR->use_empty()) {
114 CPR->destroyConstant();
120 while (!WorkList.empty()) {
121 Function *F = *WorkList.begin();
122 WorkList.erase(WorkList.begin());
124 if (PromoteArguments(F)) // Attempt to promote an argument.
125 Changed = true; // Remember that we changed something.
132 bool ArgPromotion::PromoteArguments(Function *F) {
133 assert(F->hasInternalLinkage() && "We can only process internal functions!");
135 // First check: see if there are any pointer arguments! If not, quick exit.
136 std::vector<Argument*> PointerArgs;
137 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I)
138 if (isa<PointerType>(I->getType()))
139 PointerArgs.push_back(I);
140 if (PointerArgs.empty()) return false;
142 // Second check: make sure that all callers are direct callers. We can't
143 // transform functions that have indirect callers.
144 for (Value::use_iterator UI = F->use_begin(), E = F->use_end();
146 CallSite CS = CallSite::get(*UI);
147 if (Instruction *I = CS.getInstruction()) {
148 // Ensure that this call site is CALLING the function, not passing it as
150 for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
152 if (*AI == F) return false; // Passing the function address in!
154 return false; // Cannot promote an indirect call!
158 // Check to see which arguments are promotable. If an argument is not
159 // promotable, remove it from the PointerArgs vector.
160 for (unsigned i = 0; i != PointerArgs.size(); ++i)
161 if (!isSafeToPromoteArgument(PointerArgs[i])) {
162 std::swap(PointerArgs[i--], PointerArgs.back());
163 PointerArgs.pop_back();
166 // No promotable pointer arguments.
167 if (PointerArgs.empty()) return false;
169 // Okay, promote all of the arguments are rewrite the callees!
170 DoPromotion(F, PointerArgs);
174 bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg) const {
175 // We can only promote this argument if all of the uses are loads, or are GEP
176 // instructions (with constant indices) that are subsequently loaded.
177 std::vector<LoadInst*> Loads;
178 std::vector<std::vector<Constant*> > GEPIndices;
179 for (Value::use_iterator UI = Arg->use_begin(), E = Arg->use_end();
181 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
182 if (LI->isVolatile()) return false; // Don't hack volatile loads
184 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
185 if (GEP->use_empty()) {
186 // Dead GEP's cause trouble later. Just remove them if we run into
188 GEP->getParent()->getInstList().erase(GEP);
189 return isSafeToPromoteArgument(Arg);
191 // Ensure that all of the indices are constants.
192 std::vector<Constant*> Operands;
193 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
194 if (Constant *C = dyn_cast<Constant>(GEP->getOperand(i)))
195 Operands.push_back(C);
197 return false; // Not a constant operand GEP!
199 // Ensure that the only users of the GEP are load instructions.
200 for (Value::use_iterator UI = GEP->use_begin(), E = GEP->use_end();
202 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
203 if (LI->isVolatile()) return false; // Don't hack volatile loads
209 // See if there is already a GEP with these indices. If so, check to make
210 // sure that we aren't promoting too many elements. If not, nothing to
212 if (std::find(GEPIndices.begin(), GEPIndices.end(), Operands) ==
214 if (GEPIndices.size() == 3) {
215 // We limit aggregate promotion to only promoting up to three elements
219 GEPIndices.push_back(Operands);
222 return false; // Not a load or a GEP.
225 if (Loads.empty()) return true; // No users, dead argument.
227 // Okay, now we know that the argument is only used by load instructions.
228 // Check to see if the pointer is guaranteed to not be modified from entry of
229 // the function to each of the load instructions.
230 Function &F = *Arg->getParent();
232 // Because there could be several/many load instructions, remember which
233 // blocks we know to be transparent to the load.
234 std::set<BasicBlock*> TranspBlocks;
236 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
237 TargetData &TD = getAnalysis<TargetData>();
239 for (unsigned i = 0, e = Loads.size(); i != e; ++i) {
240 // Check to see if the load is invalidated from the start of the block to
242 LoadInst *Load = Loads[i];
243 BasicBlock *BB = Load->getParent();
245 const PointerType *LoadTy =
246 cast<PointerType>(Load->getOperand(0)->getType());
247 unsigned LoadSize = TD.getTypeSize(LoadTy->getElementType());
249 if (AA.canInstructionRangeModify(BB->front(), *Load, Arg, LoadSize))
250 return false; // Pointer is invalidated!
252 // Now check every path from the entry block to the load for transparency.
253 // To do this, we perform a depth first search on the inverse CFG from the
255 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
256 for (idf_ext_iterator<BasicBlock*> I = idf_ext_begin(*PI, TranspBlocks),
257 E = idf_ext_end(*PI, TranspBlocks); I != E; ++I)
258 if (AA.canBasicBlockModify(**I, Arg, LoadSize))
262 // If the path from the entry of the function to each load is free of
263 // instructions that potentially invalidate the load, we can make the
269 void ArgPromotion::DoPromotion(Function *F, std::vector<Argument*> &Args2Prom) {
270 std::set<Argument*> ArgsToPromote(Args2Prom.begin(), Args2Prom.end());
272 // Start by computing a new prototype for the function, which is the same as
273 // the old function, but has modified arguments.
274 const FunctionType *FTy = F->getFunctionType();
275 std::vector<const Type*> Params;
277 // ScalarizedElements - If we are promoting a pointer that has elements
278 // accessed out of it, keep track of which elements are accessed so that we
279 // can add one argument for each.
281 // Arguments that are directly loaded will have a zero element value here, to
282 // handle cases where there are both a direct load and GEP accesses.
284 std::map<Argument*, std::set<std::vector<Value*> > > ScalarizedElements;
286 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I)
287 if (!ArgsToPromote.count(I)) {
288 Params.push_back(I->getType());
289 } else if (!I->use_empty()) {
290 // Okay, this is being promoted. Check to see if there are any GEP uses
292 std::set<std::vector<Value*> > &ArgIndices = ScalarizedElements[I];
293 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
295 Instruction *User = cast<Instruction>(*UI);
296 assert(isa<LoadInst>(User) || isa<GetElementPtrInst>(User));
297 ArgIndices.insert(std::vector<Value*>(User->op_begin()+1,
301 // Add a parameter to the function for each element passed in.
302 for (std::set<std::vector<Value*> >::iterator SI = ArgIndices.begin(),
303 E = ArgIndices.end(); SI != E; ++SI)
304 Params.push_back(GetElementPtrInst::getIndexedType(I->getType(), *SI));
306 if (ArgIndices.size() == 1 && ArgIndices.begin()->empty())
307 ++NumArgumentsPromoted;
309 ++NumAggregatesPromoted;
314 const Type *RetTy = FTy->getReturnType();
316 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which
317 // have zero fixed arguments.
318 bool ExtraArgHack = false;
319 if (Params.empty() && FTy->isVarArg()) {
321 Params.push_back(Type::IntTy);
323 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg());
325 // Create the new function body and insert it into the module...
326 Function *NF = new Function(NFTy, F->getLinkage(), F->getName());
327 F->getParent()->getFunctionList().insert(F, NF);
329 // Loop over all of the callers of the function, transforming the call sites
330 // to pass in the loaded pointers.
332 std::vector<Value*> Args;
333 while (!F->use_empty()) {
334 CallSite CS = CallSite::get(F->use_back());
335 Instruction *Call = CS.getInstruction();
337 // Make sure the caller of this function is revisited.
338 if (Call->getParent()->getParent()->hasInternalLinkage())
339 WorkList.insert(Call->getParent()->getParent());
341 // Loop over the operands, deleting dead ones...
342 CallSite::arg_iterator AI = CS.arg_begin();
343 for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I, ++AI)
344 if (!ArgsToPromote.count(I))
345 Args.push_back(*AI); // Unmodified argument
346 else if (!I->use_empty()) {
347 // Non-dead argument.
348 std::set<std::vector<Value*> > &ArgIndices = ScalarizedElements[I];
349 for (std::set<std::vector<Value*> >::iterator SI = ArgIndices.begin(),
350 E = ArgIndices.end(); SI != E; ++SI) {
353 V = new GetElementPtrInst(V, *SI, V->getName()+".idx", Call);
355 Args.push_back(new LoadInst(V, V->getName()+".val", Call));
360 Args.push_back(Constant::getNullValue(Type::IntTy));
362 // Push any varargs arguments on the list
363 for (; AI != CS.arg_end(); ++AI)
367 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
368 New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(),
371 New = new CallInst(NF, Args, "", Call);
375 if (!Call->use_empty()) {
376 Call->replaceAllUsesWith(New);
377 std::string Name = Call->getName();
382 // Finally, remove the old call from the program, reducing the use-count of
384 Call->getParent()->getInstList().erase(Call);
387 // Since we have now created the new function, splice the body of the old
388 // function right into the new function, leaving the old rotting hulk of the
390 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
392 // Loop over the argument list, transfering uses of the old arguments over to
393 // the new arguments, also transfering over the names as well.
395 for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin();
397 if (!ArgsToPromote.count(I)) {
398 // If this is an unmodified argument, move the name and users over to the
400 I->replaceAllUsesWith(I2);
401 I2->setName(I->getName());
403 } else if (!I->use_empty()) {
404 // Otherwise, if we promoted this argument, then all users are load
405 // instructions, and all loads should be using the new argument that we
407 std::set<std::vector<Value*> > &ArgIndices = ScalarizedElements[I];
409 while (!I->use_empty()) {
410 if (LoadInst *LI = dyn_cast<LoadInst>(I->use_back())) {
411 assert(ArgIndices.begin()->empty() &&
412 "Load element should sort to front!");
413 I2->setName(I->getName()+".val");
414 LI->replaceAllUsesWith(I2);
415 LI->getParent()->getInstList().erase(LI);
416 DEBUG(std::cerr << "*** Promoted argument '" << I->getName()
417 << "' of function '" << F->getName() << "'\n");
419 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->use_back());
420 std::vector<Value*> Operands(GEP->op_begin()+1, GEP->op_end());
423 Function::aiterator TheArg = I2;
424 for (std::set<std::vector<Value*> >::iterator It = ArgIndices.begin();
425 *It != Operands; ++It, ++TheArg) {
426 assert(It != ArgIndices.end() && "GEP not handled??");
429 std::string NewName = I->getName();
430 for (unsigned i = 0, e = Operands.size(); i != e; ++i)
431 if (ConstantInt *CI = dyn_cast<ConstantInt>(Operands[i]))
432 NewName += "."+itostr((int64_t)CI->getRawValue());
435 TheArg->setName(NewName+".val");
437 DEBUG(std::cerr << "*** Promoted agg argument '" << TheArg->getName()
438 << "' of function '" << F->getName() << "'\n");
440 // All of the uses must be load instructions. Replace them all with
441 // the argument specified by ArgNo.
442 while (!GEP->use_empty()) {
443 LoadInst *L = cast<LoadInst>(GEP->use_back());
444 L->replaceAllUsesWith(TheArg);
445 L->getParent()->getInstList().erase(L);
447 GEP->getParent()->getInstList().erase(GEP);
451 // If we inserted a new pointer type, it's possible that IT could be
452 // promoted too. Also, increment I2 past all of the arguments for this
454 for (unsigned i = 0, e = ArgIndices.size(); i != e; ++i, ++I2)
455 if (isa<PointerType>(I2->getType()))
459 // Now that the old function is dead, delete it.
460 F->getParent()->getFunctionList().erase(F);