ScalarReplAggregates.cpp revision ed7b41ea90a17c826f195acbc456c4bb733113d6
1ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 3ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// This transformation implements the well known scalar replacement of 4ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregates transformation. This xform breaks up alloca instructions of 5ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregate type (structure or array) into individual alloca instructions for 6ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// each member (if possible). 7ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 8ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===----------------------------------------------------------------------===// 9ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 10ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Transforms/Scalar.h" 11ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Function.h" 12ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Pass.h" 13ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/iMemory.h" 14ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/DerivedTypes.h" 15ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Constants.h" 16ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "Support/StringExtras.h" 17ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "Support/Statistic.h" 18ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 19ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnernamespace { 20ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Statistic<> NumReplaced("scalarrepl", "Number of alloca's broken up"); 21ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 22ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner struct SROA : public FunctionPass { 23ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 24ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 25ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 26ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); 27ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 28ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 29ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner RegisterOpt<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); 30ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 31ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 32ed7b41ea90a17c826f195acbc456c4bb733113d6Chris LattnerPass *createScalarReplAggregatesPass() { return new SROA(); } 33ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 34ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 35ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// runOnFunction - This algorithm is a simple worklist driven algorithm, which 36ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// runs on all of the malloc/alloca instructions in the function, removing them 37ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// if they are only used by getelementptr instructions. 38ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 39ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnerbool SROA::runOnFunction(Function &F) { 40ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<AllocationInst*> WorkList; 41ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 42ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Scan the entry basic block, adding any alloca's and mallocs to the worklist 43ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner BasicBlock &BB = F.getEntryNode(); 44ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 45ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (AllocationInst *A = dyn_cast<AllocationInst>(I)) 46ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(A); 47ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 48ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Process the worklist 49ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool Changed = false; 50ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner while (!WorkList.empty()) { 51ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocationInst *AI = WorkList.back(); 52ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.pop_back(); 53ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 54ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // We cannot transform the allocation instruction if it is an array 55ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // allocation, and an allocation of a scalar value cannot be decomposed 56ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (AI->isArrayAllocation() || 57ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner (!isa<StructType>(AI->getAllocatedType()) /*&& 58ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner !isa<ArrayType>(AI->getAllocatedType())*/ 59ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner )) continue; 60ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 61ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Loop over the use list of the alloca. We can only transform it if there 62ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // are only getelementptr instructions (with a zero first index) and free 63ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // instructions. 64ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // 65ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool CannotTransform = false; 66ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 67ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner I != E; ++I) { 68ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Instruction *User = cast<Instruction>(*I); 69ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 70ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // The GEP is safe to transform if it is of the form GEP <ptr>, 0, <cst> 71ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (GEPI->getNumOperands() <= 2 || 72ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner GEPI->getOperand(1) != Constant::getNullValue(Type::LongTy) || 73ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner !isa<Constant>(GEPI->getOperand(2)) || 74ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner isa<ConstantExpr>(GEPI->getOperand(2))) { 75ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner DEBUG(std::cerr << "Cannot transform: " << *AI << " due to user: " 76ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner << User); 77ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner CannotTransform = true; 78ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner break; 79ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 80ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 81ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner DEBUG(std::cerr << "Cannot transform: " << *AI << " due to user: " 82ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner << User); 83ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner CannotTransform = true; 84ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner break; 85ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 86ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 87ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 88ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (CannotTransform) continue; 89ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 90ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner DEBUG(std::cerr << "Found inst to xform: " << *AI); 91ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Changed = true; 92ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 93ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<AllocaInst*> ElementAllocas; 94ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 95ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 96ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 97ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 98ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getName() + "." + utostr(i), AI); 99ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.push_back(NA); 100ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 101ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 102ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 103ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 104ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.reserve(AT->getNumElements()); 105ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner const Type *ElTy = AT->getElementType(); 106ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 107ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *NA = new AllocaInst(ElTy, 0, 108ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getName() + "." + utostr(i), AI); 109ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.push_back(NA); 110ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 111ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 112ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 113ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 114ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Now that we have created the alloca instructions that we want to use, 115ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // expand the getelementptr instructions to use them. 116ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // 117ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 118ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner I != E; ++I) { 119ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Instruction *User = cast<Instruction>(*I); 120ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 121ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> 122ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner uint64_t Idx; 123ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(GEPI->getOperand(2))) 124ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Idx = CSI->getValue(); 125ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner else 126ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Idx = cast<ConstantUInt>(GEPI->getOperand(2))->getValue(); 127ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 128ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner assert(Idx < ElementAllocas.size() && "Index out of range?"); 129ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *AllocaToUse = ElementAllocas[Idx]; 130ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 131ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Value *RepValue; 132ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (GEPI->getNumOperands() == 3) { 133ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Do not insert a new getelementptr instruction with zero indices, 134ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // only to have it optimized out later. 135ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner RepValue = AllocaToUse; 136ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 137ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // We are indexing deeply into the structure, so we still need a 138ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // getelement ptr instruction to finish the indexing. This may be 139ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // expanded itself once the worklist is rerun. 140ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // 141ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::string OldName = GEPI->getName(); // Steal the old name... 142ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner GEPI->setName(""); 143ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner RepValue = 144ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner new GetElementPtrInst(AllocaToUse, 145ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<Value*>(GEPI->op_begin()+3, 146ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner GEPI->op_end()), 147ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner OldName, GEPI); 148ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 149ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 150ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Move all of the users over to the new GEP. 151ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner GEPI->replaceAllUsesWith(RepValue); 152ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Delete the old GEP 153ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner GEPI->getParent()->getInstList().erase(GEPI); 154ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 155ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner assert(0 && "Unexpected instruction type!"); 156ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 157ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 158ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 159ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Finally, delete the Alloca instruction 160ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getParent()->getInstList().erase(AI); 161ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 162ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 163ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner return Changed; 164ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 165