ScalarReplAggregates.cpp revision 9525528a7dc5462b6374d38c81ba5c07b11741fe
1ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 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. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 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" 27d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 2838aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Analysis/Dominators.h" 2938aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Target/TargetData.h" 3038aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 319525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Debug.h" 32a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 33a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/MathExtras.h" 349525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Visibility.h" 35551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 36551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/StringExtras.h" 37dac58ad983c62b49629e1f2969f4e0a621167d63Chris Lattner#include <iostream> 38d8664730942beb911327336d1f9db8e7efcd6813Chris Lattnerusing namespace llvm; 39d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 40ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnernamespace { 413cfb6b13c0e1d9dee0e35449aa1ac6bd8a0ee906Misha Brukman Statistic<> NumReplaced("scalarrepl", "Number of allocas broken up"); 423cfb6b13c0e1d9dee0e35449aa1ac6bd8a0ee906Misha Brukman Statistic<> NumPromoted("scalarrepl", "Number of allocas promoted"); 43a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Statistic<> NumConverted("scalarrepl", 44a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner "Number of aggregates converted to scalar"); 45ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 469525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN SROA : public FunctionPass { 47ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 48ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 4938aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performScalarRepl(Function &F); 5038aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performPromotion(Function &F); 5138aec325604635380421a27e39ab06d55ed2458dChris Lattner 52a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 53a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // will not alter the CFG, so say so. 54a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 5543f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner AU.addRequired<DominatorTree>(); 5638aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<DominanceFrontier>(); 5738aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<TargetData>(); 58a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner AU.setPreservesCFG(); 59a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner } 60a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner 61ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 62f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner int isSafeElementUse(Value *Ptr); 63f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner int isSafeUseOfAllocation(Instruction *User); 64f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner int isSafeAllocaToScalarRepl(AllocationInst *AI); 65f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner void CanonicalizeAllocaUsers(AllocationInst *AI); 66ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); 67a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 68a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *CanConvertToScalar(Value *V, bool &IsNotTrivial); 69a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner void ConvertToScalar(AllocationInst *AI, const Type *Ty); 70a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset); 71ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 72ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 73ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner RegisterOpt<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); 74ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 75ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 76d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the ScalarReplAggregates pass 774b5015604908e9296800991a7c538a255356428fChris LattnerFunctionPass *llvm::createScalarReplAggregatesPass() { return new SROA(); } 78ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 79ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 80ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnerbool SROA::runOnFunction(Function &F) { 81fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = performPromotion(F); 82fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner while (1) { 83fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool LocalChange = performScalarRepl(F); 84fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to repromote if no scalarrepl 85fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner Changed = true; 86fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner LocalChange = performPromotion(F); 87fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to re-scalarrepl if no promotion 88fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner } 8938aec325604635380421a27e39ab06d55ed2458dChris Lattner 9038aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 9138aec325604635380421a27e39ab06d55ed2458dChris Lattner} 9238aec325604635380421a27e39ab06d55ed2458dChris Lattner 9338aec325604635380421a27e39ab06d55ed2458dChris Lattner 9438aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performPromotion(Function &F) { 9538aec325604635380421a27e39ab06d55ed2458dChris Lattner std::vector<AllocaInst*> Allocas; 9638aec325604635380421a27e39ab06d55ed2458dChris Lattner const TargetData &TD = getAnalysis<TargetData>(); 9743f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 9843f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); 9938aec325604635380421a27e39ab06d55ed2458dChris Lattner 10002a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 10138aec325604635380421a27e39ab06d55ed2458dChris Lattner 102fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = false; 103fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 10438aec325604635380421a27e39ab06d55ed2458dChris Lattner while (1) { 10538aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.clear(); 10638aec325604635380421a27e39ab06d55ed2458dChris Lattner 10738aec325604635380421a27e39ab06d55ed2458dChris Lattner // Find allocas that are safe to promote, by looking at all instructions in 10838aec325604635380421a27e39ab06d55ed2458dChris Lattner // the entry node 10938aec325604635380421a27e39ab06d55ed2458dChris Lattner for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 11038aec325604635380421a27e39ab06d55ed2458dChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 11138aec325604635380421a27e39ab06d55ed2458dChris Lattner if (isAllocaPromotable(AI, TD)) 11238aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.push_back(AI); 11338aec325604635380421a27e39ab06d55ed2458dChris Lattner 11438aec325604635380421a27e39ab06d55ed2458dChris Lattner if (Allocas.empty()) break; 11538aec325604635380421a27e39ab06d55ed2458dChris Lattner 11643f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner PromoteMemToReg(Allocas, DT, DF, TD); 11738aec325604635380421a27e39ab06d55ed2458dChris Lattner NumPromoted += Allocas.size(); 11838aec325604635380421a27e39ab06d55ed2458dChris Lattner Changed = true; 11938aec325604635380421a27e39ab06d55ed2458dChris Lattner } 12038aec325604635380421a27e39ab06d55ed2458dChris Lattner 12138aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 12238aec325604635380421a27e39ab06d55ed2458dChris Lattner} 12338aec325604635380421a27e39ab06d55ed2458dChris Lattner 12438aec325604635380421a27e39ab06d55ed2458dChris Lattner// performScalarRepl - This algorithm is a simple worklist driven algorithm, 12538aec325604635380421a27e39ab06d55ed2458dChris Lattner// which runs on all of the malloc/alloca instructions in the function, removing 12638aec325604635380421a27e39ab06d55ed2458dChris Lattner// them if they are only used by getelementptr instructions. 12738aec325604635380421a27e39ab06d55ed2458dChris Lattner// 12838aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performScalarRepl(Function &F) { 129ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<AllocationInst*> WorkList; 130ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 131ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Scan the entry basic block, adding any alloca's and mallocs to the worklist 13202a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); 133ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 134ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (AllocationInst *A = dyn_cast<AllocationInst>(I)) 135ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(A); 136ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 137ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Process the worklist 138ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool Changed = false; 139ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner while (!WorkList.empty()) { 140ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocationInst *AI = WorkList.back(); 141ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.pop_back(); 142a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 143a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // If we can turn this aggregate value (potentially with casts) into a 144a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // simple scalar value that can be mem2reg'd into a register value. 145a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner bool IsNotTrivial = false; 146a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (const Type *ActualType = CanConvertToScalar(AI, IsNotTrivial)) 147df4f226cdcbe853984ddda10aa0d53590d35b97eChris Lattner if (IsNotTrivial && ActualType != Type::VoidTy) { 148a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner ConvertToScalar(AI, ActualType); 149a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Changed = true; 150a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner continue; 151a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 152ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 153ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // We cannot transform the allocation instruction if it is an array 154d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner // allocation (allocations OF arrays are ok though), and an allocation of a 155d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner // scalar value cannot be decomposed at all. 156d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner // 157ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (AI->isArrayAllocation() || 158d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner (!isa<StructType>(AI->getAllocatedType()) && 159d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner !isa<ArrayType>(AI->getAllocatedType()))) continue; 160d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner 1615e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // Check that all of the users of the allocation are capable of being 1625e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // transformed. 163f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner switch (isSafeAllocaToScalarRepl(AI)) { 164f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner default: assert(0 && "Unexpected value!"); 165f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case 0: // Not safe to scalar replace. 1665e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner continue; 167f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case 1: // Safe, but requires cleanup/canonicalizations first 168f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner CanonicalizeAllocaUsers(AI); 169f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case 3: // Safe to scalar replace. 170f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner break; 171f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 172ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 173ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner DEBUG(std::cerr << "Found inst to xform: " << *AI); 174ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner Changed = true; 175fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 176ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<AllocaInst*> ElementAllocas; 177ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 178ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 179ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 18014b0529532904b9e5a1e34526b4a3209f3e5bc62Nate Begeman AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 18114b0529532904b9e5a1e34526b4a3209f3e5bc62Nate Begeman AI->getAlignment(), 182ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getName() + "." + utostr(i), AI); 183ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.push_back(NA); 184ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 185ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 186ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 1875e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 188ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.reserve(AT->getNumElements()); 189ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner const Type *ElTy = AT->getElementType(); 190ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 19114b0529532904b9e5a1e34526b4a3209f3e5bc62Nate Begeman AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), 192ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getName() + "." + utostr(i), AI); 193ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner ElementAllocas.push_back(NA); 194ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 195ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 196ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 197fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 198ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Now that we have created the alloca instructions that we want to use, 199ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // expand the getelementptr instructions to use them. 200ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // 2018430a4545c2743568aee94c39e3912795ce463ecChris Lattner while (!AI->use_empty()) { 2028430a4545c2743568aee94c39e3912795ce463ecChris Lattner Instruction *User = cast<Instruction>(AI->use_back()); 203d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); 204d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> 205fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman unsigned Idx = 2062cc34627bb870b6a304efe673736fed2f6a63800Chris Lattner (unsigned)cast<ConstantInt>(GEPI->getOperand(2))->getRawValue(); 207fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 208d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner assert(Idx < ElementAllocas.size() && "Index out of range?"); 209d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner AllocaInst *AllocaToUse = ElementAllocas[Idx]; 210fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 211d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Value *RepValue; 212d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (GEPI->getNumOperands() == 3) { 213d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // Do not insert a new getelementptr instruction with zero indices, only 214d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // to have it optimized out later. 215d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner RepValue = AllocaToUse; 216ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } else { 217d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // We are indexing deeply into the structure, so we still need a 218d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // getelement ptr instruction to finish the indexing. This may be 219d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // expanded itself once the worklist is rerun. 220d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // 221d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner std::string OldName = GEPI->getName(); // Steal the old name. 222d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner std::vector<Value*> NewArgs; 223d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner NewArgs.push_back(Constant::getNullValue(Type::IntTy)); 224d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner NewArgs.insert(NewArgs.end(), GEPI->op_begin()+3, GEPI->op_end()); 225d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GEPI->setName(""); 226d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner RepValue = new GetElementPtrInst(AllocaToUse, NewArgs, OldName, GEPI); 227ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 228fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 229d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // Move all of the users over to the new GEP. 230d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GEPI->replaceAllUsesWith(RepValue); 231d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // Delete the old GEP 232d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GEPI->eraseFromParent(); 233ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 234ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 235ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Finally, delete the Alloca instruction 236ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AI->getParent()->getInstList().erase(AI); 237d10376bee5138d30a290f56ad84a0b26a9752bccChris Lattner NumReplaced++; 238ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 239ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 240ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner return Changed; 241ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 2425e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 2435e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 244f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// isSafeElementUse - Check to see if this use is an allowed use for a 245f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// getelementptr instruction of an array aggregate allocation. 246f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// 247f5990edc877c4e63503c589928a00ec6ec751830Chris Lattnerint SROA::isSafeElementUse(Value *Ptr) { 248f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 249f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner I != E; ++I) { 250f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner Instruction *User = cast<Instruction>(*I); 251f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner switch (User->getOpcode()) { 252f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::Load: break; 253f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::Store: 254f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner // Store is ok if storing INTO the pointer, not storing the pointer 255f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner if (User->getOperand(0) == Ptr) return 0; 256f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner break; 257f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::GetElementPtr: { 258f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner GetElementPtrInst *GEP = cast<GetElementPtrInst>(User); 259f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner if (GEP->getNumOperands() > 1) { 260f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner if (!isa<Constant>(GEP->getOperand(1)) || 261f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner !cast<Constant>(GEP->getOperand(1))->isNullValue()) 262f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return 0; // Using pointer arithmetic to navigate the array... 263f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 264f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner if (!isSafeElementUse(GEP)) return 0; 265f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner break; 266f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 267f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner default: 268f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner DEBUG(std::cerr << " Transformation preventing inst: " << *User); 269f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return 0; 270f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 271f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 272f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return 3; // All users look ok :) 273f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner} 274f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner 275d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner/// AllUsersAreLoads - Return true if all users of this value are loads. 276d878ecd904e4469344a2274f9784422c2c68b81cChris Lattnerstatic bool AllUsersAreLoads(Value *Ptr) { 277d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 278d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner I != E; ++I) 279d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (cast<Instruction>(*I)->getOpcode() != Instruction::Load) 280d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner return false; 281fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman return true; 282d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner} 283d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner 2845e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// isSafeUseOfAllocation - Check to see if this user is an allowed use for an 2855e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// aggregate allocation. 2865e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 287f5990edc877c4e63503c589928a00ec6ec751830Chris Lattnerint SROA::isSafeUseOfAllocation(Instruction *User) { 288f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner if (!isa<GetElementPtrInst>(User)) return 0; 289546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 290be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); 291be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner gep_type_iterator I = gep_type_begin(GEPI), E = gep_type_end(GEPI); 292be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner 29325de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // The GEP is not safe to transform if not of the form "GEP <ptr>, 0, <cst>". 294be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner if (I == E || 295be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner I.getOperand() != Constant::getNullValue(I.getOperand()->getType())) 296f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return 0; 297be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner 298be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner ++I; 299d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (I == E) return 0; // ran out of GEP indices?? 300546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 301be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner // If this is a use of an array allocation, do a bit more checking for sanity. 302be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 303be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner uint64_t NumElements = AT->getNumElements(); 304d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner 305d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) { 306d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // Check to make sure that index falls within the array. If not, 307d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // something funny is going on, so we won't do the optimization. 308d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // 309d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (cast<ConstantInt>(GEPI->getOperand(2))->getRawValue() >= NumElements) 310d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner return 0; 311fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 31225de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // We cannot scalar repl this level of the array unless any array 31325de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // sub-indices are in-range constants. In particular, consider: 31425de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // A[0][i]. We cannot know that the user isn't doing invalid things like 31525de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // allowing i to index an out-of-range subscript that accesses A[1]. 31625de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // 31725de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // Scalar replacing *just* the outer index of the array is probably not 31825de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // going to be a win anyway, so just give up. 31925de486263abc1882498a8701e3eb29ee0804c4eChris Lattner for (++I; I != E && isa<ArrayType>(*I); ++I) { 32025de486263abc1882498a8701e3eb29ee0804c4eChris Lattner const ArrayType *SubArrayTy = cast<ArrayType>(*I); 32125de486263abc1882498a8701e3eb29ee0804c4eChris Lattner uint64_t NumElements = SubArrayTy->getNumElements(); 32225de486263abc1882498a8701e3eb29ee0804c4eChris Lattner if (!isa<ConstantInt>(I.getOperand())) return 0; 32325de486263abc1882498a8701e3eb29ee0804c4eChris Lattner if (cast<ConstantInt>(I.getOperand())->getRawValue() >= NumElements) 32425de486263abc1882498a8701e3eb29ee0804c4eChris Lattner return 0; 32525de486263abc1882498a8701e3eb29ee0804c4eChris Lattner } 32625de486263abc1882498a8701e3eb29ee0804c4eChris Lattner 327d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } else { 328d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // If this is an array index and the index is not constant, we cannot 329d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // promote... that is unless the array has exactly one or two elements in 330d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // it, in which case we CAN promote it, but we have to canonicalize this 331d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // out if this is the only problem. 33225de486263abc1882498a8701e3eb29ee0804c4eChris Lattner if ((NumElements == 1 || NumElements == 2) && 33325de486263abc1882498a8701e3eb29ee0804c4eChris Lattner AllUsersAreLoads(GEPI)) 33425de486263abc1882498a8701e3eb29ee0804c4eChris Lattner return 1; // Canonicalization required! 335f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return 0; 336d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 3375e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 338be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner 339be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner // If there are any non-simple uses of this getelementptr, make sure to reject 340be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner // them. 341be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner return isSafeElementUse(GEPI); 3425e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 3435e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 344f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 345f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 346f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// or 1 if safe after canonicalization has been performed. 3475e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 348f5990edc877c4e63503c589928a00ec6ec751830Chris Lattnerint SROA::isSafeAllocaToScalarRepl(AllocationInst *AI) { 3495e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // Loop over the use list of the alloca. We can only transform it if all of 3505e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // the users are safe to transform. 3515e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // 352f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner int isSafe = 3; 3535e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 354f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner I != E; ++I) { 355f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner isSafe &= isSafeUseOfAllocation(cast<Instruction>(*I)); 356f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner if (isSafe == 0) { 3575e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner DEBUG(std::cerr << "Cannot transform: " << *AI << " due to user: " 358f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner << **I); 359f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return 0; 3605e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 361f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 362f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner // If we require cleanup, isSafe is now 1, otherwise it is 3. 363f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return isSafe; 364f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner} 365f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner 366f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// CanonicalizeAllocaUsers - If SROA reported that it can promote the specified 367f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// allocation, but only if cleaned up, perform the cleanups required. 368f5990edc877c4e63503c589928a00ec6ec751830Chris Lattnervoid SROA::CanonicalizeAllocaUsers(AllocationInst *AI) { 369d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // At this point, we know that the end result will be SROA'd and promoted, so 370d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // we can insert ugly code if required so long as sroa+mem2reg will clean it 371d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // up. 372d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 373d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner UI != E; ) { 374d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GetElementPtrInst *GEPI = cast<GetElementPtrInst>(*UI++); 37596326f9d312585532c95dcc31626f45f16cd5dd8Reid Spencer gep_type_iterator I = gep_type_begin(GEPI); 376d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner ++I; 377d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner 378d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 379d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner uint64_t NumElements = AT->getNumElements(); 380fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 381d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (!isa<ConstantInt>(I.getOperand())) { 382d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (NumElements == 1) { 383d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GEPI->setOperand(2, Constant::getNullValue(Type::IntTy)); 384d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } else { 385d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner assert(NumElements == 2 && "Unhandled case!"); 386d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // All users of the GEP must be loads. At each use of the GEP, insert 387d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // two loads of the appropriate indexed GEP and select between them. 388d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Value *IsOne = BinaryOperator::createSetNE(I.getOperand(), 389d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Constant::getNullValue(I.getOperand()->getType()), 390d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner "isone", GEPI); 391d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // Insert the new GEP instructions, which are properly indexed. 392d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner std::vector<Value*> Indices(GEPI->op_begin()+1, GEPI->op_end()); 393d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Indices[1] = Constant::getNullValue(Type::IntTy); 394d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Value *ZeroIdx = new GetElementPtrInst(GEPI->getOperand(0), Indices, 395d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GEPI->getName()+".0", GEPI); 396d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Indices[1] = ConstantInt::get(Type::IntTy, 1); 397d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Value *OneIdx = new GetElementPtrInst(GEPI->getOperand(0), Indices, 398d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GEPI->getName()+".1", GEPI); 399d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // Replace all loads of the variable index GEP with loads from both 400d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // indexes and a select. 401d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner while (!GEPI->use_empty()) { 402d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner LoadInst *LI = cast<LoadInst>(GEPI->use_back()); 403d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI); 404d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Value *One = new LoadInst(OneIdx , LI->getName()+".1", LI); 405d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner Value *R = new SelectInst(IsOne, One, Zero, LI->getName(), LI); 406d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner LI->replaceAllUsesWith(R); 407d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner LI->eraseFromParent(); 408d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 409d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner GEPI->eraseFromParent(); 410d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 411d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 412d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 413d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 4145e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 415a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 416a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// MergeInType - Add the 'In' type to the accumulated type so far. If the 417a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// types are incompatible, return true, otherwise update Accum and return 418a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// false. 419de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 420de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// There are two cases we handle here: 421de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 1) An effectively integer union, where the pieces are stored into as 422de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// smaller integers (common with byte swap and other idioms). 423de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 2) A union of a vector and its elements. Here we turn element accesses 424de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// into insert/extract element operations. 425a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattnerstatic bool MergeInType(const Type *In, const Type *&Accum) { 426a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // If this is our first type, just use it. 427de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner const PackedType *PTy; 428de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (Accum == Type::VoidTy || In == Accum) { 429a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Accum = In; 430de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } else if (In->isIntegral() && Accum->isIntegral()) { // integer union. 431a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Otherwise pick whichever type is larger. 432a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (In->getTypeID() > Accum->getTypeID()) 433a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Accum = In; 434de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } else if ((PTy = dyn_cast<PackedType>(Accum)) && 435de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner PTy->getElementType() == In) { 436de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // Accum is a vector, and we are accessing an element: ok. 437de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } else if ((PTy = dyn_cast<PackedType>(In)) && 438de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner PTy->getElementType() == Accum) { 439de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // In is a vector, and accum is an element: ok, remember In. 440de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner Accum = In; 441de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } else { 442de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner return true; 443a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 444a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return false; 445a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 446a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 447a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// getUIntAtLeastAsBitAs - Return an unsigned integer type that is at least 448a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// as big as the specified type. If there is no suitable type, this returns 449a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// null. 450a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattnerconst Type *getUIntAtLeastAsBitAs(unsigned NumBits) { 451a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (NumBits > 64) return 0; 452a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (NumBits > 32) return Type::ULongTy; 453a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (NumBits > 16) return Type::UIntTy; 454a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (NumBits > 8) return Type::UShortTy; 455a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return Type::UByteTy; 456a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 457a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 458a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// CanConvertToScalar - V is a pointer. If we can convert the pointee to a 459a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// single scalar integer type, return that type. Further, if the use is not 460a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// a completely trivial use that mem2reg could promote, set IsNotTrivial. If 461a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// there are no uses of this pointer, return Type::VoidTy to differentiate from 462a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// failure. 463a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// 464a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattnerconst Type *SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial) { 465a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *UsedType = Type::VoidTy; // No uses, no forced type. 466a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const TargetData &TD = getAnalysis<TargetData>(); 467a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const PointerType *PTy = cast<PointerType>(V->getType()); 468a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 469a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 470a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Instruction *User = cast<Instruction>(*UI); 471a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 472a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 473a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (MergeInType(LI->getType(), UsedType)) 474a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return 0; 475a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 476a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 477a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Storing the pointer, not the into the value? 478a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (SI->getOperand(0) == V) return 0; 479a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 480de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // NOTE: We could handle storing of FP imms into integers here! 481a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 482a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (MergeInType(SI->getOperand(0)->getType(), UsedType)) 483a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return 0; 484a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (CastInst *CI = dyn_cast<CastInst>(User)) { 485a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (!isa<PointerType>(CI->getType())) return 0; 486a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner IsNotTrivial = true; 487a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *SubTy = CanConvertToScalar(CI, IsNotTrivial); 488a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (!SubTy || MergeInType(SubTy, UsedType)) return 0; 489a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 490a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Check to see if this is stepping over an element: GEP Ptr, int C 491a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (GEP->getNumOperands() == 2 && isa<ConstantInt>(GEP->getOperand(1))) { 492a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getRawValue(); 493a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned ElSize = TD.getTypeSize(PTy->getElementType()); 494a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned BitOffset = Idx*ElSize*8; 495a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (BitOffset > 64 || !isPowerOf2_32(ElSize)) return 0; 496a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 497a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner IsNotTrivial = true; 498a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *SubElt = CanConvertToScalar(GEP, IsNotTrivial); 499a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (SubElt == 0) return 0; 500de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (SubElt != Type::VoidTy && SubElt->isInteger()) { 501a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *NewTy = 502a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner getUIntAtLeastAsBitAs(SubElt->getPrimitiveSizeInBits()+BitOffset); 503a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (NewTy == 0 || MergeInType(NewTy, UsedType)) return 0; 504a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner continue; 505a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 506a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (GEP->getNumOperands() == 3 && 507a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner isa<ConstantInt>(GEP->getOperand(1)) && 508a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner isa<ConstantInt>(GEP->getOperand(2)) && 509a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner cast<Constant>(GEP->getOperand(1))->isNullValue()) { 510a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // We are stepping into an element, e.g. a structure or an array: 511a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // GEP Ptr, int 0, uint C 512a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *AggTy = PTy->getElementType(); 513a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getRawValue(); 514a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 515a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (const ArrayType *ATy = dyn_cast<ArrayType>(AggTy)) { 516a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (Idx >= ATy->getNumElements()) return 0; // Out of range. 517de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } else if (const PackedType *PackedTy = dyn_cast<PackedType>(AggTy)) { 518de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // Getting an element of the packed vector. 519de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (Idx >= PackedTy->getNumElements()) return 0; // Out of range. 520de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner 521de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // Merge in the packed type. 522de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (MergeInType(PackedTy, UsedType)) return 0; 523de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner 524de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial); 525de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (SubTy == 0) return 0; 526de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner 527de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType)) 528de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner return 0; 529de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner 530de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // We'll need to change this to an insert/extract element operation. 531de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner IsNotTrivial = true; 532de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner continue; // Everything looks ok 533de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner 534a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (isa<StructType>(AggTy)) { 535a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Structs are always ok. 536a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else { 537a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return 0; 538a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 539a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *NTy = getUIntAtLeastAsBitAs(TD.getTypeSize(AggTy)*8); 540a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (NTy == 0 || MergeInType(NTy, UsedType)) return 0; 541a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial); 542a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (SubTy == 0) return 0; 543a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType)) 544a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return 0; 545a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner continue; // Everything looks ok 546a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 547a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return 0; 548a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else { 549a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Cannot handle this! 550a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return 0; 551a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 552a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 553a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 554a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner return UsedType; 555a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 556a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 557a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// ConvertToScalar - The specified alloca passes the CanConvertToScalar 558a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// predicate and is non-trivial. Convert it to something that can be trivially 559a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// promoted into a register by mem2reg. 560a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattnervoid SROA::ConvertToScalar(AllocationInst *AI, const Type *ActualTy) { 561a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner DEBUG(std::cerr << "CONVERT TO SCALAR: " << *AI << " TYPE = " 562a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner << *ActualTy << "\n"); 563a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner ++NumConverted; 564a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 565a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner BasicBlock *EntryBlock = AI->getParent(); 566a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner assert(EntryBlock == &EntryBlock->getParent()->front() && 567a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner "Not in the entry block!"); 568a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner EntryBlock->getInstList().remove(AI); // Take the alloca out of the program. 569a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 570de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (ActualTy->isInteger()) 571de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner ActualTy = ActualTy->getUnsignedVersion(); 572de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner 573a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Create and insert the alloca. 574de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner AllocaInst *NewAI = new AllocaInst(ActualTy, 0, AI->getName(), 575de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner EntryBlock->begin()); 576a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner ConvertUsesToScalar(AI, NewAI, 0); 577a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner delete AI; 578a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 579a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 580a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 581a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 582de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// directly. This happens when we are converting an "integer union" to a 583de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// single integer scalar, or when we are converting a "vector union" to a 584de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// vector with insert/extractelement instructions. 585de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 586de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// Offset is an offset from the original alloca, in bits that need to be 587de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// shifted to the right. By the end of this, there should be no uses of Ptr. 588a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattnervoid SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset) { 589de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner bool isVectorInsert = isa<PackedType>(NewAI->getType()->getElementType()); 590a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner while (!Ptr->use_empty()) { 591a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Instruction *User = cast<Instruction>(Ptr->use_back()); 592a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 593a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 594a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // The load is a bit extract from NewAI shifted right by Offset bits. 595a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Value *NV = new LoadInst(NewAI, LI->getName(), LI); 596de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (NV->getType() != LI->getType()) { 597de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (const PackedType *PTy = dyn_cast<PackedType>(NV->getType())) { 598de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // Must be an element access. 599de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner unsigned Elt = Offset/PTy->getElementType()->getPrimitiveSizeInBits(); 600de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner NV = new ExtractElementInst(NV, ConstantUInt::get(Type::UIntTy, Elt), 601de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner "tmp", LI); 602de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } else { 603de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner assert(NV->getType()->isInteger() && "Unknown promotion!"); 604de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (Offset && Offset < NV->getType()->getPrimitiveSizeInBits()) 605de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner NV = new ShiftInst(Instruction::Shr, NV, 606de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner ConstantUInt::get(Type::UByteTy, Offset), 607de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner LI->getName(), LI); 608de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner NV = new CastInst(NV, LI->getType(), LI->getName(), LI); 609de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } 610de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } 611a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner LI->replaceAllUsesWith(NV); 612a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner LI->eraseFromParent(); 613a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 614a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner assert(SI->getOperand(0) != Ptr && "Consistency error!"); 615a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 616a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Convert the stored type to the actual type, shift it left to insert 617a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // then 'or' into place. 618a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Value *SV = SI->getOperand(0); 619de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner const Type *AllocaType = NewAI->getType()->getElementType(); 620de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (SV->getType() != AllocaType) { 621a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Value *Old = new LoadInst(NewAI, NewAI->getName()+".in", SI); 622de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner 623de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (const PackedType *PTy = dyn_cast<PackedType>(AllocaType)) { 624de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // Must be an element insertion. 625de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner unsigned Elt = Offset/PTy->getElementType()->getPrimitiveSizeInBits(); 626de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner SV = new InsertElementInst(Old, SV, 627de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner ConstantUInt::get(Type::UIntTy, Elt), 628de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner "tmp", SI); 629de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } else { 630de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // If SV is signed, convert it to unsigned, so that the next cast zero 631de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // extends the value. 632de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (SV->getType()->isSigned()) 633de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner SV = new CastInst(SV, SV->getType()->getUnsignedVersion(), 634de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner SV->getName(), SI); 635de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner SV = new CastInst(SV, Old->getType(), SV->getName(), SI); 636de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (Offset && Offset < SV->getType()->getPrimitiveSizeInBits()) 637de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner SV = new ShiftInst(Instruction::Shl, SV, 638de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner ConstantUInt::get(Type::UByteTy, Offset), 639de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner SV->getName()+".adj", SI); 640de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner // Mask out the bits we are about to insert from the old value. 641de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner unsigned TotalBits = SV->getType()->getPrimitiveSizeInBits(); 642de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner unsigned InsertBits = 643de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner SI->getOperand(0)->getType()->getPrimitiveSizeInBits(); 644de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (TotalBits != InsertBits) { 645de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner assert(TotalBits > InsertBits); 646de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner uint64_t Mask = ~(((1ULL << InsertBits)-1) << Offset); 647de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (TotalBits != 64) 648de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner Mask = Mask & ((1ULL << TotalBits)-1); 649de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner Old = BinaryOperator::createAnd(Old, 650a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner ConstantUInt::get(Old->getType(), Mask), 651de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner Old->getName()+".mask", SI); 652de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner SV = BinaryOperator::createOr(Old, SV, SV->getName()+".ins", SI); 653de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner } 654a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 655a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 656a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner new StoreInst(SV, NewAI, SI); 657a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner SI->eraseFromParent(); 658a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 659a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (CastInst *CI = dyn_cast<CastInst>(User)) { 660a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned NewOff = Offset; 661a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const TargetData &TD = getAnalysis<TargetData>(); 662de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (TD.isBigEndian() && !isVectorInsert) { 663a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Adjust the pointer. For example, storing 16-bits into a 32-bit 664a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // alloca with just a cast makes it modify the top 16-bits. 665a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *SrcTy = cast<PointerType>(Ptr->getType())->getElementType(); 666a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *DstTy = cast<PointerType>(CI->getType())->getElementType(); 667a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner int PtrDiffBits = TD.getTypeSize(SrcTy)*8-TD.getTypeSize(DstTy)*8; 668a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner NewOff += PtrDiffBits; 669a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 670a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner ConvertUsesToScalar(CI, NewAI, NewOff); 671a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner CI->eraseFromParent(); 672a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 673a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const PointerType *AggPtrTy = 674a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner cast<PointerType>(GEP->getOperand(0)->getType()); 675a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const TargetData &TD = getAnalysis<TargetData>(); 676a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned AggSizeInBits = TD.getTypeSize(AggPtrTy->getElementType())*8; 677a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 678a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // Check to see if this is stepping over an element: GEP Ptr, int C 679a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned NewOffset = Offset; 680a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (GEP->getNumOperands() == 2) { 681a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getRawValue(); 682a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned BitOffset = Idx*AggSizeInBits; 683a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 684de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (TD.isLittleEndian() || isVectorInsert) 685a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner NewOffset += BitOffset; 686a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner else 687a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner NewOffset -= BitOffset; 688a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 689a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (GEP->getNumOperands() == 3) { 690a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner // We know that operand #2 is zero. 691a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getRawValue(); 692a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const Type *AggTy = AggPtrTy->getElementType(); 693a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (const SequentialType *SeqTy = dyn_cast<SequentialType>(AggTy)) { 694a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned ElSizeBits = TD.getTypeSize(SeqTy->getElementType())*8; 695a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 696de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (TD.isLittleEndian() || isVectorInsert) 697a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner NewOffset += ElSizeBits*Idx; 698a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner else 699a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner NewOffset += AggSizeInBits-ElSizeBits*(Idx+1); 700a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else if (const StructType *STy = dyn_cast<StructType>(AggTy)) { 701a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned EltBitOffset = TD.getStructLayout(STy)->MemberOffsets[Idx]*8; 702a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 703de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner if (TD.isLittleEndian() || isVectorInsert) 704a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner NewOffset += EltBitOffset; 705a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner else { 706a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner const PointerType *ElPtrTy = cast<PointerType>(GEP->getType()); 707a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner unsigned ElSizeBits = TD.getTypeSize(ElPtrTy->getElementType())*8; 708a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner NewOffset += AggSizeInBits-(EltBitOffset+ElSizeBits); 709a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 710a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 711a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else { 712a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner assert(0 && "Unsupported operation!"); 713a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner abort(); 714a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 715a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else { 716a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner assert(0 && "Unsupported operation!"); 717a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner abort(); 718a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 719a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner ConvertUsesToScalar(GEP, NewAI, NewOffset); 720a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner GEP->eraseFromParent(); 721a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } else { 722a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner assert(0 && "Unsupported operation!"); 723a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner abort(); 724a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 725a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 726a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 727