ScalarReplAggregates.cpp revision d0fde30ce850b78371fd1386338350591f9ff494
1ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 10ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// This transformation implements the well known scalar replacement of 11ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregates transformation. This xform breaks up alloca instructions of 12ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregate type (structure or array) into individual alloca instructions for 1338aec325604635380421a27e39ab06d55ed2458dChris Lattner// each member (if possible). Then, if possible, it transforms the individual 1438aec325604635380421a27e39ab06d55ed2458dChris Lattner// alloca instructions into nice clean scalar SSA form. 1538aec325604635380421a27e39ab06d55ed2458dChris Lattner// 1638aec325604635380421a27e39ab06d55ed2458dChris Lattner// This combines a simple SRoA algorithm with the Mem2Reg algorithm because 1738aec325604635380421a27e39ab06d55ed2458dChris Lattner// often interact, especially for C++ programs. As such, iterating between 1838aec325604635380421a27e39ab06d55ed2458dChris Lattner// SRoA, then Mem2Reg until we run out of things to promote works well. 19ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 20ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===----------------------------------------------------------------------===// 21ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 22ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Transforms/Scalar.h" 2338aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Constants.h" 2438aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/DerivedTypes.h" 25ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Function.h" 26ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Pass.h" 27ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/iMemory.h" 2838aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Analysis/Dominators.h" 2938aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Target/TargetData.h" 3038aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 316806f5614d2ec260fda954c951d33f58e77ed610Chris Lattner#include "Support/Debug.h" 32ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "Support/Statistic.h" 336806f5614d2ec260fda954c951d33f58e77ed610Chris Lattner#include "Support/StringExtras.h" 34ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 35d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 36d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 37ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnernamespace { 383cfb6b13c0e1d9dee0e35449aa1ac6bd8a0ee906Misha Brukman Statistic<> NumReplaced("scalarrepl", "Number of allocas broken up"); 393cfb6b13c0e1d9dee0e35449aa1ac6bd8a0ee906Misha Brukman Statistic<> NumPromoted("scalarrepl", "Number of allocas promoted"); 40ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 41ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner struct SROA : public FunctionPass { 42ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 43ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 4438aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performScalarRepl(Function &F); 4538aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performPromotion(Function &F); 4638aec325604635380421a27e39ab06d55ed2458dChris Lattner 47a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 48a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // will not alter the CFG, so say so. 49a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 5043f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner AU.addRequired<DominatorTree>(); 5138aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<DominanceFrontier>(); 5238aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<TargetData>(); 53a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner AU.setPreservesCFG(); 54a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner } 55a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner 56ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 57b37923f9a116fe959de1ff93cca173013e35f3daChris Lattner bool isSafeElementUse(Value *Ptr); 585e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner bool isSafeUseOfAllocation(Instruction *User); 59546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner bool isSafeAllocaToPromote(AllocationInst *AI); 60ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); 61ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 62ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 63ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner RegisterOpt<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); 64ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 65ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 66d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the ScalarReplAggregates pass 67ed7b41ea90a17c826f195acbc456c4bb733113d6Chris LattnerPass *createScalarReplAggregatesPass() { return new SROA(); } 68ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 69ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 70ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnerbool SROA::runOnFunction(Function &F) { 71fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = performPromotion(F); 72fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner while (1) { 73fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool LocalChange = performScalarRepl(F); 74fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to repromote if no scalarrepl 75fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner Changed = true; 76fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner LocalChange = performPromotion(F); 77fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to re-scalarrepl if no promotion 78fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner } 7938aec325604635380421a27e39ab06d55ed2458dChris Lattner 8038aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 8138aec325604635380421a27e39ab06d55ed2458dChris Lattner} 8238aec325604635380421a27e39ab06d55ed2458dChris Lattner 8338aec325604635380421a27e39ab06d55ed2458dChris Lattner 8438aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performPromotion(Function &F) { 8538aec325604635380421a27e39ab06d55ed2458dChris Lattner std::vector<AllocaInst*> Allocas; 8638aec325604635380421a27e39ab06d55ed2458dChris Lattner const TargetData &TD = getAnalysis<TargetData>(); 8743f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 8843f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); 8938aec325604635380421a27e39ab06d55ed2458dChris Lattner 9002a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 9138aec325604635380421a27e39ab06d55ed2458dChris Lattner 92fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = false; 9338aec325604635380421a27e39ab06d55ed2458dChris Lattner 9438aec325604635380421a27e39ab06d55ed2458dChris Lattner while (1) { 9538aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.clear(); 9638aec325604635380421a27e39ab06d55ed2458dChris Lattner 9738aec325604635380421a27e39ab06d55ed2458dChris Lattner // Find allocas that are safe to promote, by looking at all instructions in 9838aec325604635380421a27e39ab06d55ed2458dChris Lattner // the entry node 9938aec325604635380421a27e39ab06d55ed2458dChris Lattner for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 10038aec325604635380421a27e39ab06d55ed2458dChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 10138aec325604635380421a27e39ab06d55ed2458dChris Lattner if (isAllocaPromotable(AI, TD)) 10238aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.push_back(AI); 10338aec325604635380421a27e39ab06d55ed2458dChris Lattner 10438aec325604635380421a27e39ab06d55ed2458dChris Lattner if (Allocas.empty()) break; 10538aec325604635380421a27e39ab06d55ed2458dChris Lattner 10643f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner PromoteMemToReg(Allocas, DT, DF, TD); 10738aec325604635380421a27e39ab06d55ed2458dChris Lattner NumPromoted += Allocas.size(); 10838aec325604635380421a27e39ab06d55ed2458dChris Lattner Changed = true; 10938aec325604635380421a27e39ab06d55ed2458dChris Lattner } 11038aec325604635380421a27e39ab06d55ed2458dChris Lattner 11138aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 11238aec325604635380421a27e39ab06d55ed2458dChris Lattner} 11338aec325604635380421a27e39ab06d55ed2458dChris Lattner 11438aec325604635380421a27e39ab06d55ed2458dChris Lattner 11538aec325604635380421a27e39ab06d55ed2458dChris Lattner// performScalarRepl - This algorithm is a simple worklist driven algorithm, 11638aec325604635380421a27e39ab06d55ed2458dChris Lattner// which runs on all of the malloc/alloca instructions in the function, removing 11738aec325604635380421a27e39ab06d55ed2458dChris Lattner// them if they are only used by getelementptr instructions. 11838aec325604635380421a27e39ab06d55ed2458dChris Lattner// 11938aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performScalarRepl(Function &F) { 120ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<AllocationInst*> WorkList; 121ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 122ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Scan the entry basic block, adding any alloca's and mallocs to the worklist 12302a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); 124ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 125ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (AllocationInst *A = dyn_cast<AllocationInst>(I)) 126ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(A); 127ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 128ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Process the worklist 129ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool Changed = false; 130ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner while (!WorkList.empty()) { 131ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocationInst *AI = WorkList.back(); 132ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.pop_back(); 133ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 134ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // We cannot transform the allocation instruction if it is an array 135d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner // allocation (allocations OF arrays are ok though), and an allocation of a 136d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner // scalar value cannot be decomposed at all. 137d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner // 138ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (AI->isArrayAllocation() || 139d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner (!isa<StructType>(AI->getAllocatedType()) && 140d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner !isa<ArrayType>(AI->getAllocatedType()))) continue; 141d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner 1425e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // Check that all of the users of the allocation are capable of being 1435e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // transformed. 144546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner if (!isSafeAllocaToPromote(AI)) 1455e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner continue; 146ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 147ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner DEBUG(std::cerr << "Found inst to xform: " << *AI); 148ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Changed = true; 149ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 150ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<AllocaInst*> ElementAllocas; 151ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 152ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 153ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 154ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 155ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getName() + "." + utostr(i), AI); 156ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.push_back(NA); 157ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 158ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 159ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 1605e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 161ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.reserve(AT->getNumElements()); 162ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner const Type *ElTy = AT->getElementType(); 163ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 164ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *NA = new AllocaInst(ElTy, 0, 165ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getName() + "." + utostr(i), AI); 166ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.push_back(NA); 167ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 168ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 169ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 170ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 171ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Now that we have created the alloca instructions that we want to use, 172ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // expand the getelementptr instructions to use them. 173ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // 174ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 175ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner I != E; ++I) { 176ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Instruction *User = cast<Instruction>(*I); 177ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 178ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> 179c07736a397012499e337c994f7f952b07c709544Chris Lattner uint64_t Idx = cast<ConstantInt>(GEPI->getOperand(2))->getRawValue(); 180ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 181ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner assert(Idx < ElementAllocas.size() && "Index out of range?"); 182ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *AllocaToUse = ElementAllocas[Idx]; 183ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 184ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Value *RepValue; 185ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (GEPI->getNumOperands() == 3) { 186ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Do not insert a new getelementptr instruction with zero indices, 187ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // only to have it optimized out later. 188ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner RepValue = AllocaToUse; 189ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 190ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // We are indexing deeply into the structure, so we still need a 191ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // getelement ptr instruction to finish the indexing. This may be 192ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // expanded itself once the worklist is rerun. 193ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // 194ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::string OldName = GEPI->getName(); // Steal the old name... 195261d686737989a8d7eff0b0f405515a1565303d9Chris Lattner std::vector<Value*> NewArgs; 196261d686737989a8d7eff0b0f405515a1565303d9Chris Lattner NewArgs.push_back(Constant::getNullValue(Type::LongTy)); 197261d686737989a8d7eff0b0f405515a1565303d9Chris Lattner NewArgs.insert(NewArgs.end(), GEPI->op_begin()+3, GEPI->op_end()); 198ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner GEPI->setName(""); 199ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner RepValue = 200261d686737989a8d7eff0b0f405515a1565303d9Chris Lattner new GetElementPtrInst(AllocaToUse, NewArgs, OldName, GEPI); 201ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 202ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 203ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Move all of the users over to the new GEP. 204ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner GEPI->replaceAllUsesWith(RepValue); 205ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Delete the old GEP 206ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner GEPI->getParent()->getInstList().erase(GEPI); 207ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 208ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner assert(0 && "Unexpected instruction type!"); 209ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 210ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 211ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 212ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Finally, delete the Alloca instruction 213ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getParent()->getInstList().erase(AI); 214d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner NumReplaced++; 215ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 216ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 217ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner return Changed; 218ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 2195e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 2205e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 2215e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// isSafeUseOfAllocation - Check to see if this user is an allowed use for an 2225e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// aggregate allocation. 2235e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 2245e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattnerbool SROA::isSafeUseOfAllocation(Instruction *User) { 2255e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 2265e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // The GEP is safe to transform if it is of the form GEP <ptr>, 0, <cst> 2275e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner if (GEPI->getNumOperands() <= 2 || 2285e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner GEPI->getOperand(1) != Constant::getNullValue(Type::LongTy) || 2295e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner !isa<Constant>(GEPI->getOperand(2)) || 2305e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner isa<ConstantExpr>(GEPI->getOperand(2))) 2315e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner return false; 232546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 233546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner // If this is a use of an array allocation, do a bit more checking for 234546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner // sanity. 235546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner if (GEPI->getOperand(2)->getType() == Type::LongTy) { 236546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner const PointerType *PTy =cast<PointerType>(GEPI->getOperand(0)->getType()); 237546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner const ArrayType *AT = cast<ArrayType>(PTy->getElementType()); 238546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner int64_t NumElements = AT->getNumElements(); 239546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 240546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner // Check to make sure that index falls within the array. If not, 241546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner // something funny is going on, so we won't do the optimization. 242546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner // 243546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner if (cast<ConstantSInt>(GEPI->getOperand(2))->getValue() >= NumElements || 244546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner cast<ConstantSInt>(GEPI->getOperand(2))->getValue() < 0) 245546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner return false; 246546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner } 247546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 248546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner // If there are any non-simple uses of this getelementptr, make sure to 249546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner // reject them. 250546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner if (isSafeElementUse(GEPI)) 251546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner return true; 2525e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 253546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner return false; 2545e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 2555e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 256b37923f9a116fe959de1ff93cca173013e35f3daChris Lattner/// isSafeElementUse - Check to see if this use is an allowed use for a 2575e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// getelementptr instruction of an array aggregate allocation. 2585e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 259b37923f9a116fe959de1ff93cca173013e35f3daChris Lattnerbool SROA::isSafeElementUse(Value *Ptr) { 2605e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 2615e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner I != E; ++I) { 2625e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner Instruction *User = cast<Instruction>(*I); 2635e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner switch (User->getOpcode()) { 2648fce16ef1abd92c59ab2b02d59e6d16a1c0ba0b7Chris Lattner case Instruction::Load: break; 2658fce16ef1abd92c59ab2b02d59e6d16a1c0ba0b7Chris Lattner case Instruction::Store: 2668fce16ef1abd92c59ab2b02d59e6d16a1c0ba0b7Chris Lattner // Store is ok if storing INTO the pointer, not storing the pointer 2678fce16ef1abd92c59ab2b02d59e6d16a1c0ba0b7Chris Lattner if (User->getOperand(0) == Ptr) return false; 2688fce16ef1abd92c59ab2b02d59e6d16a1c0ba0b7Chris Lattner break; 2695e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner case Instruction::GetElementPtr: { 2705e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner GetElementPtrInst *GEP = cast<GetElementPtrInst>(User); 2715e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner if (GEP->getNumOperands() > 1) { 2725e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner if (!isa<Constant>(GEP->getOperand(1)) || 2735e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner !cast<Constant>(GEP->getOperand(1))->isNullValue()) 2745e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner return false; // Using pointer arithmetic to navigate the array... 2755e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 2768fce16ef1abd92c59ab2b02d59e6d16a1c0ba0b7Chris Lattner if (!isSafeElementUse(GEP)) return false; 2778fce16ef1abd92c59ab2b02d59e6d16a1c0ba0b7Chris Lattner break; 2785e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 2795e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner default: 2805e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner DEBUG(std::cerr << " Transformation preventing inst: " << *User); 2815e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner return false; 2825e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 2835e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 2845e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner return true; // All users look ok :) 2855e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 2865e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 2875e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 2885e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// isSafeStructAllocaToPromote - Check to see if the specified allocation of a 2895e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// structure can be broken down into elements. 2905e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 291546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattnerbool SROA::isSafeAllocaToPromote(AllocationInst *AI) { 2925e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // Loop over the use list of the alloca. We can only transform it if all of 2935e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // the users are safe to transform. 2945e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // 2955e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 296546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner I != E; ++I) 2975e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner if (!isSafeUseOfAllocation(cast<Instruction>(*I))) { 2985e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner DEBUG(std::cerr << "Cannot transform: " << *AI << " due to user: " 2995e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner << *I); 3005e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner return false; 3015e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 3025e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner return true; 3035e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 304d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 305d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 306