Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 1 | //===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +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 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 9 | // |
| 10 | // This transformation implements the well known scalar replacement of |
| 11 | // aggregates transformation. This xform breaks up alloca instructions of |
| 12 | // aggregate type (structure or array) into individual alloca instructions for |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 13 | // each member (if possible). Then, if possible, it transforms the individual |
| 14 | // alloca instructions into nice clean scalar SSA form. |
| 15 | // |
| 16 | // This combines a simple SRoA algorithm with the Mem2Reg algorithm because |
| 17 | // often interact, especially for C++ programs. As such, iterating between |
| 18 | // SRoA, then Mem2Reg until we run out of things to promote works well. |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 19 | // |
| 20 | //===----------------------------------------------------------------------===// |
| 21 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 22 | #define DEBUG_TYPE "scalarrepl" |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 23 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 24 | #include "llvm/Constants.h" |
| 25 | #include "llvm/DerivedTypes.h" |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 26 | #include "llvm/Function.h" |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 27 | #include "llvm/GlobalVariable.h" |
Misha Brukman | d8e1eea | 2004-07-29 17:05:13 +0000 | [diff] [blame] | 28 | #include "llvm/Instructions.h" |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 29 | #include "llvm/IntrinsicInst.h" |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 30 | #include "llvm/LLVMContext.h" |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 31 | #include "llvm/Pass.h" |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 32 | #include "llvm/Analysis/Dominators.h" |
| 33 | #include "llvm/Target/TargetData.h" |
| 34 | #include "llvm/Transforms/Utils/PromoteMemToReg.h" |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 35 | #include "llvm/Transforms/Utils/Local.h" |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 36 | #include "llvm/Support/Debug.h" |
Torok Edwin | 7d696d8 | 2009-07-11 13:10:19 +0000 | [diff] [blame] | 37 | #include "llvm/Support/ErrorHandling.h" |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 38 | #include "llvm/Support/GetElementPtrTypeIterator.h" |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 39 | #include "llvm/Support/IRBuilder.h" |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 40 | #include "llvm/Support/MathExtras.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 41 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 1ccd185 | 2007-02-12 22:56:41 +0000 | [diff] [blame] | 42 | #include "llvm/ADT/SmallVector.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 43 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | d866473 | 2003-12-02 17:43:55 +0000 | [diff] [blame] | 44 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 45 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 46 | STATISTIC(NumReplaced, "Number of allocas broken up"); |
| 47 | STATISTIC(NumPromoted, "Number of allocas promoted"); |
| 48 | STATISTIC(NumConverted, "Number of aggregates converted to scalar"); |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 49 | STATISTIC(NumGlobals, "Number of allocas copied from constant global"); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 50 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 51 | namespace { |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 52 | struct VISIBILITY_HIDDEN SROA : public FunctionPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 53 | static char ID; // Pass identification, replacement for typeid |
Dan Gohman | ae73dc1 | 2008-09-04 17:05:41 +0000 | [diff] [blame] | 54 | explicit SROA(signed T = -1) : FunctionPass(&ID) { |
Devang Patel | ff36685 | 2007-07-09 21:19:23 +0000 | [diff] [blame] | 55 | if (T == -1) |
Chris Lattner | b0e71ed | 2007-08-02 21:33:36 +0000 | [diff] [blame] | 56 | SRThreshold = 128; |
Devang Patel | ff36685 | 2007-07-09 21:19:23 +0000 | [diff] [blame] | 57 | else |
| 58 | SRThreshold = T; |
| 59 | } |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 60 | |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 61 | bool runOnFunction(Function &F); |
| 62 | |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 63 | bool performScalarRepl(Function &F); |
| 64 | bool performPromotion(Function &F); |
| 65 | |
Chris Lattner | a15854c | 2003-08-31 00:45:13 +0000 | [diff] [blame] | 66 | // getAnalysisUsage - This pass does not require any passes, but we know it |
| 67 | // will not alter the CFG, so say so. |
| 68 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Devang Patel | 326821e | 2007-06-07 21:57:03 +0000 | [diff] [blame] | 69 | AU.addRequired<DominatorTree>(); |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 70 | AU.addRequired<DominanceFrontier>(); |
| 71 | AU.addRequired<TargetData>(); |
Chris Lattner | a15854c | 2003-08-31 00:45:13 +0000 | [diff] [blame] | 72 | AU.setPreservesCFG(); |
| 73 | } |
| 74 | |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 75 | private: |
Chris Lattner | 56c3852 | 2009-01-07 06:34:28 +0000 | [diff] [blame] | 76 | TargetData *TD; |
| 77 | |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 78 | /// AllocaInfo - When analyzing uses of an alloca instruction, this captures |
| 79 | /// information about the uses. All these fields are initialized to false |
| 80 | /// and set to true when something is learned. |
| 81 | struct AllocaInfo { |
| 82 | /// isUnsafe - This is set to true if the alloca cannot be SROA'd. |
| 83 | bool isUnsafe : 1; |
| 84 | |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 85 | /// needsCleanup - This is set to true if there is some use of the alloca |
| 86 | /// that requires cleanup. |
| 87 | bool needsCleanup : 1; |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 88 | |
| 89 | /// isMemCpySrc - This is true if this aggregate is memcpy'd from. |
| 90 | bool isMemCpySrc : 1; |
| 91 | |
Zhou Sheng | 33b0b8d | 2007-07-06 06:01:16 +0000 | [diff] [blame] | 92 | /// isMemCpyDst - This is true if this aggregate is memcpy'd into. |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 93 | bool isMemCpyDst : 1; |
| 94 | |
| 95 | AllocaInfo() |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 96 | : isUnsafe(false), needsCleanup(false), |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 97 | isMemCpySrc(false), isMemCpyDst(false) {} |
| 98 | }; |
| 99 | |
Devang Patel | ff36685 | 2007-07-09 21:19:23 +0000 | [diff] [blame] | 100 | unsigned SRThreshold; |
| 101 | |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 102 | void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; } |
| 103 | |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 104 | int isSafeAllocaToScalarRepl(AllocationInst *AI); |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 105 | |
| 106 | void isSafeUseOfAllocation(Instruction *User, AllocationInst *AI, |
| 107 | AllocaInfo &Info); |
| 108 | void isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI, |
| 109 | AllocaInfo &Info); |
| 110 | void isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI, |
| 111 | unsigned OpNo, AllocaInfo &Info); |
| 112 | void isSafeUseOfBitCastedAllocation(BitCastInst *User, AllocationInst *AI, |
| 113 | AllocaInfo &Info); |
| 114 | |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 115 | void DoScalarReplacement(AllocationInst *AI, |
| 116 | std::vector<AllocationInst*> &WorkList); |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 117 | void CleanupGEP(GetElementPtrInst *GEP); |
| 118 | void CleanupAllocaUsers(AllocationInst *AI); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 119 | AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 120 | |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 121 | void RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI, |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 122 | SmallVector<AllocaInst*, 32> &NewElts); |
| 123 | |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 124 | void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *BCInst, |
| 125 | AllocationInst *AI, |
| 126 | SmallVector<AllocaInst*, 32> &NewElts); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 127 | void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocationInst *AI, |
| 128 | SmallVector<AllocaInst*, 32> &NewElts); |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 129 | void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocationInst *AI, |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 130 | SmallVector<AllocaInst*, 32> &NewElts); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 131 | |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 132 | bool CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy, |
Chris Lattner | 1a3257b | 2009-02-03 18:15:05 +0000 | [diff] [blame] | 133 | bool &SawVec, uint64_t Offset, unsigned AllocaSize); |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 134 | void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset); |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 135 | Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType, |
Chris Lattner | 9bc67da | 2009-02-03 19:45:44 +0000 | [diff] [blame] | 136 | uint64_t Offset, IRBuilder<> &Builder); |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 137 | Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal, |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 138 | uint64_t Offset, IRBuilder<> &Builder); |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 139 | static Instruction *isOnlyCopiedFromConstantGlobal(AllocationInst *AI); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 140 | }; |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 141 | } |
| 142 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 143 | char SROA::ID = 0; |
| 144 | static RegisterPass<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); |
| 145 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 146 | // Public interface to the ScalarReplAggregates pass |
Devang Patel | ff36685 | 2007-07-09 21:19:23 +0000 | [diff] [blame] | 147 | FunctionPass *llvm::createScalarReplAggregatesPass(signed int Threshold) { |
| 148 | return new SROA(Threshold); |
| 149 | } |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 150 | |
| 151 | |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 152 | bool SROA::runOnFunction(Function &F) { |
Chris Lattner | 56c3852 | 2009-01-07 06:34:28 +0000 | [diff] [blame] | 153 | TD = &getAnalysis<TargetData>(); |
| 154 | |
Chris Lattner | fe7ea0d | 2003-09-12 15:36:03 +0000 | [diff] [blame] | 155 | bool Changed = performPromotion(F); |
| 156 | while (1) { |
| 157 | bool LocalChange = performScalarRepl(F); |
| 158 | if (!LocalChange) break; // No need to repromote if no scalarrepl |
| 159 | Changed = true; |
| 160 | LocalChange = performPromotion(F); |
| 161 | if (!LocalChange) break; // No need to re-scalarrepl if no promotion |
| 162 | } |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 163 | |
| 164 | return Changed; |
| 165 | } |
| 166 | |
| 167 | |
| 168 | bool SROA::performPromotion(Function &F) { |
| 169 | std::vector<AllocaInst*> Allocas; |
Devang Patel | 326821e | 2007-06-07 21:57:03 +0000 | [diff] [blame] | 170 | DominatorTree &DT = getAnalysis<DominatorTree>(); |
Chris Lattner | 43f820d | 2003-10-05 21:20:13 +0000 | [diff] [blame] | 171 | DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 172 | |
Chris Lattner | 02a3be0 | 2003-09-20 14:39:18 +0000 | [diff] [blame] | 173 | BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 174 | |
Chris Lattner | fe7ea0d | 2003-09-12 15:36:03 +0000 | [diff] [blame] | 175 | bool Changed = false; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 176 | |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 177 | while (1) { |
| 178 | Allocas.clear(); |
| 179 | |
| 180 | // Find allocas that are safe to promote, by looking at all instructions in |
| 181 | // the entry node |
| 182 | for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) |
| 183 | if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? |
Devang Patel | 41968df | 2007-04-25 17:15:20 +0000 | [diff] [blame] | 184 | if (isAllocaPromotable(AI)) |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 185 | Allocas.push_back(AI); |
| 186 | |
| 187 | if (Allocas.empty()) break; |
| 188 | |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 189 | PromoteMemToReg(Allocas, DT, DF, F.getContext()); |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 190 | NumPromoted += Allocas.size(); |
| 191 | Changed = true; |
| 192 | } |
| 193 | |
| 194 | return Changed; |
| 195 | } |
| 196 | |
Chris Lattner | 963a97f | 2008-06-22 17:46:21 +0000 | [diff] [blame] | 197 | /// getNumSAElements - Return the number of elements in the specific struct or |
| 198 | /// array. |
| 199 | static uint64_t getNumSAElements(const Type *T) { |
| 200 | if (const StructType *ST = dyn_cast<StructType>(T)) |
| 201 | return ST->getNumElements(); |
| 202 | return cast<ArrayType>(T)->getNumElements(); |
| 203 | } |
| 204 | |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 205 | // performScalarRepl - This algorithm is a simple worklist driven algorithm, |
| 206 | // which runs on all of the malloc/alloca instructions in the function, removing |
| 207 | // them if they are only used by getelementptr instructions. |
| 208 | // |
| 209 | bool SROA::performScalarRepl(Function &F) { |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 210 | std::vector<AllocationInst*> WorkList; |
| 211 | |
| 212 | // Scan the entry basic block, adding any alloca's and mallocs to the worklist |
Chris Lattner | 02a3be0 | 2003-09-20 14:39:18 +0000 | [diff] [blame] | 213 | BasicBlock &BB = F.getEntryBlock(); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 214 | for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) |
| 215 | if (AllocationInst *A = dyn_cast<AllocationInst>(I)) |
| 216 | WorkList.push_back(A); |
| 217 | |
| 218 | // Process the worklist |
| 219 | bool Changed = false; |
| 220 | while (!WorkList.empty()) { |
| 221 | AllocationInst *AI = WorkList.back(); |
| 222 | WorkList.pop_back(); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 223 | |
Chris Lattner | add2bd7 | 2006-12-22 23:14:42 +0000 | [diff] [blame] | 224 | // Handle dead allocas trivially. These can be formed by SROA'ing arrays |
| 225 | // with unused elements. |
| 226 | if (AI->use_empty()) { |
| 227 | AI->eraseFromParent(); |
| 228 | continue; |
| 229 | } |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 230 | |
| 231 | // If this alloca is impossible for us to promote, reject it early. |
| 232 | if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized()) |
| 233 | continue; |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 234 | |
| 235 | // Check to see if this allocation is only modified by a memcpy/memmove from |
| 236 | // a constant global. If this is the case, we can change all users to use |
| 237 | // the constant global instead. This is commonly produced by the CFE by |
| 238 | // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A' |
| 239 | // is only subsequently read. |
| 240 | if (Instruction *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) { |
| 241 | DOUT << "Found alloca equal to global: " << *AI; |
| 242 | DOUT << " memcpy = " << *TheCopy; |
| 243 | Constant *TheSrc = cast<Constant>(TheCopy->getOperand(2)); |
Owen Anderson | baf3c40 | 2009-07-29 18:55:55 +0000 | [diff] [blame] | 244 | AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType())); |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 245 | TheCopy->eraseFromParent(); // Don't mutate the global. |
| 246 | AI->eraseFromParent(); |
| 247 | ++NumGlobals; |
| 248 | Changed = true; |
| 249 | continue; |
| 250 | } |
Chris Lattner | 15c8277 | 2009-02-02 20:44:45 +0000 | [diff] [blame] | 251 | |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 252 | // Check to see if we can perform the core SROA transformation. We cannot |
| 253 | // transform the allocation instruction if it is an array allocation |
| 254 | // (allocations OF arrays are ok though), and an allocation of a scalar |
| 255 | // value cannot be decomposed at all. |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 256 | uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType()); |
Bill Wendling | 5a377cb | 2009-03-03 12:12:58 +0000 | [diff] [blame] | 257 | |
| 258 | // Do not promote any struct whose size is too big. |
Bill Wendling | 3aaf5d9 | 2009-03-03 19:18:49 +0000 | [diff] [blame] | 259 | if (AllocaSize > SRThreshold) continue; |
Bill Wendling | 8fe4081 | 2009-03-01 03:55:12 +0000 | [diff] [blame] | 260 | |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 261 | if ((isa<StructType>(AI->getAllocatedType()) || |
| 262 | isa<ArrayType>(AI->getAllocatedType())) && |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 263 | // Do not promote any struct into more than "32" separate vars. |
Evan Cheng | 67fca63 | 2009-03-06 00:56:43 +0000 | [diff] [blame] | 264 | getNumSAElements(AI->getAllocatedType()) <= SRThreshold/4) { |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 265 | // Check that all of the users of the allocation are capable of being |
| 266 | // transformed. |
| 267 | switch (isSafeAllocaToScalarRepl(AI)) { |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 268 | default: llvm_unreachable("Unexpected value!"); |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 269 | case 0: // Not safe to scalar replace. |
| 270 | break; |
| 271 | case 1: // Safe, but requires cleanup/canonicalizations first |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 272 | CleanupAllocaUsers(AI); |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 273 | // FALL THROUGH. |
| 274 | case 3: // Safe to scalar replace. |
| 275 | DoScalarReplacement(AI, WorkList); |
| 276 | Changed = true; |
| 277 | continue; |
| 278 | } |
| 279 | } |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 280 | |
| 281 | // If we can turn this aggregate value (potentially with casts) into a |
| 282 | // simple scalar value that can be mem2reg'd into a register value. |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 283 | // IsNotTrivial tracks whether this is something that mem2reg could have |
| 284 | // promoted itself. If so, we don't want to transform it needlessly. Note |
| 285 | // that we can't just check based on the type: the alloca may be of an i32 |
| 286 | // but that has pointer arithmetic to set byte 3 of it or something. |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 287 | bool IsNotTrivial = false; |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 288 | const Type *VectorTy = 0; |
Chris Lattner | 1a3257b | 2009-02-03 18:15:05 +0000 | [diff] [blame] | 289 | bool HadAVector = false; |
| 290 | if (CanConvertToScalar(AI, IsNotTrivial, VectorTy, HadAVector, |
Chris Lattner | 0ff83ab | 2009-03-04 19:22:30 +0000 | [diff] [blame] | 291 | 0, unsigned(AllocaSize)) && IsNotTrivial) { |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 292 | AllocaInst *NewAI; |
Chris Lattner | 1a3257b | 2009-02-03 18:15:05 +0000 | [diff] [blame] | 293 | // If we were able to find a vector type that can handle this with |
| 294 | // insert/extract elements, and if there was at least one use that had |
| 295 | // a vector type, promote this to a vector. We don't want to promote |
| 296 | // random stuff that doesn't use vectors (e.g. <9 x double>) because then |
| 297 | // we just get a lot of insert/extracts. If at least one vector is |
| 298 | // involved, then we probably really do have a union of vector/array. |
| 299 | if (VectorTy && isa<VectorType>(VectorTy) && HadAVector) { |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 300 | DOUT << "CONVERT TO VECTOR: " << *AI << " TYPE = " << *VectorTy <<"\n"; |
Chris Lattner | 15c8277 | 2009-02-02 20:44:45 +0000 | [diff] [blame] | 301 | |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 302 | // Create and insert the vector alloca. |
Owen Anderson | 50dead0 | 2009-07-15 23:53:25 +0000 | [diff] [blame] | 303 | NewAI = new AllocaInst(VectorTy, 0, "", AI->getParent()->begin()); |
Chris Lattner | 15c8277 | 2009-02-02 20:44:45 +0000 | [diff] [blame] | 304 | ConvertUsesToScalar(AI, NewAI, 0); |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 305 | } else { |
| 306 | DOUT << "CONVERT TO SCALAR INTEGER: " << *AI << "\n"; |
| 307 | |
| 308 | // Create and insert the integer alloca. |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 309 | const Type *NewTy = IntegerType::get(AllocaSize*8); |
Owen Anderson | 50dead0 | 2009-07-15 23:53:25 +0000 | [diff] [blame] | 310 | NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin()); |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 311 | ConvertUsesToScalar(AI, NewAI, 0); |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 312 | } |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 313 | NewAI->takeName(AI); |
| 314 | AI->eraseFromParent(); |
| 315 | ++NumConverted; |
| 316 | Changed = true; |
| 317 | continue; |
| 318 | } |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 319 | |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 320 | // Otherwise, couldn't process this alloca. |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 321 | } |
| 322 | |
| 323 | return Changed; |
| 324 | } |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 325 | |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 326 | /// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl |
| 327 | /// predicate, do SROA now. |
| 328 | void SROA::DoScalarReplacement(AllocationInst *AI, |
| 329 | std::vector<AllocationInst*> &WorkList) { |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 330 | DOUT << "Found inst to SROA: " << *AI; |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 331 | SmallVector<AllocaInst*, 32> ElementAllocas; |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 332 | LLVMContext &Context = AI->getContext(); |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 333 | if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { |
| 334 | ElementAllocas.reserve(ST->getNumContainedTypes()); |
| 335 | for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { |
Owen Anderson | 50dead0 | 2009-07-15 23:53:25 +0000 | [diff] [blame] | 336 | AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 337 | AI->getAlignment(), |
Daniel Dunbar | 7f93dc8 | 2009-07-30 04:20:37 +0000 | [diff] [blame^] | 338 | AI->getName() + "." + i, AI); |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 339 | ElementAllocas.push_back(NA); |
| 340 | WorkList.push_back(NA); // Add to worklist for recursive processing |
| 341 | } |
| 342 | } else { |
| 343 | const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); |
| 344 | ElementAllocas.reserve(AT->getNumElements()); |
| 345 | const Type *ElTy = AT->getElementType(); |
| 346 | for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { |
Owen Anderson | 50dead0 | 2009-07-15 23:53:25 +0000 | [diff] [blame] | 347 | AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), |
Daniel Dunbar | 7f93dc8 | 2009-07-30 04:20:37 +0000 | [diff] [blame^] | 348 | AI->getName() + "." + i, AI); |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 349 | ElementAllocas.push_back(NA); |
| 350 | WorkList.push_back(NA); // Add to worklist for recursive processing |
| 351 | } |
| 352 | } |
| 353 | |
| 354 | // Now that we have created the alloca instructions that we want to use, |
| 355 | // expand the getelementptr instructions to use them. |
| 356 | // |
| 357 | while (!AI->use_empty()) { |
| 358 | Instruction *User = cast<Instruction>(AI->use_back()); |
| 359 | if (BitCastInst *BCInst = dyn_cast<BitCastInst>(User)) { |
| 360 | RewriteBitCastUserOfAlloca(BCInst, AI, ElementAllocas); |
| 361 | BCInst->eraseFromParent(); |
| 362 | continue; |
| 363 | } |
| 364 | |
Chris Lattner | 2a6a645 | 2008-06-23 17:11:23 +0000 | [diff] [blame] | 365 | // Replace: |
| 366 | // %res = load { i32, i32 }* %alloc |
| 367 | // with: |
| 368 | // %load.0 = load i32* %alloc.0 |
| 369 | // %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0 |
| 370 | // %load.1 = load i32* %alloc.1 |
| 371 | // %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1 |
Matthijs Kooijman | 0251814 | 2008-06-05 12:51:53 +0000 | [diff] [blame] | 372 | // (Also works for arrays instead of structs) |
| 373 | if (LoadInst *LI = dyn_cast<LoadInst>(User)) { |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 374 | Value *Insert = Context.getUndef(LI->getType()); |
Matthijs Kooijman | 0251814 | 2008-06-05 12:51:53 +0000 | [diff] [blame] | 375 | for (unsigned i = 0, e = ElementAllocas.size(); i != e; ++i) { |
| 376 | Value *Load = new LoadInst(ElementAllocas[i], "load", LI); |
| 377 | Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI); |
| 378 | } |
| 379 | LI->replaceAllUsesWith(Insert); |
| 380 | LI->eraseFromParent(); |
| 381 | continue; |
| 382 | } |
| 383 | |
Chris Lattner | 2a6a645 | 2008-06-23 17:11:23 +0000 | [diff] [blame] | 384 | // Replace: |
| 385 | // store { i32, i32 } %val, { i32, i32 }* %alloc |
| 386 | // with: |
| 387 | // %val.0 = extractvalue { i32, i32 } %val, 0 |
| 388 | // store i32 %val.0, i32* %alloc.0 |
| 389 | // %val.1 = extractvalue { i32, i32 } %val, 1 |
| 390 | // store i32 %val.1, i32* %alloc.1 |
Matthijs Kooijman | 0251814 | 2008-06-05 12:51:53 +0000 | [diff] [blame] | 391 | // (Also works for arrays instead of structs) |
| 392 | if (StoreInst *SI = dyn_cast<StoreInst>(User)) { |
| 393 | Value *Val = SI->getOperand(0); |
| 394 | for (unsigned i = 0, e = ElementAllocas.size(); i != e; ++i) { |
| 395 | Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI); |
| 396 | new StoreInst(Extract, ElementAllocas[i], SI); |
| 397 | } |
| 398 | SI->eraseFromParent(); |
| 399 | continue; |
| 400 | } |
| 401 | |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 402 | GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); |
| 403 | // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> |
| 404 | unsigned Idx = |
| 405 | (unsigned)cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); |
| 406 | |
| 407 | assert(Idx < ElementAllocas.size() && "Index out of range?"); |
| 408 | AllocaInst *AllocaToUse = ElementAllocas[Idx]; |
| 409 | |
| 410 | Value *RepValue; |
| 411 | if (GEPI->getNumOperands() == 3) { |
| 412 | // Do not insert a new getelementptr instruction with zero indices, only |
| 413 | // to have it optimized out later. |
| 414 | RepValue = AllocaToUse; |
| 415 | } else { |
| 416 | // We are indexing deeply into the structure, so we still need a |
| 417 | // getelement ptr instruction to finish the indexing. This may be |
| 418 | // expanded itself once the worklist is rerun. |
| 419 | // |
| 420 | SmallVector<Value*, 8> NewArgs; |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 421 | NewArgs.push_back(Context.getNullValue(Type::Int32Ty)); |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 422 | NewArgs.append(GEPI->op_begin()+3, GEPI->op_end()); |
Gabor Greif | 051a950 | 2008-04-06 20:25:17 +0000 | [diff] [blame] | 423 | RepValue = GetElementPtrInst::Create(AllocaToUse, NewArgs.begin(), |
| 424 | NewArgs.end(), "", GEPI); |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 425 | RepValue->takeName(GEPI); |
| 426 | } |
| 427 | |
| 428 | // If this GEP is to the start of the aggregate, check for memcpys. |
Chris Lattner | d356a7e | 2009-01-07 06:25:07 +0000 | [diff] [blame] | 429 | if (Idx == 0 && GEPI->hasAllZeroIndices()) |
| 430 | RewriteBitCastUserOfAlloca(GEPI, AI, ElementAllocas); |
Chris Lattner | a10b29b | 2007-04-25 05:02:56 +0000 | [diff] [blame] | 431 | |
| 432 | // Move all of the users over to the new GEP. |
| 433 | GEPI->replaceAllUsesWith(RepValue); |
| 434 | // Delete the old GEP |
| 435 | GEPI->eraseFromParent(); |
| 436 | } |
| 437 | |
| 438 | // Finally, delete the Alloca instruction |
| 439 | AI->eraseFromParent(); |
| 440 | NumReplaced++; |
| 441 | } |
| 442 | |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 443 | |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 444 | /// isSafeElementUse - Check to see if this use is an allowed use for a |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 445 | /// getelementptr instruction of an array aggregate allocation. isFirstElt |
| 446 | /// indicates whether Ptr is known to the start of the aggregate. |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 447 | /// |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 448 | void SROA::isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI, |
| 449 | AllocaInfo &Info) { |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 450 | for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); |
| 451 | I != E; ++I) { |
| 452 | Instruction *User = cast<Instruction>(*I); |
| 453 | switch (User->getOpcode()) { |
| 454 | case Instruction::Load: break; |
| 455 | case Instruction::Store: |
| 456 | // Store is ok if storing INTO the pointer, not storing the pointer |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 457 | if (User->getOperand(0) == Ptr) return MarkUnsafe(Info); |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 458 | break; |
| 459 | case Instruction::GetElementPtr: { |
| 460 | GetElementPtrInst *GEP = cast<GetElementPtrInst>(User); |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 461 | bool AreAllZeroIndices = isFirstElt; |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 462 | if (GEP->getNumOperands() > 1) { |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 463 | if (!isa<ConstantInt>(GEP->getOperand(1)) || |
| 464 | !cast<ConstantInt>(GEP->getOperand(1))->isZero()) |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 465 | // Using pointer arithmetic to navigate the array. |
| 466 | return MarkUnsafe(Info); |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 467 | |
Chris Lattner | d356a7e | 2009-01-07 06:25:07 +0000 | [diff] [blame] | 468 | if (AreAllZeroIndices) |
| 469 | AreAllZeroIndices = GEP->hasAllZeroIndices(); |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 470 | } |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 471 | isSafeElementUse(GEP, AreAllZeroIndices, AI, Info); |
| 472 | if (Info.isUnsafe) return; |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 473 | break; |
| 474 | } |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 475 | case Instruction::BitCast: |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 476 | if (isFirstElt) { |
| 477 | isSafeUseOfBitCastedAllocation(cast<BitCastInst>(User), AI, Info); |
| 478 | if (Info.isUnsafe) return; |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 479 | break; |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 480 | } |
| 481 | DOUT << " Transformation preventing inst: " << *User; |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 482 | return MarkUnsafe(Info); |
| 483 | case Instruction::Call: |
| 484 | if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { |
| 485 | if (isFirstElt) { |
| 486 | isSafeMemIntrinsicOnAllocation(MI, AI, I.getOperandNo(), Info); |
| 487 | if (Info.isUnsafe) return; |
| 488 | break; |
| 489 | } |
| 490 | } |
| 491 | DOUT << " Transformation preventing inst: " << *User; |
| 492 | return MarkUnsafe(Info); |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 493 | default: |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 494 | DOUT << " Transformation preventing inst: " << *User; |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 495 | return MarkUnsafe(Info); |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 496 | } |
| 497 | } |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 498 | return; // All users look ok :) |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 499 | } |
| 500 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 501 | /// AllUsersAreLoads - Return true if all users of this value are loads. |
| 502 | static bool AllUsersAreLoads(Value *Ptr) { |
| 503 | for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); |
| 504 | I != E; ++I) |
| 505 | if (cast<Instruction>(*I)->getOpcode() != Instruction::Load) |
| 506 | return false; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 507 | return true; |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 508 | } |
| 509 | |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 510 | /// isSafeUseOfAllocation - Check to see if this user is an allowed use for an |
| 511 | /// aggregate allocation. |
| 512 | /// |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 513 | void SROA::isSafeUseOfAllocation(Instruction *User, AllocationInst *AI, |
| 514 | AllocaInfo &Info) { |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 515 | LLVMContext &Context = User->getContext(); |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 516 | if (BitCastInst *C = dyn_cast<BitCastInst>(User)) |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 517 | return isSafeUseOfBitCastedAllocation(C, AI, Info); |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 518 | |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 519 | if (LoadInst *LI = dyn_cast<LoadInst>(User)) |
| 520 | if (!LI->isVolatile()) |
| 521 | return;// Loads (returning a first class aggregrate) are always rewritable |
Matthijs Kooijman | 0251814 | 2008-06-05 12:51:53 +0000 | [diff] [blame] | 522 | |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 523 | if (StoreInst *SI = dyn_cast<StoreInst>(User)) |
| 524 | if (!SI->isVolatile() && SI->getOperand(0) != AI) |
| 525 | return;// Store is ok if storing INTO the pointer, not storing the pointer |
Matthijs Kooijman | 0251814 | 2008-06-05 12:51:53 +0000 | [diff] [blame] | 526 | |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 527 | GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User); |
| 528 | if (GEPI == 0) |
| 529 | return MarkUnsafe(Info); |
| 530 | |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 531 | gep_type_iterator I = gep_type_begin(GEPI), E = gep_type_end(GEPI); |
| 532 | |
Chris Lattner | 25de486 | 2006-03-08 01:05:29 +0000 | [diff] [blame] | 533 | // The GEP is not safe to transform if not of the form "GEP <ptr>, 0, <cst>". |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 534 | if (I == E || |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 535 | I.getOperand() != Context.getNullValue(I.getOperand()->getType())) { |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 536 | return MarkUnsafe(Info); |
| 537 | } |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 538 | |
| 539 | ++I; |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 540 | if (I == E) return MarkUnsafe(Info); // ran out of GEP indices?? |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 541 | |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 542 | bool IsAllZeroIndices = true; |
| 543 | |
Chris Lattner | 88e6dc8 | 2008-08-23 05:21:06 +0000 | [diff] [blame] | 544 | // If the first index is a non-constant index into an array, see if we can |
| 545 | // handle it as a special case. |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 546 | if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { |
Chris Lattner | 88e6dc8 | 2008-08-23 05:21:06 +0000 | [diff] [blame] | 547 | if (!isa<ConstantInt>(I.getOperand())) { |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 548 | IsAllZeroIndices = 0; |
Chris Lattner | 88e6dc8 | 2008-08-23 05:21:06 +0000 | [diff] [blame] | 549 | uint64_t NumElements = AT->getNumElements(); |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 550 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 551 | // If this is an array index and the index is not constant, we cannot |
| 552 | // promote... that is unless the array has exactly one or two elements in |
| 553 | // it, in which case we CAN promote it, but we have to canonicalize this |
| 554 | // out if this is the only problem. |
Chris Lattner | 25de486 | 2006-03-08 01:05:29 +0000 | [diff] [blame] | 555 | if ((NumElements == 1 || NumElements == 2) && |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 556 | AllUsersAreLoads(GEPI)) { |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 557 | Info.needsCleanup = true; |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 558 | return; // Canonicalization required! |
| 559 | } |
| 560 | return MarkUnsafe(Info); |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 561 | } |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 562 | } |
Matthijs Kooijman | 5fac55f | 2008-10-06 16:23:31 +0000 | [diff] [blame] | 563 | |
Chris Lattner | 88e6dc8 | 2008-08-23 05:21:06 +0000 | [diff] [blame] | 564 | // Walk through the GEP type indices, checking the types that this indexes |
| 565 | // into. |
| 566 | for (; I != E; ++I) { |
| 567 | // Ignore struct elements, no extra checking needed for these. |
| 568 | if (isa<StructType>(*I)) |
| 569 | continue; |
| 570 | |
Chris Lattner | 88e6dc8 | 2008-08-23 05:21:06 +0000 | [diff] [blame] | 571 | ConstantInt *IdxVal = dyn_cast<ConstantInt>(I.getOperand()); |
| 572 | if (!IdxVal) return MarkUnsafe(Info); |
Matthijs Kooijman | 5fac55f | 2008-10-06 16:23:31 +0000 | [diff] [blame] | 573 | |
| 574 | // Are all indices still zero? |
Chris Lattner | 88e6dc8 | 2008-08-23 05:21:06 +0000 | [diff] [blame] | 575 | IsAllZeroIndices &= IdxVal->isZero(); |
Matthijs Kooijman | 5fac55f | 2008-10-06 16:23:31 +0000 | [diff] [blame] | 576 | |
| 577 | if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { |
| 578 | // This GEP indexes an array. Verify that this is an in-range constant |
| 579 | // integer. Specifically, consider A[0][i]. We cannot know that the user |
| 580 | // isn't doing invalid things like allowing i to index an out-of-range |
| 581 | // subscript that accesses A[1]. Because of this, we have to reject SROA |
Dale Johannesen | c0bc547 | 2008-11-04 20:54:03 +0000 | [diff] [blame] | 582 | // of any accesses into structs where any of the components are variables. |
Matthijs Kooijman | 5fac55f | 2008-10-06 16:23:31 +0000 | [diff] [blame] | 583 | if (IdxVal->getZExtValue() >= AT->getNumElements()) |
| 584 | return MarkUnsafe(Info); |
Dale Johannesen | c0bc547 | 2008-11-04 20:54:03 +0000 | [diff] [blame] | 585 | } else if (const VectorType *VT = dyn_cast<VectorType>(*I)) { |
| 586 | if (IdxVal->getZExtValue() >= VT->getNumElements()) |
| 587 | return MarkUnsafe(Info); |
Matthijs Kooijman | 5fac55f | 2008-10-06 16:23:31 +0000 | [diff] [blame] | 588 | } |
Chris Lattner | 88e6dc8 | 2008-08-23 05:21:06 +0000 | [diff] [blame] | 589 | } |
| 590 | |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 591 | // If there are any non-simple uses of this getelementptr, make sure to reject |
| 592 | // them. |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 593 | return isSafeElementUse(GEPI, IsAllZeroIndices, AI, Info); |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 594 | } |
| 595 | |
| 596 | /// isSafeMemIntrinsicOnAllocation - Return true if the specified memory |
| 597 | /// intrinsic can be promoted by SROA. At this point, we know that the operand |
| 598 | /// of the memintrinsic is a pointer to the beginning of the allocation. |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 599 | void SROA::isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI, |
| 600 | unsigned OpNo, AllocaInfo &Info) { |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 601 | // If not constant length, give up. |
| 602 | ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 603 | if (!Length) return MarkUnsafe(Info); |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 604 | |
| 605 | // If not the whole aggregate, give up. |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 606 | if (Length->getZExtValue() != |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 607 | TD->getTypeAllocSize(AI->getType()->getElementType())) |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 608 | return MarkUnsafe(Info); |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 609 | |
| 610 | // We only know about memcpy/memset/memmove. |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 611 | if (!isa<MemIntrinsic>(MI)) |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 612 | return MarkUnsafe(Info); |
| 613 | |
| 614 | // Otherwise, we can transform it. Determine whether this is a memcpy/set |
| 615 | // into or out of the aggregate. |
| 616 | if (OpNo == 1) |
| 617 | Info.isMemCpyDst = true; |
| 618 | else { |
| 619 | assert(OpNo == 2); |
| 620 | Info.isMemCpySrc = true; |
| 621 | } |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 622 | } |
| 623 | |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 624 | /// isSafeUseOfBitCastedAllocation - Return true if all users of this bitcast |
| 625 | /// are |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 626 | void SROA::isSafeUseOfBitCastedAllocation(BitCastInst *BC, AllocationInst *AI, |
| 627 | AllocaInfo &Info) { |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 628 | for (Value::use_iterator UI = BC->use_begin(), E = BC->use_end(); |
| 629 | UI != E; ++UI) { |
| 630 | if (BitCastInst *BCU = dyn_cast<BitCastInst>(UI)) { |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 631 | isSafeUseOfBitCastedAllocation(BCU, AI, Info); |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 632 | } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(UI)) { |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 633 | isSafeMemIntrinsicOnAllocation(MI, AI, UI.getOperandNo(), Info); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 634 | } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 635 | if (SI->isVolatile()) |
| 636 | return MarkUnsafe(Info); |
| 637 | |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 638 | // If storing the entire alloca in one chunk through a bitcasted pointer |
| 639 | // to integer, we can transform it. This happens (for example) when you |
| 640 | // cast a {i32,i32}* to i64* and store through it. This is similar to the |
| 641 | // memcpy case and occurs in various "byval" cases and emulated memcpys. |
| 642 | if (isa<IntegerType>(SI->getOperand(0)->getType()) && |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 643 | TD->getTypeAllocSize(SI->getOperand(0)->getType()) == |
| 644 | TD->getTypeAllocSize(AI->getType()->getElementType())) { |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 645 | Info.isMemCpyDst = true; |
| 646 | continue; |
| 647 | } |
| 648 | return MarkUnsafe(Info); |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 649 | } else if (LoadInst *LI = dyn_cast<LoadInst>(UI)) { |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 650 | if (LI->isVolatile()) |
| 651 | return MarkUnsafe(Info); |
| 652 | |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 653 | // If loading the entire alloca in one chunk through a bitcasted pointer |
| 654 | // to integer, we can transform it. This happens (for example) when you |
| 655 | // cast a {i32,i32}* to i64* and load through it. This is similar to the |
| 656 | // memcpy case and occurs in various "byval" cases and emulated memcpys. |
| 657 | if (isa<IntegerType>(LI->getType()) && |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 658 | TD->getTypeAllocSize(LI->getType()) == |
| 659 | TD->getTypeAllocSize(AI->getType()->getElementType())) { |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 660 | Info.isMemCpySrc = true; |
| 661 | continue; |
| 662 | } |
| 663 | return MarkUnsafe(Info); |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 664 | } else if (isa<DbgInfoIntrinsic>(UI)) { |
| 665 | // If one user is DbgInfoIntrinsic then check if all users are |
| 666 | // DbgInfoIntrinsics. |
| 667 | if (OnlyUsedByDbgInfoIntrinsics(BC)) { |
| 668 | Info.needsCleanup = true; |
| 669 | return; |
| 670 | } |
| 671 | else |
| 672 | MarkUnsafe(Info); |
| 673 | } |
| 674 | else { |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 675 | return MarkUnsafe(Info); |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 676 | } |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 677 | if (Info.isUnsafe) return; |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 678 | } |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 679 | } |
| 680 | |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 681 | /// RewriteBitCastUserOfAlloca - BCInst (transitively) bitcasts AI, or indexes |
| 682 | /// to its first element. Transform users of the cast to use the new values |
| 683 | /// instead. |
| 684 | void SROA::RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI, |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 685 | SmallVector<AllocaInst*, 32> &NewElts) { |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 686 | Value::use_iterator UI = BCInst->use_begin(), UE = BCInst->use_end(); |
| 687 | while (UI != UE) { |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 688 | Instruction *User = cast<Instruction>(*UI++); |
| 689 | if (BitCastInst *BCU = dyn_cast<BitCastInst>(User)) { |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 690 | RewriteBitCastUserOfAlloca(BCU, AI, NewElts); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 691 | if (BCU->use_empty()) BCU->eraseFromParent(); |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 692 | continue; |
| 693 | } |
| 694 | |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 695 | if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { |
| 696 | // This must be memcpy/memmove/memset of the entire aggregate. |
| 697 | // Split into one per element. |
| 698 | RewriteMemIntrinUserOfAlloca(MI, BCInst, AI, NewElts); |
Chris Lattner | 8bf9911 | 2007-03-19 00:16:43 +0000 | [diff] [blame] | 699 | continue; |
| 700 | } |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 701 | |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 702 | if (StoreInst *SI = dyn_cast<StoreInst>(User)) { |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 703 | // If this is a store of the entire alloca from an integer, rewrite it. |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 704 | RewriteStoreUserOfWholeAlloca(SI, AI, NewElts); |
| 705 | continue; |
| 706 | } |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 707 | |
| 708 | if (LoadInst *LI = dyn_cast<LoadInst>(User)) { |
| 709 | // If this is a load of the entire alloca to an integer, rewrite it. |
| 710 | RewriteLoadUserOfWholeAlloca(LI, AI, NewElts); |
| 711 | continue; |
| 712 | } |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 713 | |
| 714 | // Otherwise it must be some other user of a gep of the first pointer. Just |
| 715 | // leave these alone. |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 716 | continue; |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 717 | } |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 718 | } |
| 719 | |
| 720 | /// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI. |
| 721 | /// Rewrite it to copy or set the elements of the scalarized memory. |
| 722 | void SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *BCInst, |
| 723 | AllocationInst *AI, |
| 724 | SmallVector<AllocaInst*, 32> &NewElts) { |
| 725 | |
| 726 | // If this is a memcpy/memmove, construct the other pointer as the |
Chris Lattner | 88fe1ad | 2009-03-04 19:23:25 +0000 | [diff] [blame] | 727 | // appropriate type. The "Other" pointer is the pointer that goes to memory |
| 728 | // that doesn't have anything to do with the alloca that we are promoting. For |
| 729 | // memset, this Value* stays null. |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 730 | Value *OtherPtr = 0; |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 731 | LLVMContext &Context = MI->getContext(); |
Chris Lattner | dfe964c | 2009-03-08 03:59:00 +0000 | [diff] [blame] | 732 | unsigned MemAlignment = MI->getAlignment(); |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 733 | if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { // memmove/memcopy |
| 734 | if (BCInst == MTI->getRawDest()) |
| 735 | OtherPtr = MTI->getRawSource(); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 736 | else { |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 737 | assert(BCInst == MTI->getRawSource()); |
| 738 | OtherPtr = MTI->getRawDest(); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 739 | } |
| 740 | } |
| 741 | |
| 742 | // If there is an other pointer, we want to convert it to the same pointer |
| 743 | // type as AI has, so we can GEP through it safely. |
| 744 | if (OtherPtr) { |
| 745 | // It is likely that OtherPtr is a bitcast, if so, remove it. |
| 746 | if (BitCastInst *BC = dyn_cast<BitCastInst>(OtherPtr)) |
| 747 | OtherPtr = BC->getOperand(0); |
| 748 | // All zero GEPs are effectively bitcasts. |
| 749 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(OtherPtr)) |
| 750 | if (GEP->hasAllZeroIndices()) |
| 751 | OtherPtr = GEP->getOperand(0); |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 752 | |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 753 | if (ConstantExpr *BCE = dyn_cast<ConstantExpr>(OtherPtr)) |
| 754 | if (BCE->getOpcode() == Instruction::BitCast) |
| 755 | OtherPtr = BCE->getOperand(0); |
| 756 | |
| 757 | // If the pointer is not the right type, insert a bitcast to the right |
| 758 | // type. |
| 759 | if (OtherPtr->getType() != AI->getType()) |
| 760 | OtherPtr = new BitCastInst(OtherPtr, AI->getType(), OtherPtr->getName(), |
| 761 | MI); |
| 762 | } |
| 763 | |
| 764 | // Process each element of the aggregate. |
| 765 | Value *TheFn = MI->getOperand(0); |
| 766 | const Type *BytePtrTy = MI->getRawDest()->getType(); |
| 767 | bool SROADest = MI->getRawDest() == BCInst; |
| 768 | |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 769 | Constant *Zero = Context.getNullValue(Type::Int32Ty); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 770 | |
| 771 | for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { |
| 772 | // If this is a memcpy/memmove, emit a GEP of the other element address. |
| 773 | Value *OtherElt = 0; |
Chris Lattner | 1541e0f | 2009-03-04 19:20:50 +0000 | [diff] [blame] | 774 | unsigned OtherEltAlign = MemAlignment; |
| 775 | |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 776 | if (OtherPtr) { |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 777 | Value *Idx[2] = { Zero, ConstantInt::get(Type::Int32Ty, i) }; |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 778 | OtherElt = GetElementPtrInst::Create(OtherPtr, Idx, Idx + 2, |
Daniel Dunbar | 7f93dc8 | 2009-07-30 04:20:37 +0000 | [diff] [blame^] | 779 | OtherPtr->getNameStr()+"."+i, |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 780 | MI); |
Chris Lattner | 1541e0f | 2009-03-04 19:20:50 +0000 | [diff] [blame] | 781 | uint64_t EltOffset; |
| 782 | const PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType()); |
| 783 | if (const StructType *ST = |
| 784 | dyn_cast<StructType>(OtherPtrTy->getElementType())) { |
| 785 | EltOffset = TD->getStructLayout(ST)->getElementOffset(i); |
| 786 | } else { |
| 787 | const Type *EltTy = |
| 788 | cast<SequentialType>(OtherPtr->getType())->getElementType(); |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 789 | EltOffset = TD->getTypeAllocSize(EltTy)*i; |
Chris Lattner | 1541e0f | 2009-03-04 19:20:50 +0000 | [diff] [blame] | 790 | } |
| 791 | |
| 792 | // The alignment of the other pointer is the guaranteed alignment of the |
| 793 | // element, which is affected by both the known alignment of the whole |
| 794 | // mem intrinsic and the alignment of the element. If the alignment of |
| 795 | // the memcpy (f.e.) is 32 but the element is at a 4-byte offset, then the |
| 796 | // known alignment is just 4 bytes. |
| 797 | OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset); |
Chris Lattner | c14d3ca | 2007-03-08 06:36:54 +0000 | [diff] [blame] | 798 | } |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 799 | |
| 800 | Value *EltPtr = NewElts[i]; |
Chris Lattner | 1541e0f | 2009-03-04 19:20:50 +0000 | [diff] [blame] | 801 | const Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType(); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 802 | |
| 803 | // If we got down to a scalar, insert a load or store as appropriate. |
| 804 | if (EltTy->isSingleValueType()) { |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 805 | if (isa<MemTransferInst>(MI)) { |
Chris Lattner | 1541e0f | 2009-03-04 19:20:50 +0000 | [diff] [blame] | 806 | if (SROADest) { |
| 807 | // From Other to Alloca. |
| 808 | Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI); |
| 809 | new StoreInst(Elt, EltPtr, MI); |
| 810 | } else { |
| 811 | // From Alloca to Other. |
| 812 | Value *Elt = new LoadInst(EltPtr, "tmp", MI); |
| 813 | new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI); |
| 814 | } |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 815 | continue; |
| 816 | } |
| 817 | assert(isa<MemSetInst>(MI)); |
| 818 | |
| 819 | // If the stored element is zero (common case), just store a null |
| 820 | // constant. |
| 821 | Constant *StoreVal; |
| 822 | if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getOperand(2))) { |
| 823 | if (CI->isZero()) { |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 824 | StoreVal = Context.getNullValue(EltTy); // 0.0, null, 0, <0,0> |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 825 | } else { |
| 826 | // If EltTy is a vector type, get the element type. |
Dan Gohman | 44118f0 | 2009-06-16 00:20:26 +0000 | [diff] [blame] | 827 | const Type *ValTy = EltTy->getScalarType(); |
| 828 | |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 829 | // Construct an integer with the right value. |
| 830 | unsigned EltSize = TD->getTypeSizeInBits(ValTy); |
| 831 | APInt OneVal(EltSize, CI->getZExtValue()); |
| 832 | APInt TotalVal(OneVal); |
| 833 | // Set each byte. |
| 834 | for (unsigned i = 0; 8*i < EltSize; ++i) { |
| 835 | TotalVal = TotalVal.shl(8); |
| 836 | TotalVal |= OneVal; |
| 837 | } |
| 838 | |
| 839 | // Convert the integer value to the appropriate type. |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 840 | StoreVal = ConstantInt::get(Context, TotalVal); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 841 | if (isa<PointerType>(ValTy)) |
Owen Anderson | baf3c40 | 2009-07-29 18:55:55 +0000 | [diff] [blame] | 842 | StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 843 | else if (ValTy->isFloatingPoint()) |
Owen Anderson | baf3c40 | 2009-07-29 18:55:55 +0000 | [diff] [blame] | 844 | StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 845 | assert(StoreVal->getType() == ValTy && "Type mismatch!"); |
| 846 | |
| 847 | // If the requested value was a vector constant, create it. |
| 848 | if (EltTy != ValTy) { |
| 849 | unsigned NumElts = cast<VectorType>(ValTy)->getNumElements(); |
| 850 | SmallVector<Constant*, 16> Elts(NumElts, StoreVal); |
Owen Anderson | af7ec97 | 2009-07-28 21:19:26 +0000 | [diff] [blame] | 851 | StoreVal = ConstantVector::get(&Elts[0], NumElts); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 852 | } |
| 853 | } |
| 854 | new StoreInst(StoreVal, EltPtr, MI); |
| 855 | continue; |
| 856 | } |
| 857 | // Otherwise, if we're storing a byte variable, use a memset call for |
| 858 | // this element. |
| 859 | } |
| 860 | |
| 861 | // Cast the element pointer to BytePtrTy. |
| 862 | if (EltPtr->getType() != BytePtrTy) |
| 863 | EltPtr = new BitCastInst(EltPtr, BytePtrTy, EltPtr->getNameStr(), MI); |
| 864 | |
| 865 | // Cast the other pointer (if we have one) to BytePtrTy. |
| 866 | if (OtherElt && OtherElt->getType() != BytePtrTy) |
| 867 | OtherElt = new BitCastInst(OtherElt, BytePtrTy,OtherElt->getNameStr(), |
| 868 | MI); |
| 869 | |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 870 | unsigned EltSize = TD->getTypeAllocSize(EltTy); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 871 | |
| 872 | // Finally, insert the meminst for this element. |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 873 | if (isa<MemTransferInst>(MI)) { |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 874 | Value *Ops[] = { |
| 875 | SROADest ? EltPtr : OtherElt, // Dest ptr |
| 876 | SROADest ? OtherElt : EltPtr, // Src ptr |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 877 | ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size |
| 878 | ConstantInt::get(Type::Int32Ty, OtherEltAlign) // Align |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 879 | }; |
| 880 | CallInst::Create(TheFn, Ops, Ops + 4, "", MI); |
| 881 | } else { |
| 882 | assert(isa<MemSetInst>(MI)); |
| 883 | Value *Ops[] = { |
| 884 | EltPtr, MI->getOperand(2), // Dest, Value, |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 885 | ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 886 | Zero // Align |
| 887 | }; |
| 888 | CallInst::Create(TheFn, Ops, Ops + 4, "", MI); |
| 889 | } |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 890 | } |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 891 | MI->eraseFromParent(); |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 892 | } |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 893 | |
| 894 | /// RewriteStoreUserOfWholeAlloca - We found an store of an integer that |
| 895 | /// overwrites the entire allocation. Extract out the pieces of the stored |
| 896 | /// integer and store them individually. |
| 897 | void SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, |
| 898 | AllocationInst *AI, |
| 899 | SmallVector<AllocaInst*, 32> &NewElts){ |
| 900 | // Extract each element out of the integer according to its structure offset |
| 901 | // and store the element value to the individual alloca. |
| 902 | Value *SrcVal = SI->getOperand(0); |
| 903 | const Type *AllocaEltTy = AI->getType()->getElementType(); |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 904 | uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); |
Chris Lattner | d93afec | 2009-01-07 07:18:45 +0000 | [diff] [blame] | 905 | |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 906 | // If this isn't a store of an integer to the whole alloca, it may be a store |
| 907 | // to the first element. Just ignore the store in this case and normal SROA |
Eli Friedman | 41b33f4 | 2009-06-01 09:14:32 +0000 | [diff] [blame] | 908 | // will handle it. |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 909 | if (!isa<IntegerType>(SrcVal->getType()) || |
Eli Friedman | 41b33f4 | 2009-06-01 09:14:32 +0000 | [diff] [blame] | 910 | TD->getTypeAllocSizeInBits(SrcVal->getType()) != AllocaSizeBits) |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 911 | return; |
Eli Friedman | 41b33f4 | 2009-06-01 09:14:32 +0000 | [diff] [blame] | 912 | // Handle tail padding by extending the operand |
| 913 | if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits) |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 914 | SrcVal = new ZExtInst(SrcVal, |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 915 | IntegerType::get(AllocaSizeBits), "", SI); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 916 | |
| 917 | DOUT << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << *SI; |
| 918 | |
| 919 | // There are two forms here: AI could be an array or struct. Both cases |
| 920 | // have different ways to compute the element offset. |
| 921 | if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { |
| 922 | const StructLayout *Layout = TD->getStructLayout(EltSTy); |
| 923 | |
| 924 | for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { |
| 925 | // Get the number of bits to shift SrcVal to get the value. |
| 926 | const Type *FieldTy = EltSTy->getElementType(i); |
| 927 | uint64_t Shift = Layout->getElementOffsetInBits(i); |
| 928 | |
| 929 | if (TD->isBigEndian()) |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 930 | Shift = AllocaSizeBits-Shift-TD->getTypeAllocSizeInBits(FieldTy); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 931 | |
| 932 | Value *EltVal = SrcVal; |
| 933 | if (Shift) { |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 934 | Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 935 | EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, |
| 936 | "sroa.store.elt", SI); |
| 937 | } |
| 938 | |
| 939 | // Truncate down to an integer of the right size. |
| 940 | uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); |
Chris Lattner | 583dd60 | 2009-01-09 18:18:43 +0000 | [diff] [blame] | 941 | |
| 942 | // Ignore zero sized fields like {}, they obviously contain no data. |
| 943 | if (FieldSizeBits == 0) continue; |
| 944 | |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 945 | if (FieldSizeBits != AllocaSizeBits) |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 946 | EltVal = new TruncInst(EltVal, |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 947 | IntegerType::get(FieldSizeBits), "", SI); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 948 | Value *DestField = NewElts[i]; |
| 949 | if (EltVal->getType() == FieldTy) { |
| 950 | // Storing to an integer field of this size, just do it. |
| 951 | } else if (FieldTy->isFloatingPoint() || isa<VectorType>(FieldTy)) { |
| 952 | // Bitcast to the right element type (for fp/vector values). |
| 953 | EltVal = new BitCastInst(EltVal, FieldTy, "", SI); |
| 954 | } else { |
| 955 | // Otherwise, bitcast the dest pointer (for aggregates). |
| 956 | DestField = new BitCastInst(DestField, |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 957 | PointerType::getUnqual(EltVal->getType()), |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 958 | "", SI); |
| 959 | } |
| 960 | new StoreInst(EltVal, DestField, SI); |
| 961 | } |
| 962 | |
| 963 | } else { |
| 964 | const ArrayType *ATy = cast<ArrayType>(AllocaEltTy); |
| 965 | const Type *ArrayEltTy = ATy->getElementType(); |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 966 | uint64_t ElementOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 967 | uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy); |
| 968 | |
| 969 | uint64_t Shift; |
| 970 | |
| 971 | if (TD->isBigEndian()) |
| 972 | Shift = AllocaSizeBits-ElementOffset; |
| 973 | else |
| 974 | Shift = 0; |
| 975 | |
| 976 | for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { |
Chris Lattner | 583dd60 | 2009-01-09 18:18:43 +0000 | [diff] [blame] | 977 | // Ignore zero sized fields like {}, they obviously contain no data. |
| 978 | if (ElementSizeBits == 0) continue; |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 979 | |
| 980 | Value *EltVal = SrcVal; |
| 981 | if (Shift) { |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 982 | Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 983 | EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, |
| 984 | "sroa.store.elt", SI); |
| 985 | } |
| 986 | |
| 987 | // Truncate down to an integer of the right size. |
| 988 | if (ElementSizeBits != AllocaSizeBits) |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 989 | EltVal = new TruncInst(EltVal, |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 990 | IntegerType::get(ElementSizeBits),"",SI); |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 991 | Value *DestField = NewElts[i]; |
| 992 | if (EltVal->getType() == ArrayEltTy) { |
| 993 | // Storing to an integer field of this size, just do it. |
| 994 | } else if (ArrayEltTy->isFloatingPoint() || isa<VectorType>(ArrayEltTy)) { |
| 995 | // Bitcast to the right element type (for fp/vector values). |
| 996 | EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI); |
| 997 | } else { |
| 998 | // Otherwise, bitcast the dest pointer (for aggregates). |
| 999 | DestField = new BitCastInst(DestField, |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 1000 | PointerType::getUnqual(EltVal->getType()), |
Chris Lattner | d2fa781 | 2009-01-07 08:11:13 +0000 | [diff] [blame] | 1001 | "", SI); |
| 1002 | } |
| 1003 | new StoreInst(EltVal, DestField, SI); |
| 1004 | |
| 1005 | if (TD->isBigEndian()) |
| 1006 | Shift -= ElementOffset; |
| 1007 | else |
| 1008 | Shift += ElementOffset; |
| 1009 | } |
| 1010 | } |
| 1011 | |
| 1012 | SI->eraseFromParent(); |
| 1013 | } |
| 1014 | |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1015 | /// RewriteLoadUserOfWholeAlloca - We found an load of the entire allocation to |
| 1016 | /// an integer. Load the individual pieces to form the aggregate value. |
| 1017 | void SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocationInst *AI, |
| 1018 | SmallVector<AllocaInst*, 32> &NewElts) { |
| 1019 | // Extract each element out of the NewElts according to its structure offset |
| 1020 | // and form the result value. |
| 1021 | const Type *AllocaEltTy = AI->getType()->getElementType(); |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 1022 | uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1023 | |
| 1024 | // If this isn't a load of the whole alloca to an integer, it may be a load |
| 1025 | // of the first element. Just ignore the load in this case and normal SROA |
Eli Friedman | 41b33f4 | 2009-06-01 09:14:32 +0000 | [diff] [blame] | 1026 | // will handle it. |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1027 | if (!isa<IntegerType>(LI->getType()) || |
Eli Friedman | 41b33f4 | 2009-06-01 09:14:32 +0000 | [diff] [blame] | 1028 | TD->getTypeAllocSizeInBits(LI->getType()) != AllocaSizeBits) |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1029 | return; |
| 1030 | |
| 1031 | DOUT << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << *LI; |
| 1032 | |
| 1033 | // There are two forms here: AI could be an array or struct. Both cases |
| 1034 | // have different ways to compute the element offset. |
| 1035 | const StructLayout *Layout = 0; |
| 1036 | uint64_t ArrayEltBitOffset = 0; |
| 1037 | if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { |
| 1038 | Layout = TD->getStructLayout(EltSTy); |
| 1039 | } else { |
| 1040 | const Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType(); |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 1041 | ArrayEltBitOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1042 | } |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1043 | |
| 1044 | LLVMContext &Context = LI->getContext(); |
| 1045 | |
| 1046 | Value *ResultVal = |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 1047 | Context.getNullValue(IntegerType::get(AllocaSizeBits)); |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1048 | |
| 1049 | for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { |
| 1050 | // Load the value from the alloca. If the NewElt is an aggregate, cast |
| 1051 | // the pointer to an integer of the same size before doing the load. |
| 1052 | Value *SrcField = NewElts[i]; |
| 1053 | const Type *FieldTy = |
| 1054 | cast<PointerType>(SrcField->getType())->getElementType(); |
Chris Lattner | 583dd60 | 2009-01-09 18:18:43 +0000 | [diff] [blame] | 1055 | uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); |
| 1056 | |
| 1057 | // Ignore zero sized fields like {}, they obviously contain no data. |
| 1058 | if (FieldSizeBits == 0) continue; |
| 1059 | |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 1060 | const IntegerType *FieldIntTy = IntegerType::get(FieldSizeBits); |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1061 | if (!isa<IntegerType>(FieldTy) && !FieldTy->isFloatingPoint() && |
| 1062 | !isa<VectorType>(FieldTy)) |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1063 | SrcField = new BitCastInst(SrcField, |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 1064 | PointerType::getUnqual(FieldIntTy), |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1065 | "", LI); |
| 1066 | SrcField = new LoadInst(SrcField, "sroa.load.elt", LI); |
| 1067 | |
| 1068 | // If SrcField is a fp or vector of the right size but that isn't an |
| 1069 | // integer type, bitcast to an integer so we can shift it. |
| 1070 | if (SrcField->getType() != FieldIntTy) |
| 1071 | SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI); |
| 1072 | |
| 1073 | // Zero extend the field to be the same size as the final alloca so that |
| 1074 | // we can shift and insert it. |
| 1075 | if (SrcField->getType() != ResultVal->getType()) |
| 1076 | SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI); |
| 1077 | |
| 1078 | // Determine the number of bits to shift SrcField. |
| 1079 | uint64_t Shift; |
| 1080 | if (Layout) // Struct case. |
| 1081 | Shift = Layout->getElementOffsetInBits(i); |
| 1082 | else // Array case. |
| 1083 | Shift = i*ArrayEltBitOffset; |
| 1084 | |
| 1085 | if (TD->isBigEndian()) |
| 1086 | Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth(); |
| 1087 | |
| 1088 | if (Shift) { |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1089 | Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift); |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1090 | SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI); |
| 1091 | } |
| 1092 | |
| 1093 | ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI); |
| 1094 | } |
Eli Friedman | 41b33f4 | 2009-06-01 09:14:32 +0000 | [diff] [blame] | 1095 | |
| 1096 | // Handle tail padding by truncating the result |
| 1097 | if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits) |
| 1098 | ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI); |
| 1099 | |
Chris Lattner | 5ffe6ac | 2009-01-08 05:42:05 +0000 | [diff] [blame] | 1100 | LI->replaceAllUsesWith(ResultVal); |
| 1101 | LI->eraseFromParent(); |
| 1102 | } |
| 1103 | |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 1104 | |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1105 | /// HasPadding - Return true if the specified type has any structure or |
| 1106 | /// alignment padding, false otherwise. |
Duncan Sands | a0fcc08 | 2008-06-04 08:21:45 +0000 | [diff] [blame] | 1107 | static bool HasPadding(const Type *Ty, const TargetData &TD) { |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1108 | if (const StructType *STy = dyn_cast<StructType>(Ty)) { |
| 1109 | const StructLayout *SL = TD.getStructLayout(STy); |
| 1110 | unsigned PrevFieldBitOffset = 0; |
| 1111 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1112 | unsigned FieldBitOffset = SL->getElementOffsetInBits(i); |
| 1113 | |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1114 | // Padding in sub-elements? |
Duncan Sands | a0fcc08 | 2008-06-04 08:21:45 +0000 | [diff] [blame] | 1115 | if (HasPadding(STy->getElementType(i), TD)) |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1116 | return true; |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1117 | |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1118 | // Check to see if there is any padding between this element and the |
| 1119 | // previous one. |
| 1120 | if (i) { |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1121 | unsigned PrevFieldEnd = |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1122 | PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1)); |
| 1123 | if (PrevFieldEnd < FieldBitOffset) |
| 1124 | return true; |
| 1125 | } |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1126 | |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1127 | PrevFieldBitOffset = FieldBitOffset; |
| 1128 | } |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1129 | |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1130 | // Check for tail padding. |
| 1131 | if (unsigned EltCount = STy->getNumElements()) { |
| 1132 | unsigned PrevFieldEnd = PrevFieldBitOffset + |
| 1133 | TD.getTypeSizeInBits(STy->getElementType(EltCount-1)); |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1134 | if (PrevFieldEnd < SL->getSizeInBits()) |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1135 | return true; |
| 1136 | } |
| 1137 | |
| 1138 | } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { |
Duncan Sands | a0fcc08 | 2008-06-04 08:21:45 +0000 | [diff] [blame] | 1139 | return HasPadding(ATy->getElementType(), TD); |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1140 | } else if (const VectorType *VTy = dyn_cast<VectorType>(Ty)) { |
Duncan Sands | a0fcc08 | 2008-06-04 08:21:45 +0000 | [diff] [blame] | 1141 | return HasPadding(VTy->getElementType(), TD); |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1142 | } |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 1143 | return TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty); |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1144 | } |
Chris Lattner | 372dda8 | 2007-03-05 07:52:57 +0000 | [diff] [blame] | 1145 | |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 1146 | /// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of |
| 1147 | /// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, |
| 1148 | /// or 1 if safe after canonicalization has been performed. |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 1149 | /// |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 1150 | int SROA::isSafeAllocaToScalarRepl(AllocationInst *AI) { |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 1151 | // Loop over the use list of the alloca. We can only transform it if all of |
| 1152 | // the users are safe to transform. |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1153 | AllocaInfo Info; |
| 1154 | |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 1155 | for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 1156 | I != E; ++I) { |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1157 | isSafeUseOfAllocation(cast<Instruction>(*I), AI, Info); |
| 1158 | if (Info.isUnsafe) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 1159 | DOUT << "Cannot transform: " << *AI << " due to user: " << **I; |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 1160 | return 0; |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 1161 | } |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 1162 | } |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1163 | |
| 1164 | // Okay, we know all the users are promotable. If the aggregate is a memcpy |
| 1165 | // source and destination, we have to be careful. In particular, the memcpy |
| 1166 | // could be moving around elements that live in structure padding of the LLVM |
| 1167 | // types, but may actually be used. In these cases, we refuse to promote the |
| 1168 | // struct. |
| 1169 | if (Info.isMemCpySrc && Info.isMemCpyDst && |
Chris Lattner | 56c3852 | 2009-01-07 06:34:28 +0000 | [diff] [blame] | 1170 | HasPadding(AI->getType()->getElementType(), *TD)) |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1171 | return 0; |
Duncan Sands | 3cb3650 | 2007-11-04 14:43:57 +0000 | [diff] [blame] | 1172 | |
Chris Lattner | 39a1c04 | 2007-05-30 06:11:23 +0000 | [diff] [blame] | 1173 | // If we require cleanup, return 1, otherwise return 3. |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1174 | return Info.needsCleanup ? 1 : 3; |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 1175 | } |
| 1176 | |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1177 | /// CleanupGEP - GEP is used by an Alloca, which can be prompted after the GEP |
| 1178 | /// is canonicalized here. |
| 1179 | void SROA::CleanupGEP(GetElementPtrInst *GEPI) { |
| 1180 | gep_type_iterator I = gep_type_begin(GEPI); |
| 1181 | ++I; |
| 1182 | |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1183 | const ArrayType *AT = dyn_cast<ArrayType>(*I); |
| 1184 | if (!AT) |
| 1185 | return; |
| 1186 | |
| 1187 | uint64_t NumElements = AT->getNumElements(); |
| 1188 | |
| 1189 | if (isa<ConstantInt>(I.getOperand())) |
| 1190 | return; |
| 1191 | |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1192 | LLVMContext &Context = GEPI->getContext(); |
| 1193 | |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1194 | if (NumElements == 1) { |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1195 | GEPI->setOperand(2, Context.getNullValue(Type::Int32Ty)); |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1196 | return; |
| 1197 | } |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1198 | |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1199 | assert(NumElements == 2 && "Unhandled case!"); |
| 1200 | // All users of the GEP must be loads. At each use of the GEP, insert |
| 1201 | // two loads of the appropriate indexed GEP and select between them. |
Owen Anderson | 333c400 | 2009-07-09 23:48:35 +0000 | [diff] [blame] | 1202 | Value *IsOne = new ICmpInst(GEPI, ICmpInst::ICMP_NE, I.getOperand(), |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1203 | Context.getNullValue(I.getOperand()->getType()), |
Owen Anderson | 333c400 | 2009-07-09 23:48:35 +0000 | [diff] [blame] | 1204 | "isone"); |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1205 | // Insert the new GEP instructions, which are properly indexed. |
| 1206 | SmallVector<Value*, 8> Indices(GEPI->op_begin()+1, GEPI->op_end()); |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1207 | Indices[1] = Context.getNullValue(Type::Int32Ty); |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1208 | Value *ZeroIdx = GetElementPtrInst::Create(GEPI->getOperand(0), |
| 1209 | Indices.begin(), |
| 1210 | Indices.end(), |
| 1211 | GEPI->getName()+".0", GEPI); |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1212 | Indices[1] = ConstantInt::get(Type::Int32Ty, 1); |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1213 | Value *OneIdx = GetElementPtrInst::Create(GEPI->getOperand(0), |
| 1214 | Indices.begin(), |
| 1215 | Indices.end(), |
| 1216 | GEPI->getName()+".1", GEPI); |
| 1217 | // Replace all loads of the variable index GEP with loads from both |
| 1218 | // indexes and a select. |
| 1219 | while (!GEPI->use_empty()) { |
| 1220 | LoadInst *LI = cast<LoadInst>(GEPI->use_back()); |
| 1221 | Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI); |
| 1222 | Value *One = new LoadInst(OneIdx , LI->getName()+".1", LI); |
| 1223 | Value *R = SelectInst::Create(IsOne, One, Zero, LI->getName(), LI); |
| 1224 | LI->replaceAllUsesWith(R); |
| 1225 | LI->eraseFromParent(); |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1226 | } |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1227 | GEPI->eraseFromParent(); |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1228 | } |
| 1229 | |
Devang Patel | 7afe8fa | 2009-02-10 19:28:07 +0000 | [diff] [blame] | 1230 | |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1231 | /// CleanupAllocaUsers - If SROA reported that it can promote the specified |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 1232 | /// allocation, but only if cleaned up, perform the cleanups required. |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1233 | void SROA::CleanupAllocaUsers(AllocationInst *AI) { |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 1234 | // At this point, we know that the end result will be SROA'd and promoted, so |
| 1235 | // we can insert ugly code if required so long as sroa+mem2reg will clean it |
| 1236 | // up. |
| 1237 | for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); |
| 1238 | UI != E; ) { |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1239 | User *U = *UI++; |
| 1240 | if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) |
| 1241 | CleanupGEP(GEPI); |
Jay Foad | 0906b1b | 2009-06-06 17:49:35 +0000 | [diff] [blame] | 1242 | else { |
| 1243 | Instruction *I = cast<Instruction>(U); |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1244 | SmallVector<DbgInfoIntrinsic *, 2> DbgInUses; |
Zhou Sheng | b0c4199 | 2009-03-18 12:48:48 +0000 | [diff] [blame] | 1245 | if (!isa<StoreInst>(I) && OnlyUsedByDbgInfoIntrinsics(I, &DbgInUses)) { |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1246 | // Safe to remove debug info uses. |
| 1247 | while (!DbgInUses.empty()) { |
| 1248 | DbgInfoIntrinsic *DI = DbgInUses.back(); DbgInUses.pop_back(); |
| 1249 | DI->eraseFromParent(); |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 1250 | } |
Devang Patel | 4afc90d | 2009-02-10 07:00:59 +0000 | [diff] [blame] | 1251 | I->eraseFromParent(); |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 1252 | } |
| 1253 | } |
| 1254 | } |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 1255 | } |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1256 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1257 | /// MergeInType - Add the 'In' type to the accumulated type (Accum) so far at |
| 1258 | /// the offset specified by Offset (which is specified in bytes). |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 1259 | /// |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1260 | /// There are two cases we handle here: |
| 1261 | /// 1) A union of vector types of the same size and potentially its elements. |
Chris Lattner | d22dbdf | 2006-12-15 07:32:38 +0000 | [diff] [blame] | 1262 | /// Here we turn element accesses into insert/extract element operations. |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1263 | /// This promotes a <4 x float> with a store of float to the third element |
| 1264 | /// into a <4 x float> that uses insert element. |
| 1265 | /// 2) A fully general blob of memory, which we turn into some (potentially |
| 1266 | /// large) integer type with extract and insert operations where the loads |
| 1267 | /// and stores would mutate the memory. |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1268 | static void MergeInType(const Type *In, uint64_t Offset, const Type *&VecTy, |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1269 | unsigned AllocaSize, const TargetData &TD, |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1270 | LLVMContext &Context) { |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1271 | // If this could be contributing to a vector, analyze it. |
| 1272 | if (VecTy != Type::VoidTy) { // either null or a vector type. |
Chris Lattner | 996d7a9 | 2009-02-02 18:02:59 +0000 | [diff] [blame] | 1273 | |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1274 | // If the In type is a vector that is the same size as the alloca, see if it |
| 1275 | // matches the existing VecTy. |
| 1276 | if (const VectorType *VInTy = dyn_cast<VectorType>(In)) { |
| 1277 | if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) { |
| 1278 | // If we're storing/loading a vector of the right size, allow it as a |
| 1279 | // vector. If this the first vector we see, remember the type so that |
| 1280 | // we know the element size. |
| 1281 | if (VecTy == 0) |
| 1282 | VecTy = VInTy; |
| 1283 | return; |
| 1284 | } |
| 1285 | } else if (In == Type::FloatTy || In == Type::DoubleTy || |
| 1286 | (isa<IntegerType>(In) && In->getPrimitiveSizeInBits() >= 8 && |
| 1287 | isPowerOf2_32(In->getPrimitiveSizeInBits()))) { |
| 1288 | // If we're accessing something that could be an element of a vector, see |
| 1289 | // if the implied vector agrees with what we already have and if Offset is |
| 1290 | // compatible with it. |
| 1291 | unsigned EltSize = In->getPrimitiveSizeInBits()/8; |
| 1292 | if (Offset % EltSize == 0 && |
| 1293 | AllocaSize % EltSize == 0 && |
| 1294 | (VecTy == 0 || |
| 1295 | cast<VectorType>(VecTy)->getElementType() |
| 1296 | ->getPrimitiveSizeInBits()/8 == EltSize)) { |
| 1297 | if (VecTy == 0) |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 1298 | VecTy = VectorType::get(In, AllocaSize/EltSize); |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1299 | return; |
| 1300 | } |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1301 | } |
| 1302 | } |
| 1303 | |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1304 | // Otherwise, we have a case that we can't handle with an optimized vector |
| 1305 | // form. We can still turn this into a large integer. |
| 1306 | VecTy = Type::VoidTy; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1307 | } |
| 1308 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1309 | /// CanConvertToScalar - V is a pointer. If we can convert the pointee and all |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1310 | /// its accesses to use a to single vector type, return true, and set VecTy to |
| 1311 | /// the new type. If we could convert the alloca into a single promotable |
| 1312 | /// integer, return true but set VecTy to VoidTy. Further, if the use is not a |
| 1313 | /// completely trivial use that mem2reg could promote, set IsNotTrivial. Offset |
| 1314 | /// is the current offset from the base of the alloca being analyzed. |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1315 | /// |
Chris Lattner | 1a3257b | 2009-02-03 18:15:05 +0000 | [diff] [blame] | 1316 | /// If we see at least one access to the value that is as a vector type, set the |
| 1317 | /// SawVec flag. |
| 1318 | /// |
| 1319 | bool SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy, |
| 1320 | bool &SawVec, uint64_t Offset, |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1321 | unsigned AllocaSize) { |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1322 | for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { |
| 1323 | Instruction *User = cast<Instruction>(*UI); |
| 1324 | |
| 1325 | if (LoadInst *LI = dyn_cast<LoadInst>(User)) { |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1326 | // Don't break volatile loads. |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 1327 | if (LI->isVolatile()) |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1328 | return false; |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1329 | MergeInType(LI->getType(), Offset, VecTy, |
| 1330 | AllocaSize, *TD, V->getContext()); |
Chris Lattner | 1a3257b | 2009-02-03 18:15:05 +0000 | [diff] [blame] | 1331 | SawVec |= isa<VectorType>(LI->getType()); |
Chris Lattner | cf32186 | 2009-01-07 06:39:58 +0000 | [diff] [blame] | 1332 | continue; |
| 1333 | } |
| 1334 | |
| 1335 | if (StoreInst *SI = dyn_cast<StoreInst>(User)) { |
Reid Spencer | 24d6da5 | 2007-01-21 00:29:26 +0000 | [diff] [blame] | 1336 | // Storing the pointer, not into the value? |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 1337 | if (SI->getOperand(0) == V || SI->isVolatile()) return 0; |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1338 | MergeInType(SI->getOperand(0)->getType(), Offset, |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1339 | VecTy, AllocaSize, *TD, V->getContext()); |
Chris Lattner | 1a3257b | 2009-02-03 18:15:05 +0000 | [diff] [blame] | 1340 | SawVec |= isa<VectorType>(SI->getOperand(0)->getType()); |
Chris Lattner | cf32186 | 2009-01-07 06:39:58 +0000 | [diff] [blame] | 1341 | continue; |
| 1342 | } |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1343 | |
| 1344 | if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { |
Chris Lattner | 1a3257b | 2009-02-03 18:15:05 +0000 | [diff] [blame] | 1345 | if (!CanConvertToScalar(BCI, IsNotTrivial, VecTy, SawVec, Offset, |
| 1346 | AllocaSize)) |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1347 | return false; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1348 | IsNotTrivial = true; |
Chris Lattner | cf32186 | 2009-01-07 06:39:58 +0000 | [diff] [blame] | 1349 | continue; |
| 1350 | } |
| 1351 | |
| 1352 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1353 | // If this is a GEP with a variable indices, we can't handle it. |
| 1354 | if (!GEP->hasAllConstantIndices()) |
| 1355 | return false; |
Chris Lattner | cf32186 | 2009-01-07 06:39:58 +0000 | [diff] [blame] | 1356 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1357 | // Compute the offset that this GEP adds to the pointer. |
| 1358 | SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); |
| 1359 | uint64_t GEPOffset = TD->getIndexedOffset(GEP->getOperand(0)->getType(), |
| 1360 | &Indices[0], Indices.size()); |
| 1361 | // See if all uses can be converted. |
Chris Lattner | 1a3257b | 2009-02-03 18:15:05 +0000 | [diff] [blame] | 1362 | if (!CanConvertToScalar(GEP, IsNotTrivial, VecTy, SawVec,Offset+GEPOffset, |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1363 | AllocaSize)) |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1364 | return false; |
| 1365 | IsNotTrivial = true; |
| 1366 | continue; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1367 | } |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 1368 | |
Chris Lattner | 3d730f7 | 2009-02-03 02:01:43 +0000 | [diff] [blame] | 1369 | // If this is a constant sized memset of a constant value (e.g. 0) we can |
| 1370 | // handle it. |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 1371 | if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { |
| 1372 | // Store of constant value and constant size. |
| 1373 | if (isa<ConstantInt>(MSI->getValue()) && |
| 1374 | isa<ConstantInt>(MSI->getLength())) { |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 1375 | IsNotTrivial = true; |
| 1376 | continue; |
| 1377 | } |
Chris Lattner | 3d730f7 | 2009-02-03 02:01:43 +0000 | [diff] [blame] | 1378 | } |
Chris Lattner | c570487 | 2009-03-08 04:04:21 +0000 | [diff] [blame] | 1379 | |
| 1380 | // If this is a memcpy or memmove into or out of the whole allocation, we |
| 1381 | // can handle it like a load or store of the scalar type. |
| 1382 | if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { |
| 1383 | if (ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength())) |
| 1384 | if (Len->getZExtValue() == AllocaSize && Offset == 0) { |
| 1385 | IsNotTrivial = true; |
| 1386 | continue; |
| 1387 | } |
| 1388 | } |
Chris Lattner | dfe964c | 2009-03-08 03:59:00 +0000 | [diff] [blame] | 1389 | |
Devang Patel | 00e389c | 2009-03-06 07:03:54 +0000 | [diff] [blame] | 1390 | // Ignore dbg intrinsic. |
| 1391 | if (isa<DbgInfoIntrinsic>(User)) |
| 1392 | continue; |
| 1393 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1394 | // Otherwise, we cannot handle this! |
| 1395 | return false; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1396 | } |
| 1397 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1398 | return true; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1399 | } |
| 1400 | |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1401 | |
| 1402 | /// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 1403 | /// directly. This happens when we are converting an "integer union" to a |
| 1404 | /// single integer scalar, or when we are converting a "vector union" to a |
| 1405 | /// vector with insert/extractelement instructions. |
| 1406 | /// |
| 1407 | /// Offset is an offset from the original alloca, in bits that need to be |
| 1408 | /// shifted to the right. By the end of this, there should be no uses of Ptr. |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1409 | void SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset) { |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1410 | while (!Ptr->use_empty()) { |
| 1411 | Instruction *User = cast<Instruction>(Ptr->use_back()); |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1412 | |
Chris Lattner | cf32186 | 2009-01-07 06:39:58 +0000 | [diff] [blame] | 1413 | if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) { |
Chris Lattner | b10e0da | 2008-01-30 00:39:15 +0000 | [diff] [blame] | 1414 | ConvertUsesToScalar(CI, NewAI, Offset); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1415 | CI->eraseFromParent(); |
Chris Lattner | cf32186 | 2009-01-07 06:39:58 +0000 | [diff] [blame] | 1416 | continue; |
| 1417 | } |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1418 | |
Chris Lattner | cf32186 | 2009-01-07 06:39:58 +0000 | [diff] [blame] | 1419 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1420 | // Compute the offset that this GEP adds to the pointer. |
| 1421 | SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); |
| 1422 | uint64_t GEPOffset = TD->getIndexedOffset(GEP->getOperand(0)->getType(), |
| 1423 | &Indices[0], Indices.size()); |
| 1424 | ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1425 | GEP->eraseFromParent(); |
Chris Lattner | cf32186 | 2009-01-07 06:39:58 +0000 | [diff] [blame] | 1426 | continue; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1427 | } |
Chris Lattner | 3d730f7 | 2009-02-03 02:01:43 +0000 | [diff] [blame] | 1428 | |
Chris Lattner | 9bc67da | 2009-02-03 19:45:44 +0000 | [diff] [blame] | 1429 | IRBuilder<> Builder(User->getParent(), User); |
| 1430 | |
| 1431 | if (LoadInst *LI = dyn_cast<LoadInst>(User)) { |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1432 | // The load is a bit extract from NewAI shifted right by Offset bits. |
| 1433 | Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp"); |
| 1434 | Value *NewLoadVal |
| 1435 | = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder); |
| 1436 | LI->replaceAllUsesWith(NewLoadVal); |
Chris Lattner | 9bc67da | 2009-02-03 19:45:44 +0000 | [diff] [blame] | 1437 | LI->eraseFromParent(); |
| 1438 | continue; |
| 1439 | } |
| 1440 | |
| 1441 | if (StoreInst *SI = dyn_cast<StoreInst>(User)) { |
| 1442 | assert(SI->getOperand(0) != Ptr && "Consistency error!"); |
Daniel Dunbar | 6e0d1cb | 2009-07-25 04:41:11 +0000 | [diff] [blame] | 1443 | // FIXME: Remove once builder has Twine API. |
| 1444 | Value *Old = Builder.CreateLoad(NewAI, (NewAI->getName()+".in").str().c_str()); |
Chris Lattner | 9bc67da | 2009-02-03 19:45:44 +0000 | [diff] [blame] | 1445 | Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset, |
| 1446 | Builder); |
| 1447 | Builder.CreateStore(New, NewAI); |
| 1448 | SI->eraseFromParent(); |
| 1449 | continue; |
| 1450 | } |
| 1451 | |
Chris Lattner | 3d730f7 | 2009-02-03 02:01:43 +0000 | [diff] [blame] | 1452 | // If this is a constant sized memset of a constant value (e.g. 0) we can |
| 1453 | // transform it into a store of the expanded constant value. |
| 1454 | if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { |
| 1455 | assert(MSI->getRawDest() == Ptr && "Consistency error!"); |
| 1456 | unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); |
Chris Lattner | 33e24ad | 2009-04-21 16:52:12 +0000 | [diff] [blame] | 1457 | if (NumBytes != 0) { |
| 1458 | unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue(); |
| 1459 | |
| 1460 | // Compute the value replicated the right number of times. |
| 1461 | APInt APVal(NumBytes*8, Val); |
Chris Lattner | 3d730f7 | 2009-02-03 02:01:43 +0000 | [diff] [blame] | 1462 | |
Chris Lattner | 33e24ad | 2009-04-21 16:52:12 +0000 | [diff] [blame] | 1463 | // Splat the value if non-zero. |
| 1464 | if (Val) |
| 1465 | for (unsigned i = 1; i != NumBytes; ++i) |
| 1466 | APVal |= APVal << 8; |
| 1467 | |
Daniel Dunbar | 6e0d1cb | 2009-07-25 04:41:11 +0000 | [diff] [blame] | 1468 | // FIXME: Remove once builder has Twine API. |
| 1469 | Value *Old = Builder.CreateLoad(NewAI, (NewAI->getName()+".in").str().c_str()); |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1470 | Value *New = ConvertScalar_InsertValue( |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1471 | ConstantInt::get(User->getContext(), APVal), |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1472 | Old, Offset, Builder); |
Chris Lattner | 33e24ad | 2009-04-21 16:52:12 +0000 | [diff] [blame] | 1473 | Builder.CreateStore(New, NewAI); |
| 1474 | } |
Chris Lattner | 3d730f7 | 2009-02-03 02:01:43 +0000 | [diff] [blame] | 1475 | MSI->eraseFromParent(); |
| 1476 | continue; |
| 1477 | } |
Chris Lattner | c570487 | 2009-03-08 04:04:21 +0000 | [diff] [blame] | 1478 | |
| 1479 | // If this is a memcpy or memmove into or out of the whole allocation, we |
| 1480 | // can handle it like a load or store of the scalar type. |
| 1481 | if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { |
| 1482 | assert(Offset == 0 && "must be store to start of alloca"); |
| 1483 | |
| 1484 | // If the source and destination are both to the same alloca, then this is |
| 1485 | // a noop copy-to-self, just delete it. Otherwise, emit a load and store |
| 1486 | // as appropriate. |
| 1487 | AllocaInst *OrigAI = cast<AllocaInst>(Ptr->getUnderlyingObject()); |
| 1488 | |
| 1489 | if (MTI->getSource()->getUnderlyingObject() != OrigAI) { |
| 1490 | // Dest must be OrigAI, change this to be a load from the original |
| 1491 | // pointer (bitcasted), then a store to our new alloca. |
| 1492 | assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?"); |
| 1493 | Value *SrcPtr = MTI->getSource(); |
| 1494 | SrcPtr = Builder.CreateBitCast(SrcPtr, NewAI->getType()); |
| 1495 | |
| 1496 | LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval"); |
| 1497 | SrcVal->setAlignment(MTI->getAlignment()); |
| 1498 | Builder.CreateStore(SrcVal, NewAI); |
| 1499 | } else if (MTI->getDest()->getUnderlyingObject() != OrigAI) { |
| 1500 | // Src must be OrigAI, change this to be a load from NewAI then a store |
| 1501 | // through the original dest pointer (bitcasted). |
| 1502 | assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?"); |
| 1503 | LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval"); |
| 1504 | |
| 1505 | Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), NewAI->getType()); |
| 1506 | StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr); |
| 1507 | NewStore->setAlignment(MTI->getAlignment()); |
| 1508 | } else { |
| 1509 | // Noop transfer. Src == Dst |
| 1510 | } |
| 1511 | |
| 1512 | |
| 1513 | MTI->eraseFromParent(); |
| 1514 | continue; |
| 1515 | } |
Chris Lattner | dfe964c | 2009-03-08 03:59:00 +0000 | [diff] [blame] | 1516 | |
Devang Patel | 00e389c | 2009-03-06 07:03:54 +0000 | [diff] [blame] | 1517 | // If user is a dbg info intrinsic then it is safe to remove it. |
| 1518 | if (isa<DbgInfoIntrinsic>(User)) { |
| 1519 | User->eraseFromParent(); |
| 1520 | continue; |
| 1521 | } |
| 1522 | |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 1523 | llvm_unreachable("Unsupported operation!"); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 1524 | } |
| 1525 | } |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 1526 | |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1527 | /// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer |
| 1528 | /// or vector value FromVal, extracting the bits from the offset specified by |
| 1529 | /// Offset. This returns the value, which is of type ToType. |
| 1530 | /// |
| 1531 | /// This happens when we are converting an "integer union" to a single |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1532 | /// integer scalar, or when we are converting a "vector union" to a vector with |
| 1533 | /// insert/extractelement instructions. |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1534 | /// |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1535 | /// Offset is an offset from the original alloca, in bits that need to be |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1536 | /// shifted to the right. |
| 1537 | Value *SROA::ConvertScalar_ExtractValue(Value *FromVal, const Type *ToType, |
| 1538 | uint64_t Offset, IRBuilder<> &Builder) { |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1539 | // If the load is of the whole new alloca, no conversion is needed. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1540 | if (FromVal->getType() == ToType && Offset == 0) |
| 1541 | return FromVal; |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1542 | |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1543 | LLVMContext &Context = FromVal->getContext(); |
| 1544 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1545 | // If the result alloca is a vector type, this is either an element |
| 1546 | // access or a bitcast to another vector type of the same size. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1547 | if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) { |
| 1548 | if (isa<VectorType>(ToType)) |
| 1549 | return Builder.CreateBitCast(FromVal, ToType, "tmp"); |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1550 | |
| 1551 | // Otherwise it must be an element access. |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1552 | unsigned Elt = 0; |
| 1553 | if (Offset) { |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 1554 | unsigned EltSize = TD->getTypeAllocSizeInBits(VTy->getElementType()); |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1555 | Elt = Offset/EltSize; |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1556 | assert(EltSize*Elt == Offset && "Invalid modulus in validity checking"); |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1557 | } |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1558 | // Return the element extracted out of it. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1559 | Value *V = Builder.CreateExtractElement(FromVal, |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1560 | ConstantInt::get(Type::Int32Ty,Elt), |
Chris Lattner | 9bc67da | 2009-02-03 19:45:44 +0000 | [diff] [blame] | 1561 | "tmp"); |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1562 | if (V->getType() != ToType) |
| 1563 | V = Builder.CreateBitCast(V, ToType, "tmp"); |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1564 | return V; |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1565 | } |
Chris Lattner | 1aa7056 | 2009-02-03 21:08:45 +0000 | [diff] [blame] | 1566 | |
| 1567 | // If ToType is a first class aggregate, extract out each of the pieces and |
| 1568 | // use insertvalue's to form the FCA. |
| 1569 | if (const StructType *ST = dyn_cast<StructType>(ToType)) { |
| 1570 | const StructLayout &Layout = *TD->getStructLayout(ST); |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1571 | Value *Res = Context.getUndef(ST); |
Chris Lattner | 1aa7056 | 2009-02-03 21:08:45 +0000 | [diff] [blame] | 1572 | for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { |
| 1573 | Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i), |
Chris Lattner | e991ced | 2009-02-06 04:34:07 +0000 | [diff] [blame] | 1574 | Offset+Layout.getElementOffsetInBits(i), |
Chris Lattner | 1aa7056 | 2009-02-03 21:08:45 +0000 | [diff] [blame] | 1575 | Builder); |
| 1576 | Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); |
| 1577 | } |
| 1578 | return Res; |
| 1579 | } |
| 1580 | |
| 1581 | if (const ArrayType *AT = dyn_cast<ArrayType>(ToType)) { |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 1582 | uint64_t EltSize = TD->getTypeAllocSizeInBits(AT->getElementType()); |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1583 | Value *Res = Context.getUndef(AT); |
Chris Lattner | 1aa7056 | 2009-02-03 21:08:45 +0000 | [diff] [blame] | 1584 | for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { |
| 1585 | Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(), |
| 1586 | Offset+i*EltSize, Builder); |
| 1587 | Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); |
| 1588 | } |
| 1589 | return Res; |
| 1590 | } |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1591 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1592 | // Otherwise, this must be a union that was converted to an integer value. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1593 | const IntegerType *NTy = cast<IntegerType>(FromVal->getType()); |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1594 | |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1595 | // If this is a big-endian system and the load is narrower than the |
| 1596 | // full alloca type, we need to do a shift to get the right bits. |
| 1597 | int ShAmt = 0; |
Chris Lattner | 56c3852 | 2009-01-07 06:34:28 +0000 | [diff] [blame] | 1598 | if (TD->isBigEndian()) { |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1599 | // On big-endian machines, the lowest bit is stored at the bit offset |
| 1600 | // from the pointer given by getTypeStoreSizeInBits. This matters for |
| 1601 | // integers with a bitwidth that is not a multiple of 8. |
Chris Lattner | 56c3852 | 2009-01-07 06:34:28 +0000 | [diff] [blame] | 1602 | ShAmt = TD->getTypeStoreSizeInBits(NTy) - |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1603 | TD->getTypeStoreSizeInBits(ToType) - Offset; |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1604 | } else { |
| 1605 | ShAmt = Offset; |
| 1606 | } |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1607 | |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1608 | // Note: we support negative bitwidths (with shl) which are not defined. |
| 1609 | // We do this to support (f.e.) loads off the end of a structure where |
| 1610 | // only some bits are used. |
| 1611 | if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth()) |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1612 | FromVal = Builder.CreateLShr(FromVal, |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1613 | ConstantInt::get(FromVal->getType(), |
Chris Lattner | 1aa7056 | 2009-02-03 21:08:45 +0000 | [diff] [blame] | 1614 | ShAmt), "tmp"); |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1615 | else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth()) |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1616 | FromVal = Builder.CreateShl(FromVal, |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1617 | ConstantInt::get(FromVal->getType(), |
Chris Lattner | 1aa7056 | 2009-02-03 21:08:45 +0000 | [diff] [blame] | 1618 | -ShAmt), "tmp"); |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1619 | |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1620 | // Finally, unconditionally truncate the integer to the right width. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1621 | unsigned LIBitWidth = TD->getTypeSizeInBits(ToType); |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1622 | if (LIBitWidth < NTy->getBitWidth()) |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1623 | FromVal = |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 1624 | Builder.CreateTrunc(FromVal, IntegerType::get(LIBitWidth), "tmp"); |
Chris Lattner | 55a683d | 2009-02-03 07:08:57 +0000 | [diff] [blame] | 1625 | else if (LIBitWidth > NTy->getBitWidth()) |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1626 | FromVal = |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 1627 | Builder.CreateZExt(FromVal, IntegerType::get(LIBitWidth), "tmp"); |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1628 | |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1629 | // If the result is an integer, this is a trunc or bitcast. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1630 | if (isa<IntegerType>(ToType)) { |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1631 | // Should be done. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1632 | } else if (ToType->isFloatingPoint() || isa<VectorType>(ToType)) { |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1633 | // Just do a bitcast, we know the sizes match up. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1634 | FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp"); |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1635 | } else { |
Chris Lattner | 9d34c4d | 2008-02-29 07:12:06 +0000 | [diff] [blame] | 1636 | // Otherwise must be a pointer. |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1637 | FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp"); |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1638 | } |
Chris Lattner | 6e01115 | 2009-02-03 21:01:03 +0000 | [diff] [blame] | 1639 | assert(FromVal->getType() == ToType && "Didn't convert right?"); |
| 1640 | return FromVal; |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1641 | } |
| 1642 | |
| 1643 | |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1644 | /// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer |
| 1645 | /// or vector value "Old" at the offset specified by Offset. |
| 1646 | /// |
| 1647 | /// This happens when we are converting an "integer union" to a |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1648 | /// single integer scalar, or when we are converting a "vector union" to a |
| 1649 | /// vector with insert/extractelement instructions. |
| 1650 | /// |
| 1651 | /// Offset is an offset from the original alloca, in bits that need to be |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1652 | /// shifted to the right. |
| 1653 | Value *SROA::ConvertScalar_InsertValue(Value *SV, Value *Old, |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 1654 | uint64_t Offset, IRBuilder<> &Builder) { |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1655 | |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1656 | // Convert the stored type to the actual type, shift it left to insert |
| 1657 | // then 'or' into place. |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1658 | const Type *AllocaType = Old->getType(); |
Owen Anderson | e922c02 | 2009-07-22 00:24:57 +0000 | [diff] [blame] | 1659 | LLVMContext &Context = Old->getContext(); |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1660 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1661 | if (const VectorType *VTy = dyn_cast<VectorType>(AllocaType)) { |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 1662 | uint64_t VecSize = TD->getTypeAllocSizeInBits(VTy); |
| 1663 | uint64_t ValSize = TD->getTypeAllocSizeInBits(SV->getType()); |
Chris Lattner | 29e6417 | 2009-03-08 04:17:04 +0000 | [diff] [blame] | 1664 | |
| 1665 | // Changing the whole vector with memset or with an access of a different |
| 1666 | // vector type? |
| 1667 | if (ValSize == VecSize) |
| 1668 | return Builder.CreateBitCast(SV, AllocaType, "tmp"); |
| 1669 | |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 1670 | uint64_t EltSize = TD->getTypeAllocSizeInBits(VTy->getElementType()); |
Chris Lattner | 29e6417 | 2009-03-08 04:17:04 +0000 | [diff] [blame] | 1671 | |
| 1672 | // Must be an element insertion. |
| 1673 | unsigned Elt = Offset/EltSize; |
| 1674 | |
| 1675 | if (SV->getType() != VTy->getElementType()) |
| 1676 | SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp"); |
| 1677 | |
| 1678 | SV = Builder.CreateInsertElement(Old, SV, |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1679 | ConstantInt::get(Type::Int32Ty, Elt), |
Chris Lattner | 29e6417 | 2009-03-08 04:17:04 +0000 | [diff] [blame] | 1680 | "tmp"); |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1681 | return SV; |
| 1682 | } |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1683 | |
| 1684 | // If SV is a first-class aggregate value, insert each value recursively. |
| 1685 | if (const StructType *ST = dyn_cast<StructType>(SV->getType())) { |
| 1686 | const StructLayout &Layout = *TD->getStructLayout(ST); |
| 1687 | for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 1688 | Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1689 | Old = ConvertScalar_InsertValue(Elt, Old, |
Chris Lattner | e991ced | 2009-02-06 04:34:07 +0000 | [diff] [blame] | 1690 | Offset+Layout.getElementOffsetInBits(i), |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 1691 | Builder); |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1692 | } |
| 1693 | return Old; |
| 1694 | } |
| 1695 | |
| 1696 | if (const ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) { |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 1697 | uint64_t EltSize = TD->getTypeAllocSizeInBits(AT->getElementType()); |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1698 | for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 1699 | Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); |
| 1700 | Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder); |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1701 | } |
| 1702 | return Old; |
| 1703 | } |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1704 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1705 | // If SV is a float, convert it to the appropriate integer type. |
Chris Lattner | 9b872db | 2009-02-03 19:30:11 +0000 | [diff] [blame] | 1706 | // If it is a pointer, do the same. |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1707 | unsigned SrcWidth = TD->getTypeSizeInBits(SV->getType()); |
| 1708 | unsigned DestWidth = TD->getTypeSizeInBits(AllocaType); |
| 1709 | unsigned SrcStoreWidth = TD->getTypeStoreSizeInBits(SV->getType()); |
| 1710 | unsigned DestStoreWidth = TD->getTypeStoreSizeInBits(AllocaType); |
| 1711 | if (SV->getType()->isFloatingPoint() || isa<VectorType>(SV->getType())) |
Owen Anderson | debcb01 | 2009-07-29 22:17:13 +0000 | [diff] [blame] | 1712 | SV = Builder.CreateBitCast(SV, IntegerType::get(SrcWidth), "tmp"); |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1713 | else if (isa<PointerType>(SV->getType())) |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 1714 | SV = Builder.CreatePtrToInt(SV, TD->getIntPtrType(), "tmp"); |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1715 | |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1716 | // Zero extend or truncate the value if needed. |
| 1717 | if (SV->getType() != AllocaType) { |
| 1718 | if (SV->getType()->getPrimitiveSizeInBits() < |
| 1719 | AllocaType->getPrimitiveSizeInBits()) |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 1720 | SV = Builder.CreateZExt(SV, AllocaType, "tmp"); |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1721 | else { |
| 1722 | // Truncation may be needed if storing more than the alloca can hold |
| 1723 | // (undefined behavior). |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 1724 | SV = Builder.CreateTrunc(SV, AllocaType, "tmp"); |
Chris Lattner | 7809ecd | 2009-02-03 01:30:09 +0000 | [diff] [blame] | 1725 | SrcWidth = DestWidth; |
| 1726 | SrcStoreWidth = DestStoreWidth; |
| 1727 | } |
| 1728 | } |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1729 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1730 | // If this is a big-endian system and the store is narrower than the |
| 1731 | // full alloca type, we need to do a shift to get the right bits. |
| 1732 | int ShAmt = 0; |
| 1733 | if (TD->isBigEndian()) { |
| 1734 | // On big-endian machines, the lowest bit is stored at the bit offset |
| 1735 | // from the pointer given by getTypeStoreSizeInBits. This matters for |
| 1736 | // integers with a bitwidth that is not a multiple of 8. |
| 1737 | ShAmt = DestStoreWidth - SrcStoreWidth - Offset; |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1738 | } else { |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1739 | ShAmt = Offset; |
| 1740 | } |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1741 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1742 | // Note: we support negative bitwidths (with shr) which are not defined. |
| 1743 | // We do this to support (f.e.) stores off the end of a structure where |
| 1744 | // only some bits in the structure are set. |
| 1745 | APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth)); |
| 1746 | if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) { |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1747 | SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(), |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1748 | ShAmt), "tmp"); |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1749 | Mask <<= ShAmt; |
| 1750 | } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) { |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1751 | SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(), |
Owen Anderson | fa5cbd6 | 2009-07-03 19:42:02 +0000 | [diff] [blame] | 1752 | -ShAmt), "tmp"); |
Duncan Sands | 0e7c46b | 2009-02-02 09:53:14 +0000 | [diff] [blame] | 1753 | Mask = Mask.lshr(-ShAmt); |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1754 | } |
Duncan Sands | 4b3dfbd | 2009-02-02 10:06:20 +0000 | [diff] [blame] | 1755 | |
Chris Lattner | 2e0d5f8 | 2009-01-31 02:28:54 +0000 | [diff] [blame] | 1756 | // Mask out the bits we are about to insert from the old value, and or |
| 1757 | // in the new bits. |
| 1758 | if (SrcWidth != DestWidth) { |
| 1759 | assert(DestWidth > SrcWidth); |
Owen Anderson | eed707b | 2009-07-24 23:12:02 +0000 | [diff] [blame] | 1760 | Old = Builder.CreateAnd(Old, ConstantInt::get(Context, ~Mask), "mask"); |
Chris Lattner | 65a6502 | 2009-02-03 19:41:50 +0000 | [diff] [blame] | 1761 | SV = Builder.CreateOr(Old, SV, "ins"); |
Chris Lattner | 800de31 | 2008-02-29 07:03:13 +0000 | [diff] [blame] | 1762 | } |
| 1763 | return SV; |
| 1764 | } |
| 1765 | |
| 1766 | |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 1767 | |
| 1768 | /// PointsToConstantGlobal - Return true if V (possibly indirectly) points to |
| 1769 | /// some part of a constant global variable. This intentionally only accepts |
| 1770 | /// constant expressions because we don't can't rewrite arbitrary instructions. |
| 1771 | static bool PointsToConstantGlobal(Value *V) { |
| 1772 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) |
| 1773 | return GV->isConstant(); |
| 1774 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) |
| 1775 | if (CE->getOpcode() == Instruction::BitCast || |
| 1776 | CE->getOpcode() == Instruction::GetElementPtr) |
| 1777 | return PointsToConstantGlobal(CE->getOperand(0)); |
| 1778 | return false; |
| 1779 | } |
| 1780 | |
| 1781 | /// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) |
| 1782 | /// pointer to an alloca. Ignore any reads of the pointer, return false if we |
| 1783 | /// see any stores or other unknown uses. If we see pointer arithmetic, keep |
| 1784 | /// track of whether it moves the pointer (with isOffset) but otherwise traverse |
| 1785 | /// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to |
| 1786 | /// the alloca, and if the source pointer is a pointer to a constant global, we |
| 1787 | /// can optimize this. |
| 1788 | static bool isOnlyCopiedFromConstantGlobal(Value *V, Instruction *&TheCopy, |
| 1789 | bool isOffset) { |
| 1790 | for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { |
Chris Lattner | 6e733d3 | 2009-01-28 20:16:43 +0000 | [diff] [blame] | 1791 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) |
| 1792 | // Ignore non-volatile loads, they are always ok. |
| 1793 | if (!LI->isVolatile()) |
| 1794 | continue; |
| 1795 | |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 1796 | if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) { |
| 1797 | // If uses of the bitcast are ok, we are ok. |
| 1798 | if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset)) |
| 1799 | return false; |
| 1800 | continue; |
| 1801 | } |
| 1802 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { |
| 1803 | // If the GEP has all zero indices, it doesn't offset the pointer. If it |
| 1804 | // doesn't, it does. |
| 1805 | if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy, |
| 1806 | isOffset || !GEP->hasAllZeroIndices())) |
| 1807 | return false; |
| 1808 | continue; |
| 1809 | } |
| 1810 | |
| 1811 | // If this is isn't our memcpy/memmove, reject it as something we can't |
| 1812 | // handle. |
Chris Lattner | 3ce5e88 | 2009-03-08 03:37:16 +0000 | [diff] [blame] | 1813 | if (!isa<MemTransferInst>(*UI)) |
Chris Lattner | 79b3bd3 | 2007-04-25 06:40:51 +0000 | [diff] [blame] | 1814 | return false; |
| 1815 | |
| 1816 | // If we already have seen a copy, reject the second one. |
| 1817 | if (TheCopy) return false; |
| 1818 | |
| 1819 | // If the pointer has been offset from the start of the alloca, we can't |
| 1820 | // safely handle this. |
| 1821 | if (isOffset) return false; |
| 1822 | |
| 1823 | // If the memintrinsic isn't using the alloca as the dest, reject it. |
| 1824 | if (UI.getOperandNo() != 1) return false; |
| 1825 | |
| 1826 | MemIntrinsic *MI = cast<MemIntrinsic>(*UI); |
| 1827 | |
| 1828 | // If the source of the memcpy/move is not a constant global, reject it. |
| 1829 | if (!PointsToConstantGlobal(MI->getOperand(2))) |
| 1830 | return false; |
| 1831 | |
| 1832 | // Otherwise, the transform is safe. Remember the copy instruction. |
| 1833 | TheCopy = MI; |
| 1834 | } |
| 1835 | return true; |
| 1836 | } |
| 1837 | |
| 1838 | /// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only |
| 1839 | /// modified by a copy from a constant global. If we can prove this, we can |
| 1840 | /// replace any uses of the alloca with uses of the global directly. |
| 1841 | Instruction *SROA::isOnlyCopiedFromConstantGlobal(AllocationInst *AI) { |
| 1842 | Instruction *TheCopy = 0; |
| 1843 | if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false)) |
| 1844 | return TheCopy; |
| 1845 | return 0; |
| 1846 | } |