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 |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 20 | // by default it refuses to scalarize aggregates which would require passing in |
| 21 | // more than three operands to the function, because passing thousands of |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 22 | // operands for a large array or structure is unprofitable! This limit can be |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 23 | // configured or disabled, however. |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 24 | // |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 25 | // 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] | 26 | // stored to (returning the value instead), but does not currently. This case |
| 27 | // would be best handled when and if LLVM begins supporting multiple return |
| 28 | // values from functions. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 29 | // |
| 30 | //===----------------------------------------------------------------------===// |
| 31 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 32 | #define DEBUG_TYPE "argpromotion" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 33 | #include "llvm/Transforms/IPO.h" |
| 34 | #include "llvm/Constants.h" |
| 35 | #include "llvm/DerivedTypes.h" |
| 36 | #include "llvm/Module.h" |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 37 | #include "llvm/CallGraphSCCPass.h" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 38 | #include "llvm/Instructions.h" |
Owen Anderson | 14ce9ef | 2009-07-06 01:34:54 +0000 | [diff] [blame] | 39 | #include "llvm/LLVMContext.h" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 40 | #include "llvm/Analysis/AliasAnalysis.h" |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 41 | #include "llvm/Analysis/CallGraph.h" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 42 | #include "llvm/Target/TargetData.h" |
| 43 | #include "llvm/Support/CallSite.h" |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 44 | #include "llvm/Support/Compiler.h" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 45 | #include "llvm/Support/CFG.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 46 | #include "llvm/Support/Debug.h" |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 47 | #include "llvm/Support/raw_ostream.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 48 | #include "llvm/ADT/DepthFirstIterator.h" |
| 49 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 50 | #include <set> |
| 51 | using namespace llvm; |
| 52 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 53 | STATISTIC(NumArgumentsPromoted , "Number of pointer arguments promoted"); |
| 54 | STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted"); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 55 | STATISTIC(NumByValArgsPromoted , "Number of byval arguments promoted"); |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 56 | STATISTIC(NumArgumentsDead , "Number of dead pointer args eliminated"); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 57 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 58 | namespace { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 59 | /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass. |
| 60 | /// |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 61 | struct VISIBILITY_HIDDEN 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); |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 69 | static char ID; // Pass identification, replacement for typeid |
Dan Gohman | 38deef9 | 2009-02-18 16:37:45 +0000 | [diff] [blame] | 70 | explicit ArgPromotion(unsigned maxElements = 3) |
| 71 | : CallGraphSCCPass(&ID), maxElements(maxElements) {} |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 72 | |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 73 | /// A vector used to hold the indices of a single GEP instruction |
| 74 | typedef std::vector<uint64_t> IndicesVector; |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 75 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 76 | private: |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 77 | bool PromoteArguments(CallGraphNode *CGN); |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 78 | bool isSafeToPromoteArgument(Argument *Arg, bool isByVal) const; |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 79 | Function *DoPromotion(Function *F, |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 80 | SmallPtrSet<Argument*, 8> &ArgsToPromote, |
| 81 | SmallPtrSet<Argument*, 8> &ByValArgsToTransform); |
Matthijs Kooijman | 992e97e | 2008-05-23 07:57:02 +0000 | [diff] [blame] | 82 | /// The maximum number of elements to expand, or 0 for unlimited. |
| 83 | unsigned maxElements; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 84 | }; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 85 | } |
| 86 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 87 | char ArgPromotion::ID = 0; |
| 88 | static RegisterPass<ArgPromotion> |
| 89 | X("argpromotion", "Promote 'by reference' arguments to scalars"); |
| 90 | |
Chris Lattner | bcd203c | 2008-04-19 19:50:01 +0000 | [diff] [blame] | 91 | Pass *llvm::createArgumentPromotionPass(unsigned maxElements) { |
| 92 | return new ArgPromotion(maxElements); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 93 | } |
| 94 | |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 95 | bool ArgPromotion::runOnSCC(const std::vector<CallGraphNode *> &SCC) { |
| 96 | bool Changed = false, LocalChange; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 97 | |
Chris Lattner | f5afcab | 2004-09-19 01:05:16 +0000 | [diff] [blame] | 98 | do { // Iterate until we stop promoting from this SCC. |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 99 | LocalChange = false; |
| 100 | // Attempt to promote arguments from all functions in this SCC. |
| 101 | for (unsigned i = 0, e = SCC.size(); i != e; ++i) |
| 102 | LocalChange |= PromoteArguments(SCC[i]); |
| 103 | Changed |= LocalChange; // Remember that we changed something. |
| 104 | } while (LocalChange); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 105 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 106 | return Changed; |
| 107 | } |
| 108 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 109 | /// PromoteArguments - This method checks the specified function to see if there |
| 110 | /// are any promotable arguments and if it is safe to promote the function (for |
| 111 | /// example, all callers are direct). If safe to promote some arguments, it |
| 112 | /// calls the DoPromotion method. |
| 113 | /// |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 114 | bool ArgPromotion::PromoteArguments(CallGraphNode *CGN) { |
| 115 | Function *F = CGN->getFunction(); |
| 116 | |
| 117 | // Make sure that it is local to this module. |
Rafael Espindola | bb46f52 | 2009-01-15 20:18:42 +0000 | [diff] [blame] | 118 | if (!F || !F->hasLocalLinkage()) return false; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 119 | |
| 120 | // 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] | 121 | SmallVector<std::pair<Argument*, unsigned>, 16> PointerArgs; |
| 122 | unsigned ArgNo = 0; |
| 123 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); |
| 124 | I != E; ++I, ++ArgNo) |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 125 | if (isa<PointerType>(I->getType())) |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 126 | PointerArgs.push_back(std::pair<Argument*, unsigned>(I, ArgNo)); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 127 | if (PointerArgs.empty()) return false; |
| 128 | |
| 129 | // Second check: make sure that all callers are direct callers. We can't |
| 130 | // transform functions that have indirect callers. |
Jay Foad | 757068f | 2009-06-10 08:41:11 +0000 | [diff] [blame] | 131 | if (F->hasAddressTaken()) |
| 132 | return false; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 133 | |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 134 | // Check to see which arguments are promotable. If an argument is promotable, |
| 135 | // add it to ArgsToPromote. |
| 136 | SmallPtrSet<Argument*, 8> ArgsToPromote; |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 137 | SmallPtrSet<Argument*, 8> ByValArgsToTransform; |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 138 | for (unsigned i = 0; i != PointerArgs.size(); ++i) { |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 139 | bool isByVal = F->paramHasAttr(PointerArgs[i].second+1, Attribute::ByVal); |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 140 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 141 | // If this is a byval argument, and if the aggregate type is small, just |
| 142 | // pass the elements, which is always safe. |
| 143 | Argument *PtrArg = PointerArgs[i].first; |
| 144 | if (isByVal) { |
| 145 | const Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType(); |
Duncan Sands | 43e2a03 | 2008-05-27 11:50:51 +0000 | [diff] [blame] | 146 | if (const StructType *STy = dyn_cast<StructType>(AgTy)) { |
Chris Lattner | bcd203c | 2008-04-19 19:50:01 +0000 | [diff] [blame] | 147 | if (maxElements > 0 && STy->getNumElements() > maxElements) { |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 148 | DEBUG(errs() << "argpromotion disable promoting argument '" |
| 149 | << PtrArg->getName() << "' because it would require adding more" |
| 150 | << " than " << maxElements << " arguments to the function.\n"); |
Chris Lattner | bcd203c | 2008-04-19 19:50:01 +0000 | [diff] [blame] | 151 | } else { |
Dan Gohman | 399101a | 2008-05-23 00:17:26 +0000 | [diff] [blame] | 152 | // If all the elements are single-value types, we can promote it. |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 153 | bool AllSimple = true; |
| 154 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) |
Dan Gohman | 399101a | 2008-05-23 00:17:26 +0000 | [diff] [blame] | 155 | if (!STy->getElementType(i)->isSingleValueType()) { |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 156 | AllSimple = false; |
| 157 | break; |
| 158 | } |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 159 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 160 | // Safe to transform, don't even bother trying to "promote" it. |
| 161 | // Passing the elements as a scalar will allow scalarrepl to hack on |
| 162 | // the new alloca we introduce. |
| 163 | if (AllSimple) { |
| 164 | ByValArgsToTransform.insert(PtrArg); |
| 165 | continue; |
| 166 | } |
| 167 | } |
Duncan Sands | 43e2a03 | 2008-05-27 11:50:51 +0000 | [diff] [blame] | 168 | } |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 169 | } |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 170 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 171 | // Otherwise, see if we can promote the pointer to its value. |
| 172 | if (isSafeToPromoteArgument(PtrArg, isByVal)) |
| 173 | ArgsToPromote.insert(PtrArg); |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 174 | } |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 175 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 176 | // No promotable pointer arguments. |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 177 | if (ArgsToPromote.empty() && ByValArgsToTransform.empty()) return false; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 178 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 179 | Function *NewF = DoPromotion(F, ArgsToPromote, ByValArgsToTransform); |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 180 | |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 181 | // Update the call graph to know that the function has been transformed. |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 182 | getAnalysis<CallGraph>().changeFunction(F, NewF); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 183 | return true; |
| 184 | } |
| 185 | |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 186 | /// IsAlwaysValidPointer - Return true if the specified pointer is always legal |
| 187 | /// to load. |
| 188 | static bool IsAlwaysValidPointer(Value *V) { |
| 189 | if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true; |
| 190 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) |
| 191 | return IsAlwaysValidPointer(GEP->getOperand(0)); |
| 192 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) |
| 193 | if (CE->getOpcode() == Instruction::GetElementPtr) |
| 194 | return IsAlwaysValidPointer(CE->getOperand(0)); |
| 195 | |
| 196 | return false; |
| 197 | } |
| 198 | |
| 199 | /// AllCalleesPassInValidPointerForArgument - Return true if we can prove that |
| 200 | /// all callees pass in a valid pointer for the specified function argument. |
| 201 | static bool AllCalleesPassInValidPointerForArgument(Argument *Arg) { |
| 202 | Function *Callee = Arg->getParent(); |
| 203 | |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 204 | unsigned ArgNo = std::distance(Callee->arg_begin(), |
| 205 | Function::arg_iterator(Arg)); |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 206 | |
| 207 | // Look at all call sites of the function. At this pointer we know we only |
| 208 | // have direct callees. |
| 209 | for (Value::use_iterator UI = Callee->use_begin(), E = Callee->use_end(); |
| 210 | UI != E; ++UI) { |
| 211 | CallSite CS = CallSite::get(*UI); |
| 212 | assert(CS.getInstruction() && "Should only have direct calls!"); |
| 213 | |
| 214 | if (!IsAlwaysValidPointer(CS.getArgument(ArgNo))) |
| 215 | return false; |
| 216 | } |
| 217 | return true; |
| 218 | } |
| 219 | |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 220 | /// Returns true if Prefix is a prefix of longer. That means, Longer has a size |
| 221 | /// that is greater than or equal to the size of prefix, and each of the |
| 222 | /// elements in Prefix is the same as the corresponding elements in Longer. |
| 223 | /// |
| 224 | /// This means it also returns true when Prefix and Longer are equal! |
| 225 | static bool IsPrefix(const ArgPromotion::IndicesVector &Prefix, |
| 226 | const ArgPromotion::IndicesVector &Longer) { |
| 227 | if (Prefix.size() > Longer.size()) |
| 228 | return false; |
| 229 | for (unsigned i = 0, e = Prefix.size(); i != e; ++i) |
| 230 | if (Prefix[i] != Longer[i]) |
| 231 | return false; |
| 232 | return true; |
| 233 | } |
| 234 | |
| 235 | |
| 236 | /// Checks if Indices, or a prefix of Indices, is in Set. |
| 237 | static bool PrefixIn(const ArgPromotion::IndicesVector &Indices, |
| 238 | std::set<ArgPromotion::IndicesVector> &Set) { |
| 239 | std::set<ArgPromotion::IndicesVector>::iterator Low; |
| 240 | Low = Set.upper_bound(Indices); |
| 241 | if (Low != Set.begin()) |
| 242 | Low--; |
| 243 | // Low is now the last element smaller than or equal to Indices. This means |
| 244 | // it points to a prefix of Indices (possibly Indices itself), if such |
| 245 | // prefix exists. |
| 246 | // |
| 247 | // This load is safe if any prefix of its operands is safe to load. |
| 248 | return Low != Set.end() && IsPrefix(*Low, Indices); |
| 249 | } |
| 250 | |
| 251 | /// Mark the given indices (ToMark) as safe in the the given set of indices |
| 252 | /// (Safe). Marking safe usually means adding ToMark to Safe. However, if there |
| 253 | /// is already a prefix of Indices in Safe, Indices are implicitely marked safe |
| 254 | /// already. Furthermore, any indices that Indices is itself a prefix of, are |
| 255 | /// removed from Safe (since they are implicitely safe because of Indices now). |
| 256 | static void MarkIndicesSafe(const ArgPromotion::IndicesVector &ToMark, |
| 257 | std::set<ArgPromotion::IndicesVector> &Safe) { |
| 258 | std::set<ArgPromotion::IndicesVector>::iterator Low; |
| 259 | Low = Safe.upper_bound(ToMark); |
| 260 | // Guard against the case where Safe is empty |
| 261 | if (Low != Safe.begin()) |
| 262 | Low--; |
| 263 | // Low is now the last element smaller than or equal to Indices. This |
| 264 | // means it points to a prefix of Indices (possibly Indices itself), if |
| 265 | // such prefix exists. |
| 266 | if (Low != Safe.end()) { |
| 267 | if (IsPrefix(*Low, ToMark)) |
| 268 | // If there is already a prefix of these indices (or exactly these |
| 269 | // indices) marked a safe, don't bother adding these indices |
| 270 | return; |
| 271 | |
| 272 | // Increment Low, so we can use it as a "insert before" hint |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 273 | ++Low; |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 274 | } |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 275 | // Insert |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 276 | Low = Safe.insert(Low, ToMark); |
| 277 | ++Low; |
| 278 | // If there we're a prefix of longer index list(s), remove those |
| 279 | std::set<ArgPromotion::IndicesVector>::iterator End = Safe.end(); |
| 280 | while (Low != End && IsPrefix(ToMark, *Low)) { |
| 281 | std::set<ArgPromotion::IndicesVector>::iterator Remove = Low; |
| 282 | ++Low; |
| 283 | Safe.erase(Remove); |
| 284 | } |
| 285 | } |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 286 | |
| 287 | /// isSafeToPromoteArgument - As you might guess from the name of this method, |
| 288 | /// it checks to see if it is both safe and useful to promote the argument. |
| 289 | /// This method limits promotion of aggregates to only promote up to three |
| 290 | /// elements of the aggregate in order to avoid exploding the number of |
| 291 | /// arguments passed in. |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 292 | bool ArgPromotion::isSafeToPromoteArgument(Argument *Arg, bool isByVal) const { |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 293 | typedef std::set<IndicesVector> GEPIndicesSet; |
| 294 | |
| 295 | // Quick exit for unused arguments |
| 296 | if (Arg->use_empty()) |
| 297 | return true; |
| 298 | |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 299 | // We can only promote this argument if all of the uses are loads, or are GEP |
| 300 | // instructions (with constant indices) that are subsequently loaded. |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 301 | // |
| 302 | // Promoting the argument causes it to be loaded in the caller |
| 303 | // unconditionally. This is only safe if we can prove that either the load |
| 304 | // would have happened in the callee anyway (ie, there is a load in the entry |
| 305 | // block) or the pointer passed in at every call site is guaranteed to be |
| 306 | // valid. |
| 307 | // In the former case, invalid loads can happen, but would have happened |
| 308 | // anyway, in the latter case, invalid loads won't happen. This prevents us |
| 309 | // from introducing an invalid load that wouldn't have happened in the |
| 310 | // original code. |
| 311 | // |
| 312 | // This set will contain all sets of indices that are loaded in the entry |
| 313 | // block, and thus are safe to unconditionally load in the caller. |
| 314 | GEPIndicesSet SafeToUnconditionallyLoad; |
Chris Lattner | 170b181 | 2008-01-11 19:34:32 +0000 | [diff] [blame] | 315 | |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 316 | // This set contains all the sets of indices that we are planning to promote. |
| 317 | // This makes it possible to limit the number of arguments added. |
| 318 | GEPIndicesSet ToPromote; |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 319 | |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 320 | // If the pointer is always valid, any load with first index 0 is valid. |
| 321 | if(isByVal || AllCalleesPassInValidPointerForArgument(Arg)) |
| 322 | SafeToUnconditionallyLoad.insert(IndicesVector(1, 0)); |
| 323 | |
| 324 | // First, iterate the entry block and mark loads of (geps of) arguments as |
| 325 | // safe. |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 326 | BasicBlock *EntryBlock = Arg->getParent()->begin(); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 327 | // Declare this here so we can reuse it |
| 328 | IndicesVector Indices; |
| 329 | for (BasicBlock::iterator I = EntryBlock->begin(), E = EntryBlock->end(); |
| 330 | I != E; ++I) |
| 331 | if (LoadInst *LI = dyn_cast<LoadInst>(I)) { |
| 332 | Value *V = LI->getPointerOperand(); |
| 333 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) { |
| 334 | V = GEP->getPointerOperand(); |
| 335 | if (V == Arg) { |
| 336 | // This load actually loads (part of) Arg? Check the indices then. |
| 337 | Indices.reserve(GEP->getNumIndices()); |
| 338 | for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end(); |
| 339 | II != IE; ++II) |
| 340 | if (ConstantInt *CI = dyn_cast<ConstantInt>(*II)) |
| 341 | Indices.push_back(CI->getSExtValue()); |
| 342 | else |
| 343 | // We found a non-constant GEP index for this argument? Bail out |
| 344 | // right away, can't promote this argument at all. |
| 345 | return false; |
| 346 | |
| 347 | // Indices checked out, mark them as safe |
| 348 | MarkIndicesSafe(Indices, SafeToUnconditionallyLoad); |
| 349 | Indices.clear(); |
| 350 | } |
| 351 | } else if (V == Arg) { |
| 352 | // Direct loads are equivalent to a GEP with a single 0 index. |
| 353 | MarkIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad); |
| 354 | } |
| 355 | } |
| 356 | |
| 357 | // Now, iterate all uses of the argument to see if there are any uses that are |
| 358 | // not (GEP+)loads, or any (GEP+)loads that are not safe to promote. |
Chris Lattner | a10145f | 2008-01-11 18:43:58 +0000 | [diff] [blame] | 359 | SmallVector<LoadInst*, 16> Loads; |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 360 | IndicesVector Operands; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 361 | for (Value::use_iterator UI = Arg->use_begin(), E = Arg->use_end(); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 362 | UI != E; ++UI) { |
| 363 | Operands.clear(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 364 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 365 | if (LI->isVolatile()) return false; // Don't hack volatile loads |
| 366 | Loads.push_back(LI); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 367 | // Direct loads are equivalent to a GEP with a zero index and then a load. |
| 368 | Operands.push_back(0); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 369 | } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { |
| 370 | if (GEP->use_empty()) { |
| 371 | // Dead GEP's cause trouble later. Just remove them if we run into |
| 372 | // them. |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 373 | getAnalysis<AliasAnalysis>().deleteValue(GEP); |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 374 | GEP->eraseFromParent(); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 375 | // TODO: This runs the above loop over and over again for dead GEPS |
| 376 | // Couldn't we just do increment the UI iterator earlier and erase the |
| 377 | // use? |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 378 | return isSafeToPromoteArgument(Arg, isByVal); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 379 | } |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 380 | |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 381 | // Ensure that all of the indices are constants. |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 382 | for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); |
| 383 | i != e; ++i) |
Gabor Greif | 5e46321 | 2008-05-29 01:59:18 +0000 | [diff] [blame] | 384 | if (ConstantInt *C = dyn_cast<ConstantInt>(*i)) |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 385 | Operands.push_back(C->getSExtValue()); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 386 | else |
| 387 | return false; // Not a constant operand GEP! |
| 388 | |
| 389 | // Ensure that the only users of the GEP are load instructions. |
| 390 | for (Value::use_iterator UI = GEP->use_begin(), E = GEP->use_end(); |
| 391 | UI != E; ++UI) |
| 392 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 393 | if (LI->isVolatile()) return false; // Don't hack volatile loads |
| 394 | Loads.push_back(LI); |
| 395 | } else { |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 396 | // Other uses than load? |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 397 | return false; |
| 398 | } |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 399 | } else { |
| 400 | return false; // Not a load or a GEP. |
| 401 | } |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 402 | |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 403 | // Now, see if it is safe to promote this load / loads of this GEP. Loading |
| 404 | // is safe if Operands, or a prefix of Operands, is marked as safe. |
| 405 | if (!PrefixIn(Operands, SafeToUnconditionallyLoad)) |
| 406 | return false; |
| 407 | |
| 408 | // See if we are already promoting a load with these indices. If not, check |
| 409 | // to make sure that we aren't promoting too many elements. If so, nothing |
| 410 | // to do. |
| 411 | if (ToPromote.find(Operands) == ToPromote.end()) { |
| 412 | if (maxElements > 0 && ToPromote.size() == maxElements) { |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 413 | DEBUG(errs() << "argpromotion not promoting argument '" |
| 414 | << Arg->getName() << "' because it would require adding more " |
| 415 | << "than " << maxElements << " arguments to the function.\n"); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 416 | // We limit aggregate promotion to only promoting up to a fixed number |
| 417 | // of elements of the aggregate. |
| 418 | return false; |
| 419 | } |
| 420 | ToPromote.insert(Operands); |
| 421 | } |
| 422 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 423 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 424 | if (Loads.empty()) return true; // No users, this is a dead argument. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 425 | |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 426 | // Okay, now we know that the argument is only used by load instructions and |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 427 | // it is safe to unconditionally perform all of them. Use alias analysis to |
Chris Lattner | 11a3d7b | 2004-11-13 23:31:34 +0000 | [diff] [blame] | 428 | // check to see if the pointer is guaranteed to not be modified from entry of |
| 429 | // the function to each of the load instructions. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 430 | |
| 431 | // Because there could be several/many load instructions, remember which |
| 432 | // blocks we know to be transparent to the load. |
Chris Lattner | e027efa | 2008-01-11 19:36:30 +0000 | [diff] [blame] | 433 | SmallPtrSet<BasicBlock*, 16> TranspBlocks; |
Owen Anderson | 46f022a | 2006-09-15 05:22:51 +0000 | [diff] [blame] | 434 | |
| 435 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 436 | TargetData &TD = getAnalysis<TargetData>(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 437 | |
| 438 | for (unsigned i = 0, e = Loads.size(); i != e; ++i) { |
| 439 | // Check to see if the load is invalidated from the start of the block to |
| 440 | // the load itself. |
| 441 | LoadInst *Load = Loads[i]; |
| 442 | BasicBlock *BB = Load->getParent(); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 443 | |
| 444 | const PointerType *LoadTy = |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 445 | cast<PointerType>(Load->getPointerOperand()->getType()); |
Duncan Sands | 514ab34 | 2007-11-01 20:53:16 +0000 | [diff] [blame] | 446 | unsigned LoadSize = (unsigned)TD.getTypeStoreSize(LoadTy->getElementType()); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 447 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 448 | if (AA.canInstructionRangeModify(BB->front(), *Load, Arg, LoadSize)) |
| 449 | return false; // Pointer is invalidated! |
| 450 | |
| 451 | // Now check every path from the entry block to the load for transparency. |
| 452 | // To do this, we perform a depth first search on the inverse CFG from the |
| 453 | // loading block. |
| 454 | 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] | 455 | for (idf_ext_iterator<BasicBlock*, SmallPtrSet<BasicBlock*, 16> > |
| 456 | I = idf_ext_begin(*PI, TranspBlocks), |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 457 | E = idf_ext_end(*PI, TranspBlocks); I != E; ++I) |
| 458 | if (AA.canBasicBlockModify(**I, Arg, LoadSize)) |
| 459 | return false; |
| 460 | } |
| 461 | |
| 462 | // If the path from the entry of the function to each load is free of |
| 463 | // instructions that potentially invalidate the load, we can make the |
| 464 | // transformation! |
| 465 | return true; |
| 466 | } |
| 467 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 468 | /// DoPromotion - This method actually performs the promotion of the specified |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 469 | /// arguments, and returns the new function. At this point, we know that it's |
| 470 | /// safe to do so. |
| 471 | Function *ArgPromotion::DoPromotion(Function *F, |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 472 | SmallPtrSet<Argument*, 8> &ArgsToPromote, |
| 473 | SmallPtrSet<Argument*, 8> &ByValArgsToTransform) { |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 474 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 475 | // Start by computing a new prototype for the function, which is the same as |
| 476 | // the old function, but has modified arguments. |
| 477 | const FunctionType *FTy = F->getFunctionType(); |
| 478 | std::vector<const Type*> Params; |
| 479 | |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 480 | typedef std::set<IndicesVector> ScalarizeTable; |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 481 | |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 482 | // ScalarizedElements - If we are promoting a pointer that has elements |
| 483 | // accessed out of it, keep track of which elements are accessed so that we |
| 484 | // can add one argument for each. |
| 485 | // |
| 486 | // Arguments that are directly loaded will have a zero element value here, to |
| 487 | // handle cases where there are both a direct load and GEP accesses. |
| 488 | // |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 489 | std::map<Argument*, ScalarizeTable> ScalarizedElements; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 490 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 491 | // OriginalLoads - Keep track of a representative load instruction from the |
| 492 | // original function so that we can tell the alias analysis implementation |
| 493 | // what the new GEP/Load instructions we are inserting look like. |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 494 | std::map<IndicesVector, LoadInst*> OriginalLoads; |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 495 | |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 496 | // Attributes - Keep track of the parameter attributes for the arguments |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 497 | // that we are *not* promoting. For the ones that we do promote, the parameter |
| 498 | // attributes are lost |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 499 | SmallVector<AttributeWithIndex, 8> AttributesVec; |
| 500 | const AttrListPtr &PAL = F->getAttributes(); |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 501 | |
Duncan Sands | 532d022 | 2008-02-01 20:37:16 +0000 | [diff] [blame] | 502 | // Add any return attributes. |
Devang Patel | 19c8746 | 2008-09-26 22:53:05 +0000 | [diff] [blame] | 503 | if (Attributes attrs = PAL.getRetAttributes()) |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 504 | AttributesVec.push_back(AttributeWithIndex::get(0, attrs)); |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 505 | |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 506 | // First, determine the new argument list |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 507 | unsigned ArgIndex = 1; |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 508 | 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] | 509 | ++I, ++ArgIndex) { |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 510 | if (ByValArgsToTransform.count(I)) { |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 511 | // Simple byval argument? Just add all the struct element types. |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 512 | const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); |
| 513 | const StructType *STy = cast<StructType>(AgTy); |
| 514 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) |
| 515 | Params.push_back(STy->getElementType(i)); |
| 516 | ++NumByValArgsPromoted; |
| 517 | } else if (!ArgsToPromote.count(I)) { |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 518 | // Unchanged argument |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 519 | Params.push_back(I->getType()); |
Devang Patel | 19c8746 | 2008-09-26 22:53:05 +0000 | [diff] [blame] | 520 | if (Attributes attrs = PAL.getParamAttributes(ArgIndex)) |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 521 | AttributesVec.push_back(AttributeWithIndex::get(Params.size(), attrs)); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 522 | } else if (I->use_empty()) { |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 523 | // Dead argument (which are always marked as promotable) |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 524 | ++NumArgumentsDead; |
| 525 | } else { |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 526 | // Okay, this is being promoted. This means that the only uses are loads |
| 527 | // or GEPs which are only used by loads |
| 528 | |
| 529 | // In this table, we will track which indices are loaded from the argument |
| 530 | // (where direct loads are tracked as no indices). |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 531 | ScalarizeTable &ArgIndices = ScalarizedElements[I]; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 532 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; |
| 533 | ++UI) { |
| 534 | Instruction *User = cast<Instruction>(*UI); |
Owen Anderson | 46f022a | 2006-09-15 05:22:51 +0000 | [diff] [blame] | 535 | assert(isa<LoadInst>(User) || isa<GetElementPtrInst>(User)); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 536 | IndicesVector Indices; |
| 537 | Indices.reserve(User->getNumOperands() - 1); |
| 538 | // Since loads will only have a single operand, and GEPs only a single |
| 539 | // non-index operand, this will record direct loads without any indices, |
| 540 | // and gep+loads with the GEP indices. |
| 541 | for (User::op_iterator II = User->op_begin() + 1, IE = User->op_end(); |
| 542 | II != IE; ++II) |
| 543 | Indices.push_back(cast<ConstantInt>(*II)->getSExtValue()); |
| 544 | // GEPs with a single 0 index can be merged with direct loads |
| 545 | if (Indices.size() == 1 && Indices.front() == 0) |
| 546 | Indices.clear(); |
Owen Anderson | 46f022a | 2006-09-15 05:22:51 +0000 | [diff] [blame] | 547 | ArgIndices.insert(Indices); |
| 548 | LoadInst *OrigLoad; |
| 549 | if (LoadInst *L = dyn_cast<LoadInst>(User)) |
| 550 | OrigLoad = L; |
| 551 | else |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 552 | // Take any load, we will use it only to update Alias Analysis |
Owen Anderson | 46f022a | 2006-09-15 05:22:51 +0000 | [diff] [blame] | 553 | OrigLoad = cast<LoadInst>(User->use_back()); |
| 554 | OriginalLoads[Indices] = OrigLoad; |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 555 | } |
| 556 | |
| 557 | // Add a parameter to the function for each element passed in. |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 558 | for (ScalarizeTable::iterator SI = ArgIndices.begin(), |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 559 | E = ArgIndices.end(); SI != E; ++SI) { |
Torok Edwin | b079a39 | 2008-11-16 17:21:25 +0000 | [diff] [blame] | 560 | // not allowed to dereference ->begin() if size() is 0 |
Chris Lattner | 1ccd185 | 2007-02-12 22:56:41 +0000 | [diff] [blame] | 561 | Params.push_back(GetElementPtrInst::getIndexedType(I->getType(), |
David Greene | 5b7dfbd | 2009-04-17 14:56:18 +0000 | [diff] [blame] | 562 | SI->begin(), |
| 563 | SI->end())); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 564 | assert(Params.back()); |
| 565 | } |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 566 | |
| 567 | if (ArgIndices.size() == 1 && ArgIndices.begin()->empty()) |
| 568 | ++NumArgumentsPromoted; |
| 569 | else |
| 570 | ++NumAggregatesPromoted; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 571 | } |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 572 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 573 | |
Devang Patel | 19c8746 | 2008-09-26 22:53:05 +0000 | [diff] [blame] | 574 | // Add any function attributes. |
| 575 | if (Attributes attrs = PAL.getFnAttributes()) |
| 576 | AttributesVec.push_back(AttributeWithIndex::get(~0, attrs)); |
| 577 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 578 | const Type *RetTy = FTy->getReturnType(); |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 579 | LLVMContext &Context = RetTy->getContext(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 580 | |
| 581 | // Work around LLVM bug PR56: the CWriter cannot emit varargs functions which |
| 582 | // have zero fixed arguments. |
| 583 | bool ExtraArgHack = false; |
| 584 | if (Params.empty() && FTy->isVarArg()) { |
| 585 | ExtraArgHack = true; |
Reid Spencer | c5b206b | 2006-12-31 05:48:39 +0000 | [diff] [blame] | 586 | Params.push_back(Type::Int32Ty); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 587 | } |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 588 | |
| 589 | // Construct the new function type using the new arguments. |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 590 | FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg()); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 591 | |
Duncan Sands | dc02467 | 2007-11-27 13:23:08 +0000 | [diff] [blame] | 592 | // Create the new function body and insert it into the module... |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 593 | Function *NF = Function::Create(NFTy, F->getLinkage(), F->getName()); |
Duncan Sands | 28c3cff | 2008-05-26 19:58:59 +0000 | [diff] [blame] | 594 | NF->copyAttributesFrom(F); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 595 | |
| 596 | // Recompute the parameter attributes list based on the new arguments for |
| 597 | // the function. |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 598 | NF->setAttributes(AttrListPtr::get(AttributesVec.begin(), AttributesVec.end())); |
| 599 | AttributesVec.clear(); |
Duncan Sands | 28c3cff | 2008-05-26 19:58:59 +0000 | [diff] [blame] | 600 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 601 | F->getParent()->getFunctionList().insert(F, NF); |
Zhou Sheng | 2b3407f | 2008-03-20 08:05:05 +0000 | [diff] [blame] | 602 | NF->takeName(F); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 603 | |
| 604 | // Get the alias analysis information that we need to update to reflect our |
| 605 | // changes. |
| 606 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 607 | |
Duncan Sands | 34c8847 | 2008-09-08 11:07:35 +0000 | [diff] [blame] | 608 | // Get the callgraph information that we need to update to reflect our |
| 609 | // changes. |
| 610 | CallGraph &CG = getAnalysis<CallGraph>(); |
| 611 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 612 | // Loop over all of the callers of the function, transforming the call sites |
| 613 | // to pass in the loaded pointers. |
| 614 | // |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 615 | SmallVector<Value*, 16> Args; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 616 | while (!F->use_empty()) { |
| 617 | CallSite CS = CallSite::get(F->use_back()); |
| 618 | Instruction *Call = CS.getInstruction(); |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 619 | const AttrListPtr &CallPAL = CS.getAttributes(); |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 620 | |
Duncan Sands | 532d022 | 2008-02-01 20:37:16 +0000 | [diff] [blame] | 621 | // Add any return attributes. |
Devang Patel | 19c8746 | 2008-09-26 22:53:05 +0000 | [diff] [blame] | 622 | if (Attributes attrs = CallPAL.getRetAttributes()) |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 623 | AttributesVec.push_back(AttributeWithIndex::get(0, attrs)); |
Duncan Sands | 532d022 | 2008-02-01 20:37:16 +0000 | [diff] [blame] | 624 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 625 | // Loop over the operands, inserting GEP and loads in the caller as |
| 626 | // appropriate. |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 627 | CallSite::arg_iterator AI = CS.arg_begin(); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 628 | ArgIndex = 1; |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 629 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 630 | I != E; ++I, ++AI, ++ArgIndex) |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 631 | if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 632 | Args.push_back(*AI); // Unmodified argument |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 633 | |
Devang Patel | 19c8746 | 2008-09-26 22:53:05 +0000 | [diff] [blame] | 634 | if (Attributes Attrs = CallPAL.getParamAttributes(ArgIndex)) |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 635 | AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 636 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 637 | } else if (ByValArgsToTransform.count(I)) { |
| 638 | // Emit a GEP and load for each element of the struct. |
| 639 | const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); |
| 640 | const StructType *STy = cast<StructType>(AgTy); |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 641 | Value *Idxs[2] = { ConstantInt::get(Type::Int32Ty, 0), 0 }; |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 642 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 643 | Idxs[1] = ConstantInt::get(Type::Int32Ty, i); |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 644 | Value *Idx = GetElementPtrInst::Create(*AI, Idxs, Idxs+2, |
| 645 | (*AI)->getName()+"."+utostr(i), |
| 646 | Call); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 647 | // TODO: Tell AA about the new values? |
| 648 | Args.push_back(new LoadInst(Idx, Idx->getName()+".val", Call)); |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 649 | } |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 650 | } else if (!I->use_empty()) { |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 651 | // Non-dead argument: insert GEPs and loads as appropriate. |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 652 | ScalarizeTable &ArgIndices = ScalarizedElements[I]; |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 653 | // Store the Value* version of the indices in here, but declare it now |
| 654 | // for reuse |
| 655 | std::vector<Value*> Ops; |
Chris Lattner | beabf45 | 2004-06-21 00:07:58 +0000 | [diff] [blame] | 656 | for (ScalarizeTable::iterator SI = ArgIndices.begin(), |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 657 | E = ArgIndices.end(); SI != E; ++SI) { |
| 658 | Value *V = *AI; |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 659 | LoadInst *OrigLoad = OriginalLoads[*SI]; |
| 660 | if (!SI->empty()) { |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 661 | Ops.reserve(SI->size()); |
| 662 | const Type *ElTy = V->getType(); |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 663 | for (IndicesVector::const_iterator II = SI->begin(), |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 664 | IE = SI->end(); II != IE; ++II) { |
| 665 | // Use i32 to index structs, and i64 for others (pointers/arrays). |
| 666 | // This satisfies GEP constraints. |
| 667 | const Type *IdxTy = (isa<StructType>(ElTy) ? Type::Int32Ty : Type::Int64Ty); |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 668 | Ops.push_back(ConstantInt::get(IdxTy, *II)); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 669 | // Keep track of the type we're currently indexing |
| 670 | ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(*II); |
| 671 | } |
| 672 | // And create a GEP to extract those indices |
| 673 | V = GetElementPtrInst::Create(V, Ops.begin(), Ops.end(), |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 674 | V->getName()+".idx", Call); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 675 | Ops.clear(); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 676 | AA.copyValue(OrigLoad->getOperand(0), V); |
| 677 | } |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 678 | Args.push_back(new LoadInst(V, V->getName()+".val", Call)); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 679 | AA.copyValue(OrigLoad, Args.back()); |
Chris Lattner | 9440db8 | 2004-03-08 01:04:36 +0000 | [diff] [blame] | 680 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 681 | } |
| 682 | |
| 683 | if (ExtraArgHack) |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 684 | Args.push_back(Context.getNullValue(Type::Int32Ty)); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 685 | |
| 686 | // Push any varargs arguments on the list |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 687 | for (; AI != CS.arg_end(); ++AI, ++ArgIndex) { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 688 | Args.push_back(*AI); |
Devang Patel | 19c8746 | 2008-09-26 22:53:05 +0000 | [diff] [blame] | 689 | if (Attributes Attrs = CallPAL.getParamAttributes(ArgIndex)) |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 690 | AttributesVec.push_back(AttributeWithIndex::get(Args.size(), Attrs)); |
Chris Lattner | ab04e13 | 2008-01-17 01:17:03 +0000 | [diff] [blame] | 691 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 692 | |
Devang Patel | 19c8746 | 2008-09-26 22:53:05 +0000 | [diff] [blame] | 693 | // Add any function attributes. |
| 694 | if (Attributes attrs = CallPAL.getFnAttributes()) |
| 695 | AttributesVec.push_back(AttributeWithIndex::get(~0, attrs)); |
| 696 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 697 | Instruction *New; |
| 698 | if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) { |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 699 | New = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(), |
| 700 | Args.begin(), Args.end(), "", Call); |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 701 | cast<InvokeInst>(New)->setCallingConv(CS.getCallingConv()); |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 702 | cast<InvokeInst>(New)->setAttributes(AttrListPtr::get(AttributesVec.begin(), |
| 703 | AttributesVec.end())); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 704 | } else { |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 705 | New = CallInst::Create(NF, Args.begin(), Args.end(), "", Call); |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 706 | cast<CallInst>(New)->setCallingConv(CS.getCallingConv()); |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 707 | cast<CallInst>(New)->setAttributes(AttrListPtr::get(AttributesVec.begin(), |
| 708 | AttributesVec.end())); |
Chris Lattner | 1430ef1 | 2005-05-06 06:46:58 +0000 | [diff] [blame] | 709 | if (cast<CallInst>(Call)->isTailCall()) |
| 710 | cast<CallInst>(New)->setTailCall(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 711 | } |
| 712 | Args.clear(); |
Devang Patel | 0598866 | 2008-09-25 21:00:45 +0000 | [diff] [blame] | 713 | AttributesVec.clear(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 714 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 715 | // Update the alias analysis implementation to know that we are replacing |
| 716 | // the old call with a new one. |
| 717 | AA.replaceWithNewValue(Call, New); |
| 718 | |
Duncan Sands | 34c8847 | 2008-09-08 11:07:35 +0000 | [diff] [blame] | 719 | // Update the callgraph to know that the callsite has been transformed. |
| 720 | CG[Call->getParent()->getParent()]->replaceCallSite(Call, New); |
| 721 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 722 | if (!Call->use_empty()) { |
| 723 | Call->replaceAllUsesWith(New); |
Chris Lattner | 046800a | 2007-02-11 01:08:35 +0000 | [diff] [blame] | 724 | New->takeName(Call); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 725 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 726 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 727 | // Finally, remove the old call from the program, reducing the use-count of |
| 728 | // F. |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 729 | Call->eraseFromParent(); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 730 | } |
| 731 | |
| 732 | // Since we have now created the new function, splice the body of the old |
| 733 | // function right into the new function, leaving the old rotting hulk of the |
| 734 | // function empty. |
| 735 | NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList()); |
| 736 | |
| 737 | // Loop over the argument list, transfering uses of the old arguments over to |
| 738 | // the new arguments, also transfering over the names as well. |
| 739 | // |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 740 | for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(), |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 741 | I2 = NF->arg_begin(); I != E; ++I) { |
| 742 | if (!ArgsToPromote.count(I) && !ByValArgsToTransform.count(I)) { |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 743 | // If this is an unmodified argument, move the name and users over to the |
| 744 | // new version. |
| 745 | I->replaceAllUsesWith(I2); |
Chris Lattner | 046800a | 2007-02-11 01:08:35 +0000 | [diff] [blame] | 746 | I2->takeName(I); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 747 | AA.replaceWithNewValue(I, I2); |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 748 | ++I2; |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 749 | continue; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 750 | } |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 751 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 752 | if (ByValArgsToTransform.count(I)) { |
| 753 | // In the callee, we create an alloca, and store each of the new incoming |
| 754 | // arguments into the alloca. |
| 755 | Instruction *InsertPt = NF->begin()->begin(); |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 756 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 757 | // Just add all the struct element types. |
| 758 | const Type *AgTy = cast<PointerType>(I->getType())->getElementType(); |
Owen Anderson | 50dead0 | 2009-07-15 23:53:25 +0000 | [diff] [blame] | 759 | Value *TheAlloca = new AllocaInst(AgTy, 0, "", InsertPt); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 760 | const StructType *STy = cast<StructType>(AgTy); |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 761 | Value *Idxs[2] = { ConstantInt::get(Type::Int32Ty, 0), 0 }; |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 762 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 763 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 764 | Idxs[1] = ConstantInt::get(Type::Int32Ty, i); |
Daniel Dunbar | dfd3b64 | 2009-07-22 20:46:46 +0000 | [diff] [blame] | 765 | Value *Idx = |
| 766 | GetElementPtrInst::Create(TheAlloca, Idxs, Idxs+2, |
Daniel Dunbar | 7f93dc8 | 2009-07-30 04:20:37 +0000 | [diff] [blame^] | 767 | TheAlloca->getName()+"."+i, |
Daniel Dunbar | dfd3b64 | 2009-07-22 20:46:46 +0000 | [diff] [blame] | 768 | InsertPt); |
Daniel Dunbar | 7f93dc8 | 2009-07-30 04:20:37 +0000 | [diff] [blame^] | 769 | I2->setName(I->getName()+"."+i); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 770 | new StoreInst(I2++, Idx, InsertPt); |
| 771 | } |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 772 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 773 | // Anything that used the arg should now use the alloca. |
| 774 | I->replaceAllUsesWith(TheAlloca); |
| 775 | TheAlloca->takeName(I); |
| 776 | AA.replaceWithNewValue(I, TheAlloca); |
| 777 | continue; |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 778 | } |
| 779 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 780 | if (I->use_empty()) { |
| 781 | AA.deleteValue(I); |
| 782 | continue; |
| 783 | } |
Duncan Sands | 4cddaf7 | 2008-09-07 09:54:09 +0000 | [diff] [blame] | 784 | |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 785 | // Otherwise, if we promoted this argument, then all users are load |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 786 | // instructions (or GEPs with only load users), and all loads should be |
| 787 | // using the new argument that we added. |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 788 | ScalarizeTable &ArgIndices = ScalarizedElements[I]; |
| 789 | |
| 790 | while (!I->use_empty()) { |
| 791 | if (LoadInst *LI = dyn_cast<LoadInst>(I->use_back())) { |
| 792 | assert(ArgIndices.begin()->empty() && |
| 793 | "Load element should sort to front!"); |
| 794 | I2->setName(I->getName()+".val"); |
| 795 | LI->replaceAllUsesWith(I2); |
| 796 | AA.replaceWithNewValue(LI, I2); |
| 797 | LI->eraseFromParent(); |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 798 | DEBUG(errs() << "*** Promoted load of argument '" << I->getName() |
| 799 | << "' in function '" << F->getName() << "'\n"); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 800 | } else { |
| 801 | GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->use_back()); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 802 | IndicesVector Operands; |
| 803 | Operands.reserve(GEP->getNumIndices()); |
| 804 | for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end(); |
| 805 | II != IE; ++II) |
| 806 | Operands.push_back(cast<ConstantInt>(*II)->getSExtValue()); |
| 807 | |
| 808 | // GEPs with a single 0 index can be merged with direct loads |
| 809 | if (Operands.size() == 1 && Operands.front() == 0) |
| 810 | Operands.clear(); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 811 | |
| 812 | Function::arg_iterator TheArg = I2; |
| 813 | for (ScalarizeTable::iterator It = ArgIndices.begin(); |
| 814 | *It != Operands; ++It, ++TheArg) { |
| 815 | assert(It != ArgIndices.end() && "GEP not handled??"); |
| 816 | } |
| 817 | |
| 818 | std::string NewName = I->getName(); |
Matthijs Kooijman | 477f5a2 | 2008-07-29 10:00:13 +0000 | [diff] [blame] | 819 | for (unsigned i = 0, e = Operands.size(); i != e; ++i) { |
| 820 | NewName += "." + utostr(Operands[i]); |
| 821 | } |
| 822 | NewName += ".val"; |
| 823 | TheArg->setName(NewName); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 824 | |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 825 | DEBUG(errs() << "*** Promoted agg argument '" << TheArg->getName() |
| 826 | << "' of function '" << NF->getName() << "'\n"); |
Chris Lattner | 10603e0 | 2008-01-11 22:31:41 +0000 | [diff] [blame] | 827 | |
| 828 | // All of the uses must be load instructions. Replace them all with |
| 829 | // the argument specified by ArgNo. |
| 830 | while (!GEP->use_empty()) { |
| 831 | LoadInst *L = cast<LoadInst>(GEP->use_back()); |
| 832 | L->replaceAllUsesWith(TheArg); |
| 833 | AA.replaceWithNewValue(L, TheArg); |
| 834 | L->eraseFromParent(); |
| 835 | } |
| 836 | AA.deleteValue(GEP); |
| 837 | GEP->eraseFromParent(); |
| 838 | } |
| 839 | } |
| 840 | |
| 841 | // Increment I2 past all of the arguments added for this promoted pointer. |
| 842 | for (unsigned i = 0, e = ArgIndices.size(); i != e; ++i) |
| 843 | ++I2; |
| 844 | } |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 845 | |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 846 | // Notify the alias analysis implementation that we inserted a new argument. |
| 847 | if (ExtraArgHack) |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 848 | AA.copyValue(Context.getNullValue(Type::Int32Ty), NF->arg_begin()); |
Chris Lattner | 9e7cc2f | 2004-05-23 21:21:17 +0000 | [diff] [blame] | 849 | |
| 850 | |
| 851 | // Tell the alias analysis that the old function is about to disappear. |
| 852 | AA.replaceWithNewValue(F, NF); |
| 853 | |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 854 | // Now that the old function is dead, delete it. |
Chris Lattner | 40c14be | 2008-01-11 19:20:39 +0000 | [diff] [blame] | 855 | F->eraseFromParent(); |
Chris Lattner | 5eb6f6c | 2004-09-18 00:34:13 +0000 | [diff] [blame] | 856 | return NF; |
Chris Lattner | ed570a7 | 2004-03-07 21:29:54 +0000 | [diff] [blame] | 857 | } |