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