LLVM API Documentation
00001 //===-- ArgumentPromotion.cpp - Promote by-reference 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 promotes "by reference" arguments to be "by value" arguments. In 00011 // practice, this means looking for internal functions that have pointer 00012 // arguments. If it can prove, through the use of alias analysis, that an 00013 // argument is *only* loaded, then it can pass the value into the function 00014 // instead of the address of the value. This can cause recursive simplification 00015 // of code and lead to the elimination of allocas (especially in C++ template 00016 // code like the STL). 00017 // 00018 // This pass also handles aggregate arguments that are passed into a function, 00019 // scalarizing them if the elements of the aggregate are only loaded. Note that 00020 // by default it refuses to scalarize aggregates which would require passing in 00021 // more than three operands to the function, because passing thousands of 00022 // operands for a large array or structure is unprofitable! This limit can be 00023 // configured or disabled, however. 00024 // 00025 // Note that this transformation could also be done for arguments that are only 00026 // stored to (returning the value instead), but does not currently. This case 00027 // would be best handled when and if LLVM begins supporting multiple return 00028 // values from functions. 00029 // 00030 //===----------------------------------------------------------------------===// 00031 00032 #define DEBUG_TYPE "argpromotion" 00033 #include "llvm/Transforms/IPO.h" 00034 #include "llvm/Constants.h" 00035 #include "llvm/DerivedTypes.h" 00036 #include "llvm/Module.h" 00037 #include "llvm/CallGraphSCCPass.h" 00038 #include "llvm/Instructions.h" 00039 #include "llvm/LLVMContext.h" 00040 #include "llvm/Analysis/AliasAnalysis.h" 00041 #include "llvm/Analysis/CallGraph.h" 00042 #include "llvm/Target/TargetData.h" 00043 #include "llvm/Support/CallSite.h" 00044 #include "llvm/Support/Compiler.h" 00045 #include "llvm/Support/CFG.h" 00046 #include "llvm/Support/Debug.h" 00047 #include "llvm/Support/raw_ostream.h" 00048 #include "llvm/ADT/DepthFirstIterator.h" 00049 #include "llvm/ADT/Statistic.h" 00050 #include <set> 00051 using namespace llvm; 00052 00053 STATISTIC(NumArgumentsPromoted , "Number of pointer arguments promoted"); 00054 STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted"); 00055 STATISTIC(NumByValArgsPromoted , "Number of byval arguments promoted"); 00056 STATISTIC(NumArgumentsDead , "Number of dead pointer args eliminated"); 00057 00058 namespace { 00059 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass. 00060 /// 00061 struct VISIBILITY_HIDDEN ArgPromotion : public CallGraphSCCPass { 00062 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00063 AU.addRequired<AliasAnalysis>(); 00064 CallGraphSCCPass::getAnalysisUsage(AU); 00065 } 00066 00067 virtual bool runOnSCC(const std::vector<CallGraphNode *> &SCC); 00068 static char ID; // Pass identification, replacement for typeid 00069 explicit ArgPromotion(unsigned maxElements = 3) 00070 : CallGraphSCCPass(&ID), maxElements(maxElements) {} 00071 00072 /// A vector used to hold the indices of a single GEP instruction 00073 typedef std::vector<uint64_t> IndicesVector; 00074 00075 private: 00076 bool PromoteArguments(CallGraphNode *CGN); 00077 bool isSafeToPromoteArgument(Argument *Arg, bool isByVal) const; 00078 Function *DoPromotion(Function *F, 00079 SmallPtrSet<Argument*, 8> &ArgsToPromote, 00080 SmallPtrSet<Argument*, 8> &ByValArgsToTransform); 00081 /// The maximum number of elements to expand, or 0 for unlimited. 00082 unsigned maxElements; 00083 }; 00084 } 00085 00086 char ArgPromotion::ID = 0; 00087 static RegisterPass<ArgPromotion> 00088 X("argpromotion", "Promote 'by reference' arguments to scalars"); 00089 00090 Pass *llvm::createArgumentPromotionPass(unsigned maxElements) { 00091 return new ArgPromotion(maxElements); 00092 } 00093 00094 bool ArgPromotion::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 00095 bool Changed = false, LocalChange; 00096 00097 do { // Iterate until we stop promoting from this SCC. 00098 LocalChange = false; 00099 // Attempt to promote arguments from all functions in this SCC. 00100 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 00101 LocalChange |= PromoteArguments(SCC[i]); 00102 Changed |= LocalChange; // Remember that we changed something. 00103 } while (LocalChange); 00104 00105 return Changed; 00106 } 00107 00108 /// PromoteArguments - This method checks the specified function to see if there 00109 /// are any promotable arguments and if it is safe to promote the function (for 00110 /// example, all callers are direct). If safe to promote some arguments, it 00111 /// calls the DoPromotion method. 00112 /// 00113 bool ArgPromotion::PromoteArguments(CallGraphNode *CGN) { 00114 Function *F = CGN->getFunction(); 00115 00116 // Make sure that it is local to this module. 00117 if (!F || !F->hasLocalLinkage()) return false; 00118 00119 // First check: see if there are any pointer arguments! If not, quick exit. 00120 SmallVector<std::pair<Argument*, unsigned>, 16> PointerArgs; 00121 unsigned ArgNo = 0; 00122 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00123 I != E; ++I, ++ArgNo) 00124 if (isa<PointerType>(I->getType())) 00125 PointerArgs.push_back(std::pair<Argument*, unsigned>(I, ArgNo)); 00126 if (PointerArgs.empty()) return false; 00127 00128 // Second check: make sure that all callers are direct callers. We can't 00129 // transform functions that have indirect callers. 00130 if (F->hasAddressTaken()) 00131 return false; 00132 00133 // Check to see which arguments are promotable. If an argument is promotable, 00134 // add it to ArgsToPromote. 00135 SmallPtrSet<Argument*, 8> ArgsToPromote; 00136 SmallPtrSet<Argument*, 8> ByValArgsToTransform; 00137 for (unsigned i = 0; i != PointerArgs.size(); ++i) { 00138 bool isByVal = F->paramHasAttr(PointerArgs[i].second+1, Attribute::ByVal); 00139 00140 // If this is a byval argument, and if the aggregate type is small, just 00141 // pass the elements, which is always safe. 00142 Argument *PtrArg = PointerArgs[i].first; 00143 if (isByVal) { 00144 const Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType(); 00145 if (const StructType *STy = dyn_cast<StructType>(AgTy)) { 00146 if (maxElements > 0 && STy->getNumElements() > maxElements) { 00147 DEBUG(errs() << "argpromotion disable promoting argument '" 00148 << PtrArg->getName() << "' because it would require adding more" 00149 << " than " << maxElements << " arguments to the function.\n"); 00150 } else { 00151 // If all the elements are single-value types, we can promote it. 00152 bool AllSimple = true; 00153 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 00154 if (!STy->getElementType(i)->isSingleValueType()) { 00155 AllSimple = false; 00156 break; 00157 } 00158 00159 // Safe to transform, don't even bother trying to "promote" it. 00160 // Passing the elements as a scalar will allow scalarrepl to hack on 00161 // the new alloca we introduce. 00162 if (AllSimple) { 00163 ByValArgsToTransform.insert(PtrArg); 00164 continue; 00165 } 00166 } 00167 } 00168 } 00169 00170 // Otherwise, see if we can promote the pointer to its value. 00171 if (isSafeToPromoteArgument(PtrArg, isByVal)) 00172 ArgsToPromote.insert(PtrArg); 00173 } 00174 00175 // No promotable pointer arguments. 00176 if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) return false; 00177 00178 Function *NewF = DoPromotion(F, ArgsToPromote, ByValArgsToTransform); 00179 00180 // Update the call graph to know that the function has been transformed. 00181 getAnalysis<CallGraph>().changeFunction(F, NewF); 00182 return true; 00183 } 00184 00185 /// IsAlwaysValidPointer - Return true if the specified pointer is always legal 00186 /// to load. 00187 static bool IsAlwaysValidPointer(Value *V) { 00188 if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true; 00189 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) 00190 return IsAlwaysValidPointer(GEP->getOperand(0)); 00191 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 00192 if (CE->getOpcode() == Instruction::GetElementPtr) 00193 return IsAlwaysValidPointer(CE->getOperand(0)); 00194 00195 return false; 00196 } 00197 00198 /// AllCalleesPassInValidPointerForArgument - Return true if we can prove that 00199 /// all callees pass in a valid pointer for the specified function argument. 00200 static bool AllCalleesPassInValidPointerForArgument(Argument *Arg) { 00201 Function *Callee = Arg->getParent(); 00202 00203 unsigned ArgNo = std::distance(Callee->arg_begin(), 00204 Function::arg_iterator(Arg)); 00205 00206 // Look at all call sites of the function. At this pointer we know we only 00207 // have direct callees. 00208 for (Value::use_iterator UI = Callee->use_begin(), E = Callee->use_end(); 00209 UI != E; ++UI) { 00210 CallSite CS = CallSite::get(*UI); 00211 assert(CS.getInstruction() && "Should only have direct calls!"); 00212 00213 if (!IsAlwaysValidPointer(CS.getArgument(ArgNo))) 00214 return false; 00215 } 00216 return true; 00217 } 00218 00219 /// Returns true if Prefix is a prefix of longer. That means, Longer has a size 00220 /// that is greater than or equal to the size of prefix, and each of the 00221 /// elements in Prefix is the same as the corresponding elements in Longer. 00222 /// 00223 /// This means it also returns true when Prefix and Longer are equal! 00224 static bool IsPrefix(const ArgPromotion::IndicesVector &Prefix, 00225 const ArgPromotion::IndicesVector &Longer) { 00226 if (Prefix.size() > Longer.size()) 00227 return false; 00228 for (unsigned i = 0, e = Prefix.size(); i != e; ++i) 00229 if (Prefix[i] != Longer[i]) 00230 return false; 00231 return true; 00232 } 00233 00234 00235 /// Checks if Indices, or a prefix of Indices, is in Set. 00236 static bool PrefixIn(const ArgPromotion::IndicesVector &Indices, 00237 std::set<ArgPromotion::IndicesVector> &Set) { 00238 std::set<ArgPromotion::IndicesVector>::iterator Low; 00239 Low = Set.upper_bound(Indices); 00240 if (Low != Set.begin()) 00241 Low--; 00242 // Low is now the last element smaller than or equal to Indices. This means 00243 // it points to a prefix of Indices (possibly Indices itself), if such 00244 // prefix exists. 00245 // 00246 // This load is safe if any prefix of its operands is safe to load. 00247 return Low != Set.end() && IsPrefix(*Low, Indices); 00248 } 00249 00250 /// Mark the given indices (ToMark) as safe in the the given set of indices 00251 /// (Safe). Marking safe usually means adding ToMark to Safe. However, if there 00252 /// is already a prefix of Indices in Safe, Indices are implicitely marked safe 00253 /// already. Furthermore, any indices that Indices is itself a prefix of, are 00254 /// removed from Safe (since they are implicitely safe because of Indices now). 00255 static void MarkIndicesSafe(const ArgPromotion::IndicesVector &ToMark, 00256 std::set<ArgPromotion::IndicesVector> &Safe) { 00257 std::set<ArgPromotion::IndicesVector>::iterator Low; 00258 Low = Safe.upper_bound(ToMark); 00259 // Guard against the case where Safe is empty 00260 if (Low != Safe.begin()) 00261 Low--; 00262 // Low is now the last element smaller than or equal to Indices. This 00263 // means it points to a prefix of Indices (possibly Indices itself), if 00264 // such prefix exists. 00265 if (Low != Safe.end()) { 00266 if (IsPrefix(*Low, ToMark)) 00267 // If there is already a prefix of these indices (or exactly these 00268 // indices) marked a safe, don't bother adding these indices 00269 return; 00270 00271 // Increment Low, so we can use it as a "insert before" hint 00272 ++Low; 00273 } 00274 // Insert 00275 Low = Safe.insert(Low, ToMark); 00276 ++Low; 00277 // If there we're a prefix of longer index list(s), remove those 00278 std::set<ArgPromotion::IndicesVector>::iterator End = Safe.end(); 00279 while (Low != End && IsPrefix(ToMark, *Low)) { 00280 std::set<ArgPromotion::IndicesVector>::iterator Remove = Low; 00281 ++Low; 00282 Safe.erase(Remove); 00283 } 00284 } 00285 00286 /// isSafeToPromoteArgument - As you might guess from the name of this method, 00287 /// it checks to see if it is both safe and useful to promote the argument. 00288 /// This method limits promotion of aggregates to only promote up to three 00289 /// elements of the aggregate in order to avoid exploding the number of 00290 /// arguments passed in. 00291 bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const { 00292 typedef std::set<IndicesVector> GEPIndicesSet; 00293 00294 // Quick exit for unused arguments 00295 if (Arg->use_empty()) 00296 return true; 00297 00298 // We can only promote this argument if all of the uses are loads, or are GEP 00299 // instructions (with constant indices) that are subsequently loaded. 00300 // 00301 // Promoting the argument causes it to be loaded in the caller 00302 // unconditionally. This is only safe if we can prove that either the load 00303 // would have happened in the callee anyway (ie, there is a load in the entry 00304 // block) or the pointer passed in at every call site is guaranteed to be 00305 // valid. 00306 // In the former case, invalid loads can happen, but would have happened 00307 // anyway, in the latter case, invalid loads won't happen. This prevents us 00308 // from introducing an invalid load that wouldn't have happened in the 00309 // original code. 00310 // 00311 // This set will contain all sets of indices that are loaded in the entry 00312 // block, and thus are safe to unconditionally load in the caller. 00313 GEPIndicesSet SafeToUnconditionallyLoad; 00314 00315 // This set contains all the sets of indices that we are planning to promote. 00316 // This makes it possible to limit the number of arguments added. 00317 GEPIndicesSet ToPromote; 00318 00319 // If the pointer is always valid, any load with first index 0 is valid. 00320 if(isByVal || AllCalleesPassInValidPointerForArgument(Arg)) 00321 SafeToUnconditionallyLoad.insert(IndicesVector(1, 0)); 00322 00323 // First, iterate the entry block and mark loads of (geps of) arguments as 00324 // safe. 00325 BasicBlock *EntryBlock = Arg->getParent()->begin(); 00326 // Declare this here so we can reuse it 00327 IndicesVector Indices; 00328 for (BasicBlock::iterator I = EntryBlock->begin(), E = EntryBlock->end(); 00329 I != E; ++I) 00330 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00331 Value *V = LI->getPointerOperand(); 00332 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) { 00333 V = GEP->getPointerOperand(); 00334 if (V == Arg) { 00335 // This load actually loads (part of) Arg? Check the indices then. 00336 Indices.reserve(GEP->getNumIndices()); 00337 for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end(); 00338 II != IE; ++II) 00339 if (ConstantInt *CI = dyn_cast<ConstantInt>(*II)) 00340 Indices.push_back(CI->getSExtValue()); 00341 else 00342 // We found a non-constant GEP index for this argument? Bail out 00343 // right away, can't promote this argument at all. 00344 return false; 00345 00346 // Indices checked out, mark them as safe 00347 MarkIndicesSafe(Indices, SafeToUnconditionallyLoad); 00348 Indices.clear(); 00349 } 00350 } else if (V == Arg) { 00351 // Direct loads are equivalent to a GEP with a single 0 index. 00352 MarkIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad); 00353 } 00354 } 00355 00356 // Now, iterate all uses of the argument to see if there are any uses that are 00357 // not (GEP+)loads, or any (GEP+)loads that are not safe to promote. 00358 SmallVector<LoadInst*, 16> Loads; 00359 IndicesVector Operands; 00360 for (Value::use_iterator UI = Arg->use_begin(), E = Arg->use_end(); 00361 UI != E; ++UI) { 00362 Operands.clear(); 00363 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 00364 if (LI->isVolatile()) return false; // Don't hack volatile loads 00365 Loads.push_back(LI); 00366 // Direct loads are equivalent to a GEP with a zero index and then a load. 00367 Operands.push_back(0); 00368 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { 00369 if (GEP->use_empty()) { 00370 // Dead GEP's cause trouble later. Just remove them if we run into 00371 // them. 00372 getAnalysis<AliasAnalysis>().deleteValue(GEP); 00373 GEP->eraseFromParent(); 00374 // TODO: This runs the above loop over and over again for dead GEPS 00375 // Couldn't we just do increment the UI iterator earlier and erase the 00376 // use? 00377 return isSafeToPromoteArgument(Arg, isByVal); 00378 } 00379 00380 // Ensure that all of the indices are constants. 00381 for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); 00382 i != e; ++i) 00383 if (ConstantInt *C = dyn_cast<ConstantInt>(*i)) 00384 Operands.push_back(C->getSExtValue()); 00385 else 00386 return false; // Not a constant operand GEP! 00387 00388 // Ensure that the only users of the GEP are load instructions. 00389 for (Value::use_iterator UI = GEP->use_begin(), E = GEP->use_end(); 00390 UI != E; ++UI) 00391 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 00392 if (LI->isVolatile()) return false; // Don't hack volatile loads 00393 Loads.push_back(LI); 00394 } else { 00395 // Other uses than load? 00396 return false; 00397 } 00398 } else { 00399 return false; // Not a load or a GEP. 00400 } 00401 00402 // Now, see if it is safe to promote this load / loads of this GEP. Loading 00403 // is safe if Operands, or a prefix of Operands, is marked as safe. 00404 if (!PrefixIn(Operands, SafeToUnconditionallyLoad)) 00405 return false; 00406 00407 // See if we are already promoting a load with these indices. If not, check 00408 // to make sure that we aren't promoting too many elements. If so, nothing 00409 // to do. 00410 if (ToPromote.find(Operands) == ToPromote.end()) { 00411 if (maxElements > 0 && ToPromote.size() == maxElements) { 00412 DEBUG(errs() << "argpromotion not promoting argument '" 00413 << Arg->getName() << "' because it would require adding more " 00414 << "than " << maxElements << " arguments to the function.\n"); 00415 // We limit aggregate promotion to only promoting up to a fixed number 00416 // of elements of the aggregate. 00417 return false; 00418 } 00419 ToPromote.insert(Operands); 00420 } 00421 } 00422 00423 if (Loads.empty()) return true; // No users, this is a dead argument. 00424 00425 // Okay, now we know that the argument is only used by load instructions and 00426 // it is safe to unconditionally perform all of them. Use alias analysis to 00427 // check to see if the pointer is guaranteed to not be modified from entry of 00428 // the function to each of the load instructions. 00429 00430 // Because there could be several/many load instructions, remember which 00431 // blocks we know to be transparent to the load. 00432 SmallPtrSet<BasicBlock*, 16> TranspBlocks; 00433 00434 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 00435 TargetData *TD = getAnalysisIfAvailable<TargetData>(); 00436 if (!TD) return false; // Without TargetData, assume the worst. 00437 00438 for (unsigned i = 0, e = Loads.size(); i != e; ++i) { 00439 // Check to see if the load is invalidated from the start of the block to 00440 // the load itself. 00441 LoadInst *Load = Loads[i]; 00442 BasicBlock *BB = Load->getParent(); 00443 00444 const PointerType *LoadTy = 00445 cast<PointerType>(Load->getPointerOperand()->getType()); 00446 unsigned LoadSize =(unsigned)TD->getTypeStoreSize(LoadTy->getElementType()); 00447 00448 if (AA.canInstructionRangeModify(BB->front(), *Load, Arg, LoadSize)) 00449 return false; // Pointer is invalidated! 00450 00451 // Now check every path from the entry block to the load for transparency. 00452 // To do this, we perform a depth first search on the inverse CFG from the 00453 // loading block. 00454 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 00455 for (idf_ext_iterator<BasicBlock*, SmallPtrSet<BasicBlock*, 16> > 00456 I = idf_ext_begin(*PI, TranspBlocks), 00457 E = idf_ext_end(*PI, TranspBlocks); I != E; ++I) 00458 if (AA.canBasicBlockModify(**I, Arg, LoadSize)) 00459 return false; 00460 } 00461 00462 // If the path from the entry of the function to each load is free of 00463 // instructions that potentially invalidate the load, we can make the 00464 // transformation! 00465 return true; 00466 } 00467 00468 /// DoPromotion - This method actually performs the promotion of the specified 00469 /// arguments, and returns the new function. At this point, we know that it's 00470 /// safe to do so. 00471 Function *ArgPromotion::DoPromotion(Function *F, 00472 SmallPtrSet<Argument*, 8> &ArgsToPromote, 00473 SmallPtrSet<Argument*, 8> &ByValArgsToTransform) { 00474 00475 // Start by computing a new prototype for the function, which is the same as 00476 // the old function, but has modified arguments. 00477 const FunctionType *FTy = F->getFunctionType(); 00478 std::vector<const Type*> Params; 00479 00480 typedef std::set<IndicesVector> ScalarizeTable; 00481 00482 // ScalarizedElements - If we are promoting a pointer that has elements 00483 // accessed out of it, keep track of which elements are accessed so that we 00484 // can add one argument for each. 00485 // 00486 // Arguments that are directly loaded will have a zero element value here, to 00487 // handle cases where there are both a direct load and GEP accesses. 00488 // 00489 std::map<Argument*, ScalarizeTable> ScalarizedElements; 00490 00491 // OriginalLoads - Keep track of a representative load instruction from the 00492 // original function so that we can tell the alias analysis implementation 00493 // what the new GEP/Load instructions we are inserting look like. 00494 std::map<IndicesVector, LoadInst*> OriginalLoads; 00495 00496 // Attributes - Keep track of the parameter attributes for the arguments 00497 // that we are *not* promoting. For the ones that we do promote, the parameter 00498 // attributes are lost 00499 SmallVector<AttributeWithIndex, 8> AttributesVec; 00500 const AttrListPtr &PAL = F->getAttributes(); 00501 00502 // Add any return attributes. 00503 if (Attributes attrs = PAL.getRetAttributes()) 00504 AttributesVec.push_back(AttributeWithIndex::get(0, attrs)); 00505 00506 // First, determine the new argument list 00507 unsigned ArgIndex = 1; 00508 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; 00509 ++I, ++ArgIndex) { 00510 if (ByValArgsToTransform.count(I)) { 00511 // Simple byval argument? Just add all the struct element types. 00512 const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 00513 const StructType *STy = cast<StructType>(AgTy); 00514 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 00515 Params.push_back(STy->getElementType(i)); 00516 ++NumByValArgsPromoted; 00517 } else if (!ArgsToPromote.count(I)) { 00518 // Unchanged argument 00519 Params.push_back(I->getType()); 00520 if (Attributes attrs = PAL.getParamAttributes(ArgIndex)) 00521 AttributesVec.push_back(AttributeWithIndex::get(Params.size(), attrs)); 00522 } else if (I->use_empty()) { 00523 // Dead argument (which are always marked as promotable) 00524 ++NumArgumentsDead; 00525 } else { 00526 // Okay, this is being promoted. This means that the only uses are loads 00527 // or GEPs which are only used by loads 00528 00529 // In this table, we will track which indices are loaded from the argument 00530 // (where direct loads are tracked as no indices). 00531 ScalarizeTable &ArgIndices = ScalarizedElements[I]; 00532 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 00533 ++UI) { 00534 Instruction *User = cast<Instruction>(*UI); 00535 assert(isa<LoadInst>(User) || isa<GetElementPtrInst>(User)); 00536 IndicesVector Indices; 00537 Indices.reserve(User->getNumOperands() - 1); 00538 // Since loads will only have a single operand, and GEPs only a single 00539 // non-index operand, this will record direct loads without any indices, 00540 // and gep+loads with the GEP indices. 00541 for (User::op_iterator II = User->op_begin() + 1, IE = User->op_end(); 00542 II != IE; ++II) 00543 Indices.push_back(cast<ConstantInt>(*II)->getSExtValue()); 00544 // GEPs with a single 0 index can be merged with direct loads 00545 if (Indices.size() == 1 && Indices.front() == 0) 00546 Indices.clear(); 00547 ArgIndices.insert(Indices); 00548 LoadInst *OrigLoad; 00549 if (LoadInst *L = dyn_cast<LoadInst>(User)) 00550 OrigLoad = L; 00551 else 00552 // Take any load, we will use it only to update Alias Analysis 00553 OrigLoad = cast<LoadInst>(User->use_back()); 00554 OriginalLoads[Indices] = OrigLoad; 00555 } 00556 00557 // Add a parameter to the function for each element passed in. 00558 for (ScalarizeTable::iterator SI = ArgIndices.begin(), 00559 E = ArgIndices.end(); SI != E; ++SI) { 00560 // not allowed to dereference ->begin() if size() is 0 00561 Params.push_back(GetElementPtrInst::getIndexedType(I->getType(), 00562 SI->begin(), 00563 SI->end())); 00564 assert(Params.back()); 00565 } 00566 00567 if (ArgIndices.size() == 1 && ArgIndices.begin()->empty()) 00568 ++NumArgumentsPromoted; 00569 else 00570 ++NumAggregatesPromoted; 00571 } 00572 } 00573 00574 // Add any function attributes. 00575 if (Attributes attrs = PAL.getFnAttributes()) 00576 AttributesVec.push_back(AttributeWithIndex::get(~0, attrs)); 00577 00578 const Type *RetTy = FTy->getReturnType(); 00579 00580 // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which 00581 // have zero fixed arguments. 00582 bool ExtraArgHack = false; 00583 if (Params.empty() && FTy->isVarArg()) { 00584 ExtraArgHack = true; 00585 Params.push_back(Type::getInt32Ty(F->getContext())); 00586 } 00587 00588 // Construct the new function type using the new arguments. 00589 FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); 00590 00591 // Create the new function body and insert it into the module... 00592 Function *NF = Function::Create(NFTy, F->getLinkage(), F->getName()); 00593 NF->copyAttributesFrom(F); 00594 00595 // Recompute the parameter attributes list based on the new arguments for 00596 // the function. 00597 NF->setAttributes(AttrListPtr::get(AttributesVec.begin(), AttributesVec.end())); 00598 AttributesVec.clear(); 00599 00600 F->getParent()->getFunctionList().insert(F, NF); 00601 NF->takeName(F); 00602 00603 // Get the alias analysis information that we need to update to reflect our 00604 // changes. 00605 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 00606 00607 // Get the callgraph information that we need to update to reflect our 00608 // changes. 00609 CallGraph &CG = getAnalysis<CallGraph>(); 00610 00611 // Loop over all of the callers of the function, transforming the call sites 00612 // to pass in the loaded pointers. 00613 // 00614 SmallVector<Value*, 16> Args; 00615 while (!F->use_empty()) { 00616 CallSite CS = CallSite::get(F->use_back()); 00617 Instruction *Call = CS.getInstruction(); 00618 const AttrListPtr &CallPAL = CS.getAttributes(); 00619 00620 // Add any return attributes. 00621 if (Attributes attrs = CallPAL.getRetAttributes()) 00622 AttributesVec.push_back(AttributeWithIndex::get(0, attrs)); 00623 00624 // Loop over the operands, inserting GEP and loads in the caller as 00625 // appropriate. 00626 CallSite::arg_iterator AI = CS.arg_begin(); 00627 ArgIndex = 1; 00628 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); 00629 I != E; ++I, ++AI, ++ArgIndex) 00630 if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) { 00631 Args.push_back(*AI); // Unmodified argument 00632 00633 if (Attributes Attrs = CallPAL.getParamAttributes(ArgIndex)) 00634 AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); 00635 00636 } else if (ByValArgsToTransform.count(I)) { 00637 // Emit a GEP and load for each element of the struct. 00638 const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 00639 const StructType *STy = cast<StructType>(AgTy); 00640 Value *Idxs[2] = { 00641 ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), 0 }; 00642 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 00643 Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i); 00644 Value *Idx = GetElementPtrInst::Create(*AI, Idxs, Idxs+2, 00645 (*AI)->getName()+"."+utostr(i), 00646 Call); 00647 // TODO: Tell AA about the new values? 00648 Args.push_back(new LoadInst(Idx, Idx->getName()+".val", Call)); 00649 } 00650 } else if (!I->use_empty()) { 00651 // Non-dead argument: insert GEPs and loads as appropriate. 00652 ScalarizeTable &ArgIndices = ScalarizedElements[I]; 00653 // Store the Value* version of the indices in here, but declare it now 00654 // for reuse 00655 std::vector<Value*> Ops; 00656 for (ScalarizeTable::iterator SI = ArgIndices.begin(), 00657 E = ArgIndices.end(); SI != E; ++SI) { 00658 Value *V = *AI; 00659 LoadInst *OrigLoad = OriginalLoads[*SI]; 00660 if (!SI->empty()) { 00661 Ops.reserve(SI->size()); 00662 const Type *ElTy = V->getType(); 00663 for (IndicesVector::const_iterator II = SI->begin(), 00664 IE = SI->end(); II != IE; ++II) { 00665 // Use i32 to index structs, and i64 for others (pointers/arrays). 00666 // This satisfies GEP constraints. 00667 const Type *IdxTy = (isa<StructType>(ElTy) ? 00668 Type::getInt32Ty(F->getContext()) : 00669 Type::getInt64Ty(F->getContext())); 00670 Ops.push_back(ConstantInt::get(IdxTy, *II)); 00671 // Keep track of the type we're currently indexing 00672 ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(*II); 00673 } 00674 // And create a GEP to extract those indices 00675 V = GetElementPtrInst::Create(V, Ops.begin(), Ops.end(), 00676 V->getName()+".idx", Call); 00677 Ops.clear(); 00678 AA.copyValue(OrigLoad->getOperand(0), V); 00679 } 00680 Args.push_back(new LoadInst(V, V->getName()+".val", Call)); 00681 AA.copyValue(OrigLoad, Args.back()); 00682 } 00683 } 00684 00685 if (ExtraArgHack) 00686 Args.push_back(Constant::getNullValue(Type::getInt32Ty(F->getContext()))); 00687 00688 // Push any varargs arguments on the list 00689 for (; AI != CS.arg_end(); ++AI, ++ArgIndex) { 00690 Args.push_back(*AI); 00691 if (Attributes Attrs = CallPAL.getParamAttributes(ArgIndex)) 00692 AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); 00693 } 00694 00695 // Add any function attributes. 00696 if (Attributes attrs = CallPAL.getFnAttributes()) 00697 AttributesVec.push_back(AttributeWithIndex::get(~0, attrs)); 00698 00699 Instruction *New; 00700 if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { 00701 New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), 00702 Args.begin(), Args.end(), "", Call); 00703 cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); 00704 cast<InvokeInst>(New)->setAttributes(AttrListPtr::get(AttributesVec.begin(), 00705 AttributesVec.end())); 00706 } else { 00707 New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call); 00708 cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); 00709 cast<CallInst>(New)->setAttributes(AttrListPtr::get(AttributesVec.begin(), 00710 AttributesVec.end())); 00711 if (cast<CallInst>(Call)->isTailCall()) 00712 cast<CallInst>(New)->setTailCall(); 00713 } 00714 Args.clear(); 00715 AttributesVec.clear(); 00716 00717 // Update the alias analysis implementation to know that we are replacing 00718 // the old call with a new one. 00719 AA.replaceWithNewValue(Call, New); 00720 00721 // Update the callgraph to know that the callsite has been transformed. 00722 CG[Call->getParent()->getParent()]->replaceCallSite(Call, New); 00723 00724 if (!Call->use_empty()) { 00725 Call->replaceAllUsesWith(New); 00726 New->takeName(Call); 00727 } 00728 00729 // Finally, remove the old call from the program, reducing the use-count of 00730 // F. 00731 Call->eraseFromParent(); 00732 } 00733 00734 // Since we have now created the new function, splice the body of the old 00735 // function right into the new function, leaving the old rotting hulk of the 00736 // function empty. 00737 NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); 00738 00739 // Loop over the argument list, transfering uses of the old arguments over to 00740 // the new arguments, also transfering over the names as well. 00741 // 00742 for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), 00743 I2 = NF->arg_begin(); I != E; ++I) { 00744 if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) { 00745 // If this is an unmodified argument, move the name and users over to the 00746 // new version. 00747 I->replaceAllUsesWith(I2); 00748 I2->takeName(I); 00749 AA.replaceWithNewValue(I, I2); 00750 ++I2; 00751 continue; 00752 } 00753 00754 if (ByValArgsToTransform.count(I)) { 00755 // In the callee, we create an alloca, and store each of the new incoming 00756 // arguments into the alloca. 00757 Instruction *InsertPt = NF->begin()->begin(); 00758 00759 // Just add all the struct element types. 00760 const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); 00761 Value *TheAlloca = new AllocaInst(AgTy, 0, "", InsertPt); 00762 const StructType *STy = cast<StructType>(AgTy); 00763 Value *Idxs[2] = { 00764 ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), 0 }; 00765 00766 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 00767 Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i); 00768 Value *Idx = 00769 GetElementPtrInst::Create(TheAlloca, Idxs, Idxs+2, 00770 TheAlloca->getName()+"."+Twine(i), 00771 InsertPt); 00772 I2->setName(I->getName()+"."+Twine(i)); 00773 new StoreInst(I2++, Idx, InsertPt); 00774 } 00775 00776 // Anything that used the arg should now use the alloca. 00777 I->replaceAllUsesWith(TheAlloca); 00778 TheAlloca->takeName(I); 00779 AA.replaceWithNewValue(I, TheAlloca); 00780 continue; 00781 } 00782 00783 if (I->use_empty()) { 00784 AA.deleteValue(I); 00785 continue; 00786 } 00787 00788 // Otherwise, if we promoted this argument, then all users are load 00789 // instructions (or GEPs with only load users), and all loads should be 00790 // using the new argument that we added. 00791 ScalarizeTable &ArgIndices = ScalarizedElements[I]; 00792 00793 while (!I->use_empty()) { 00794 if (LoadInst *LI = dyn_cast<LoadInst>(I->use_back())) { 00795 assert(ArgIndices.begin()->empty() && 00796 "Load element should sort to front!"); 00797 I2->setName(I->getName()+".val"); 00798 LI->replaceAllUsesWith(I2); 00799 AA.replaceWithNewValue(LI, I2); 00800 LI->eraseFromParent(); 00801 DEBUG(errs() << "*** Promoted load of argument '" << I->getName() 00802 << "' in function '" << F->getName() << "'\n"); 00803 } else { 00804 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->use_back()); 00805 IndicesVector Operands; 00806 Operands.reserve(GEP->getNumIndices()); 00807 for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end(); 00808 II != IE; ++II) 00809 Operands.push_back(cast<ConstantInt>(*II)->getSExtValue()); 00810 00811 // GEPs with a single 0 index can be merged with direct loads 00812 if (Operands.size() == 1 && Operands.front() == 0) 00813 Operands.clear(); 00814 00815 Function::arg_iterator TheArg = I2; 00816 for (ScalarizeTable::iterator It = ArgIndices.begin(); 00817 *It != Operands; ++It, ++TheArg) { 00818 assert(It != ArgIndices.end() && "GEP not handled??"); 00819 } 00820 00821 std::string NewName = I->getName(); 00822 for (unsigned i = 0, e = Operands.size(); i != e; ++i) { 00823 NewName += "." + utostr(Operands[i]); 00824 } 00825 NewName += ".val"; 00826 TheArg->setName(NewName); 00827 00828 DEBUG(errs() << "*** Promoted agg argument '" << TheArg->getName() 00829 << "' of function '" << NF->getName() << "'\n"); 00830 00831 // All of the uses must be load instructions. Replace them all with 00832 // the argument specified by ArgNo. 00833 while (!GEP->use_empty()) { 00834 LoadInst *L = cast<LoadInst>(GEP->use_back()); 00835 L->replaceAllUsesWith(TheArg); 00836 AA.replaceWithNewValue(L, TheArg); 00837 L->eraseFromParent(); 00838 } 00839 AA.deleteValue(GEP); 00840 GEP->eraseFromParent(); 00841 } 00842 } 00843 00844 // Increment I2 past all of the arguments added for this promoted pointer. 00845 for (unsigned i = 0, e = ArgIndices.size(); i != e; ++i) 00846 ++I2; 00847 } 00848 00849 // Notify the alias analysis implementation that we inserted a new argument. 00850 if (ExtraArgHack) 00851 AA.copyValue(Constant::getNullValue(Type::getInt32Ty(F->getContext())), 00852 NF->arg_begin()); 00853 00854 00855 // Tell the alias analysis that the old function is about to disappear. 00856 AA.replaceWithNewValue(F, NF); 00857 00858 // Now that the old function is dead, delete it. 00859 F->eraseFromParent(); 00860 return NF; 00861 }