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 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
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 | |
| 22 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 23 | #include "llvm/Constants.h" |
| 24 | #include "llvm/DerivedTypes.h" |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 25 | #include "llvm/Function.h" |
| 26 | #include "llvm/Pass.h" |
Misha Brukman | d8e1eea | 2004-07-29 17:05:13 +0000 | [diff] [blame] | 27 | #include "llvm/Instructions.h" |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 28 | #include "llvm/Analysis/Dominators.h" |
| 29 | #include "llvm/Target/TargetData.h" |
| 30 | #include "llvm/Transforms/Utils/PromoteMemToReg.h" |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 31 | #include "llvm/Support/Debug.h" |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 32 | #include "llvm/Support/GetElementPtrTypeIterator.h" |
| 33 | #include "llvm/Support/MathExtras.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 34 | #include "llvm/Support/Compiler.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 35 | #include "llvm/ADT/Statistic.h" |
| 36 | #include "llvm/ADT/StringExtras.h" |
Chris Lattner | d866473 | 2003-12-02 17:43:55 +0000 | [diff] [blame] | 37 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 38 | |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 39 | namespace { |
Misha Brukman | 3cfb6b1 | 2003-09-11 16:58:31 +0000 | [diff] [blame] | 40 | Statistic<> NumReplaced("scalarrepl", "Number of allocas broken up"); |
| 41 | Statistic<> NumPromoted("scalarrepl", "Number of allocas promoted"); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 42 | Statistic<> NumConverted("scalarrepl", |
| 43 | "Number of aggregates converted to scalar"); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 44 | |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 45 | struct VISIBILITY_HIDDEN SROA : public FunctionPass { |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 46 | bool runOnFunction(Function &F); |
| 47 | |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 48 | bool performScalarRepl(Function &F); |
| 49 | bool performPromotion(Function &F); |
| 50 | |
Chris Lattner | a15854c | 2003-08-31 00:45:13 +0000 | [diff] [blame] | 51 | // getAnalysisUsage - This pass does not require any passes, but we know it |
| 52 | // will not alter the CFG, so say so. |
| 53 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | 43f820d | 2003-10-05 21:20:13 +0000 | [diff] [blame] | 54 | AU.addRequired<DominatorTree>(); |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 55 | AU.addRequired<DominanceFrontier>(); |
| 56 | AU.addRequired<TargetData>(); |
Chris Lattner | a15854c | 2003-08-31 00:45:13 +0000 | [diff] [blame] | 57 | AU.setPreservesCFG(); |
| 58 | } |
| 59 | |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 60 | private: |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 61 | int isSafeElementUse(Value *Ptr); |
| 62 | int isSafeUseOfAllocation(Instruction *User); |
| 63 | int isSafeAllocaToScalarRepl(AllocationInst *AI); |
| 64 | void CanonicalizeAllocaUsers(AllocationInst *AI); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 65 | AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 66 | |
| 67 | const Type *CanConvertToScalar(Value *V, bool &IsNotTrivial); |
| 68 | void ConvertToScalar(AllocationInst *AI, const Type *Ty); |
| 69 | void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 70 | }; |
| 71 | |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 72 | RegisterPass<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 73 | } |
| 74 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 75 | // Public interface to the ScalarReplAggregates pass |
Chris Lattner | 4b50156 | 2004-09-20 04:43:15 +0000 | [diff] [blame] | 76 | FunctionPass *llvm::createScalarReplAggregatesPass() { return new SROA(); } |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 77 | |
| 78 | |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 79 | bool SROA::runOnFunction(Function &F) { |
Chris Lattner | fe7ea0d | 2003-09-12 15:36:03 +0000 | [diff] [blame] | 80 | bool Changed = performPromotion(F); |
| 81 | while (1) { |
| 82 | bool LocalChange = performScalarRepl(F); |
| 83 | if (!LocalChange) break; // No need to repromote if no scalarrepl |
| 84 | Changed = true; |
| 85 | LocalChange = performPromotion(F); |
| 86 | if (!LocalChange) break; // No need to re-scalarrepl if no promotion |
| 87 | } |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 88 | |
| 89 | return Changed; |
| 90 | } |
| 91 | |
| 92 | |
| 93 | bool SROA::performPromotion(Function &F) { |
| 94 | std::vector<AllocaInst*> Allocas; |
| 95 | const TargetData &TD = getAnalysis<TargetData>(); |
Chris Lattner | 43f820d | 2003-10-05 21:20:13 +0000 | [diff] [blame] | 96 | DominatorTree &DT = getAnalysis<DominatorTree>(); |
| 97 | DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 98 | |
Chris Lattner | 02a3be0 | 2003-09-20 14:39:18 +0000 | [diff] [blame] | 99 | BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 100 | |
Chris Lattner | fe7ea0d | 2003-09-12 15:36:03 +0000 | [diff] [blame] | 101 | bool Changed = false; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 102 | |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 103 | while (1) { |
| 104 | Allocas.clear(); |
| 105 | |
| 106 | // Find allocas that are safe to promote, by looking at all instructions in |
| 107 | // the entry node |
| 108 | for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) |
| 109 | if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? |
| 110 | if (isAllocaPromotable(AI, TD)) |
| 111 | Allocas.push_back(AI); |
| 112 | |
| 113 | if (Allocas.empty()) break; |
| 114 | |
Chris Lattner | 43f820d | 2003-10-05 21:20:13 +0000 | [diff] [blame] | 115 | PromoteMemToReg(Allocas, DT, DF, TD); |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 116 | NumPromoted += Allocas.size(); |
| 117 | Changed = true; |
| 118 | } |
| 119 | |
| 120 | return Changed; |
| 121 | } |
| 122 | |
Chris Lattner | 38aec32 | 2003-09-11 16:45:55 +0000 | [diff] [blame] | 123 | // performScalarRepl - This algorithm is a simple worklist driven algorithm, |
| 124 | // which runs on all of the malloc/alloca instructions in the function, removing |
| 125 | // them if they are only used by getelementptr instructions. |
| 126 | // |
| 127 | bool SROA::performScalarRepl(Function &F) { |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 128 | std::vector<AllocationInst*> WorkList; |
| 129 | |
| 130 | // 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] | 131 | BasicBlock &BB = F.getEntryBlock(); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 132 | for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) |
| 133 | if (AllocationInst *A = dyn_cast<AllocationInst>(I)) |
| 134 | WorkList.push_back(A); |
| 135 | |
| 136 | // Process the worklist |
| 137 | bool Changed = false; |
| 138 | while (!WorkList.empty()) { |
| 139 | AllocationInst *AI = WorkList.back(); |
| 140 | WorkList.pop_back(); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 141 | |
| 142 | // If we can turn this aggregate value (potentially with casts) into a |
| 143 | // simple scalar value that can be mem2reg'd into a register value. |
| 144 | bool IsNotTrivial = false; |
| 145 | if (const Type *ActualType = CanConvertToScalar(AI, IsNotTrivial)) |
Chris Lattner | df4f226 | 2006-04-20 20:48:50 +0000 | [diff] [blame] | 146 | if (IsNotTrivial && ActualType != Type::VoidTy) { |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 147 | ConvertToScalar(AI, ActualType); |
| 148 | Changed = true; |
| 149 | continue; |
| 150 | } |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 151 | |
| 152 | // We cannot transform the allocation instruction if it is an array |
Chris Lattner | d10376b | 2003-05-27 16:09:27 +0000 | [diff] [blame] | 153 | // allocation (allocations OF arrays are ok though), and an allocation of a |
| 154 | // scalar value cannot be decomposed at all. |
| 155 | // |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 156 | if (AI->isArrayAllocation() || |
Chris Lattner | d10376b | 2003-05-27 16:09:27 +0000 | [diff] [blame] | 157 | (!isa<StructType>(AI->getAllocatedType()) && |
| 158 | !isa<ArrayType>(AI->getAllocatedType()))) continue; |
| 159 | |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 160 | // Check that all of the users of the allocation are capable of being |
| 161 | // transformed. |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 162 | switch (isSafeAllocaToScalarRepl(AI)) { |
| 163 | default: assert(0 && "Unexpected value!"); |
| 164 | case 0: // Not safe to scalar replace. |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 165 | continue; |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 166 | case 1: // Safe, but requires cleanup/canonicalizations first |
| 167 | CanonicalizeAllocaUsers(AI); |
| 168 | case 3: // Safe to scalar replace. |
| 169 | break; |
| 170 | } |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 171 | |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 172 | DOUT << "Found inst to xform: " << *AI; |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 173 | Changed = true; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 174 | |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 175 | std::vector<AllocaInst*> ElementAllocas; |
| 176 | if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { |
| 177 | ElementAllocas.reserve(ST->getNumContainedTypes()); |
| 178 | for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { |
Nate Begeman | 14b0529 | 2005-11-05 09:21:28 +0000 | [diff] [blame] | 179 | AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, |
| 180 | AI->getAlignment(), |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 181 | AI->getName() + "." + utostr(i), AI); |
| 182 | ElementAllocas.push_back(NA); |
| 183 | WorkList.push_back(NA); // Add to worklist for recursive processing |
| 184 | } |
| 185 | } else { |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 186 | const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 187 | ElementAllocas.reserve(AT->getNumElements()); |
| 188 | const Type *ElTy = AT->getElementType(); |
| 189 | for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { |
Nate Begeman | 14b0529 | 2005-11-05 09:21:28 +0000 | [diff] [blame] | 190 | AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 191 | AI->getName() + "." + utostr(i), AI); |
| 192 | ElementAllocas.push_back(NA); |
| 193 | WorkList.push_back(NA); // Add to worklist for recursive processing |
| 194 | } |
| 195 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 196 | |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 197 | // Now that we have created the alloca instructions that we want to use, |
| 198 | // expand the getelementptr instructions to use them. |
| 199 | // |
Chris Lattner | 8430a45 | 2004-06-19 02:02:22 +0000 | [diff] [blame] | 200 | while (!AI->use_empty()) { |
| 201 | Instruction *User = cast<Instruction>(AI->use_back()); |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 202 | GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); |
| 203 | // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 204 | unsigned Idx = |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 205 | (unsigned)cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 206 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 207 | assert(Idx < ElementAllocas.size() && "Index out of range?"); |
| 208 | AllocaInst *AllocaToUse = ElementAllocas[Idx]; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 209 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 210 | Value *RepValue; |
| 211 | if (GEPI->getNumOperands() == 3) { |
| 212 | // Do not insert a new getelementptr instruction with zero indices, only |
| 213 | // to have it optimized out later. |
| 214 | RepValue = AllocaToUse; |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 215 | } else { |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 216 | // We are indexing deeply into the structure, so we still need a |
| 217 | // getelement ptr instruction to finish the indexing. This may be |
| 218 | // expanded itself once the worklist is rerun. |
| 219 | // |
| 220 | std::string OldName = GEPI->getName(); // Steal the old name. |
| 221 | std::vector<Value*> NewArgs; |
| 222 | NewArgs.push_back(Constant::getNullValue(Type::IntTy)); |
| 223 | NewArgs.insert(NewArgs.end(), GEPI->op_begin()+3, GEPI->op_end()); |
| 224 | GEPI->setName(""); |
| 225 | RepValue = new GetElementPtrInst(AllocaToUse, NewArgs, OldName, GEPI); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 226 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 227 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 228 | // Move all of the users over to the new GEP. |
| 229 | GEPI->replaceAllUsesWith(RepValue); |
| 230 | // Delete the old GEP |
| 231 | GEPI->eraseFromParent(); |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 232 | } |
| 233 | |
| 234 | // Finally, delete the Alloca instruction |
| 235 | AI->getParent()->getInstList().erase(AI); |
Chris Lattner | d10376b | 2003-05-27 16:09:27 +0000 | [diff] [blame] | 236 | NumReplaced++; |
Chris Lattner | ed7b41e | 2003-05-27 15:45:27 +0000 | [diff] [blame] | 237 | } |
| 238 | |
| 239 | return Changed; |
| 240 | } |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 241 | |
| 242 | |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 243 | /// isSafeElementUse - Check to see if this use is an allowed use for a |
| 244 | /// getelementptr instruction of an array aggregate allocation. |
| 245 | /// |
| 246 | int SROA::isSafeElementUse(Value *Ptr) { |
| 247 | for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); |
| 248 | I != E; ++I) { |
| 249 | Instruction *User = cast<Instruction>(*I); |
| 250 | switch (User->getOpcode()) { |
| 251 | case Instruction::Load: break; |
| 252 | case Instruction::Store: |
| 253 | // Store is ok if storing INTO the pointer, not storing the pointer |
| 254 | if (User->getOperand(0) == Ptr) return 0; |
| 255 | break; |
| 256 | case Instruction::GetElementPtr: { |
| 257 | GetElementPtrInst *GEP = cast<GetElementPtrInst>(User); |
| 258 | if (GEP->getNumOperands() > 1) { |
| 259 | if (!isa<Constant>(GEP->getOperand(1)) || |
| 260 | !cast<Constant>(GEP->getOperand(1))->isNullValue()) |
| 261 | return 0; // Using pointer arithmetic to navigate the array... |
| 262 | } |
| 263 | if (!isSafeElementUse(GEP)) return 0; |
| 264 | break; |
| 265 | } |
| 266 | default: |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 267 | DOUT << " Transformation preventing inst: " << *User; |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 268 | return 0; |
| 269 | } |
| 270 | } |
| 271 | return 3; // All users look ok :) |
| 272 | } |
| 273 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 274 | /// AllUsersAreLoads - Return true if all users of this value are loads. |
| 275 | static bool AllUsersAreLoads(Value *Ptr) { |
| 276 | for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); |
| 277 | I != E; ++I) |
| 278 | if (cast<Instruction>(*I)->getOpcode() != Instruction::Load) |
| 279 | return false; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 280 | return true; |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 281 | } |
| 282 | |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 283 | /// isSafeUseOfAllocation - Check to see if this user is an allowed use for an |
| 284 | /// aggregate allocation. |
| 285 | /// |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 286 | int SROA::isSafeUseOfAllocation(Instruction *User) { |
| 287 | if (!isa<GetElementPtrInst>(User)) return 0; |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 288 | |
| 289 | GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); |
| 290 | gep_type_iterator I = gep_type_begin(GEPI), E = gep_type_end(GEPI); |
| 291 | |
Chris Lattner | 25de486 | 2006-03-08 01:05:29 +0000 | [diff] [blame] | 292 | // 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] | 293 | if (I == E || |
| 294 | I.getOperand() != Constant::getNullValue(I.getOperand()->getType())) |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 295 | return 0; |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 296 | |
| 297 | ++I; |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 298 | if (I == E) return 0; // ran out of GEP indices?? |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 299 | |
| 300 | // If this is a use of an array allocation, do a bit more checking for sanity. |
| 301 | if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { |
| 302 | uint64_t NumElements = AT->getNumElements(); |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 303 | |
Reid Spencer | 3ed469c | 2006-11-02 20:25:50 +0000 | [diff] [blame] | 304 | if (isa<ConstantInt>(I.getOperand())) { |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 305 | // Check to make sure that index falls within the array. If not, |
| 306 | // something funny is going on, so we won't do the optimization. |
| 307 | // |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 308 | if (cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue() >= NumElements) |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 309 | return 0; |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 310 | |
Chris Lattner | 25de486 | 2006-03-08 01:05:29 +0000 | [diff] [blame] | 311 | // We cannot scalar repl this level of the array unless any array |
| 312 | // sub-indices are in-range constants. In particular, consider: |
| 313 | // A[0][i]. We cannot know that the user isn't doing invalid things like |
| 314 | // allowing i to index an out-of-range subscript that accesses A[1]. |
| 315 | // |
| 316 | // Scalar replacing *just* the outer index of the array is probably not |
| 317 | // going to be a win anyway, so just give up. |
Chris Lattner | d925150 | 2006-11-07 22:42:47 +0000 | [diff] [blame] | 318 | for (++I; I != E && (isa<ArrayType>(*I) || isa<PackedType>(*I)); ++I) { |
| 319 | uint64_t NumElements; |
| 320 | if (const ArrayType *SubArrayTy = dyn_cast<ArrayType>(*I)) |
| 321 | NumElements = SubArrayTy->getNumElements(); |
| 322 | else |
| 323 | NumElements = cast<PackedType>(*I)->getNumElements(); |
| 324 | |
Chris Lattner | 25de486 | 2006-03-08 01:05:29 +0000 | [diff] [blame] | 325 | if (!isa<ConstantInt>(I.getOperand())) return 0; |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 326 | if (cast<ConstantInt>(I.getOperand())->getZExtValue() >= NumElements) |
Chris Lattner | 25de486 | 2006-03-08 01:05:29 +0000 | [diff] [blame] | 327 | return 0; |
| 328 | } |
| 329 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 330 | } else { |
| 331 | // If this is an array index and the index is not constant, we cannot |
| 332 | // promote... that is unless the array has exactly one or two elements in |
| 333 | // it, in which case we CAN promote it, but we have to canonicalize this |
| 334 | // out if this is the only problem. |
Chris Lattner | 25de486 | 2006-03-08 01:05:29 +0000 | [diff] [blame] | 335 | if ((NumElements == 1 || NumElements == 2) && |
| 336 | AllUsersAreLoads(GEPI)) |
| 337 | return 1; // Canonicalization required! |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 338 | return 0; |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 339 | } |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 340 | } |
Chris Lattner | be883a2 | 2003-11-25 21:09:18 +0000 | [diff] [blame] | 341 | |
| 342 | // If there are any non-simple uses of this getelementptr, make sure to reject |
| 343 | // them. |
| 344 | return isSafeElementUse(GEPI); |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 345 | } |
| 346 | |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 347 | /// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of |
| 348 | /// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, |
| 349 | /// or 1 if safe after canonicalization has been performed. |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 350 | /// |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 351 | int SROA::isSafeAllocaToScalarRepl(AllocationInst *AI) { |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 352 | // Loop over the use list of the alloca. We can only transform it if all of |
| 353 | // the users are safe to transform. |
| 354 | // |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 355 | int isSafe = 3; |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 356 | for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 357 | I != E; ++I) { |
| 358 | isSafe &= isSafeUseOfAllocation(cast<Instruction>(*I)); |
| 359 | if (isSafe == 0) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 360 | DOUT << "Cannot transform: " << *AI << " due to user: " << **I; |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 361 | return 0; |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 362 | } |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 363 | } |
| 364 | // If we require cleanup, isSafe is now 1, otherwise it is 3. |
| 365 | return isSafe; |
| 366 | } |
| 367 | |
| 368 | /// CanonicalizeAllocaUsers - If SROA reported that it can promote the specified |
| 369 | /// allocation, but only if cleaned up, perform the cleanups required. |
| 370 | void SROA::CanonicalizeAllocaUsers(AllocationInst *AI) { |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 371 | // At this point, we know that the end result will be SROA'd and promoted, so |
| 372 | // we can insert ugly code if required so long as sroa+mem2reg will clean it |
| 373 | // up. |
| 374 | for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); |
| 375 | UI != E; ) { |
| 376 | GetElementPtrInst *GEPI = cast<GetElementPtrInst>(*UI++); |
Reid Spencer | 96326f9 | 2004-11-15 17:29:41 +0000 | [diff] [blame] | 377 | gep_type_iterator I = gep_type_begin(GEPI); |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 378 | ++I; |
Chris Lattner | f5990ed | 2004-11-14 04:24:28 +0000 | [diff] [blame] | 379 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 380 | if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { |
| 381 | uint64_t NumElements = AT->getNumElements(); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 382 | |
Chris Lattner | d878ecd | 2004-11-14 05:00:19 +0000 | [diff] [blame] | 383 | if (!isa<ConstantInt>(I.getOperand())) { |
| 384 | if (NumElements == 1) { |
| 385 | GEPI->setOperand(2, Constant::getNullValue(Type::IntTy)); |
| 386 | } else { |
| 387 | assert(NumElements == 2 && "Unhandled case!"); |
| 388 | // All users of the GEP must be loads. At each use of the GEP, insert |
| 389 | // two loads of the appropriate indexed GEP and select between them. |
| 390 | Value *IsOne = BinaryOperator::createSetNE(I.getOperand(), |
| 391 | Constant::getNullValue(I.getOperand()->getType()), |
| 392 | "isone", GEPI); |
| 393 | // Insert the new GEP instructions, which are properly indexed. |
| 394 | std::vector<Value*> Indices(GEPI->op_begin()+1, GEPI->op_end()); |
| 395 | Indices[1] = Constant::getNullValue(Type::IntTy); |
| 396 | Value *ZeroIdx = new GetElementPtrInst(GEPI->getOperand(0), Indices, |
| 397 | GEPI->getName()+".0", GEPI); |
| 398 | Indices[1] = ConstantInt::get(Type::IntTy, 1); |
| 399 | Value *OneIdx = new GetElementPtrInst(GEPI->getOperand(0), Indices, |
| 400 | GEPI->getName()+".1", GEPI); |
| 401 | // Replace all loads of the variable index GEP with loads from both |
| 402 | // indexes and a select. |
| 403 | while (!GEPI->use_empty()) { |
| 404 | LoadInst *LI = cast<LoadInst>(GEPI->use_back()); |
| 405 | Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI); |
| 406 | Value *One = new LoadInst(OneIdx , LI->getName()+".1", LI); |
| 407 | Value *R = new SelectInst(IsOne, One, Zero, LI->getName(), LI); |
| 408 | LI->replaceAllUsesWith(R); |
| 409 | LI->eraseFromParent(); |
| 410 | } |
| 411 | GEPI->eraseFromParent(); |
| 412 | } |
| 413 | } |
| 414 | } |
| 415 | } |
Chris Lattner | 5e062a1 | 2003-05-30 04:15:41 +0000 | [diff] [blame] | 416 | } |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 417 | |
| 418 | /// MergeInType - Add the 'In' type to the accumulated type so far. If the |
| 419 | /// types are incompatible, return true, otherwise update Accum and return |
| 420 | /// false. |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 421 | /// |
| 422 | /// There are two cases we handle here: |
| 423 | /// 1) An effectively integer union, where the pieces are stored into as |
| 424 | /// smaller integers (common with byte swap and other idioms). |
| 425 | /// 2) A union of a vector and its elements. Here we turn element accesses |
| 426 | /// into insert/extract element operations. |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 427 | static bool MergeInType(const Type *In, const Type *&Accum, |
| 428 | const TargetData &TD) { |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 429 | // If this is our first type, just use it. |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 430 | const PackedType *PTy; |
| 431 | if (Accum == Type::VoidTy || In == Accum) { |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 432 | Accum = In; |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 433 | } else if (In->isIntegral() && Accum->isIntegral()) { // integer union. |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 434 | // Otherwise pick whichever type is larger. |
| 435 | if (In->getTypeID() > Accum->getTypeID()) |
| 436 | Accum = In; |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 437 | } else if (isa<PointerType>(In) && isa<PointerType>(Accum)) { |
Chris Lattner | c836333 | 2006-10-08 23:53:04 +0000 | [diff] [blame] | 438 | // Pointer unions just stay as one of the pointers. |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 439 | } else if ((PTy = dyn_cast<PackedType>(Accum)) && |
| 440 | PTy->getElementType() == In) { |
| 441 | // Accum is a vector, and we are accessing an element: ok. |
| 442 | } else if ((PTy = dyn_cast<PackedType>(In)) && |
| 443 | PTy->getElementType() == Accum) { |
| 444 | // In is a vector, and accum is an element: ok, remember In. |
| 445 | Accum = In; |
Chris Lattner | c836333 | 2006-10-08 23:53:04 +0000 | [diff] [blame] | 446 | } else if (isa<PointerType>(In) && Accum->isIntegral()) { |
| 447 | // Pointer/Integer unions merge together as integers. |
| 448 | return MergeInType(TD.getIntPtrType(), Accum, TD); |
| 449 | } else if (isa<PointerType>(Accum) && In->isIntegral()) { |
| 450 | // Pointer/Integer unions merge together as integers. |
| 451 | Accum = TD.getIntPtrType(); |
| 452 | return MergeInType(In, Accum, TD); |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 453 | } else { |
| 454 | return true; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 455 | } |
| 456 | return false; |
| 457 | } |
| 458 | |
| 459 | /// getUIntAtLeastAsBitAs - Return an unsigned integer type that is at least |
| 460 | /// as big as the specified type. If there is no suitable type, this returns |
| 461 | /// null. |
| 462 | const Type *getUIntAtLeastAsBitAs(unsigned NumBits) { |
| 463 | if (NumBits > 64) return 0; |
| 464 | if (NumBits > 32) return Type::ULongTy; |
| 465 | if (NumBits > 16) return Type::UIntTy; |
| 466 | if (NumBits > 8) return Type::UShortTy; |
| 467 | return Type::UByteTy; |
| 468 | } |
| 469 | |
| 470 | /// CanConvertToScalar - V is a pointer. If we can convert the pointee to a |
| 471 | /// single scalar integer type, return that type. Further, if the use is not |
| 472 | /// a completely trivial use that mem2reg could promote, set IsNotTrivial. If |
| 473 | /// there are no uses of this pointer, return Type::VoidTy to differentiate from |
| 474 | /// failure. |
| 475 | /// |
| 476 | const Type *SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial) { |
| 477 | const Type *UsedType = Type::VoidTy; // No uses, no forced type. |
| 478 | const TargetData &TD = getAnalysis<TargetData>(); |
| 479 | const PointerType *PTy = cast<PointerType>(V->getType()); |
| 480 | |
| 481 | for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { |
| 482 | Instruction *User = cast<Instruction>(*UI); |
| 483 | |
| 484 | if (LoadInst *LI = dyn_cast<LoadInst>(User)) { |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 485 | if (MergeInType(LI->getType(), UsedType, TD)) |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 486 | return 0; |
| 487 | |
| 488 | } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { |
| 489 | // Storing the pointer, not the into the value? |
| 490 | if (SI->getOperand(0) == V) return 0; |
| 491 | |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 492 | // NOTE: We could handle storing of FP imms into integers here! |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 493 | |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 494 | if (MergeInType(SI->getOperand(0)->getType(), UsedType, TD)) |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 495 | return 0; |
| 496 | } else if (CastInst *CI = dyn_cast<CastInst>(User)) { |
| 497 | if (!isa<PointerType>(CI->getType())) return 0; |
| 498 | IsNotTrivial = true; |
| 499 | const Type *SubTy = CanConvertToScalar(CI, IsNotTrivial); |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 500 | if (!SubTy || MergeInType(SubTy, UsedType, TD)) return 0; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 501 | } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { |
| 502 | // Check to see if this is stepping over an element: GEP Ptr, int C |
| 503 | if (GEP->getNumOperands() == 2 && isa<ConstantInt>(GEP->getOperand(1))) { |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 504 | unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getZExtValue(); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 505 | unsigned ElSize = TD.getTypeSize(PTy->getElementType()); |
| 506 | unsigned BitOffset = Idx*ElSize*8; |
| 507 | if (BitOffset > 64 || !isPowerOf2_32(ElSize)) return 0; |
| 508 | |
| 509 | IsNotTrivial = true; |
| 510 | const Type *SubElt = CanConvertToScalar(GEP, IsNotTrivial); |
| 511 | if (SubElt == 0) return 0; |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 512 | if (SubElt != Type::VoidTy && SubElt->isInteger()) { |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 513 | const Type *NewTy = |
Chris Lattner | c836333 | 2006-10-08 23:53:04 +0000 | [diff] [blame] | 514 | getUIntAtLeastAsBitAs(TD.getTypeSize(SubElt)*8+BitOffset); |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 515 | if (NewTy == 0 || MergeInType(NewTy, UsedType, TD)) return 0; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 516 | continue; |
| 517 | } |
| 518 | } else if (GEP->getNumOperands() == 3 && |
| 519 | isa<ConstantInt>(GEP->getOperand(1)) && |
| 520 | isa<ConstantInt>(GEP->getOperand(2)) && |
| 521 | cast<Constant>(GEP->getOperand(1))->isNullValue()) { |
| 522 | // We are stepping into an element, e.g. a structure or an array: |
| 523 | // GEP Ptr, int 0, uint C |
| 524 | const Type *AggTy = PTy->getElementType(); |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 525 | unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue(); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 526 | |
| 527 | if (const ArrayType *ATy = dyn_cast<ArrayType>(AggTy)) { |
| 528 | if (Idx >= ATy->getNumElements()) return 0; // Out of range. |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 529 | } else if (const PackedType *PackedTy = dyn_cast<PackedType>(AggTy)) { |
| 530 | // Getting an element of the packed vector. |
| 531 | if (Idx >= PackedTy->getNumElements()) return 0; // Out of range. |
| 532 | |
| 533 | // Merge in the packed type. |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 534 | if (MergeInType(PackedTy, UsedType, TD)) return 0; |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 535 | |
| 536 | const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial); |
| 537 | if (SubTy == 0) return 0; |
| 538 | |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 539 | if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType, TD)) |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 540 | return 0; |
| 541 | |
| 542 | // We'll need to change this to an insert/extract element operation. |
| 543 | IsNotTrivial = true; |
| 544 | continue; // Everything looks ok |
| 545 | |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 546 | } else if (isa<StructType>(AggTy)) { |
| 547 | // Structs are always ok. |
| 548 | } else { |
| 549 | return 0; |
| 550 | } |
| 551 | const Type *NTy = getUIntAtLeastAsBitAs(TD.getTypeSize(AggTy)*8); |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 552 | if (NTy == 0 || MergeInType(NTy, UsedType, TD)) return 0; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 553 | const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial); |
| 554 | if (SubTy == 0) return 0; |
Chris Lattner | 5b121cc | 2006-10-08 23:28:04 +0000 | [diff] [blame] | 555 | if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType, TD)) |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 556 | return 0; |
| 557 | continue; // Everything looks ok |
| 558 | } |
| 559 | return 0; |
| 560 | } else { |
| 561 | // Cannot handle this! |
| 562 | return 0; |
| 563 | } |
| 564 | } |
| 565 | |
| 566 | return UsedType; |
| 567 | } |
| 568 | |
| 569 | /// ConvertToScalar - The specified alloca passes the CanConvertToScalar |
| 570 | /// predicate and is non-trivial. Convert it to something that can be trivially |
| 571 | /// promoted into a register by mem2reg. |
| 572 | void SROA::ConvertToScalar(AllocationInst *AI, const Type *ActualTy) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 573 | DOUT << "CONVERT TO SCALAR: " << *AI << " TYPE = " |
| 574 | << *ActualTy << "\n"; |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 575 | ++NumConverted; |
| 576 | |
| 577 | BasicBlock *EntryBlock = AI->getParent(); |
| 578 | assert(EntryBlock == &EntryBlock->getParent()->front() && |
| 579 | "Not in the entry block!"); |
| 580 | EntryBlock->getInstList().remove(AI); // Take the alloca out of the program. |
| 581 | |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 582 | if (ActualTy->isInteger()) |
| 583 | ActualTy = ActualTy->getUnsignedVersion(); |
| 584 | |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 585 | // Create and insert the alloca. |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 586 | AllocaInst *NewAI = new AllocaInst(ActualTy, 0, AI->getName(), |
| 587 | EntryBlock->begin()); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 588 | ConvertUsesToScalar(AI, NewAI, 0); |
| 589 | delete AI; |
| 590 | } |
| 591 | |
| 592 | |
| 593 | /// 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] | 594 | /// directly. This happens when we are converting an "integer union" to a |
| 595 | /// single integer scalar, or when we are converting a "vector union" to a |
| 596 | /// vector with insert/extractelement instructions. |
| 597 | /// |
| 598 | /// Offset is an offset from the original alloca, in bits that need to be |
| 599 | /// shifted to the right. By the end of this, there should be no uses of Ptr. |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 600 | void SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset) { |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 601 | bool isVectorInsert = isa<PackedType>(NewAI->getType()->getElementType()); |
Chris Lattner | c836333 | 2006-10-08 23:53:04 +0000 | [diff] [blame] | 602 | const TargetData &TD = getAnalysis<TargetData>(); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 603 | while (!Ptr->use_empty()) { |
| 604 | Instruction *User = cast<Instruction>(Ptr->use_back()); |
| 605 | |
| 606 | if (LoadInst *LI = dyn_cast<LoadInst>(User)) { |
| 607 | // The load is a bit extract from NewAI shifted right by Offset bits. |
| 608 | Value *NV = new LoadInst(NewAI, LI->getName(), LI); |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 609 | if (NV->getType() != LI->getType()) { |
| 610 | if (const PackedType *PTy = dyn_cast<PackedType>(NV->getType())) { |
| 611 | // Must be an element access. |
Chris Lattner | c836333 | 2006-10-08 23:53:04 +0000 | [diff] [blame] | 612 | unsigned Elt = Offset/(TD.getTypeSize(PTy->getElementType())*8); |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 613 | NV = new ExtractElementInst(NV, ConstantInt::get(Type::UIntTy, Elt), |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 614 | "tmp", LI); |
| 615 | } else { |
Chris Lattner | ae5d51c | 2006-10-24 06:26:32 +0000 | [diff] [blame] | 616 | if (Offset) { |
| 617 | assert(NV->getType()->isInteger() && "Unknown promotion!"); |
Reid Spencer | 3822ff5 | 2006-11-08 06:47:33 +0000 | [diff] [blame] | 618 | if (Offset < TD.getTypeSize(NV->getType())*8) { |
| 619 | NV = new ShiftInst(Instruction::LShr, NV, |
| 620 | ConstantInt::get(Type::UByteTy, Offset), |
Chris Lattner | ae5d51c | 2006-10-24 06:26:32 +0000 | [diff] [blame] | 621 | LI->getName(), LI); |
Reid Spencer | 3822ff5 | 2006-11-08 06:47:33 +0000 | [diff] [blame] | 622 | } |
Chris Lattner | ae5d51c | 2006-10-24 06:26:32 +0000 | [diff] [blame] | 623 | } else { |
| 624 | assert((NV->getType()->isInteger() || |
| 625 | isa<PointerType>(NV->getType())) && "Unknown promotion!"); |
| 626 | } |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 627 | NV = CastInst::createInferredCast(NV, LI->getType(), LI->getName(), |
| 628 | LI); |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 629 | } |
| 630 | } |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 631 | LI->replaceAllUsesWith(NV); |
| 632 | LI->eraseFromParent(); |
| 633 | } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { |
| 634 | assert(SI->getOperand(0) != Ptr && "Consistency error!"); |
| 635 | |
| 636 | // Convert the stored type to the actual type, shift it left to insert |
| 637 | // then 'or' into place. |
| 638 | Value *SV = SI->getOperand(0); |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 639 | const Type *AllocaType = NewAI->getType()->getElementType(); |
| 640 | if (SV->getType() != AllocaType) { |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 641 | Value *Old = new LoadInst(NewAI, NewAI->getName()+".in", SI); |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 642 | |
| 643 | if (const PackedType *PTy = dyn_cast<PackedType>(AllocaType)) { |
| 644 | // Must be an element insertion. |
Chris Lattner | c836333 | 2006-10-08 23:53:04 +0000 | [diff] [blame] | 645 | unsigned Elt = Offset/(TD.getTypeSize(PTy->getElementType())*8); |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 646 | SV = new InsertElementInst(Old, SV, |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 647 | ConstantInt::get(Type::UIntTy, Elt), |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 648 | "tmp", SI); |
| 649 | } else { |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 650 | // Always zero extend the value. |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 651 | if (SV->getType()->isSigned()) |
Reid Spencer | 3da59db | 2006-11-27 01:05:10 +0000 | [diff] [blame^] | 652 | SV = CastInst::createInferredCast(SV, |
| 653 | SV->getType()->getUnsignedVersion(), SV->getName(), SI); |
| 654 | SV = CastInst::createInferredCast(SV, Old->getType(), SV->getName(), |
| 655 | SI); |
Chris Lattner | c836333 | 2006-10-08 23:53:04 +0000 | [diff] [blame] | 656 | if (Offset && Offset < TD.getTypeSize(SV->getType())*8) |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 657 | SV = new ShiftInst(Instruction::Shl, SV, |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 658 | ConstantInt::get(Type::UByteTy, Offset), |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 659 | SV->getName()+".adj", SI); |
| 660 | // Mask out the bits we are about to insert from the old value. |
Chris Lattner | c836333 | 2006-10-08 23:53:04 +0000 | [diff] [blame] | 661 | unsigned TotalBits = TD.getTypeSize(SV->getType())*8; |
| 662 | unsigned InsertBits = TD.getTypeSize(SI->getOperand(0)->getType())*8; |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 663 | if (TotalBits != InsertBits) { |
| 664 | assert(TotalBits > InsertBits); |
| 665 | uint64_t Mask = ~(((1ULL << InsertBits)-1) << Offset); |
| 666 | if (TotalBits != 64) |
| 667 | Mask = Mask & ((1ULL << TotalBits)-1); |
| 668 | Old = BinaryOperator::createAnd(Old, |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 669 | ConstantInt::get(Old->getType(), Mask), |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 670 | Old->getName()+".mask", SI); |
| 671 | SV = BinaryOperator::createOr(Old, SV, SV->getName()+".ins", SI); |
| 672 | } |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 673 | } |
| 674 | } |
| 675 | new StoreInst(SV, NewAI, SI); |
| 676 | SI->eraseFromParent(); |
| 677 | |
| 678 | } else if (CastInst *CI = dyn_cast<CastInst>(User)) { |
| 679 | unsigned NewOff = Offset; |
| 680 | const TargetData &TD = getAnalysis<TargetData>(); |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 681 | if (TD.isBigEndian() && !isVectorInsert) { |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 682 | // Adjust the pointer. For example, storing 16-bits into a 32-bit |
| 683 | // alloca with just a cast makes it modify the top 16-bits. |
| 684 | const Type *SrcTy = cast<PointerType>(Ptr->getType())->getElementType(); |
| 685 | const Type *DstTy = cast<PointerType>(CI->getType())->getElementType(); |
| 686 | int PtrDiffBits = TD.getTypeSize(SrcTy)*8-TD.getTypeSize(DstTy)*8; |
| 687 | NewOff += PtrDiffBits; |
| 688 | } |
| 689 | ConvertUsesToScalar(CI, NewAI, NewOff); |
| 690 | CI->eraseFromParent(); |
| 691 | } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { |
| 692 | const PointerType *AggPtrTy = |
| 693 | cast<PointerType>(GEP->getOperand(0)->getType()); |
| 694 | const TargetData &TD = getAnalysis<TargetData>(); |
| 695 | unsigned AggSizeInBits = TD.getTypeSize(AggPtrTy->getElementType())*8; |
| 696 | |
| 697 | // Check to see if this is stepping over an element: GEP Ptr, int C |
| 698 | unsigned NewOffset = Offset; |
| 699 | if (GEP->getNumOperands() == 2) { |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 700 | unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getZExtValue(); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 701 | unsigned BitOffset = Idx*AggSizeInBits; |
| 702 | |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 703 | if (TD.isLittleEndian() || isVectorInsert) |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 704 | NewOffset += BitOffset; |
| 705 | else |
| 706 | NewOffset -= BitOffset; |
| 707 | |
| 708 | } else if (GEP->getNumOperands() == 3) { |
| 709 | // We know that operand #2 is zero. |
Reid Spencer | b83eb64 | 2006-10-20 07:07:24 +0000 | [diff] [blame] | 710 | unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue(); |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 711 | const Type *AggTy = AggPtrTy->getElementType(); |
| 712 | if (const SequentialType *SeqTy = dyn_cast<SequentialType>(AggTy)) { |
| 713 | unsigned ElSizeBits = TD.getTypeSize(SeqTy->getElementType())*8; |
| 714 | |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 715 | if (TD.isLittleEndian() || isVectorInsert) |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 716 | NewOffset += ElSizeBits*Idx; |
| 717 | else |
| 718 | NewOffset += AggSizeInBits-ElSizeBits*(Idx+1); |
| 719 | } else if (const StructType *STy = dyn_cast<StructType>(AggTy)) { |
| 720 | unsigned EltBitOffset = TD.getStructLayout(STy)->MemberOffsets[Idx]*8; |
| 721 | |
Chris Lattner | de6df88 | 2006-04-14 21:42:41 +0000 | [diff] [blame] | 722 | if (TD.isLittleEndian() || isVectorInsert) |
Chris Lattner | a188894 | 2005-12-12 07:19:13 +0000 | [diff] [blame] | 723 | NewOffset += EltBitOffset; |
| 724 | else { |
| 725 | const PointerType *ElPtrTy = cast<PointerType>(GEP->getType()); |
| 726 | unsigned ElSizeBits = TD.getTypeSize(ElPtrTy->getElementType())*8; |
| 727 | NewOffset += AggSizeInBits-(EltBitOffset+ElSizeBits); |
| 728 | } |
| 729 | |
| 730 | } else { |
| 731 | assert(0 && "Unsupported operation!"); |
| 732 | abort(); |
| 733 | } |
| 734 | } else { |
| 735 | assert(0 && "Unsupported operation!"); |
| 736 | abort(); |
| 737 | } |
| 738 | ConvertUsesToScalar(GEP, NewAI, NewOffset); |
| 739 | GEP->eraseFromParent(); |
| 740 | } else { |
| 741 | assert(0 && "Unsupported operation!"); |
| 742 | abort(); |
| 743 | } |
| 744 | } |
| 745 | } |