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 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // 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 |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 12 | // arguments. If it can prove, through the use of alias analysis, that an |
| 13 | // argument is *only* loaded, then it can pass the value into the function |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 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 |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 20 | // it refuses to scalarize aggregates which would require passing in more than |
| 21 | // three operands to the function, because passing thousands of operands for a |
| 22 | // large array or structure is unprofitable! |
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 |
Gordon Henriksen | 55cbec3 | 2007-10-26 03:03:51 +0000 | [diff] [blame] | 25 | // stored to (returning the value instead), but does not currently. This case |
| 26 | // would be best handled when and if LLVM begins supporting multiple return |
| 27 | // 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" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 47 | #include "llvm/Support/Compiler.h" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 48 | #include <set> |
| 49 | using namespace llvm; |
| 50 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 51 | STATISTIC(NumArgumentsPromoted , "Number of pointer arguments promoted"); |
| 52 | STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted"); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 53 | STATISTIC(NumByValArgsPromoted , "Number of byval arguments promoted"); |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 54 | STATISTIC(NumArgumentsDead , "Number of dead pointer args eliminated"); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 55 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 56 | namespace { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 57 | /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass. |
| 58 | /// |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 59 | struct VISIBILITY_HIDDEN ArgPromotion : public CallGraphSCCPass { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 60 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 61 | AU.addRequired<AliasAnalysis>(); |
| 62 | AU.addRequired<TargetData>(); |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 63 | CallGraphSCCPass::getAnalysisUsage(AU); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 64 | } |
| 65 | |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 66 | virtual bool runOnSCC(const std::vector<CallGraphNode *> &SCC); |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 67 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 68 | ArgPromotion() : CallGraphSCCPass((intptr_t)&ID) {} |
| 69 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 70 | private: |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 71 | bool PromoteArguments(CallGraphNode *CGN); |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 72 | bool isSafeToPromoteArgument(Argument *Arg, bool isByVal) const; |
Chris Lattner | a10145f | 2008-01-11 18:43:58 +0000 | [diff] [blame] | 73 | Function *DoPromotion(Function *F, |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 74 | SmallPtrSet<Argument*, 8> &ArgsToPromote, |
| 75 | SmallPtrSet<Argument*, 8> &ByValArgsToTransform); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 76 | }; |
| 77 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 78 | char ArgPromotion::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 79 | RegisterPass<ArgPromotion> X("argpromotion", |
| 80 | "Promote 'by reference' arguments to scalars"); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 81 | } |
| 82 | |
Devang Patel | c71ca3c | 2007-01-26 00:47:38 +0000 | [diff] [blame] | 83 | Pass *llvm::createArgumentPromotionPass() { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 84 | return new ArgPromotion(); |
| 85 | } |
| 86 | |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 87 | bool ArgPromotion::runOnSCC(const std::vector<CallGraphNode *> &SCC) { |
| 88 | bool Changed = false, LocalChange; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 89 | |
Chris Lattner | f5afcab | 2004-09-19 01:05:16 +0000 | [diff] [blame] | 90 | do { // Iterate until we stop promoting from this SCC. |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 91 | LocalChange = false; |
| 92 | // Attempt to promote arguments from all functions in this SCC. |
| 93 | for (unsigned i = 0, e = SCC.size(); i != e; ++i) |
| 94 | LocalChange |= PromoteArguments(SCC[i]); |
| 95 | Changed |= LocalChange; // Remember that we changed something. |
| 96 | } while (LocalChange); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 97 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 98 | return Changed; |
| 99 | } |
| 100 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 101 | /// PromoteArguments - This method checks the specified function to see if there |
| 102 | /// are any promotable arguments and if it is safe to promote the function (for |
| 103 | /// example, all callers are direct). If safe to promote some arguments, it |
| 104 | /// calls the DoPromotion method. |
| 105 | /// |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 106 | bool ArgPromotion::PromoteArguments(CallGraphNode *CGN) { |
| 107 | Function *F = CGN->getFunction(); |
| 108 | |
| 109 | // Make sure that it is local to this module. |
| 110 | if (!F || !F->hasInternalLinkage()) return false; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 111 | |
| 112 | // First check: see if there are any pointer arguments! If not, quick exit. |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 113 | SmallVector<std::pair<Argument*, unsigned>, 16> PointerArgs; |
| 114 | unsigned ArgNo = 0; |
| 115 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); |
| 116 | I != E; ++I, ++ArgNo) |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 117 | if (isa<PointerType>(I->getType())) |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 118 | PointerArgs.push_back(std::pair<Argument*, unsigned>(I, ArgNo)); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 119 | if (PointerArgs.empty()) return false; |
| 120 | |
| 121 | // Second check: make sure that all callers are direct callers. We can't |
| 122 | // transform functions that have indirect callers. |
| 123 | for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); |
Chris Lattner | 7db5a6d | 2004-03-07 22:43:27 +0000 | [diff] [blame] | 124 | UI != E; ++UI) { |
| 125 | CallSite CS = CallSite::get(*UI); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 126 | if (!CS.getInstruction()) // "Taking the address" of the function |
| 127 | return false; |
| 128 | |
| 129 | // Ensure that this call site is CALLING the function, not passing it as |
| 130 | // an argument. |
Chris Lattner | f157701 | 2008-01-11 18:55:10 +0000 | [diff] [blame] | 131 | if (UI.getOperandNo() != 0) |
| 132 | return false; |
Chris Lattner | 7db5a6d | 2004-03-07 22:43:27 +0000 | [diff] [blame] | 133 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 134 | |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 135 | // Check to see which arguments are promotable. If an argument is promotable, |
| 136 | // add it to ArgsToPromote. |
| 137 | SmallPtrSet<Argument*, 8> ArgsToPromote; |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 138 | SmallPtrSet<Argument*, 8> ByValArgsToTransform; |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 139 | for (unsigned i = 0; i != PointerArgs.size(); ++i) { |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 140 | bool isByVal = F->paramHasAttr(PointerArgs[i].second+1, ParamAttr::ByVal); |
| 141 | |
| 142 | // If this is a byval argument, and if the aggregate type is small, just |
| 143 | // pass the elements, which is always safe. |
| 144 | Argument *PtrArg = PointerArgs[i].first; |
| 145 | if (isByVal) { |
| 146 | const Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType(); |
| 147 | if (const StructType *STy = dyn_cast<StructType>(AgTy)) |
| 148 | if (STy->getNumElements() <= 3) { |
| 149 | // If all the elements are first class types, we can promote it. |
| 150 | bool AllSimple = true; |
| 151 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) |
| 152 | if (!STy->getElementType(i)->isFirstClassType()) { |
| 153 | AllSimple = false; |
| 154 | break; |
| 155 | } |
| 156 | |
| 157 | // Safe to transform, don't even bother trying to "promote" it. |
| 158 | // Passing the elements as a scalar will allow scalarrepl to hack on |
| 159 | // the new alloca we introduce. |
| 160 | if (AllSimple) { |
| 161 | ByValArgsToTransform.insert(PtrArg); |
| 162 | continue; |
| 163 | } |
| 164 | } |
| 165 | } |
| 166 | |
| 167 | // Otherwise, see if we can promote the pointer to its value. |
| 168 | if (isSafeToPromoteArgument(PtrArg, isByVal)) |
| 169 | ArgsToPromote.insert(PtrArg); |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 170 | } |
| 171 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 172 | // No promotable pointer arguments. |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 173 | if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) return false; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 174 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 175 | Function *NewF = DoPromotion(F, ArgsToPromote, ByValArgsToTransform); |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 176 | |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 177 | // Update the call graph to know that the function has been transformed. |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 178 | getAnalysis<CallGraph>().changeFunction(F, NewF); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 179 | return true; |
| 180 | } |
| 181 | |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 182 | /// IsAlwaysValidPointer - Return true if the specified pointer is always legal |
| 183 | /// to load. |
| 184 | static bool IsAlwaysValidPointer(Value *V) { |
| 185 | if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true; |
| 186 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) |
| 187 | return IsAlwaysValidPointer(GEP->getOperand(0)); |
| 188 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) |
| 189 | if (CE->getOpcode() == Instruction::GetElementPtr) |
| 190 | return IsAlwaysValidPointer(CE->getOperand(0)); |
| 191 | |
| 192 | return false; |
| 193 | } |
| 194 | |
| 195 | /// AllCalleesPassInValidPointerForArgument - Return true if we can prove that |
| 196 | /// all callees pass in a valid pointer for the specified function argument. |
| 197 | static bool AllCalleesPassInValidPointerForArgument(Argument *Arg) { |
| 198 | Function *Callee = Arg->getParent(); |
| 199 | |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 200 | unsigned ArgNo = std::distance(Callee->arg_begin(), |
| 201 | Function::arg_iterator(Arg)); |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 202 | |
| 203 | // Look at all call sites of the function. At this pointer we know we only |
| 204 | // have direct callees. |
| 205 | for (Value::use_iterator UI = Callee->use_begin(), E = Callee->use_end(); |
| 206 | UI != E; ++UI) { |
| 207 | CallSite CS = CallSite::get(*UI); |
| 208 | assert(CS.getInstruction() && "Should only have direct calls!"); |
| 209 | |
| 210 | if (!IsAlwaysValidPointer(CS.getArgument(ArgNo))) |
| 211 | return false; |
| 212 | } |
| 213 | return true; |
| 214 | } |
| 215 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 216 | |
| 217 | /// isSafeToPromoteArgument - As you might guess from the name of this method, |
| 218 | /// it checks to see if it is both safe and useful to promote the argument. |
| 219 | /// This method limits promotion of aggregates to only promote up to three |
| 220 | /// elements of the aggregate in order to avoid exploding the number of |
| 221 | /// arguments passed in. |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 222 | bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const { |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 223 | // We can only promote this argument if all of the uses are loads, or are GEP |
| 224 | // instructions (with constant indices) that are subsequently loaded. |
Chris Lattner | 170b181 | 2008-01-11 19:34:32 +0000 | [diff] [blame] | 225 | |
| 226 | // We can also only promote the load if we can guarantee that it will happen. |
| 227 | // Promoting a load causes the load to be unconditionally executed in the |
| 228 | // caller, so we can't turn a conditional load into an unconditional load in |
| 229 | // general. |
| 230 | bool SafeToUnconditionallyLoad = false; |
| 231 | if (isByVal) // ByVal arguments are always safe to load from. |
| 232 | SafeToUnconditionallyLoad = true; |
| 233 | |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 234 | BasicBlock *EntryBlock = Arg->getParent()->begin(); |
Chris Lattner | a10145f | 2008-01-11 18:43:58 +0000 | [diff] [blame] | 235 | SmallVector<LoadInst*, 16> Loads; |
| 236 | std::vector<SmallVector<ConstantInt*, 8> > GEPIndices; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 237 | for (Value::use_iterator UI = Arg->use_begin(), E = Arg->use_end(); |
| 238 | UI != E; ++UI) |
| 239 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 240 | if (LI->isVolatile()) return false; // Don't hack volatile loads |
| 241 | Loads.push_back(LI); |
Chris Lattner | 170b181 | 2008-01-11 19:34:32 +0000 | [diff] [blame] | 242 | |
| 243 | // If this load occurs in the entry block, then the pointer is |
| 244 | // unconditionally loaded. |
| 245 | SafeToUnconditionallyLoad |= LI->getParent() == EntryBlock; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 246 | } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { |
| 247 | if (GEP->use_empty()) { |
| 248 | // Dead GEP's cause trouble later. Just remove them if we run into |
| 249 | // them. |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 250 | getAnalysis<AliasAnalysis>().deleteValue(GEP); |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 251 | GEP->eraseFromParent(); |
| 252 | return isSafeToPromoteArgument(Arg, isByVal); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 253 | } |
| 254 | // Ensure that all of the indices are constants. |
Chris Lattner | a10145f | 2008-01-11 18:43:58 +0000 | [diff] [blame] | 255 | SmallVector<ConstantInt*, 8> Operands; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 256 | for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 257 | if (ConstantInt *C = dyn_cast<ConstantInt>(GEP->getOperand(i))) |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 258 | Operands.push_back(C); |
| 259 | else |
| 260 | return false; // Not a constant operand GEP! |
| 261 | |
| 262 | // Ensure that the only users of the GEP are load instructions. |
| 263 | for (Value::use_iterator UI = GEP->use_begin(), E = GEP->use_end(); |
| 264 | UI != E; ++UI) |
| 265 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 266 | if (LI->isVolatile()) return false; // Don't hack volatile loads |
| 267 | Loads.push_back(LI); |
Chris Lattner | 170b181 | 2008-01-11 19:34:32 +0000 | [diff] [blame] | 268 | |
| 269 | // If this load occurs in the entry block, then the pointer is |
| 270 | // unconditionally loaded. |
| 271 | SafeToUnconditionallyLoad |= LI->getParent() == EntryBlock; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 272 | } else { |
| 273 | return false; |
| 274 | } |
| 275 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 276 | // See if there is already a GEP with these indices. If not, check to |
| 277 | // make sure that we aren't promoting too many elements. If so, nothing |
| 278 | // to do. |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 279 | if (std::find(GEPIndices.begin(), GEPIndices.end(), Operands) == |
| 280 | GEPIndices.end()) { |
| 281 | if (GEPIndices.size() == 3) { |
Bill Wendling | 0a81aac | 2006-11-26 10:02:32 +0000 | [diff] [blame] | 282 | DOUT << "argpromotion disable promoting argument '" |
| 283 | << Arg->getName() << "' because it would require adding more " |
| 284 | << "than 3 arguments to the function.\n"; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 285 | // We limit aggregate promotion to only promoting up to three elements |
| 286 | // of the aggregate. |
| 287 | return false; |
| 288 | } |
| 289 | GEPIndices.push_back(Operands); |
| 290 | } |
| 291 | } else { |
| 292 | return false; // Not a load or a GEP. |
| 293 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 294 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 295 | if (Loads.empty()) return true; // No users, this is a dead argument. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 296 | |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 297 | // If we decide that we want to promote this argument, the value is going to |
| 298 | // be unconditionally loaded in all callees. This is only safe to do if the |
| 299 | // pointer was going to be unconditionally loaded anyway (i.e. there is a load |
| 300 | // of the pointer in the entry block of the function) or if we can prove that |
| 301 | // all pointers passed in are always to legal locations (for example, no null |
| 302 | // pointers are passed in, no pointers to free'd memory, etc). |
Chris Lattner | 170b181 | 2008-01-11 19:34:32 +0000 | [diff] [blame] | 303 | if (!SafeToUnconditionallyLoad && |
| 304 | !AllCalleesPassInValidPointerForArgument(Arg)) |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 305 | return false; // Cannot prove that this is safe!! |
| 306 | |
| 307 | // Okay, now we know that the argument is only used by load instructions and |
| 308 | // it is safe to unconditionally load the pointer. Use alias analysis to |
| 309 | // check to see if the pointer is guaranteed to not be modified from entry of |
| 310 | // the function to each of the load instructions. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 311 | |
| 312 | // Because there could be several/many load instructions, remember which |
| 313 | // blocks we know to be transparent to the load. |
Chris Lattner | e027efa | 2008-01-11 19:36:30 +0000 | [diff] [blame] | 314 | SmallPtrSet<BasicBlock*, 16> TranspBlocks; |
Owen Anderson | 46f022a | 2006-09-15 05:22:51 +0000 | [diff] [blame] | 315 | |
| 316 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 317 | TargetData &TD = getAnalysis<TargetData>(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 318 | |
| 319 | for (unsigned i = 0, e = Loads.size(); i != e; ++i) { |
| 320 | // Check to see if the load is invalidated from the start of the block to |
| 321 | // the load itself. |
| 322 | LoadInst *Load = Loads[i]; |
| 323 | BasicBlock *BB = Load->getParent(); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 324 | |
| 325 | const PointerType *LoadTy = |
| 326 | cast<PointerType>(Load->getOperand(0)->getType()); |
Duncan Sands | 514ab34 | 2007-11-01 20:53:16 +0000 | [diff] [blame] | 327 | unsigned LoadSize = (unsigned)TD.getTypeStoreSize(LoadTy->getElementType()); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 328 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 329 | if (AA.canInstructionRangeModify(BB->front(), *Load, Arg, LoadSize)) |
| 330 | return false; // Pointer is invalidated! |
| 331 | |
| 332 | // Now check every path from the entry block to the load for transparency. |
| 333 | // To do this, we perform a depth first search on the inverse CFG from the |
| 334 | // loading block. |
| 335 | for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) |
Chris Lattner | e027efa | 2008-01-11 19:36:30 +0000 | [diff] [blame] | 336 | for (idf_ext_iterator<BasicBlock*, SmallPtrSet<BasicBlock*, 16> > |
| 337 | I = idf_ext_begin(*PI, TranspBlocks), |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 338 | E = idf_ext_end(*PI, TranspBlocks); I != E; ++I) |
| 339 | if (AA.canBasicBlockModify(**I, Arg, LoadSize)) |
| 340 | return false; |
| 341 | } |
| 342 | |
| 343 | // If the path from the entry of the function to each load is free of |
| 344 | // instructions that potentially invalidate the load, we can make the |
| 345 | // transformation! |
| 346 | return true; |
| 347 | } |
| 348 | |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 349 | namespace { |
| 350 | /// GEPIdxComparator - Provide a strong ordering for GEP indices. All Value* |
| 351 | /// elements are instances of ConstantInt. |
| 352 | /// |
| 353 | struct GEPIdxComparator { |
| 354 | bool operator()(const std::vector<Value*> &LHS, |
| 355 | const std::vector<Value*> &RHS) const { |
| 356 | unsigned idx = 0; |
| 357 | for (; idx < LHS.size() && idx < RHS.size(); ++idx) { |
| 358 | if (LHS[idx] != RHS[idx]) { |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 359 | return cast<ConstantInt>(LHS[idx])->getZExtValue() < |
| 360 | cast<ConstantInt>(RHS[idx])->getZExtValue(); |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 361 | } |
| 362 | } |
| 363 | |
| 364 | // Return less than if we ran out of stuff in LHS and we didn't run out of |
| 365 | // stuff in RHS. |
| 366 | return idx == LHS.size() && idx != RHS.size(); |
| 367 | } |
| 368 | }; |
| 369 | } |
| 370 | |
| 371 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 372 | /// DoPromotion - This method actually performs the promotion of the specified |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 373 | /// arguments, and returns the new function. At this point, we know that it's |
| 374 | /// safe to do so. |
| 375 | Function *ArgPromotion::DoPromotion(Function *F, |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 376 | SmallPtrSet<Argument*, 8> &ArgsToPromote, |
| 377 | SmallPtrSet<Argument*, 8> &ByValArgsToTransform) { |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 378 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 379 | // Start by computing a new prototype for the function, which is the same as |
| 380 | // the old function, but has modified arguments. |
| 381 | const FunctionType *FTy = F->getFunctionType(); |
| 382 | std::vector<const Type*> Params; |
| 383 | |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 384 | typedef std::set<std::vector<Value*>, GEPIdxComparator> ScalarizeTable; |
| 385 | |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 386 | // ScalarizedElements - If we are promoting a pointer that has elements |
| 387 | // accessed out of it, keep track of which elements are accessed so that we |
| 388 | // can add one argument for each. |
| 389 | // |
| 390 | // Arguments that are directly loaded will have a zero element value here, to |
| 391 | // handle cases where there are both a direct load and GEP accesses. |
| 392 | // |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 393 | std::map<Argument*, ScalarizeTable> ScalarizedElements; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 394 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 395 | // OriginalLoads - Keep track of a representative load instruction from the |
| 396 | // original function so that we can tell the alias analysis implementation |
| 397 | // what the new GEP/Load instructions we are inserting look like. |
| 398 | std::map<std::vector<Value*>, LoadInst*> OriginalLoads; |
| 399 | |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 400 | // ParamAttrs - Keep track of the parameter attributes for the arguments |
| 401 | // that we are *not* promoting. For the ones that we do promote, the parameter |
| 402 | // attributes are lost |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 403 | SmallVector<ParamAttrsWithIndex, 8> ParamAttrsVec; |
| 404 | const PAListPtr &PAL = F->getParamAttrs(); |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 405 | |
Duncan Sands | 532d022 | 2008-02-01 20:37:16 +0000 | [diff] [blame] | 406 | // Add any return attributes. |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 407 | if (ParameterAttributes attrs = PAL.getParamAttrs(0)) |
Duncan Sands | 532d022 | 2008-02-01 20:37:16 +0000 | [diff] [blame] | 408 | ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, attrs)); |
| 409 | |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 410 | unsigned ArgIndex = 1; |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 411 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 412 | ++I, ++ArgIndex) { |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 413 | if (ByValArgsToTransform.count(I)) { |
| 414 | // Just add all the struct element types. |
| 415 | const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); |
| 416 | const StructType *STy = cast<StructType>(AgTy); |
| 417 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) |
| 418 | Params.push_back(STy->getElementType(i)); |
| 419 | ++NumByValArgsPromoted; |
| 420 | } else if (!ArgsToPromote.count(I)) { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 421 | Params.push_back(I->getType()); |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 422 | if (ParameterAttributes attrs = PAL.getParamAttrs(ArgIndex)) |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 423 | ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Params.size(), attrs)); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 424 | } else if (I->use_empty()) { |
| 425 | ++NumArgumentsDead; |
| 426 | } else { |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 427 | // Okay, this is being promoted. Check to see if there are any GEP uses |
| 428 | // of the argument. |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 429 | ScalarizeTable &ArgIndices = ScalarizedElements[I]; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 430 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; |
| 431 | ++UI) { |
| 432 | Instruction *User = cast<Instruction>(*UI); |
Owen Anderson | 46f022a | 2006-09-15 05:22:51 +0000 | [diff] [blame] | 433 | assert(isa<LoadInst>(User) || isa<GetElementPtrInst>(User)); |
| 434 | std::vector<Value*> Indices(User->op_begin()+1, User->op_end()); |
| 435 | ArgIndices.insert(Indices); |
| 436 | LoadInst *OrigLoad; |
| 437 | if (LoadInst *L = dyn_cast<LoadInst>(User)) |
| 438 | OrigLoad = L; |
| 439 | else |
| 440 | OrigLoad = cast<LoadInst>(User->use_back()); |
| 441 | OriginalLoads[Indices] = OrigLoad; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 442 | } |
| 443 | |
| 444 | // Add a parameter to the function for each element passed in. |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 445 | for (ScalarizeTable::iterator SI = ArgIndices.begin(), |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 446 | E = ArgIndices.end(); SI != E; ++SI) |
Chris Lattner | 1ccd185 | 2007-02-12 22:56:41 +0000 | [diff] [blame] | 447 | Params.push_back(GetElementPtrInst::getIndexedType(I->getType(), |
David Greene | b8f7479 | 2007-09-04 15:46:09 +0000 | [diff] [blame] | 448 | SI->begin(), |
| 449 | SI->end())); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 450 | |
| 451 | if (ArgIndices.size() == 1 && ArgIndices.begin()->empty()) |
| 452 | ++NumArgumentsPromoted; |
| 453 | else |
| 454 | ++NumAggregatesPromoted; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 455 | } |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 456 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 457 | |
| 458 | const Type *RetTy = FTy->getReturnType(); |
| 459 | |
| 460 | // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which |
| 461 | // have zero fixed arguments. |
| 462 | bool ExtraArgHack = false; |
| 463 | if (Params.empty() && FTy->isVarArg()) { |
| 464 | ExtraArgHack = true; |
Reid Spencer | c5b206b | 2006-12-31 05:48:39 +0000 | [diff] [blame] | 465 | Params.push_back(Type::Int32Ty); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 466 | } |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 467 | |
| 468 | // Construct the new function type using the new arguments. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 469 | FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 470 | |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 471 | // Create the new function body and insert it into the module... |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 472 | Function *NF = Function::Create(NFTy, F->getLinkage(), F->getName()); |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 473 | NF->setCallingConv(F->getCallingConv()); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 474 | |
| 475 | // Recompute the parameter attributes list based on the new arguments for |
| 476 | // the function. |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 477 | NF->setParamAttrs(PAListPtr::get(ParamAttrsVec.begin(), ParamAttrsVec.end())); |
| 478 | ParamAttrsVec.clear(); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 479 | |
Gordon Henriksen | 194c90e | 2007-12-25 22:16:06 +0000 | [diff] [blame] | 480 | if (F->hasCollector()) |
| 481 | NF->setCollector(F->getCollector()); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 482 | F->getParent()->getFunctionList().insert(F, NF); |
Zhou Sheng | 2b3407f | 2008-03-20 08:05:05 +0000 | [diff] [blame] | 483 | NF->takeName(F); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 484 | |
| 485 | // Get the alias analysis information that we need to update to reflect our |
| 486 | // changes. |
| 487 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 488 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 489 | // Loop over all of the callers of the function, transforming the call sites |
| 490 | // to pass in the loaded pointers. |
| 491 | // |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 492 | SmallVector<Value*, 16> Args; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 493 | while (!F->use_empty()) { |
| 494 | CallSite CS = CallSite::get(F->use_back()); |
| 495 | Instruction *Call = CS.getInstruction(); |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 496 | const PAListPtr &CallPAL = CS.getParamAttrs(); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 497 | |
Duncan Sands | 532d022 | 2008-02-01 20:37:16 +0000 | [diff] [blame] | 498 | // Add any return attributes. |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 499 | if (ParameterAttributes attrs = CallPAL.getParamAttrs(0)) |
Duncan Sands | 532d022 | 2008-02-01 20:37:16 +0000 | [diff] [blame] | 500 | ParamAttrsVec.push_back(ParamAttrsWithIndex::get(0, attrs)); |
| 501 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 502 | // Loop over the operands, inserting GEP and loads in the caller as |
| 503 | // appropriate. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 504 | CallSite::arg_iterator AI = CS.arg_begin(); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 505 | ArgIndex = 1; |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 506 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 507 | I != E; ++I, ++AI, ++ArgIndex) |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 508 | if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 509 | Args.push_back(*AI); // Unmodified argument |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 510 | |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 511 | if (ParameterAttributes Attrs = CallPAL.getParamAttrs(ArgIndex)) |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 512 | ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); |
| 513 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 514 | } else if (ByValArgsToTransform.count(I)) { |
| 515 | // Emit a GEP and load for each element of the struct. |
| 516 | const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); |
| 517 | const StructType *STy = cast<StructType>(AgTy); |
| 518 | Value *Idxs[2] = { ConstantInt::get(Type::Int32Ty, 0), 0 }; |
| 519 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { |
| 520 | Idxs[1] = ConstantInt::get(Type::Int32Ty, i); |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 521 | Value *Idx = GetElementPtrInst::Create(*AI, Idxs, Idxs+2, |
| 522 | (*AI)->getName()+"."+utostr(i), |
| 523 | Call); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 524 | // TODO: Tell AA about the new values? |
| 525 | Args.push_back(new LoadInst(Idx, Idx->getName()+".val", Call)); |
| 526 | } |
| 527 | } else if (!I->use_empty()) { |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 528 | // Non-dead argument: insert GEPs and loads as appropriate. |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 529 | ScalarizeTable &ArgIndices = ScalarizedElements[I]; |
| 530 | for (ScalarizeTable::iterator SI = ArgIndices.begin(), |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 531 | E = ArgIndices.end(); SI != E; ++SI) { |
| 532 | Value *V = *AI; |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 533 | LoadInst *OrigLoad = OriginalLoads[*SI]; |
| 534 | if (!SI->empty()) { |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 535 | V = GetElementPtrInst::Create(V, SI->begin(), SI->end(), |
| 536 | V->getName()+".idx", Call); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 537 | AA.copyValue(OrigLoad->getOperand(0), V); |
| 538 | } |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 539 | Args.push_back(new LoadInst(V, V->getName()+".val", Call)); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 540 | AA.copyValue(OrigLoad, Args.back()); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 541 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 542 | } |
| 543 | |
| 544 | if (ExtraArgHack) |
Reid Spencer | c5b206b | 2006-12-31 05:48:39 +0000 | [diff] [blame] | 545 | Args.push_back(Constant::getNullValue(Type::Int32Ty)); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 546 | |
| 547 | // Push any varargs arguments on the list |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 548 | for (; AI != CS.arg_end(); ++AI, ++ArgIndex) { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 549 | Args.push_back(*AI); |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 550 | if (ParameterAttributes Attrs = CallPAL.getParamAttrs(ArgIndex)) |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 551 | ParamAttrsVec.push_back(ParamAttrsWithIndex::get(Args.size(), Attrs)); |
| 552 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 553 | |
| 554 | Instruction *New; |
| 555 | if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 556 | New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), |
| 557 | Args.begin(), Args.end(), "", Call); |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 558 | cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 559 | cast<InvokeInst>(New)->setParamAttrs(PAListPtr::get(ParamAttrsVec.begin(), |
| 560 | ParamAttrsVec.end())); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 561 | } else { |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 562 | New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call); |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 563 | cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); |
Chris Lattner | 58d7491 | 2008-03-12 17:45:29 +0000 | [diff] [blame] | 564 | cast<CallInst>(New)->setParamAttrs(PAListPtr::get(ParamAttrsVec.begin(), |
| 565 | ParamAttrsVec.end())); |
Chris Lattner | 1430ef1 | 2005-05-06 06:46:58 +0000 | [diff] [blame] | 566 | if (cast<CallInst>(Call)->isTailCall()) |
| 567 | cast<CallInst>(New)->setTailCall(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 568 | } |
| 569 | Args.clear(); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 570 | ParamAttrsVec.clear(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 571 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 572 | // Update the alias analysis implementation to know that we are replacing |
| 573 | // the old call with a new one. |
| 574 | AA.replaceWithNewValue(Call, New); |
| 575 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 576 | if (!Call->use_empty()) { |
| 577 | Call->replaceAllUsesWith(New); |
Chris Lattner | 046800a | 2007-02-11 01:08:35 +0000 | [diff] [blame] | 578 | New->takeName(Call); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 579 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 580 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 581 | // Finally, remove the old call from the program, reducing the use-count of |
| 582 | // F. |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 583 | Call->eraseFromParent(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 584 | } |
| 585 | |
| 586 | // Since we have now created the new function, splice the body of the old |
| 587 | // function right into the new function, leaving the old rotting hulk of the |
| 588 | // function empty. |
| 589 | NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); |
| 590 | |
| 591 | // Loop over the argument list, transfering uses of the old arguments over to |
| 592 | // the new arguments, also transfering over the names as well. |
| 593 | // |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 594 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 595 | I2 = NF->arg_begin(); I != E; ++I) { |
| 596 | if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 597 | // If this is an unmodified argument, move the name and users over to the |
| 598 | // new version. |
| 599 | I->replaceAllUsesWith(I2); |
Chris Lattner | 046800a | 2007-02-11 01:08:35 +0000 | [diff] [blame] | 600 | I2->takeName(I); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 601 | AA.replaceWithNewValue(I, I2); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 602 | ++I2; |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 603 | continue; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 604 | } |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 605 | |
| 606 | if (ByValArgsToTransform.count(I)) { |
| 607 | // In the callee, we create an alloca, and store each of the new incoming |
| 608 | // arguments into the alloca. |
| 609 | Instruction *InsertPt = NF->begin()->begin(); |
| 610 | |
| 611 | // Just add all the struct element types. |
| 612 | const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); |
| 613 | Value *TheAlloca = new AllocaInst(AgTy, 0, "", InsertPt); |
| 614 | const StructType *STy = cast<StructType>(AgTy); |
| 615 | Value *Idxs[2] = { ConstantInt::get(Type::Int32Ty, 0), 0 }; |
| 616 | |
| 617 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { |
| 618 | Idxs[1] = ConstantInt::get(Type::Int32Ty, i); |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame^] | 619 | Value *Idx = GetElementPtrInst::Create(TheAlloca, Idxs, Idxs+2, |
| 620 | TheAlloca->getName()+"."+utostr(i), |
| 621 | InsertPt); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 622 | I2->setName(I->getName()+"."+utostr(i)); |
| 623 | new StoreInst(I2++, Idx, InsertPt); |
| 624 | } |
| 625 | |
| 626 | // Anything that used the arg should now use the alloca. |
| 627 | I->replaceAllUsesWith(TheAlloca); |
| 628 | TheAlloca->takeName(I); |
| 629 | AA.replaceWithNewValue(I, TheAlloca); |
| 630 | continue; |
| 631 | } |
| 632 | |
| 633 | if (I->use_empty()) { |
| 634 | AA.deleteValue(I); |
| 635 | continue; |
| 636 | } |
| 637 | |
| 638 | // Otherwise, if we promoted this argument, then all users are load |
| 639 | // instructions, and all loads should be using the new argument that we |
| 640 | // added. |
| 641 | ScalarizeTable &ArgIndices = ScalarizedElements[I]; |
| 642 | |
| 643 | while (!I->use_empty()) { |
| 644 | if (LoadInst *LI = dyn_cast<LoadInst>(I->use_back())) { |
| 645 | assert(ArgIndices.begin()->empty() && |
| 646 | "Load element should sort to front!"); |
| 647 | I2->setName(I->getName()+".val"); |
| 648 | LI->replaceAllUsesWith(I2); |
| 649 | AA.replaceWithNewValue(LI, I2); |
| 650 | LI->eraseFromParent(); |
| 651 | DOUT << "*** Promoted load of argument '" << I->getName() |
| 652 | << "' in function '" << F->getName() << "'\n"; |
| 653 | } else { |
| 654 | GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->use_back()); |
| 655 | std::vector<Value*> Operands(GEP->op_begin()+1, GEP->op_end()); |
| 656 | |
| 657 | Function::arg_iterator TheArg = I2; |
| 658 | for (ScalarizeTable::iterator It = ArgIndices.begin(); |
| 659 | *It != Operands; ++It, ++TheArg) { |
| 660 | assert(It != ArgIndices.end() && "GEP not handled??"); |
| 661 | } |
| 662 | |
| 663 | std::string NewName = I->getName(); |
| 664 | for (unsigned i = 0, e = Operands.size(); i != e; ++i) |
| 665 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Operands[i])) |
| 666 | NewName += "." + CI->getValue().toStringUnsigned(10); |
| 667 | else |
| 668 | NewName += ".x"; |
| 669 | TheArg->setName(NewName+".val"); |
| 670 | |
| 671 | DOUT << "*** Promoted agg argument '" << TheArg->getName() |
| 672 | << "' of function '" << F->getName() << "'\n"; |
| 673 | |
| 674 | // All of the uses must be load instructions. Replace them all with |
| 675 | // the argument specified by ArgNo. |
| 676 | while (!GEP->use_empty()) { |
| 677 | LoadInst *L = cast<LoadInst>(GEP->use_back()); |
| 678 | L->replaceAllUsesWith(TheArg); |
| 679 | AA.replaceWithNewValue(L, TheArg); |
| 680 | L->eraseFromParent(); |
| 681 | } |
| 682 | AA.deleteValue(GEP); |
| 683 | GEP->eraseFromParent(); |
| 684 | } |
| 685 | } |
| 686 | |
| 687 | // Increment I2 past all of the arguments added for this promoted pointer. |
| 688 | for (unsigned i = 0, e = ArgIndices.size(); i != e; ++i) |
| 689 | ++I2; |
| 690 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 691 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 692 | // Notify the alias analysis implementation that we inserted a new argument. |
| 693 | if (ExtraArgHack) |
Reid Spencer | c5b206b | 2006-12-31 05:48:39 +0000 | [diff] [blame] | 694 | AA.copyValue(Constant::getNullValue(Type::Int32Ty), NF->arg_begin()); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 695 | |
| 696 | |
| 697 | // Tell the alias analysis that the old function is about to disappear. |
| 698 | AA.replaceWithNewValue(F, NF); |
| 699 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 700 | // Now that the old function is dead, delete it. |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 701 | F->eraseFromParent(); |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 702 | return NF; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 703 | } |