LLVM API Documentation
00001 //===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This transformation implements the well known scalar replacement of 00011 // aggregates transformation. This xform breaks up alloca instructions of 00012 // aggregate type (structure or array) into individual alloca instructions for 00013 // each member (if possible). Then, if possible, it transforms the individual 00014 // alloca instructions into nice clean scalar SSA form. 00015 // 00016 // This combines a simple SRoA algorithm with the Mem2Reg algorithm because 00017 // often interact, especially for C++ programs. As such, iterating between 00018 // SRoA, then Mem2Reg until we run out of things to promote works well. 00019 // 00020 //===----------------------------------------------------------------------===// 00021 00022 #include "llvm/Transforms/Scalar.h" 00023 #include "llvm/Constants.h" 00024 #include "llvm/DerivedTypes.h" 00025 #include "llvm/Function.h" 00026 #include "llvm/Pass.h" 00027 #include "llvm/Instructions.h" 00028 #include "llvm/Analysis/Dominators.h" 00029 #include "llvm/Target/TargetData.h" 00030 #include "llvm/Transforms/Utils/PromoteMemToReg.h" 00031 #include "llvm/Support/GetElementPtrTypeIterator.h" 00032 #include "llvm/Support/MathExtras.h" 00033 #include "llvm/Support/Debug.h" 00034 #include "llvm/ADT/Statistic.h" 00035 #include "llvm/ADT/StringExtras.h" 00036 #include <iostream> 00037 using namespace llvm; 00038 00039 namespace { 00040 Statistic<> NumReplaced("scalarrepl", "Number of allocas broken up"); 00041 Statistic<> NumPromoted("scalarrepl", "Number of allocas promoted"); 00042 Statistic<> NumConverted("scalarrepl", 00043 "Number of aggregates converted to scalar"); 00044 00045 struct SROA : public FunctionPass { 00046 bool runOnFunction(Function &F); 00047 00048 bool performScalarRepl(Function &F); 00049 bool performPromotion(Function &F); 00050 00051 // getAnalysisUsage - This pass does not require any passes, but we know it 00052 // will not alter the CFG, so say so. 00053 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00054 AU.addRequired<DominatorTree>(); 00055 AU.addRequired<DominanceFrontier>(); 00056 AU.addRequired<TargetData>(); 00057 AU.setPreservesCFG(); 00058 } 00059 00060 private: 00061 int isSafeElementUse(Value *Ptr); 00062 int isSafeUseOfAllocation(Instruction *User); 00063 int isSafeAllocaToScalarRepl(AllocationInst *AI); 00064 void CanonicalizeAllocaUsers(AllocationInst *AI); 00065 AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); 00066 00067 const Type *CanConvertToScalar(Value *V, bool &IsNotTrivial); 00068 void ConvertToScalar(AllocationInst *AI, const Type *Ty); 00069 void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset); 00070 }; 00071 00072 RegisterOpt<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); 00073 } 00074 00075 // Public interface to the ScalarReplAggregates pass 00076 FunctionPass *llvm::createScalarReplAggregatesPass() { return new SROA(); } 00077 00078 00079 bool SROA::runOnFunction(Function &F) { 00080 bool Changed = performPromotion(F); 00081 while (1) { 00082 bool LocalChange = performScalarRepl(F); 00083 if (!LocalChange) break; // No need to repromote if no scalarrepl 00084 Changed = true; 00085 LocalChange = performPromotion(F); 00086 if (!LocalChange) break; // No need to re-scalarrepl if no promotion 00087 } 00088 00089 return Changed; 00090 } 00091 00092 00093 bool SROA::performPromotion(Function &F) { 00094 std::vector<AllocaInst*> Allocas; 00095 const TargetData &TD = getAnalysis<TargetData>(); 00096 DominatorTree &DT = getAnalysis<DominatorTree>(); 00097 DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); 00098 00099 BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 00100 00101 bool Changed = false; 00102 00103 while (1) { 00104 Allocas.clear(); 00105 00106 // Find allocas that are safe to promote, by looking at all instructions in 00107 // the entry node 00108 for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 00109 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 00110 if (isAllocaPromotable(AI, TD)) 00111 Allocas.push_back(AI); 00112 00113 if (Allocas.empty()) break; 00114 00115 PromoteMemToReg(Allocas, DT, DF, TD); 00116 NumPromoted += Allocas.size(); 00117 Changed = true; 00118 } 00119 00120 return Changed; 00121 } 00122 00123 // performScalarRepl - This algorithm is a simple worklist driven algorithm, 00124 // which runs on all of the malloc/alloca instructions in the function, removing 00125 // them if they are only used by getelementptr instructions. 00126 // 00127 bool SROA::performScalarRepl(Function &F) { 00128 std::vector<AllocationInst*> WorkList; 00129 00130 // Scan the entry basic block, adding any alloca's and mallocs to the worklist 00131 BasicBlock &BB = F.getEntryBlock(); 00132 for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 00133 if (AllocationInst *A = dyn_cast<AllocationInst>(I)) 00134 WorkList.push_back(A); 00135 00136 // Process the worklist 00137 bool Changed = false; 00138 while (!WorkList.empty()) { 00139 AllocationInst *AI = WorkList.back(); 00140 WorkList.pop_back(); 00141 00142 // If we can turn this aggregate value (potentially with casts) into a 00143 // simple scalar value that can be mem2reg'd into a register value. 00144 bool IsNotTrivial = false; 00145 if (const Type *ActualType = CanConvertToScalar(AI, IsNotTrivial)) 00146 if (IsNotTrivial) { 00147 ConvertToScalar(AI, ActualType); 00148 Changed = true; 00149 continue; 00150 } 00151 00152 // We cannot transform the allocation instruction if it is an array 00153 // allocation (allocations OF arrays are ok though), and an allocation of a 00154 // scalar value cannot be decomposed at all. 00155 // 00156 if (AI->isArrayAllocation() || 00157 (!isa<StructType>(AI->getAllocatedType()) && 00158 !isa<ArrayType>(AI->getAllocatedType()))) continue; 00159 00160 // Check that all of the users of the allocation are capable of being 00161 // transformed. 00162 switch (isSafeAllocaToScalarRepl(AI)) { 00163 default: assert(0 && "Unexpected value!"); 00164 case 0: // Not safe to scalar replace. 00165 continue; 00166 case 1: // Safe, but requires cleanup/canonicalizations first 00167 CanonicalizeAllocaUsers(AI); 00168 case 3: // Safe to scalar replace. 00169 break; 00170 } 00171 00172 DEBUG(std::cerr << "Found inst to xform: " << *AI); 00173 Changed = true; 00174 00175 std::vector<AllocaInst*> ElementAllocas; 00176 if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 00177 ElementAllocas.reserve(ST->getNumContainedTypes()); 00178 for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 00179 AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 00180 AI->getAlignment(), 00181 AI->getName() + "." + utostr(i), AI); 00182 ElementAllocas.push_back(NA); 00183 WorkList.push_back(NA); // Add to worklist for recursive processing 00184 } 00185 } else { 00186 const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 00187 ElementAllocas.reserve(AT->getNumElements()); 00188 const Type *ElTy = AT->getElementType(); 00189 for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 00190 AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), 00191 AI->getName() + "." + utostr(i), AI); 00192 ElementAllocas.push_back(NA); 00193 WorkList.push_back(NA); // Add to worklist for recursive processing 00194 } 00195 } 00196 00197 // Now that we have created the alloca instructions that we want to use, 00198 // expand the getelementptr instructions to use them. 00199 // 00200 while (!AI->use_empty()) { 00201 Instruction *User = cast<Instruction>(AI->use_back()); 00202 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); 00203 // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> 00204 unsigned Idx = 00205 (unsigned)cast<ConstantInt>(GEPI->getOperand(2))->getRawValue(); 00206 00207 assert(Idx < ElementAllocas.size() && "Index out of range?"); 00208 AllocaInst *AllocaToUse = ElementAllocas[Idx]; 00209 00210 Value *RepValue; 00211 if (GEPI->getNumOperands() == 3) { 00212 // Do not insert a new getelementptr instruction with zero indices, only 00213 // to have it optimized out later. 00214 RepValue = AllocaToUse; 00215 } else { 00216 // We are indexing deeply into the structure, so we still need a 00217 // getelement ptr instruction to finish the indexing. This may be 00218 // expanded itself once the worklist is rerun. 00219 // 00220 std::string OldName = GEPI->getName(); // Steal the old name. 00221 std::vector<Value*> NewArgs; 00222 NewArgs.push_back(Constant::getNullValue(Type::IntTy)); 00223 NewArgs.insert(NewArgs.end(), GEPI->op_begin()+3, GEPI->op_end()); 00224 GEPI->setName(""); 00225 RepValue = new GetElementPtrInst(AllocaToUse, NewArgs, OldName, GEPI); 00226 } 00227 00228 // Move all of the users over to the new GEP. 00229 GEPI->replaceAllUsesWith(RepValue); 00230 // Delete the old GEP 00231 GEPI->eraseFromParent(); 00232 } 00233 00234 // Finally, delete the Alloca instruction 00235 AI->getParent()->getInstList().erase(AI); 00236 NumReplaced++; 00237 } 00238 00239 return Changed; 00240 } 00241 00242 00243 /// isSafeElementUse - Check to see if this use is an allowed use for a 00244 /// getelementptr instruction of an array aggregate allocation. 00245 /// 00246 int SROA::isSafeElementUse(Value *Ptr) { 00247 for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 00248 I != E; ++I) { 00249 Instruction *User = cast<Instruction>(*I); 00250 switch (User->getOpcode()) { 00251 case Instruction::Load: break; 00252 case Instruction::Store: 00253 // Store is ok if storing INTO the pointer, not storing the pointer 00254 if (User->getOperand(0) == Ptr) return 0; 00255 break; 00256 case Instruction::GetElementPtr: { 00257 GetElementPtrInst *GEP = cast<GetElementPtrInst>(User); 00258 if (GEP->getNumOperands() > 1) { 00259 if (!isa<Constant>(GEP->getOperand(1)) || 00260 !cast<Constant>(GEP->getOperand(1))->isNullValue()) 00261 return 0; // Using pointer arithmetic to navigate the array... 00262 } 00263 if (!isSafeElementUse(GEP)) return 0; 00264 break; 00265 } 00266 default: 00267 DEBUG(std::cerr << " Transformation preventing inst: " << *User); 00268 return 0; 00269 } 00270 } 00271 return 3; // All users look ok :) 00272 } 00273 00274 /// AllUsersAreLoads - Return true if all users of this value are loads. 00275 static bool AllUsersAreLoads(Value *Ptr) { 00276 for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 00277 I != E; ++I) 00278 if (cast<Instruction>(*I)->getOpcode() != Instruction::Load) 00279 return false; 00280 return true; 00281 } 00282 00283 /// isSafeUseOfAllocation - Check to see if this user is an allowed use for an 00284 /// aggregate allocation. 00285 /// 00286 int SROA::isSafeUseOfAllocation(Instruction *User) { 00287 if (!isa<GetElementPtrInst>(User)) return 0; 00288 00289 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); 00290 gep_type_iterator I = gep_type_begin(GEPI), E = gep_type_end(GEPI); 00291 00292 // The GEP is not safe to transform if not of the form "GEP <ptr>, 0, <cst>". 00293 if (I == E || 00294 I.getOperand() != Constant::getNullValue(I.getOperand()->getType())) 00295 return 0; 00296 00297 ++I; 00298 if (I == E) return 0; // ran out of GEP indices?? 00299 00300 // If this is a use of an array allocation, do a bit more checking for sanity. 00301 if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 00302 uint64_t NumElements = AT->getNumElements(); 00303 00304 if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 00305 // Check to make sure that index falls within the array. If not, 00306 // something funny is going on, so we won't do the optimization. 00307 // 00308 if (cast<ConstantInt>(GEPI->getOperand(2))->getRawValue() >= NumElements) 00309 return 0; 00310 00311 // We cannot scalar repl this level of the array unless any array 00312 // sub-indices are in-range constants. In particular, consider: 00313 // A[0][i]. We cannot know that the user isn't doing invalid things like 00314 // allowing i to index an out-of-range subscript that accesses A[1]. 00315 // 00316 // Scalar replacing *just* the outer index of the array is probably not 00317 // going to be a win anyway, so just give up. 00318 for (++I; I != E && isa<ArrayType>(*I); ++I) { 00319 const ArrayType *SubArrayTy = cast<ArrayType>(*I); 00320 uint64_t NumElements = SubArrayTy->getNumElements(); 00321 if (!isa<ConstantInt>(I.getOperand())) return 0; 00322 if (cast<ConstantInt>(I.getOperand())->getRawValue() >= NumElements) 00323 return 0; 00324 } 00325 00326 } else { 00327 // If this is an array index and the index is not constant, we cannot 00328 // promote... that is unless the array has exactly one or two elements in 00329 // it, in which case we CAN promote it, but we have to canonicalize this 00330 // out if this is the only problem. 00331 if ((NumElements == 1 || NumElements == 2) && 00332 AllUsersAreLoads(GEPI)) 00333 return 1; // Canonicalization required! 00334 return 0; 00335 } 00336 } 00337 00338 // If there are any non-simple uses of this getelementptr, make sure to reject 00339 // them. 00340 return isSafeElementUse(GEPI); 00341 } 00342 00343 /// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 00344 /// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 00345 /// or 1 if safe after canonicalization has been performed. 00346 /// 00347 int SROA::isSafeAllocaToScalarRepl(AllocationInst *AI) { 00348 // Loop over the use list of the alloca. We can only transform it if all of 00349 // the users are safe to transform. 00350 // 00351 int isSafe = 3; 00352 for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 00353 I != E; ++I) { 00354 isSafe &= isSafeUseOfAllocation(cast<Instruction>(*I)); 00355 if (isSafe == 0) { 00356 DEBUG(std::cerr << "Cannot transform: " << *AI << " due to user: " 00357 << **I); 00358 return 0; 00359 } 00360 } 00361 // If we require cleanup, isSafe is now 1, otherwise it is 3. 00362 return isSafe; 00363 } 00364 00365 /// CanonicalizeAllocaUsers - If SROA reported that it can promote the specified 00366 /// allocation, but only if cleaned up, perform the cleanups required. 00367 void SROA::CanonicalizeAllocaUsers(AllocationInst *AI) { 00368 // At this point, we know that the end result will be SROA'd and promoted, so 00369 // we can insert ugly code if required so long as sroa+mem2reg will clean it 00370 // up. 00371 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 00372 UI != E; ) { 00373 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(*UI++); 00374 gep_type_iterator I = gep_type_begin(GEPI); 00375 ++I; 00376 00377 if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 00378 uint64_t NumElements = AT->getNumElements(); 00379 00380 if (!isa<ConstantInt>(I.getOperand())) { 00381 if (NumElements == 1) { 00382 GEPI->setOperand(2, Constant::getNullValue(Type::IntTy)); 00383 } else { 00384 assert(NumElements == 2 && "Unhandled case!"); 00385 // All users of the GEP must be loads. At each use of the GEP, insert 00386 // two loads of the appropriate indexed GEP and select between them. 00387 Value *IsOne = BinaryOperator::createSetNE(I.getOperand(), 00388 Constant::getNullValue(I.getOperand()->getType()), 00389 "isone", GEPI); 00390 // Insert the new GEP instructions, which are properly indexed. 00391 std::vector<Value*> Indices(GEPI->op_begin()+1, GEPI->op_end()); 00392 Indices[1] = Constant::getNullValue(Type::IntTy); 00393 Value *ZeroIdx = new GetElementPtrInst(GEPI->getOperand(0), Indices, 00394 GEPI->getName()+".0", GEPI); 00395 Indices[1] = ConstantInt::get(Type::IntTy, 1); 00396 Value *OneIdx = new GetElementPtrInst(GEPI->getOperand(0), Indices, 00397 GEPI->getName()+".1", GEPI); 00398 // Replace all loads of the variable index GEP with loads from both 00399 // indexes and a select. 00400 while (!GEPI->use_empty()) { 00401 LoadInst *LI = cast<LoadInst>(GEPI->use_back()); 00402 Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI); 00403 Value *One = new LoadInst(OneIdx , LI->getName()+".1", LI); 00404 Value *R = new SelectInst(IsOne, One, Zero, LI->getName(), LI); 00405 LI->replaceAllUsesWith(R); 00406 LI->eraseFromParent(); 00407 } 00408 GEPI->eraseFromParent(); 00409 } 00410 } 00411 } 00412 } 00413 } 00414 00415 /// MergeInType - Add the 'In' type to the accumulated type so far. If the 00416 /// types are incompatible, return true, otherwise update Accum and return 00417 /// false. 00418 static bool MergeInType(const Type *In, const Type *&Accum) { 00419 if (!In->isIntegral()) return true; 00420 00421 // If this is our first type, just use it. 00422 if (Accum == Type::VoidTy) { 00423 Accum = In; 00424 } else { 00425 // Otherwise pick whichever type is larger. 00426 if (In->getTypeID() > Accum->getTypeID()) 00427 Accum = In; 00428 } 00429 return false; 00430 } 00431 00432 /// getUIntAtLeastAsBitAs - Return an unsigned integer type that is at least 00433 /// as big as the specified type. If there is no suitable type, this returns 00434 /// null. 00435 const Type *getUIntAtLeastAsBitAs(unsigned NumBits) { 00436 if (NumBits > 64) return 0; 00437 if (NumBits > 32) return Type::ULongTy; 00438 if (NumBits > 16) return Type::UIntTy; 00439 if (NumBits > 8) return Type::UShortTy; 00440 return Type::UByteTy; 00441 } 00442 00443 /// CanConvertToScalar - V is a pointer. If we can convert the pointee to a 00444 /// single scalar integer type, return that type. Further, if the use is not 00445 /// a completely trivial use that mem2reg could promote, set IsNotTrivial. If 00446 /// there are no uses of this pointer, return Type::VoidTy to differentiate from 00447 /// failure. 00448 /// 00449 const Type *SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial) { 00450 const Type *UsedType = Type::VoidTy; // No uses, no forced type. 00451 const TargetData &TD = getAnalysis<TargetData>(); 00452 const PointerType *PTy = cast<PointerType>(V->getType()); 00453 00454 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 00455 Instruction *User = cast<Instruction>(*UI); 00456 00457 if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 00458 if (MergeInType(LI->getType(), UsedType)) 00459 return 0; 00460 00461 } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 00462 // Storing the pointer, not the into the value? 00463 if (SI->getOperand(0) == V) return 0; 00464 00465 // NOTE: We could handle storing of FP imms here! 00466 00467 if (MergeInType(SI->getOperand(0)->getType(), UsedType)) 00468 return 0; 00469 } else if (CastInst *CI = dyn_cast<CastInst>(User)) { 00470 if (!isa<PointerType>(CI->getType())) return 0; 00471 IsNotTrivial = true; 00472 const Type *SubTy = CanConvertToScalar(CI, IsNotTrivial); 00473 if (!SubTy || MergeInType(SubTy, UsedType)) return 0; 00474 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 00475 // Check to see if this is stepping over an element: GEP Ptr, int C 00476 if (GEP->getNumOperands() == 2 && isa<ConstantInt>(GEP->getOperand(1))) { 00477 unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getRawValue(); 00478 unsigned ElSize = TD.getTypeSize(PTy->getElementType()); 00479 unsigned BitOffset = Idx*ElSize*8; 00480 if (BitOffset > 64 || !isPowerOf2_32(ElSize)) return 0; 00481 00482 IsNotTrivial = true; 00483 const Type *SubElt = CanConvertToScalar(GEP, IsNotTrivial); 00484 if (SubElt == 0) return 0; 00485 if (SubElt != Type::VoidTy) { 00486 const Type *NewTy = 00487 getUIntAtLeastAsBitAs(SubElt->getPrimitiveSizeInBits()+BitOffset); 00488 if (NewTy == 0 || MergeInType(NewTy, UsedType)) return 0; 00489 continue; 00490 } 00491 } else if (GEP->getNumOperands() == 3 && 00492 isa<ConstantInt>(GEP->getOperand(1)) && 00493 isa<ConstantInt>(GEP->getOperand(2)) && 00494 cast<Constant>(GEP->getOperand(1))->isNullValue()) { 00495 // We are stepping into an element, e.g. a structure or an array: 00496 // GEP Ptr, int 0, uint C 00497 const Type *AggTy = PTy->getElementType(); 00498 unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getRawValue(); 00499 00500 if (const ArrayType *ATy = dyn_cast<ArrayType>(AggTy)) { 00501 if (Idx >= ATy->getNumElements()) return 0; // Out of range. 00502 } else if (const PackedType *PTy = dyn_cast<PackedType>(AggTy)) { 00503 if (Idx >= PTy->getNumElements()) return 0; // Out of range. 00504 } else if (isa<StructType>(AggTy)) { 00505 // Structs are always ok. 00506 } else { 00507 return 0; 00508 } 00509 const Type *NTy = getUIntAtLeastAsBitAs(TD.getTypeSize(AggTy)*8); 00510 if (NTy == 0 || MergeInType(NTy, UsedType)) return 0; 00511 const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial); 00512 if (SubTy == 0) return 0; 00513 if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType)) 00514 return 0; 00515 continue; // Everything looks ok 00516 } 00517 return 0; 00518 } else { 00519 // Cannot handle this! 00520 return 0; 00521 } 00522 } 00523 00524 return UsedType; 00525 } 00526 00527 /// ConvertToScalar - The specified alloca passes the CanConvertToScalar 00528 /// predicate and is non-trivial. Convert it to something that can be trivially 00529 /// promoted into a register by mem2reg. 00530 void SROA::ConvertToScalar(AllocationInst *AI, const Type *ActualTy) { 00531 DEBUG(std::cerr << "CONVERT TO SCALAR: " << *AI << " TYPE = " 00532 << *ActualTy << "\n"); 00533 ++NumConverted; 00534 00535 BasicBlock *EntryBlock = AI->getParent(); 00536 assert(EntryBlock == &EntryBlock->getParent()->front() && 00537 "Not in the entry block!"); 00538 EntryBlock->getInstList().remove(AI); // Take the alloca out of the program. 00539 00540 // Create and insert the alloca. 00541 AllocaInst *NewAI = new AllocaInst(ActualTy->getUnsignedVersion(), 0, 00542 AI->getName(), EntryBlock->begin()); 00543 ConvertUsesToScalar(AI, NewAI, 0); 00544 delete AI; 00545 } 00546 00547 00548 /// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 00549 /// directly. Offset is an offset from the original alloca, in bits that need 00550 /// to be shifted to the right. By the end of this, there should be no uses of 00551 /// Ptr. 00552 void SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset) { 00553 while (!Ptr->use_empty()) { 00554 Instruction *User = cast<Instruction>(Ptr->use_back()); 00555 00556 if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 00557 // The load is a bit extract from NewAI shifted right by Offset bits. 00558 Value *NV = new LoadInst(NewAI, LI->getName(), LI); 00559 if (Offset && Offset < NV->getType()->getPrimitiveSizeInBits()) 00560 NV = new ShiftInst(Instruction::Shr, NV, 00561 ConstantUInt::get(Type::UByteTy, Offset), 00562 LI->getName(), LI); 00563 if (NV->getType() != LI->getType()) 00564 NV = new CastInst(NV, LI->getType(), LI->getName(), LI); 00565 LI->replaceAllUsesWith(NV); 00566 LI->eraseFromParent(); 00567 } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 00568 assert(SI->getOperand(0) != Ptr && "Consistency error!"); 00569 00570 // Convert the stored type to the actual type, shift it left to insert 00571 // then 'or' into place. 00572 Value *SV = SI->getOperand(0); 00573 if (SV->getType() != NewAI->getType()->getElementType() || Offset != 0) { 00574 Value *Old = new LoadInst(NewAI, NewAI->getName()+".in", SI); 00575 // If SV is signed, convert it to unsigned, so that the next cast zero 00576 // extends the value. 00577 if (SV->getType()->isSigned()) 00578 SV = new CastInst(SV, SV->getType()->getUnsignedVersion(), 00579 SV->getName(), SI); 00580 SV = new CastInst(SV, Old->getType(), SV->getName(), SI); 00581 if (Offset && Offset < SV->getType()->getPrimitiveSizeInBits()) 00582 SV = new ShiftInst(Instruction::Shl, SV, 00583 ConstantUInt::get(Type::UByteTy, Offset), 00584 SV->getName()+".adj", SI); 00585 // Mask out the bits we are about to insert from the old value. 00586 unsigned TotalBits = SV->getType()->getPrimitiveSizeInBits(); 00587 unsigned InsertBits = 00588 SI->getOperand(0)->getType()->getPrimitiveSizeInBits(); 00589 if (TotalBits != InsertBits) { 00590 assert(TotalBits > InsertBits); 00591 uint64_t Mask = ~(((1ULL << InsertBits)-1) << Offset); 00592 if (TotalBits != 64) 00593 Mask = Mask & ((1ULL << TotalBits)-1); 00594 Old = BinaryOperator::createAnd(Old, 00595 ConstantUInt::get(Old->getType(), Mask), 00596 Old->getName()+".mask", SI); 00597 SV = BinaryOperator::createOr(Old, SV, SV->getName()+".ins", SI); 00598 } 00599 } 00600 new StoreInst(SV, NewAI, SI); 00601 SI->eraseFromParent(); 00602 00603 } else if (CastInst *CI = dyn_cast<CastInst>(User)) { 00604 unsigned NewOff = Offset; 00605 const TargetData &TD = getAnalysis<TargetData>(); 00606 if (TD.isBigEndian()) { 00607 // Adjust the pointer. For example, storing 16-bits into a 32-bit 00608 // alloca with just a cast makes it modify the top 16-bits. 00609 const Type *SrcTy = cast<PointerType>(Ptr->getType())->getElementType(); 00610 const Type *DstTy = cast<PointerType>(CI->getType())->getElementType(); 00611 int PtrDiffBits = TD.getTypeSize(SrcTy)*8-TD.getTypeSize(DstTy)*8; 00612 NewOff += PtrDiffBits; 00613 } 00614 ConvertUsesToScalar(CI, NewAI, NewOff); 00615 CI->eraseFromParent(); 00616 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 00617 const PointerType *AggPtrTy = 00618 cast<PointerType>(GEP->getOperand(0)->getType()); 00619 const TargetData &TD = getAnalysis<TargetData>(); 00620 unsigned AggSizeInBits = TD.getTypeSize(AggPtrTy->getElementType())*8; 00621 00622 // Check to see if this is stepping over an element: GEP Ptr, int C 00623 unsigned NewOffset = Offset; 00624 if (GEP->getNumOperands() == 2) { 00625 unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getRawValue(); 00626 unsigned BitOffset = Idx*AggSizeInBits; 00627 00628 if (TD.isLittleEndian()) 00629 NewOffset += BitOffset; 00630 else 00631 NewOffset -= BitOffset; 00632 00633 } else if (GEP->getNumOperands() == 3) { 00634 // We know that operand #2 is zero. 00635 unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getRawValue(); 00636 const Type *AggTy = AggPtrTy->getElementType(); 00637 if (const SequentialType *SeqTy = dyn_cast<SequentialType>(AggTy)) { 00638 unsigned ElSizeBits = TD.getTypeSize(SeqTy->getElementType())*8; 00639 00640 if (TD.isLittleEndian()) 00641 NewOffset += ElSizeBits*Idx; 00642 else 00643 NewOffset += AggSizeInBits-ElSizeBits*(Idx+1); 00644 } else if (const StructType *STy = dyn_cast<StructType>(AggTy)) { 00645 unsigned EltBitOffset = TD.getStructLayout(STy)->MemberOffsets[Idx]*8; 00646 00647 if (TD.isLittleEndian()) 00648 NewOffset += EltBitOffset; 00649 else { 00650 const PointerType *ElPtrTy = cast<PointerType>(GEP->getType()); 00651 unsigned ElSizeBits = TD.getTypeSize(ElPtrTy->getElementType())*8; 00652 NewOffset += AggSizeInBits-(EltBitOffset+ElSizeBits); 00653 } 00654 00655 } else { 00656 assert(0 && "Unsupported operation!"); 00657 abort(); 00658 } 00659 } else { 00660 assert(0 && "Unsupported operation!"); 00661 abort(); 00662 } 00663 ConvertUsesToScalar(GEP, NewAI, NewOffset); 00664 GEP->eraseFromParent(); 00665 } else { 00666 assert(0 && "Unsupported operation!"); 00667 abort(); 00668 } 00669 } 00670 }