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