Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 1 | //===-- ArgumentPromotion.cpp - Promote by-reference arguments ------------===// |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 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 |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 15 | // of code and lead to the elimination of allocas (especially in C++ template |
| 16 | // code like the STL). |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 17 | // |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 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 |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 22 | // operands for a large array or structure! |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 23 | // |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 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 |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 26 | // case. This case would be best handled when and if we start supporting |
| 27 | // multiple return values from functions. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 28 | // |
| 29 | //===----------------------------------------------------------------------===// |
| 30 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 31 | #define DEBUG_TYPE "argpromotion" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 32 | #include "llvm/Transforms/IPO.h" |
| 33 | #include "llvm/Constants.h" |
| 34 | #include "llvm/DerivedTypes.h" |
| 35 | #include "llvm/Module.h" |
| 36 | #include "llvm/Pass.h" |
| 37 | #include "llvm/Instructions.h" |
| 38 | #include "llvm/Analysis/AliasAnalysis.h" |
| 39 | #include "llvm/Target/TargetData.h" |
| 40 | #include "llvm/Support/CallSite.h" |
| 41 | #include "llvm/Support/CFG.h" |
| 42 | #include "Support/Debug.h" |
| 43 | #include "Support/DepthFirstIterator.h" |
| 44 | #include "Support/Statistic.h" |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 45 | #include "Support/StringExtras.h" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 46 | #include <set> |
| 47 | using namespace llvm; |
| 48 | |
| 49 | namespace { |
| 50 | Statistic<> NumArgumentsPromoted("argpromotion", |
| 51 | "Number of pointer arguments promoted"); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 52 | Statistic<> NumAggregatesPromoted("argpromotion", |
| 53 | "Number of aggregate arguments promoted"); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 54 | Statistic<> NumArgumentsDead("argpromotion", |
| 55 | "Number of dead pointer args eliminated"); |
| 56 | |
| 57 | /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass. |
| 58 | /// |
| 59 | class ArgPromotion : public Pass { |
| 60 | // WorkList - The set of internal functions that we have yet to process. As |
| 61 | // we eliminate arguments from a function, we push all callers into this set |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 62 | // so that the by-reference argument can be bubbled out as far as possible. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 63 | // This set contains only internal functions. |
| 64 | std::set<Function*> WorkList; |
| 65 | public: |
| 66 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 67 | AU.addRequired<AliasAnalysis>(); |
| 68 | AU.addRequired<TargetData>(); |
| 69 | } |
| 70 | |
| 71 | virtual bool run(Module &M); |
| 72 | private: |
| 73 | bool PromoteArguments(Function *F); |
| 74 | bool isSafeToPromoteArgument(Argument *Arg) const; |
| 75 | void DoPromotion(Function *F, std::vector<Argument*> &ArgsToPromote); |
| 76 | }; |
| 77 | |
| 78 | RegisterOpt<ArgPromotion> X("argpromotion", |
| 79 | "Promote 'by reference' arguments to scalars"); |
| 80 | } |
| 81 | |
| 82 | Pass *llvm::createArgumentPromotionPass() { |
| 83 | return new ArgPromotion(); |
| 84 | } |
| 85 | |
| 86 | bool ArgPromotion::run(Module &M) { |
| 87 | bool Changed = false; |
| 88 | for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| 89 | if (I->hasInternalLinkage()) { |
| 90 | WorkList.insert(I); |
| 91 | |
| 92 | // If there are any constant pointer refs pointing to this function, |
| 93 | // eliminate them now if possible. |
| 94 | ConstantPointerRef *CPR = 0; |
| 95 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; |
| 96 | ++UI) |
| 97 | if ((CPR = dyn_cast<ConstantPointerRef>(*UI))) |
| 98 | break; // Found one! |
| 99 | if (CPR) { |
| 100 | // See if we can transform all users to use the function directly. |
| 101 | while (!CPR->use_empty()) { |
| 102 | User *TheUser = CPR->use_back(); |
Chris Lattner | 7e6f509 | 2004-03-07 21:54:50 +0000 | [diff] [blame] | 103 | if (!isa<Constant>(TheUser) && !isa<GlobalVariable>(TheUser)) { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 104 | Changed = true; |
| 105 | TheUser->replaceUsesOfWith(CPR, I); |
| 106 | } else { |
| 107 | // We won't be able to eliminate all users. :( |
| 108 | WorkList.erase(I); // Minor efficiency win. |
| 109 | break; |
| 110 | } |
| 111 | } |
| 112 | |
| 113 | // If we nuked all users of the CPR, kill the CPR now! |
| 114 | if (CPR->use_empty()) { |
| 115 | CPR->destroyConstant(); |
| 116 | Changed = true; |
| 117 | } |
| 118 | } |
| 119 | } |
| 120 | |
| 121 | while (!WorkList.empty()) { |
| 122 | Function *F = *WorkList.begin(); |
| 123 | WorkList.erase(WorkList.begin()); |
| 124 | |
| 125 | if (PromoteArguments(F)) // Attempt to promote an argument. |
| 126 | Changed = true; // Remember that we changed something. |
| 127 | } |
| 128 | |
| 129 | return Changed; |
| 130 | } |
| 131 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 132 | /// PromoteArguments - This method checks the specified function to see if there |
| 133 | /// are any promotable arguments and if it is safe to promote the function (for |
| 134 | /// example, all callers are direct). If safe to promote some arguments, it |
| 135 | /// calls the DoPromotion method. |
| 136 | /// |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 137 | bool ArgPromotion::PromoteArguments(Function *F) { |
| 138 | assert(F->hasInternalLinkage() && "We can only process internal functions!"); |
| 139 | |
| 140 | // First check: see if there are any pointer arguments! If not, quick exit. |
| 141 | std::vector<Argument*> PointerArgs; |
| 142 | for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) |
| 143 | if (isa<PointerType>(I->getType())) |
| 144 | PointerArgs.push_back(I); |
| 145 | if (PointerArgs.empty()) return false; |
| 146 | |
| 147 | // Second check: make sure that all callers are direct callers. We can't |
| 148 | // transform functions that have indirect callers. |
| 149 | for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); |
Chris Lattner | 7db5a6d | 2004-03-07 22:43:27 +0000 | [diff] [blame] | 150 | UI != E; ++UI) { |
| 151 | CallSite CS = CallSite::get(*UI); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 152 | if (!CS.getInstruction()) // "Taking the address" of the function |
| 153 | return false; |
| 154 | |
| 155 | // Ensure that this call site is CALLING the function, not passing it as |
| 156 | // an argument. |
| 157 | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
| 158 | AI != E; ++AI) |
| 159 | if (*AI == F) return false; // Passing the function address in! |
Chris Lattner | 7db5a6d | 2004-03-07 22:43:27 +0000 | [diff] [blame] | 160 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 161 | |
| 162 | // Check to see which arguments are promotable. If an argument is not |
| 163 | // promotable, remove it from the PointerArgs vector. |
| 164 | for (unsigned i = 0; i != PointerArgs.size(); ++i) |
| 165 | if (!isSafeToPromoteArgument(PointerArgs[i])) { |
| 166 | std::swap(PointerArgs[i--], PointerArgs.back()); |
| 167 | PointerArgs.pop_back(); |
| 168 | } |
| 169 | |
| 170 | // No promotable pointer arguments. |
| 171 | if (PointerArgs.empty()) return false; |
| 172 | |
| 173 | // Okay, promote all of the arguments are rewrite the callees! |
| 174 | DoPromotion(F, PointerArgs); |
| 175 | return true; |
| 176 | } |
| 177 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 178 | |
| 179 | /// isSafeToPromoteArgument - As you might guess from the name of this method, |
| 180 | /// it checks to see if it is both safe and useful to promote the argument. |
| 181 | /// This method limits promotion of aggregates to only promote up to three |
| 182 | /// elements of the aggregate in order to avoid exploding the number of |
| 183 | /// arguments passed in. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 184 | bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg) const { |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 185 | // We can only promote this argument if all of the uses are loads, or are GEP |
| 186 | // instructions (with constant indices) that are subsequently loaded. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 187 | std::vector<LoadInst*> Loads; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 188 | std::vector<std::vector<Constant*> > GEPIndices; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 189 | for (Value::use_iterator UI = Arg->use_begin(), E = Arg->use_end(); |
| 190 | UI != E; ++UI) |
| 191 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 192 | if (LI->isVolatile()) return false; // Don't hack volatile loads |
| 193 | Loads.push_back(LI); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 194 | } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { |
| 195 | if (GEP->use_empty()) { |
| 196 | // Dead GEP's cause trouble later. Just remove them if we run into |
| 197 | // them. |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 198 | getAnalysis<AliasAnalysis>().deleteValue(GEP); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 199 | GEP->getParent()->getInstList().erase(GEP); |
| 200 | return isSafeToPromoteArgument(Arg); |
| 201 | } |
| 202 | // Ensure that all of the indices are constants. |
| 203 | std::vector<Constant*> Operands; |
| 204 | for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) |
| 205 | if (Constant *C = dyn_cast<Constant>(GEP->getOperand(i))) |
| 206 | Operands.push_back(C); |
| 207 | else |
| 208 | return false; // Not a constant operand GEP! |
| 209 | |
| 210 | // Ensure that the only users of the GEP are load instructions. |
| 211 | for (Value::use_iterator UI = GEP->use_begin(), E = GEP->use_end(); |
| 212 | UI != E; ++UI) |
| 213 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 214 | if (LI->isVolatile()) return false; // Don't hack volatile loads |
| 215 | Loads.push_back(LI); |
| 216 | } else { |
| 217 | return false; |
| 218 | } |
| 219 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 220 | // See if there is already a GEP with these indices. If not, check to |
| 221 | // make sure that we aren't promoting too many elements. If so, nothing |
| 222 | // to do. |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 223 | if (std::find(GEPIndices.begin(), GEPIndices.end(), Operands) == |
| 224 | GEPIndices.end()) { |
| 225 | if (GEPIndices.size() == 3) { |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 226 | DEBUG(std::cerr << "argpromotion disable promoting argument '" |
| 227 | << Arg->getName() << "' because it would require adding more " |
| 228 | << "than 3 arguments to the function.\n"); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 229 | // We limit aggregate promotion to only promoting up to three elements |
| 230 | // of the aggregate. |
| 231 | return false; |
| 232 | } |
| 233 | GEPIndices.push_back(Operands); |
| 234 | } |
| 235 | } else { |
| 236 | return false; // Not a load or a GEP. |
| 237 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 238 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 239 | if (Loads.empty()) return true; // No users, this is a dead argument. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 240 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 241 | // Okay, now we know that the argument is only used by load instructions. Use |
| 242 | // alias analysis to check to see if the pointer is guaranteed to not be |
| 243 | // modified from entry of the function to each of the load instructions. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 244 | Function &F = *Arg->getParent(); |
| 245 | |
| 246 | // Because there could be several/many load instructions, remember which |
| 247 | // blocks we know to be transparent to the load. |
| 248 | std::set<BasicBlock*> TranspBlocks; |
| 249 | |
| 250 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 251 | TargetData &TD = getAnalysis<TargetData>(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 252 | |
| 253 | for (unsigned i = 0, e = Loads.size(); i != e; ++i) { |
| 254 | // Check to see if the load is invalidated from the start of the block to |
| 255 | // the load itself. |
| 256 | LoadInst *Load = Loads[i]; |
| 257 | BasicBlock *BB = Load->getParent(); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 258 | |
| 259 | const PointerType *LoadTy = |
| 260 | cast<PointerType>(Load->getOperand(0)->getType()); |
| 261 | unsigned LoadSize = TD.getTypeSize(LoadTy->getElementType()); |
| 262 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 263 | if (AA.canInstructionRangeModify(BB->front(), *Load, Arg, LoadSize)) |
| 264 | return false; // Pointer is invalidated! |
| 265 | |
| 266 | // Now check every path from the entry block to the load for transparency. |
| 267 | // To do this, we perform a depth first search on the inverse CFG from the |
| 268 | // loading block. |
| 269 | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) |
| 270 | for (idf_ext_iterator<BasicBlock*> I = idf_ext_begin(*PI, TranspBlocks), |
| 271 | E = idf_ext_end(*PI, TranspBlocks); I != E; ++I) |
| 272 | if (AA.canBasicBlockModify(**I, Arg, LoadSize)) |
| 273 | return false; |
| 274 | } |
| 275 | |
| 276 | // If the path from the entry of the function to each load is free of |
| 277 | // instructions that potentially invalidate the load, we can make the |
| 278 | // transformation! |
| 279 | return true; |
| 280 | } |
| 281 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 282 | /// DoPromotion - This method actually performs the promotion of the specified |
| 283 | /// arguments. At this point, we know that it's safe to do so. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 284 | void ArgPromotion::DoPromotion(Function *F, std::vector<Argument*> &Args2Prom) { |
| 285 | std::set<Argument*> ArgsToPromote(Args2Prom.begin(), Args2Prom.end()); |
| 286 | |
| 287 | // Start by computing a new prototype for the function, which is the same as |
| 288 | // the old function, but has modified arguments. |
| 289 | const FunctionType *FTy = F->getFunctionType(); |
| 290 | std::vector<const Type*> Params; |
| 291 | |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 292 | // ScalarizedElements - If we are promoting a pointer that has elements |
| 293 | // accessed out of it, keep track of which elements are accessed so that we |
| 294 | // can add one argument for each. |
| 295 | // |
| 296 | // Arguments that are directly loaded will have a zero element value here, to |
| 297 | // handle cases where there are both a direct load and GEP accesses. |
| 298 | // |
| 299 | std::map<Argument*, std::set<std::vector<Value*> > > ScalarizedElements; |
| 300 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 301 | // OriginalLoads - Keep track of a representative load instruction from the |
| 302 | // original function so that we can tell the alias analysis implementation |
| 303 | // what the new GEP/Load instructions we are inserting look like. |
| 304 | std::map<std::vector<Value*>, LoadInst*> OriginalLoads; |
| 305 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 306 | for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I) |
| 307 | if (!ArgsToPromote.count(I)) { |
| 308 | Params.push_back(I->getType()); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 309 | } else if (I->use_empty()) { |
| 310 | ++NumArgumentsDead; |
| 311 | } else { |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 312 | // Okay, this is being promoted. Check to see if there are any GEP uses |
| 313 | // of the argument. |
| 314 | std::set<std::vector<Value*> > &ArgIndices = ScalarizedElements[I]; |
| 315 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; |
| 316 | ++UI) { |
| 317 | Instruction *User = cast<Instruction>(*UI); |
| 318 | assert(isa<LoadInst>(User) || isa<GetElementPtrInst>(User)); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 319 | std::vector<Value*> Indices(User->op_begin()+1, User->op_end()); |
| 320 | ArgIndices.insert(Indices); |
| 321 | LoadInst *OrigLoad; |
| 322 | if (LoadInst *L = dyn_cast<LoadInst>(User)) |
| 323 | OrigLoad = L; |
| 324 | else |
| 325 | OrigLoad = cast<LoadInst>(User->use_back()); |
| 326 | OriginalLoads[Indices] = OrigLoad; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 327 | } |
| 328 | |
| 329 | // Add a parameter to the function for each element passed in. |
| 330 | for (std::set<std::vector<Value*> >::iterator SI = ArgIndices.begin(), |
| 331 | E = ArgIndices.end(); SI != E; ++SI) |
| 332 | Params.push_back(GetElementPtrInst::getIndexedType(I->getType(), *SI)); |
| 333 | |
| 334 | if (ArgIndices.size() == 1 && ArgIndices.begin()->empty()) |
| 335 | ++NumArgumentsPromoted; |
| 336 | else |
| 337 | ++NumAggregatesPromoted; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 338 | } |
| 339 | |
| 340 | const Type *RetTy = FTy->getReturnType(); |
| 341 | |
| 342 | // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which |
| 343 | // have zero fixed arguments. |
| 344 | bool ExtraArgHack = false; |
| 345 | if (Params.empty() && FTy->isVarArg()) { |
| 346 | ExtraArgHack = true; |
| 347 | Params.push_back(Type::IntTy); |
| 348 | } |
| 349 | FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); |
| 350 | |
| 351 | // Create the new function body and insert it into the module... |
| 352 | Function *NF = new Function(NFTy, F->getLinkage(), F->getName()); |
| 353 | F->getParent()->getFunctionList().insert(F, NF); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 354 | |
| 355 | // Get the alias analysis information that we need to update to reflect our |
| 356 | // changes. |
| 357 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 358 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 359 | // Loop over all of the callers of the function, transforming the call sites |
| 360 | // to pass in the loaded pointers. |
| 361 | // |
| 362 | std::vector<Value*> Args; |
| 363 | while (!F->use_empty()) { |
| 364 | CallSite CS = CallSite::get(F->use_back()); |
| 365 | Instruction *Call = CS.getInstruction(); |
| 366 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 367 | // Make sure the caller of this function is revisited now that we promoted |
| 368 | // arguments in a callee of it. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 369 | if (Call->getParent()->getParent()->hasInternalLinkage()) |
| 370 | WorkList.insert(Call->getParent()->getParent()); |
| 371 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 372 | // Loop over the operands, inserting GEP and loads in the caller as |
| 373 | // appropriate. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 374 | CallSite::arg_iterator AI = CS.arg_begin(); |
| 375 | for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I, ++AI) |
| 376 | if (!ArgsToPromote.count(I)) |
| 377 | Args.push_back(*AI); // Unmodified argument |
| 378 | else if (!I->use_empty()) { |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 379 | // Non-dead argument: insert GEPs and loads as appropriate. |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 380 | std::set<std::vector<Value*> > &ArgIndices = ScalarizedElements[I]; |
| 381 | for (std::set<std::vector<Value*> >::iterator SI = ArgIndices.begin(), |
| 382 | E = ArgIndices.end(); SI != E; ++SI) { |
| 383 | Value *V = *AI; |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 384 | LoadInst *OrigLoad = OriginalLoads[*SI]; |
| 385 | if (!SI->empty()) { |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 386 | V = new GetElementPtrInst(V, *SI, V->getName()+".idx", Call); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 387 | AA.copyValue(OrigLoad->getOperand(0), V); |
| 388 | } |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 389 | Args.push_back(new LoadInst(V, V->getName()+".val", Call)); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 390 | AA.copyValue(OrigLoad, Args.back()); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 391 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 392 | } |
| 393 | |
| 394 | if (ExtraArgHack) |
| 395 | Args.push_back(Constant::getNullValue(Type::IntTy)); |
| 396 | |
| 397 | // Push any varargs arguments on the list |
| 398 | for (; AI != CS.arg_end(); ++AI) |
| 399 | Args.push_back(*AI); |
| 400 | |
| 401 | Instruction *New; |
| 402 | if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { |
| 403 | New = new InvokeInst(NF, II->getNormalDest(), II->getUnwindDest(), |
| 404 | Args, "", Call); |
| 405 | } else { |
| 406 | New = new CallInst(NF, Args, "", Call); |
| 407 | } |
| 408 | Args.clear(); |
| 409 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 410 | // Update the alias analysis implementation to know that we are replacing |
| 411 | // the old call with a new one. |
| 412 | AA.replaceWithNewValue(Call, New); |
| 413 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 414 | if (!Call->use_empty()) { |
| 415 | Call->replaceAllUsesWith(New); |
| 416 | std::string Name = Call->getName(); |
| 417 | Call->setName(""); |
| 418 | New->setName(Name); |
| 419 | } |
| 420 | |
| 421 | // Finally, remove the old call from the program, reducing the use-count of |
| 422 | // F. |
| 423 | Call->getParent()->getInstList().erase(Call); |
| 424 | } |
| 425 | |
| 426 | // Since we have now created the new function, splice the body of the old |
| 427 | // function right into the new function, leaving the old rotting hulk of the |
| 428 | // function empty. |
| 429 | NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); |
| 430 | |
| 431 | // Loop over the argument list, transfering uses of the old arguments over to |
| 432 | // the new arguments, also transfering over the names as well. |
| 433 | // |
| 434 | for (Function::aiterator I = F->abegin(), E = F->aend(), I2 = NF->abegin(); |
| 435 | I != E; ++I) |
| 436 | if (!ArgsToPromote.count(I)) { |
| 437 | // If this is an unmodified argument, move the name and users over to the |
| 438 | // new version. |
| 439 | I->replaceAllUsesWith(I2); |
| 440 | I2->setName(I->getName()); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 441 | AA.replaceWithNewValue(I, I2); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 442 | ++I2; |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 443 | } else if (I->use_empty()) { |
| 444 | AA.deleteValue(I); |
| 445 | } else { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 446 | // Otherwise, if we promoted this argument, then all users are load |
| 447 | // instructions, and all loads should be using the new argument that we |
| 448 | // added. |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 449 | std::set<std::vector<Value*> > &ArgIndices = ScalarizedElements[I]; |
| 450 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 451 | while (!I->use_empty()) { |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 452 | if (LoadInst *LI = dyn_cast<LoadInst>(I->use_back())) { |
| 453 | assert(ArgIndices.begin()->empty() && |
| 454 | "Load element should sort to front!"); |
| 455 | I2->setName(I->getName()+".val"); |
| 456 | LI->replaceAllUsesWith(I2); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 457 | AA.replaceWithNewValue(LI, I2); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 458 | LI->getParent()->getInstList().erase(LI); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 459 | DEBUG(std::cerr << "*** Promoted load of argument '" << I->getName() |
| 460 | << "' in function '" << F->getName() << "'\n"); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 461 | } else { |
| 462 | GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->use_back()); |
| 463 | std::vector<Value*> Operands(GEP->op_begin()+1, GEP->op_end()); |
| 464 | |
| 465 | unsigned ArgNo = 0; |
| 466 | Function::aiterator TheArg = I2; |
| 467 | for (std::set<std::vector<Value*> >::iterator It = ArgIndices.begin(); |
| 468 | *It != Operands; ++It, ++TheArg) { |
| 469 | assert(It != ArgIndices.end() && "GEP not handled??"); |
| 470 | } |
| 471 | |
| 472 | std::string NewName = I->getName(); |
| 473 | for (unsigned i = 0, e = Operands.size(); i != e; ++i) |
| 474 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Operands[i])) |
| 475 | NewName += "."+itostr((int64_t)CI->getRawValue()); |
| 476 | else |
| 477 | NewName += ".x"; |
| 478 | TheArg->setName(NewName+".val"); |
| 479 | |
| 480 | DEBUG(std::cerr << "*** Promoted agg argument '" << TheArg->getName() |
| 481 | << "' of function '" << F->getName() << "'\n"); |
| 482 | |
| 483 | // All of the uses must be load instructions. Replace them all with |
| 484 | // the argument specified by ArgNo. |
| 485 | while (!GEP->use_empty()) { |
| 486 | LoadInst *L = cast<LoadInst>(GEP->use_back()); |
| 487 | L->replaceAllUsesWith(TheArg); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 488 | AA.replaceWithNewValue(L, TheArg); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 489 | L->getParent()->getInstList().erase(L); |
| 490 | } |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 491 | AA.deleteValue(GEP); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 492 | GEP->getParent()->getInstList().erase(GEP); |
| 493 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 494 | } |
Chris Lattner | 86a734b | 2004-03-07 22:52:53 +0000 | [diff] [blame] | 495 | |
| 496 | // If we inserted a new pointer type, it's possible that IT could be |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 497 | // promoted too. Also, increment I2 past all of the arguments added for |
| 498 | // this promoted pointer. |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 499 | for (unsigned i = 0, e = ArgIndices.size(); i != e; ++i, ++I2) |
| 500 | if (isa<PointerType>(I2->getType())) |
| 501 | WorkList.insert(NF); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 502 | } |
| 503 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame^] | 504 | // Notify the alias analysis implementation that we inserted a new argument. |
| 505 | if (ExtraArgHack) |
| 506 | AA.copyValue(Constant::getNullValue(Type::IntTy), NF->abegin()); |
| 507 | |
| 508 | |
| 509 | // Tell the alias analysis that the old function is about to disappear. |
| 510 | AA.replaceWithNewValue(F, NF); |
| 511 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 512 | // Now that the old function is dead, delete it. |
| 513 | F->getParent()->getFunctionList().erase(F); |
| 514 | } |