ScalarReplAggregates.cpp revision 26d2ca1d134a8deb91f0246b70024ac1032e544c
1//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2// 3// This transformation implements the well known scalar replacement of 4// aggregates transformation. This xform breaks up alloca instructions of 5// aggregate type (structure or array) into individual alloca instructions for 6// each member (if possible). 7// 8//===----------------------------------------------------------------------===// 9 10#include "llvm/Transforms/Scalar.h" 11#include "llvm/Function.h" 12#include "llvm/Pass.h" 13#include "llvm/iMemory.h" 14#include "llvm/DerivedTypes.h" 15#include "llvm/Constants.h" 16#include "Support/StringExtras.h" 17#include "Support/Statistic.h" 18 19namespace { 20 Statistic<> NumReplaced("scalarrepl", "Number of alloca's broken up"); 21 22 struct SROA : public FunctionPass { 23 bool runOnFunction(Function &F); 24 25 private: 26 bool isSafeStructElementUse(Value *Ptr); 27 bool isSafeArrayElementUse(Value *Ptr); 28 bool isSafeUseOfAllocation(Instruction *User); 29 bool isSafeStructAllocaToPromote(AllocationInst *AI); 30 bool isSafeArrayAllocaToPromote(AllocationInst *AI); 31 AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); 32 }; 33 34 RegisterOpt<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); 35} 36 37Pass *createScalarReplAggregatesPass() { return new SROA(); } 38 39 40// runOnFunction - This algorithm is a simple worklist driven algorithm, which 41// runs on all of the malloc/alloca instructions in the function, removing them 42// if they are only used by getelementptr instructions. 43// 44bool SROA::runOnFunction(Function &F) { 45 std::vector<AllocationInst*> WorkList; 46 47 // Scan the entry basic block, adding any alloca's and mallocs to the worklist 48 BasicBlock &BB = F.getEntryNode(); 49 for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 50 if (AllocationInst *A = dyn_cast<AllocationInst>(I)) 51 WorkList.push_back(A); 52 53 // Process the worklist 54 bool Changed = false; 55 while (!WorkList.empty()) { 56 AllocationInst *AI = WorkList.back(); 57 WorkList.pop_back(); 58 59 // We cannot transform the allocation instruction if it is an array 60 // allocation (allocations OF arrays are ok though), and an allocation of a 61 // scalar value cannot be decomposed at all. 62 // 63 if (AI->isArrayAllocation() || 64 (!isa<StructType>(AI->getAllocatedType()) && 65 !isa<ArrayType>(AI->getAllocatedType()))) continue; 66 67 // Check that all of the users of the allocation are capable of being 68 // transformed. 69 if (isa<StructType>(AI->getAllocatedType())) { 70 if (!isSafeStructAllocaToPromote(AI)) 71 continue; 72 } else if (!isSafeArrayAllocaToPromote(AI)) 73 continue; 74 75 DEBUG(std::cerr << "Found inst to xform: " << *AI); 76 Changed = true; 77 78 std::vector<AllocaInst*> ElementAllocas; 79 if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 80 ElementAllocas.reserve(ST->getNumContainedTypes()); 81 for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 82 AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 83 AI->getName() + "." + utostr(i), AI); 84 ElementAllocas.push_back(NA); 85 WorkList.push_back(NA); // Add to worklist for recursive processing 86 } 87 } else { 88 const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 89 ElementAllocas.reserve(AT->getNumElements()); 90 const Type *ElTy = AT->getElementType(); 91 for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 92 AllocaInst *NA = new AllocaInst(ElTy, 0, 93 AI->getName() + "." + utostr(i), AI); 94 ElementAllocas.push_back(NA); 95 WorkList.push_back(NA); // Add to worklist for recursive processing 96 } 97 } 98 99 // Now that we have created the alloca instructions that we want to use, 100 // expand the getelementptr instructions to use them. 101 // 102 for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 103 I != E; ++I) { 104 Instruction *User = cast<Instruction>(*I); 105 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 106 // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> 107 uint64_t Idx; 108 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(GEPI->getOperand(2))) 109 Idx = CSI->getValue(); 110 else 111 Idx = cast<ConstantUInt>(GEPI->getOperand(2))->getValue(); 112 113 assert(Idx < ElementAllocas.size() && "Index out of range?"); 114 AllocaInst *AllocaToUse = ElementAllocas[Idx]; 115 116 Value *RepValue; 117 if (GEPI->getNumOperands() == 3) { 118 // Do not insert a new getelementptr instruction with zero indices, 119 // only to have it optimized out later. 120 RepValue = AllocaToUse; 121 } else { 122 // We are indexing deeply into the structure, so we still need a 123 // getelement ptr instruction to finish the indexing. This may be 124 // expanded itself once the worklist is rerun. 125 // 126 std::string OldName = GEPI->getName(); // Steal the old name... 127 std::vector<Value*> NewArgs; 128 NewArgs.push_back(Constant::getNullValue(Type::LongTy)); 129 NewArgs.insert(NewArgs.end(), GEPI->op_begin()+3, GEPI->op_end()); 130 GEPI->setName(""); 131 RepValue = 132 new GetElementPtrInst(AllocaToUse, NewArgs, OldName, GEPI); 133 } 134 135 // Move all of the users over to the new GEP. 136 GEPI->replaceAllUsesWith(RepValue); 137 // Delete the old GEP 138 GEPI->getParent()->getInstList().erase(GEPI); 139 } else { 140 assert(0 && "Unexpected instruction type!"); 141 } 142 } 143 144 // Finally, delete the Alloca instruction 145 AI->getParent()->getInstList().erase(AI); 146 NumReplaced++; 147 } 148 149 return Changed; 150} 151 152 153/// isSafeUseOfAllocation - Check to see if this user is an allowed use for an 154/// aggregate allocation. 155/// 156bool SROA::isSafeUseOfAllocation(Instruction *User) { 157 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 158 // The GEP is safe to transform if it is of the form GEP <ptr>, 0, <cst> 159 if (GEPI->getNumOperands() <= 2 || 160 GEPI->getOperand(1) != Constant::getNullValue(Type::LongTy) || 161 !isa<Constant>(GEPI->getOperand(2)) || 162 isa<ConstantExpr>(GEPI->getOperand(2))) 163 return false; 164 } else { 165 return false; 166 } 167 return true; 168} 169 170/// isSafeStructElementUse - It is illegal in C to take the address of a 171/// structure sub-element, and then use pointer arithmetic to access other 172/// elements of the struct. Despite the fact that this is illegal, some 173/// programs do this, so do at least a simple check to try to avoid breaking 174/// broken programs if possible. 175/// 176bool SROA::isSafeStructElementUse(Value *Ptr) { 177 for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 178 I != E; ++I) 179 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*I)) { 180 if (GEP->getNumOperands() > 1) { 181 if (!isa<Constant>(GEP->getOperand(1)) || 182 !cast<Constant>(GEP->getOperand(1))->isNullValue()) { 183 std::cerr << "WARNING: Undefined behavior found: " << *GEP 184 << " ... uses pointer arithmetic to access other struct " 185 << "elements!\n"; 186 return false; 187 188 return false; // Using pointer arithmetic to navigate the array... 189 } 190 } 191 } 192 193 return true; 194} 195 196/// isSafeArrayElementUse - Check to see if this use is an allowed use for a 197/// getelementptr instruction of an array aggregate allocation. 198/// 199bool SROA::isSafeArrayElementUse(Value *Ptr) { 200 for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 201 I != E; ++I) { 202 Instruction *User = cast<Instruction>(*I); 203 switch (User->getOpcode()) { 204 case Instruction::Load: return true; 205 case Instruction::Store: return User->getOperand(0) != Ptr; 206 case Instruction::GetElementPtr: { 207 GetElementPtrInst *GEP = cast<GetElementPtrInst>(User); 208 if (GEP->getNumOperands() > 1) { 209 if (!isa<Constant>(GEP->getOperand(1)) || 210 !cast<Constant>(GEP->getOperand(1))->isNullValue()) 211 return false; // Using pointer arithmetic to navigate the array... 212 213 // Check to see if there are any structure indexes involved in this GEP. 214 // If so, then we can safely break the array up until at least the 215 // structure. 216 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) 217 if (GEP->getOperand(i)->getType()->isUnsigned()) 218 break; 219 } 220 return isSafeArrayElementUse(GEP); 221 } 222 default: 223 DEBUG(std::cerr << " Transformation preventing inst: " << *User); 224 return false; 225 } 226 } 227 return true; // All users look ok :) 228} 229 230 231/// isSafeStructAllocaToPromote - Check to see if the specified allocation of a 232/// structure can be broken down into elements. 233/// 234bool SROA::isSafeStructAllocaToPromote(AllocationInst *AI) { 235 // Loop over the use list of the alloca. We can only transform it if all of 236 // the users are safe to transform. 237 // 238 for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 239 I != E; ++I) { 240 if (!isSafeUseOfAllocation(cast<Instruction>(*I))) { 241 DEBUG(std::cerr << "Cannot transform: " << *AI << " due to user: " 242 << *I); 243 return false; 244 } 245 246 // Pedantic check to avoid breaking broken programs... 247 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*I)) 248 if (GEPI->getNumOperands() == 3 && !isSafeStructElementUse(GEPI)) 249 return false; 250 } 251 return true; 252} 253 254 255/// isSafeArrayAllocaToPromote - Check to see if the specified allocation of a 256/// structure can be broken down into elements. 257/// 258bool SROA::isSafeArrayAllocaToPromote(AllocationInst *AI) { 259 const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 260 int64_t NumElements = AT->getNumElements(); 261 262 // Loop over the use list of the alloca. We can only transform it if all of 263 // the users are safe to transform. Array allocas have extra constraints to 264 // meet though. 265 // 266 for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 267 I != E; ++I) { 268 Instruction *User = cast<Instruction>(*I); 269 if (!isSafeUseOfAllocation(User)) { 270 DEBUG(std::cerr << "Cannot transform: " << *AI << " due to user: " 271 << User); 272 return false; 273 } 274 275 // Check to make sure that getelementptr follow the extra rules for arrays: 276 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 277 // Check to make sure that index falls within the array. If not, 278 // something funny is going on, so we won't do the optimization. 279 // 280 if (cast<ConstantSInt>(GEPI->getOperand(2))->getValue() >= NumElements) 281 return false; 282 283 // Check to make sure that the only thing that uses the resultant pointer 284 // is safe for an array access. For example, code that looks like: 285 // P = &A[0]; P = P + 1 286 // is legal, and should prevent promotion. 287 // 288 if (!isSafeArrayElementUse(GEPI)) { 289 DEBUG(std::cerr << "Cannot transform: " << *AI 290 << " due to uses of user: " << *GEPI); 291 return false; 292 } 293 } 294 } 295 return true; 296} 297 298