Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame^] | 1 | //===-- ArgumentPromotion.cpp - Promote 'by reference' arguments ----------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 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. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 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 |
| 16 | // code like the STL. |
| 17 | // |
| 18 | // Note that this transformation could also be done for arguments that are only |
| 19 | // stored to (returning the value instead), but we do not currently handle that |
| 20 | // case. |
| 21 | // |
| 22 | // Note that we should be able to promote pointers to structures that are only |
| 23 | // loaded from as well. The danger is creating way to many arguments, so this |
| 24 | // transformation should be limited to 3 element structs or something. |
| 25 | // |
| 26 | //===----------------------------------------------------------------------===// |
| 27 | |
| 28 | #include "llvm/Transforms/IPO.h" |
| 29 | #include "llvm/Constants.h" |
| 30 | #include "llvm/DerivedTypes.h" |
| 31 | #include "llvm/Module.h" |
| 32 | #include "llvm/Pass.h" |
| 33 | #include "llvm/Instructions.h" |
| 34 | #include "llvm/Analysis/AliasAnalysis.h" |
| 35 | #include "llvm/Target/TargetData.h" |
| 36 | #include "llvm/Support/CallSite.h" |
| 37 | #include "llvm/Support/CFG.h" |
| 38 | #include "Support/Debug.h" |
| 39 | #include "Support/DepthFirstIterator.h" |
| 40 | #include "Support/Statistic.h" |
| 41 | #include <set> |
| 42 | using namespace llvm; |
| 43 | |
| 44 | namespace { |
| 45 | Statistic<> NumArgumentsPromoted("argpromotion", |
| 46 | "Number of pointer arguments promoted"); |
| 47 | Statistic<> NumArgumentsDead("argpromotion", |
| 48 | "Number of dead pointer args eliminated"); |
| 49 | |
| 50 | /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass. |
| 51 | /// |
| 52 | class ArgPromotion : public Pass { |
| 53 | // WorkList - The set of internal functions that we have yet to process. As |
| 54 | // we eliminate arguments from a function, we push all callers into this set |
| 55 | // so that the by reference argument can be bubbled out as far as possible. |
| 56 | // This set contains only internal functions. |
| 57 | std::set<Function*> WorkList; |
| 58 | public: |
| 59 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 60 | AU.addRequired<AliasAnalysis>(); |
| 61 | AU.addRequired<TargetData>(); |
| 62 | } |
| 63 | |
| 64 | virtual bool run(Module &M); |
| 65 | private: |
| 66 | bool PromoteArguments(Function *F); |
| 67 | bool isSafeToPromoteArgument(Argument *Arg) const; |
| 68 | void DoPromotion(Function *F, std::vector<Argument*> &ArgsToPromote); |
| 69 | }; |
| 70 | |
| 71 | RegisterOpt<ArgPromotion> X("argpromotion", |
| 72 | "Promote 'by reference' arguments to scalars"); |
| 73 | } |
| 74 | |
| 75 | Pass *llvm::createArgumentPromotionPass() { |
| 76 | return new ArgPromotion(); |
| 77 | } |
| 78 | |
| 79 | bool ArgPromotion::run(Module &M) { |
| 80 | bool Changed = false; |
| 81 | for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| 82 | if (I->hasInternalLinkage()) { |
| 83 | WorkList.insert(I); |
| 84 | |
| 85 | // If there are any constant pointer refs pointing to this function, |
| 86 | // eliminate them now if possible. |
| 87 | ConstantPointerRef *CPR = 0; |
| 88 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; |
| 89 | ++UI) |
| 90 | if ((CPR = dyn_cast<ConstantPointerRef>(*UI))) |
| 91 | break; // Found one! |
| 92 | if (CPR) { |
| 93 | // See if we can transform all users to use the function directly. |
| 94 | while (!CPR->use_empty()) { |
| 95 | User *TheUser = CPR->use_back(); |
| 96 | if (!isa<Constant>(TheUser)) { |
| 97 | Changed = true; |
| 98 | TheUser->replaceUsesOfWith(CPR, I); |
| 99 | } else { |
| 100 | // We won't be able to eliminate all users. :( |
| 101 | WorkList.erase(I); // Minor efficiency win. |
| 102 | break; |
| 103 | } |
| 104 | } |
| 105 | |
| 106 | // If we nuked all users of the CPR, kill the CPR now! |
| 107 | if (CPR->use_empty()) { |
| 108 | CPR->destroyConstant(); |
| 109 | Changed = true; |
| 110 | } |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | while (!WorkList.empty()) { |
| 115 | Function *F = *WorkList.begin(); |
| 116 | WorkList.erase(WorkList.begin()); |
| 117 | |
| 118 | if (PromoteArguments(F)) // Attempt to promote an argument. |
| 119 | Changed = true; // Remember that we changed something. |
| 120 | } |
| 121 | |
| 122 | return Changed; |
| 123 | } |
| 124 | |
| 125 | |
| 126 | bool ArgPromotion::PromoteArguments(Function *F) { |
| 127 | assert(F->hasInternalLinkage() && "We can only process internal functions!"); |
| 128 | |
| 129 | // First check: see if there are any pointer arguments! If not, quick exit. |
| 130 | std::vector<Argument*> PointerArgs; |
| 131 | for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) |
| 132 | if (isa<PointerType>(I->getType())) |
| 133 | PointerArgs.push_back(I); |
| 134 | if (PointerArgs.empty()) return false; |
| 135 | |
| 136 | // Second check: make sure that all callers are direct callers. We can't |
| 137 | // transform functions that have indirect callers. |
| 138 | for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); |
| 139 | UI != E; ++UI) |
| 140 | // What about CPRs? |
| 141 | if (!CallSite::get(*UI).getInstruction()) |
| 142 | return false; // Cannot promote an indirect call! |
| 143 | |
| 144 | // Check to see which arguments are promotable. If an argument is not |
| 145 | // promotable, remove it from the PointerArgs vector. |
| 146 | for (unsigned i = 0; i != PointerArgs.size(); ++i) |
| 147 | if (!isSafeToPromoteArgument(PointerArgs[i])) { |
| 148 | std::swap(PointerArgs[i--], PointerArgs.back()); |
| 149 | PointerArgs.pop_back(); |
| 150 | } |
| 151 | |
| 152 | // No promotable pointer arguments. |
| 153 | if (PointerArgs.empty()) return false; |
| 154 | |
| 155 | // Okay, promote all of the arguments are rewrite the callees! |
| 156 | DoPromotion(F, PointerArgs); |
| 157 | return true; |
| 158 | } |
| 159 | |
| 160 | bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg) const { |
| 161 | // We can only promote this argument if all of the uses are loads... |
| 162 | std::vector<LoadInst*> Loads; |
| 163 | for (Value::use_iterator UI = Arg->use_begin(), E = Arg->use_end(); |
| 164 | UI != E; ++UI) |
| 165 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 166 | if (LI->isVolatile()) return false; // Don't hack volatile loads |
| 167 | Loads.push_back(LI); |
| 168 | } else |
| 169 | return false; |
| 170 | |
| 171 | if (Loads.empty()) return true; // No users, dead argument. |
| 172 | |
| 173 | const Type *LoadTy = cast<PointerType>(Arg->getType())->getElementType(); |
| 174 | unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LoadTy); |
| 175 | |
| 176 | // Okay, now we know that the argument is only used by load instructions. |
| 177 | // Check to see if the pointer is guaranteed to not be modified from entry of |
| 178 | // the function to each of the load instructions. |
| 179 | Function &F = *Arg->getParent(); |
| 180 | |
| 181 | // Because there could be several/many load instructions, remember which |
| 182 | // blocks we know to be transparent to the load. |
| 183 | std::set<BasicBlock*> TranspBlocks; |
| 184 | |
| 185 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 186 | |
| 187 | for (unsigned i = 0, e = Loads.size(); i != e; ++i) { |
| 188 | // Check to see if the load is invalidated from the start of the block to |
| 189 | // the load itself. |
| 190 | LoadInst *Load = Loads[i]; |
| 191 | BasicBlock *BB = Load->getParent(); |
| 192 | if (AA.canInstructionRangeModify(BB->front(), *Load, Arg, LoadSize)) |
| 193 | return false; // Pointer is invalidated! |
| 194 | |
| 195 | // Now check every path from the entry block to the load for transparency. |
| 196 | // To do this, we perform a depth first search on the inverse CFG from the |
| 197 | // loading block. |
| 198 | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) |
| 199 | for (idf_ext_iterator<BasicBlock*> I = idf_ext_begin(*PI, TranspBlocks), |
| 200 | E = idf_ext_end(*PI, TranspBlocks); I != E; ++I) |
| 201 | if (AA.canBasicBlockModify(**I, Arg, LoadSize)) |
| 202 | return false; |
| 203 | } |
| 204 | |
| 205 | // If the path from the entry of the function to each load is free of |
| 206 | // instructions that potentially invalidate the load, we can make the |
| 207 | // transformation! |
| 208 | return true; |
| 209 | } |
| 210 | |
| 211 | |
| 212 | void ArgPromotion::DoPromotion(Function *F, std::vector<Argument*> &Args2Prom) { |
| 213 | std::set<Argument*> ArgsToPromote(Args2Prom.begin(), Args2Prom.end()); |
| 214 | |
| 215 | // Start by computing a new prototype for the function, which is the same as |
| 216 | // the old function, but has modified arguments. |
| 217 | const FunctionType *FTy = F->getFunctionType(); |
| 218 | std::vector<const Type*> Params; |
| 219 | |
| 220 | for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) |
| 221 | if (!ArgsToPromote.count(I)) { |
| 222 | Params.push_back(I->getType()); |
| 223 | } else if (!I->use_empty()) { |
| 224 | Params.push_back(cast<PointerType>(I->getType())->getElementType()); |
| 225 | ++NumArgumentsPromoted; |
| 226 | } else { |
| 227 | ++NumArgumentsDead; |
| 228 | } |
| 229 | |
| 230 | const Type *RetTy = FTy->getReturnType(); |
| 231 | |
| 232 | // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which |
| 233 | // have zero fixed arguments. |
| 234 | bool ExtraArgHack = false; |
| 235 | if (Params.empty() && FTy->isVarArg()) { |
| 236 | ExtraArgHack = true; |
| 237 | Params.push_back(Type::IntTy); |
| 238 | } |
| 239 | FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); |
| 240 | |
| 241 | // Create the new function body and insert it into the module... |
| 242 | Function *NF = new Function(NFTy, F->getLinkage(), F->getName()); |
| 243 | F->getParent()->getFunctionList().insert(F, NF); |
| 244 | |
| 245 | // Loop over all of the callers of the function, transforming the call sites |
| 246 | // to pass in the loaded pointers. |
| 247 | // |
| 248 | std::vector<Value*> Args; |
| 249 | while (!F->use_empty()) { |
| 250 | CallSite CS = CallSite::get(F->use_back()); |
| 251 | Instruction *Call = CS.getInstruction(); |
| 252 | |
| 253 | // Make sure the caller of this function is revisited. |
| 254 | if (Call->getParent()->getParent()->hasInternalLinkage()) |
| 255 | WorkList.insert(Call->getParent()->getParent()); |
| 256 | |
| 257 | // Loop over the operands, deleting dead ones... |
| 258 | CallSite::arg_iterator AI = CS.arg_begin(); |
| 259 | for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I, ++AI) |
| 260 | if (!ArgsToPromote.count(I)) |
| 261 | Args.push_back(*AI); // Unmodified argument |
| 262 | else if (!I->use_empty()) { |
| 263 | // Non-dead instruction |
| 264 | Args.push_back(new LoadInst(*AI, (*AI)->getName()+".val", Call)); |
| 265 | } |
| 266 | |
| 267 | if (ExtraArgHack) |
| 268 | Args.push_back(Constant::getNullValue(Type::IntTy)); |
| 269 | |
| 270 | // Push any varargs arguments on the list |
| 271 | for (; AI != CS.arg_end(); ++AI) |
| 272 | Args.push_back(*AI); |
| 273 | |
| 274 | Instruction *New; |
| 275 | if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { |
| 276 | New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), |
| 277 | Args, "", Call); |
| 278 | } else { |
| 279 | New = new CallInst(NF, Args, "", Call); |
| 280 | } |
| 281 | Args.clear(); |
| 282 | |
| 283 | if (!Call->use_empty()) { |
| 284 | Call->replaceAllUsesWith(New); |
| 285 | std::string Name = Call->getName(); |
| 286 | Call->setName(""); |
| 287 | New->setName(Name); |
| 288 | } |
| 289 | |
| 290 | // Finally, remove the old call from the program, reducing the use-count of |
| 291 | // F. |
| 292 | Call->getParent()->getInstList().erase(Call); |
| 293 | } |
| 294 | |
| 295 | // Since we have now created the new function, splice the body of the old |
| 296 | // function right into the new function, leaving the old rotting hulk of the |
| 297 | // function empty. |
| 298 | NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); |
| 299 | |
| 300 | // Loop over the argument list, transfering uses of the old arguments over to |
| 301 | // the new arguments, also transfering over the names as well. |
| 302 | // |
| 303 | for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin(); |
| 304 | I != E; ++I) |
| 305 | if (!ArgsToPromote.count(I)) { |
| 306 | // If this is an unmodified argument, move the name and users over to the |
| 307 | // new version. |
| 308 | I->replaceAllUsesWith(I2); |
| 309 | I2->setName(I->getName()); |
| 310 | ++I2; |
| 311 | } else if (!I->use_empty()) { |
| 312 | // Otherwise, if we promoted this argument, then all users are load |
| 313 | // instructions, and all loads should be using the new argument that we |
| 314 | // added. |
| 315 | /*DEBUG*/(std::cerr << "*** Promoted argument '" << I->getName() |
| 316 | << "' of function '" << F->getName() << "'\n"); |
| 317 | I2->setName(I->getName()+".val"); |
| 318 | while (!I->use_empty()) { |
| 319 | LoadInst *LI = cast<LoadInst>(I->use_back()); |
| 320 | LI->replaceAllUsesWith(I2); |
| 321 | LI->getParent()->getInstList().erase(LI); |
| 322 | } |
| 323 | ++I2; |
| 324 | } |
| 325 | |
| 326 | // Now that the old function is dead, delete it. |
| 327 | F->getParent()->getFunctionList().erase(F); |
| 328 | } |