ScalarReplAggregates.cpp revision fa5cbd6d0fbda23fd669c8718e07b19001b2d21a
1ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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 220e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner#define DEBUG_TYPE "scalarrepl" 23ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Transforms/Scalar.h" 2438aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Constants.h" 2538aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/DerivedTypes.h" 26ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Function.h" 2779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner#include "llvm/GlobalVariable.h" 28d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 29372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/IntrinsicInst.h" 30fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson#include "llvm/LLVMContext.h" 31372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/Pass.h" 3238aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Analysis/Dominators.h" 3338aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Target/TargetData.h" 3438aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 354afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel#include "llvm/Transforms/Utils/Local.h" 369525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Debug.h" 37a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 3865a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner#include "llvm/Support/IRBuilder.h" 39a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/MathExtras.h" 40a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 411ccd185cb49d81465a2901622e58ceae046d1d83Chris Lattner#include "llvm/ADT/SmallVector.h" 42551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 43551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/StringExtras.h" 44d8664730942beb911327336d1f9db8e7efcd6813Chris Lattnerusing namespace llvm; 45d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 460e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of allocas broken up"); 470e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted, "Number of allocas promoted"); 480e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumConverted, "Number of aggregates converted to scalar"); 4979b3bd395dc3303cde65e18e0524ed2f70268c99Chris LattnerSTATISTIC(NumGlobals, "Number of allocas copied from constant global"); 50ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 510e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 529525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN SROA : public FunctionPass { 53ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 54ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman explicit SROA(signed T = -1) : FunctionPass(&ID) { 55ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel if (T == -1) 56b0e71edb6b33f822e001500dac90acf95faacea8Chris Lattner SRThreshold = 128; 57ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel else 58ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel SRThreshold = T; 59ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel } 60794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 61ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 62ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 6338aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performScalarRepl(Function &F); 6438aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performPromotion(Function &F); 6538aec325604635380421a27e39ab06d55ed2458dChris Lattner 66a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 67a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // will not alter the CFG, so say so. 68a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 69326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel AU.addRequired<DominatorTree>(); 7038aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<DominanceFrontier>(); 7138aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<TargetData>(); 72a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner AU.setPreservesCFG(); 73a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner } 74a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner 75ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 7656c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner TargetData *TD; 7756c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner 7839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// AllocaInfo - When analyzing uses of an alloca instruction, this captures 7939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// information about the uses. All these fields are initialized to false 8039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// and set to true when something is learned. 8139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner struct AllocaInfo { 8239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isUnsafe - This is set to true if the alloca cannot be SROA'd. 8339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isUnsafe : 1; 8439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 854afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel /// needsCleanup - This is set to true if there is some use of the alloca 864afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel /// that requires cleanup. 874afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel bool needsCleanup : 1; 8839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 8939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isMemCpySrc - This is true if this aggregate is memcpy'd from. 9039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpySrc : 1; 9139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9233b0b8d242de8d428f11e77ea734a08b47797216Zhou Sheng /// isMemCpyDst - This is true if this aggregate is memcpy'd into. 9339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpyDst : 1; 9439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo() 964afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel : isUnsafe(false), needsCleanup(false), 9739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isMemCpySrc(false), isMemCpyDst(false) {} 9839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner }; 9939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 100ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel unsigned SRThreshold; 101ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel 10239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; } 10339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 104f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner int isSafeAllocaToScalarRepl(AllocationInst *AI); 10539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 10639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void isSafeUseOfAllocation(Instruction *User, AllocationInst *AI, 10739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info); 10839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI, 10939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info); 11039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI, 11139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned OpNo, AllocaInfo &Info); 11239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void isSafeUseOfBitCastedAllocation(BitCastInst *User, AllocationInst *AI, 11339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info); 11439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 115a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner void DoScalarReplacement(AllocationInst *AI, 116a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner std::vector<AllocationInst*> &WorkList); 1174afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel void CleanupGEP(GetElementPtrInst *GEP); 1184afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel void CleanupAllocaUsers(AllocationInst *AI); 119ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); 120a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1218bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner void RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI, 122372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 123372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 124d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *BCInst, 125d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner AllocationInst *AI, 126d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts); 127d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocationInst *AI, 128d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1295ffe6acd577696a41932c7b82db06a04687e07baChris Lattner void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocationInst *AI, 1306e733d34ca487ab7ff8a6def018a933620393869Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 131d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 1327809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner bool CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy, 1331a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool &SawVec, uint64_t Offset, unsigned AllocaSize); 1342e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset); 1356e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType, 1369bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 1379b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal, 13865a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 13979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner static Instruction *isOnlyCopiedFromConstantGlobal(AllocationInst *AI); 140ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 141ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 142ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 143844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar SROA::ID = 0; 144844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); 145844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 146d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the ScalarReplAggregates pass 147ff366850aa9956e167e78d4f5b57aae10d8c5779Devang PatelFunctionPass *llvm::createScalarReplAggregatesPass(signed int Threshold) { 148ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel return new SROA(Threshold); 149ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel} 150ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 151ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 152ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnerbool SROA::runOnFunction(Function &F) { 15356c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner TD = &getAnalysis<TargetData>(); 15456c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner 155fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = performPromotion(F); 156fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner while (1) { 157fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool LocalChange = performScalarRepl(F); 158fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to repromote if no scalarrepl 159fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner Changed = true; 160fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner LocalChange = performPromotion(F); 161fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to re-scalarrepl if no promotion 162fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner } 16338aec325604635380421a27e39ab06d55ed2458dChris Lattner 16438aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 16538aec325604635380421a27e39ab06d55ed2458dChris Lattner} 16638aec325604635380421a27e39ab06d55ed2458dChris Lattner 16738aec325604635380421a27e39ab06d55ed2458dChris Lattner 16838aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performPromotion(Function &F) { 16938aec325604635380421a27e39ab06d55ed2458dChris Lattner std::vector<AllocaInst*> Allocas; 170326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel DominatorTree &DT = getAnalysis<DominatorTree>(); 17143f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); 17238aec325604635380421a27e39ab06d55ed2458dChris Lattner 17302a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 17438aec325604635380421a27e39ab06d55ed2458dChris Lattner 175fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = false; 176fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 17738aec325604635380421a27e39ab06d55ed2458dChris Lattner while (1) { 17838aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.clear(); 17938aec325604635380421a27e39ab06d55ed2458dChris Lattner 18038aec325604635380421a27e39ab06d55ed2458dChris Lattner // Find allocas that are safe to promote, by looking at all instructions in 18138aec325604635380421a27e39ab06d55ed2458dChris Lattner // the entry node 18238aec325604635380421a27e39ab06d55ed2458dChris Lattner for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 18338aec325604635380421a27e39ab06d55ed2458dChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 18441968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patel if (isAllocaPromotable(AI)) 18538aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.push_back(AI); 18638aec325604635380421a27e39ab06d55ed2458dChris Lattner 18738aec325604635380421a27e39ab06d55ed2458dChris Lattner if (Allocas.empty()) break; 18838aec325604635380421a27e39ab06d55ed2458dChris Lattner 189326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel PromoteMemToReg(Allocas, DT, DF); 19038aec325604635380421a27e39ab06d55ed2458dChris Lattner NumPromoted += Allocas.size(); 19138aec325604635380421a27e39ab06d55ed2458dChris Lattner Changed = true; 19238aec325604635380421a27e39ab06d55ed2458dChris Lattner } 19338aec325604635380421a27e39ab06d55ed2458dChris Lattner 19438aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 19538aec325604635380421a27e39ab06d55ed2458dChris Lattner} 19638aec325604635380421a27e39ab06d55ed2458dChris Lattner 197963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner/// getNumSAElements - Return the number of elements in the specific struct or 198963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner/// array. 199963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattnerstatic uint64_t getNumSAElements(const Type *T) { 200963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) 201963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner return ST->getNumElements(); 202963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner return cast<ArrayType>(T)->getNumElements(); 203963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner} 204963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner 20538aec325604635380421a27e39ab06d55ed2458dChris Lattner// performScalarRepl - This algorithm is a simple worklist driven algorithm, 20638aec325604635380421a27e39ab06d55ed2458dChris Lattner// which runs on all of the malloc/alloca instructions in the function, removing 20738aec325604635380421a27e39ab06d55ed2458dChris Lattner// them if they are only used by getelementptr instructions. 20838aec325604635380421a27e39ab06d55ed2458dChris Lattner// 20938aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performScalarRepl(Function &F) { 210ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<AllocationInst*> WorkList; 211ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 212ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Scan the entry basic block, adding any alloca's and mallocs to the worklist 21302a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); 214ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 215ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (AllocationInst *A = dyn_cast<AllocationInst>(I)) 216ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(A); 217ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 218ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Process the worklist 219ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool Changed = false; 220ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner while (!WorkList.empty()) { 221ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocationInst *AI = WorkList.back(); 222ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.pop_back(); 223a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 224add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner // Handle dead allocas trivially. These can be formed by SROA'ing arrays 225add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner // with unused elements. 226add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner if (AI->use_empty()) { 227add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner AI->eraseFromParent(); 228add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner continue; 229add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner } 2307809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 2317809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If this alloca is impossible for us to promote, reject it early. 2327809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized()) 2337809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 2347809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 2357809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Check to see if this allocation is only modified by a memcpy/memmove from 2367809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // a constant global. If this is the case, we can change all users to use 2377809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // the constant global instead. This is commonly produced by the CFE by 2387809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A' 2397809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // is only subsequently read. 2407809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (Instruction *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) { 2417809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner DOUT << "Found alloca equal to global: " << *AI; 2427809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner DOUT << " memcpy = " << *TheCopy; 2437809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Constant *TheSrc = cast<Constant>(TheCopy->getOperand(2)); 244fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson AI->replaceAllUsesWith( 245fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getConstantExprBitCast(TheSrc, AI->getType())); 2467809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner TheCopy->eraseFromParent(); // Don't mutate the global. 2477809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AI->eraseFromParent(); 2487809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ++NumGlobals; 2497809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Changed = true; 2507809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 2517809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 252add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner 25379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Check to see if we can perform the core SROA transformation. We cannot 25479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // transform the allocation instruction if it is an array allocation 25579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // (allocations OF arrays are ok though), and an allocation of a scalar 25679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // value cannot be decomposed at all. 257777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType()); 2585a377cb27bb65ea608b63716454c9ae214ef81c9Bill Wendling 2595a377cb27bb65ea608b63716454c9ae214ef81c9Bill Wendling // Do not promote any struct whose size is too big. 2603aaf5d993365c803dad9a8815b6c9864505af5b6Bill Wendling if (AllocaSize > SRThreshold) continue; 2618fe40819aed54e3c33adcbc972f414f5e13a6de8Bill Wendling 2627809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if ((isa<StructType>(AI->getAllocatedType()) || 2637139406707eb3869183fd6a3329fe4a77d309692Chris Lattner isa<ArrayType>(AI->getAllocatedType())) && 264963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner // Do not promote any struct into more than "32" separate vars. 26567fca63da267da491de9526b09a7de0a2e99ece2Evan Cheng getNumSAElements(AI->getAllocatedType()) <= SRThreshold/4) { 266a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Check that all of the users of the allocation are capable of being 267a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // transformed. 268a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner switch (isSafeAllocaToScalarRepl(AI)) { 269a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner default: assert(0 && "Unexpected value!"); 270a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 0: // Not safe to scalar replace. 271a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner break; 272a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 1: // Safe, but requires cleanup/canonicalizations first 2734afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel CleanupAllocaUsers(AI); 274a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // FALL THROUGH. 275a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 3: // Safe to scalar replace. 276a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner DoScalarReplacement(AI, WorkList); 277a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner Changed = true; 278a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner continue; 279a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 280f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 2816e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 2826e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // If we can turn this aggregate value (potentially with casts) into a 2836e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // simple scalar value that can be mem2reg'd into a register value. 2842e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // IsNotTrivial tracks whether this is something that mem2reg could have 2852e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // promoted itself. If so, we don't want to transform it needlessly. Note 2862e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // that we can't just check based on the type: the alloca may be of an i32 2872e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // but that has pointer arithmetic to set byte 3 of it or something. 2886e733d34ca487ab7ff8a6def018a933620393869Chris Lattner bool IsNotTrivial = false; 2897809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner const Type *VectorTy = 0; 2901a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool HadAVector = false; 2911a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (CanConvertToScalar(AI, IsNotTrivial, VectorTy, HadAVector, 2920ff83ab9858d56fb37ea634c52eafb3de641d733Chris Lattner 0, unsigned(AllocaSize)) && IsNotTrivial) { 2937809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaInst *NewAI; 2941a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // If we were able to find a vector type that can handle this with 2951a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // insert/extract elements, and if there was at least one use that had 2961a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // a vector type, promote this to a vector. We don't want to promote 2971a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // random stuff that doesn't use vectors (e.g. <9 x double>) because then 2981a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // we just get a lot of insert/extracts. If at least one vector is 2991a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // involved, then we probably really do have a union of vector/array. 3001a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (VectorTy && isa<VectorType>(VectorTy) && HadAVector) { 3017809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner DOUT << "CONVERT TO VECTOR: " << *AI << " TYPE = " << *VectorTy <<"\n"; 30215c82779033826a0958182b746b03a22ad04a16aChris Lattner 3037809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Create and insert the vector alloca. 3047809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner NewAI = new AllocaInst(VectorTy, 0, "", AI->getParent()->begin()); 3057809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ConvertUsesToScalar(AI, NewAI, 0); 3067809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } else { 3077809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner DOUT << "CONVERT TO SCALAR INTEGER: " << *AI << "\n"; 3087809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 3097809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Create and insert the integer alloca. 310fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson const Type *NewTy = Context->getIntegerType(AllocaSize*8); 3117809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin()); 31215c82779033826a0958182b746b03a22ad04a16aChris Lattner ConvertUsesToScalar(AI, NewAI, 0); 3136e733d34ca487ab7ff8a6def018a933620393869Chris Lattner } 3147809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner NewAI->takeName(AI); 3157809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AI->eraseFromParent(); 3167809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ++NumConverted; 3177809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Changed = true; 3187809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 3197809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 3206e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 3217809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Otherwise, couldn't process this alloca. 322a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 323ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 324a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner return Changed; 325a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner} 326fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 327a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner/// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl 328a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner/// predicate, do SROA now. 329a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattnervoid SROA::DoScalarReplacement(AllocationInst *AI, 330a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner std::vector<AllocationInst*> &WorkList) { 33179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner DOUT << "Found inst to SROA: " << *AI; 332a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner SmallVector<AllocaInst*, 32> ElementAllocas; 333a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 334a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 335a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 336a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 337a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->getAlignment(), 338a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->getName() + "." + utostr(i), AI); 339a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.push_back(NA); 340a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 341a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 342a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } else { 343a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 344a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.reserve(AT->getNumElements()); 345a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner const Type *ElTy = AT->getElementType(); 346a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 347a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), 348a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->getName() + "." + utostr(i), AI); 349a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.push_back(NA); 350a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 351ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 352a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 353fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 354a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Now that we have created the alloca instructions that we want to use, 355a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // expand the getelementptr instructions to use them. 356a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // 357a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner while (!AI->use_empty()) { 358a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner Instruction *User = cast<Instruction>(AI->use_back()); 359a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner if (BitCastInst *BCInst = dyn_cast<BitCastInst>(User)) { 360a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner RewriteBitCastUserOfAlloca(BCInst, AI, ElementAllocas); 361a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner BCInst->eraseFromParent(); 362a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner continue; 363a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 364a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner 3652a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // Replace: 3662a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %res = load { i32, i32 }* %alloc 3672a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // with: 3682a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %load.0 = load i32* %alloc.0 3692a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0 3702a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %load.1 = load i32* %alloc.1 3712a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1 37202518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman // (Also works for arrays instead of structs) 37302518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 374fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *Insert = Context->getUndef(LI->getType()); 37502518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman for (unsigned i = 0, e = ElementAllocas.size(); i != e; ++i) { 37602518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Value *Load = new LoadInst(ElementAllocas[i], "load", LI); 37702518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI); 37802518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman } 37902518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman LI->replaceAllUsesWith(Insert); 38002518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman LI->eraseFromParent(); 38102518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman continue; 38202518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman } 38302518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman 3842a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // Replace: 3852a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // store { i32, i32 } %val, { i32, i32 }* %alloc 3862a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // with: 3872a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %val.0 = extractvalue { i32, i32 } %val, 0 3882a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // store i32 %val.0, i32* %alloc.0 3892a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %val.1 = extractvalue { i32, i32 } %val, 1 3902a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // store i32 %val.1, i32* %alloc.1 39102518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman // (Also works for arrays instead of structs) 39202518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 39302518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Value *Val = SI->getOperand(0); 39402518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman for (unsigned i = 0, e = ElementAllocas.size(); i != e; ++i) { 39502518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI); 39602518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman new StoreInst(Extract, ElementAllocas[i], SI); 39702518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman } 39802518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman SI->eraseFromParent(); 39902518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman continue; 40002518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman } 40102518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman 402a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); 403a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> 404a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner unsigned Idx = 405a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner (unsigned)cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); 406a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner 407a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner assert(Idx < ElementAllocas.size() && "Index out of range?"); 408a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AllocaInst *AllocaToUse = ElementAllocas[Idx]; 409a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner 410a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner Value *RepValue; 411a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner if (GEPI->getNumOperands() == 3) { 412a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Do not insert a new getelementptr instruction with zero indices, only 413a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // to have it optimized out later. 414a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner RepValue = AllocaToUse; 415a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } else { 416a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // We are indexing deeply into the structure, so we still need a 417a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // getelement ptr instruction to finish the indexing. This may be 418a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // expanded itself once the worklist is rerun. 419a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // 420a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner SmallVector<Value*, 8> NewArgs; 421fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson NewArgs.push_back(Context->getNullValue(Type::Int32Ty)); 422a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner NewArgs.append(GEPI->op_begin()+3, GEPI->op_end()); 423051a950000e21935165db56695e35bade668193bGabor Greif RepValue = GetElementPtrInst::Create(AllocaToUse, NewArgs.begin(), 424051a950000e21935165db56695e35bade668193bGabor Greif NewArgs.end(), "", GEPI); 425a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner RepValue->takeName(GEPI); 426a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 427a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner 428a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // If this GEP is to the start of the aggregate, check for memcpys. 429d356a7ee0ed7744857dcf497cb20b0128770fb0fChris Lattner if (Idx == 0 && GEPI->hasAllZeroIndices()) 430d356a7ee0ed7744857dcf497cb20b0128770fb0fChris Lattner RewriteBitCastUserOfAlloca(GEPI, AI, ElementAllocas); 431ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 432a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Move all of the users over to the new GEP. 433a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner GEPI->replaceAllUsesWith(RepValue); 434a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Delete the old GEP 435a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner GEPI->eraseFromParent(); 436ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 437ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 438a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Finally, delete the Alloca instruction 439a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->eraseFromParent(); 440a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner NumReplaced++; 441ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 4425e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 4435e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 444f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// isSafeElementUse - Check to see if this use is an allowed use for a 4458bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// getelementptr instruction of an array aggregate allocation. isFirstElt 4468bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// indicates whether Ptr is known to the start of the aggregate. 447f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// 44839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattnervoid SROA::isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI, 44939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info) { 450f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 451f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner I != E; ++I) { 452f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner Instruction *User = cast<Instruction>(*I); 453f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner switch (User->getOpcode()) { 454f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::Load: break; 455f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::Store: 456f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner // Store is ok if storing INTO the pointer, not storing the pointer 45739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (User->getOperand(0) == Ptr) return MarkUnsafe(Info); 458f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner break; 459f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::GetElementPtr: { 460f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner GetElementPtrInst *GEP = cast<GetElementPtrInst>(User); 4618bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner bool AreAllZeroIndices = isFirstElt; 462f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner if (GEP->getNumOperands() > 1) { 4638bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner if (!isa<ConstantInt>(GEP->getOperand(1)) || 4648bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner !cast<ConstantInt>(GEP->getOperand(1))->isZero()) 46539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Using pointer arithmetic to navigate the array. 46639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 4678bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 468d356a7ee0ed7744857dcf497cb20b0128770fb0fChris Lattner if (AreAllZeroIndices) 469d356a7ee0ed7744857dcf497cb20b0128770fb0fChris Lattner AreAllZeroIndices = GEP->hasAllZeroIndices(); 470f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 47139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeElementUse(GEP, AreAllZeroIndices, AI, Info); 47239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) return; 473f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner break; 474f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 4758bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner case Instruction::BitCast: 47639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (isFirstElt) { 47739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeUseOfBitCastedAllocation(cast<BitCastInst>(User), AI, Info); 47839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) return; 4798bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner break; 48039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 4818bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner DOUT << " Transformation preventing inst: " << *User; 48239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 4838bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner case Instruction::Call: 4848bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 48539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (isFirstElt) { 48639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeMemIntrinsicOnAllocation(MI, AI, I.getOperandNo(), Info); 48739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) return; 4888bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner break; 48939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 4908bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner } 4918bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner DOUT << " Transformation preventing inst: " << *User; 49239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 493f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner default: 494b7427031372337e6d67f9573ec6c722ab5ea913eBill Wendling DOUT << " Transformation preventing inst: " << *User; 49539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 496f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 497f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 49839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return; // All users look ok :) 499f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner} 500f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner 501d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner/// AllUsersAreLoads - Return true if all users of this value are loads. 502d878ecd904e4469344a2274f9784422c2c68b81cChris Lattnerstatic bool AllUsersAreLoads(Value *Ptr) { 503d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 504d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner I != E; ++I) 505d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (cast<Instruction>(*I)->getOpcode() != Instruction::Load) 506d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner return false; 507fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman return true; 508d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner} 509d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner 5105e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// isSafeUseOfAllocation - Check to see if this user is an allowed use for an 5115e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// aggregate allocation. 5125e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 51339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattnervoid SROA::isSafeUseOfAllocation(Instruction *User, AllocationInst *AI, 51439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info) { 515372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner if (BitCastInst *C = dyn_cast<BitCastInst>(User)) 51639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return isSafeUseOfBitCastedAllocation(C, AI, Info); 51739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 5186e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) 5196e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (!LI->isVolatile()) 5206e733d34ca487ab7ff8a6def018a933620393869Chris Lattner return;// Loads (returning a first class aggregrate) are always rewritable 52102518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman 5226e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) 5236e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (!SI->isVolatile() && SI->getOperand(0) != AI) 5246e733d34ca487ab7ff8a6def018a933620393869Chris Lattner return;// Store is ok if storing INTO the pointer, not storing the pointer 52502518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman 52639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User); 52739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (GEPI == 0) 52839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 529546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 530be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner gep_type_iterator I = gep_type_begin(GEPI), E = gep_type_end(GEPI); 531be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner 53225de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // The GEP is not safe to transform if not of the form "GEP <ptr>, 0, <cst>". 533be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner if (I == E || 534fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson I.getOperand() != Context->getNullValue(I.getOperand()->getType())) { 53539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 53639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 537be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner 538be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner ++I; 53939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (I == E) return MarkUnsafe(Info); // ran out of GEP indices?? 540546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 5418bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner bool IsAllZeroIndices = true; 5428bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 54388e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // If the first index is a non-constant index into an array, see if we can 54488e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // handle it as a special case. 545be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 54688e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner if (!isa<ConstantInt>(I.getOperand())) { 5478bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner IsAllZeroIndices = 0; 54888e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner uint64_t NumElements = AT->getNumElements(); 5498bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 550d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // If this is an array index and the index is not constant, we cannot 551d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // promote... that is unless the array has exactly one or two elements in 552d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // it, in which case we CAN promote it, but we have to canonicalize this 553d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // out if this is the only problem. 55425de486263abc1882498a8701e3eb29ee0804c4eChris Lattner if ((NumElements == 1 || NumElements == 2) && 55539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllUsersAreLoads(GEPI)) { 5564afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Info.needsCleanup = true; 55739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return; // Canonicalization required! 55839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 55939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 560d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 5615e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 5625fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 56388e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // Walk through the GEP type indices, checking the types that this indexes 56488e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // into. 56588e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner for (; I != E; ++I) { 56688e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // Ignore struct elements, no extra checking needed for these. 56788e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner if (isa<StructType>(*I)) 56888e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner continue; 56988e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner 57088e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner ConstantInt *IdxVal = dyn_cast<ConstantInt>(I.getOperand()); 57188e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner if (!IdxVal) return MarkUnsafe(Info); 5725fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 5735fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // Are all indices still zero? 57488e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner IsAllZeroIndices &= IdxVal->isZero(); 5755fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 5765fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 5775fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // This GEP indexes an array. Verify that this is an in-range constant 5785fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // integer. Specifically, consider A[0][i]. We cannot know that the user 5795fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // isn't doing invalid things like allowing i to index an out-of-range 5805fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // subscript that accesses A[1]. Because of this, we have to reject SROA 581c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen // of any accesses into structs where any of the components are variables. 5825fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman if (IdxVal->getZExtValue() >= AT->getNumElements()) 5835fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman return MarkUnsafe(Info); 584c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen } else if (const VectorType *VT = dyn_cast<VectorType>(*I)) { 585c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen if (IdxVal->getZExtValue() >= VT->getNumElements()) 586c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen return MarkUnsafe(Info); 5875fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman } 58888e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner } 58988e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner 590be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner // If there are any non-simple uses of this getelementptr, make sure to reject 591be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner // them. 59239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return isSafeElementUse(GEPI, IsAllZeroIndices, AI, Info); 5938bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner} 5948bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 5958bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// isSafeMemIntrinsicOnAllocation - Return true if the specified memory 5968bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// intrinsic can be promoted by SROA. At this point, we know that the operand 5978bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// of the memintrinsic is a pointer to the beginning of the allocation. 59839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattnervoid SROA::isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI, 59939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned OpNo, AllocaInfo &Info) { 6008bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner // If not constant length, give up. 6018bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 60239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (!Length) return MarkUnsafe(Info); 6038bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 6048bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner // If not the whole aggregate, give up. 6053cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands if (Length->getZExtValue() != 606777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands TD->getTypeAllocSize(AI->getType()->getElementType())) 60739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 6088bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 6098bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner // We only know about memcpy/memset/memmove. 6103ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (!isa<MemIntrinsic>(MI)) 61139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 61239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 61339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Otherwise, we can transform it. Determine whether this is a memcpy/set 61439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // into or out of the aggregate. 61539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (OpNo == 1) 61639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner Info.isMemCpyDst = true; 61739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner else { 61839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner assert(OpNo == 2); 61939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner Info.isMemCpySrc = true; 62039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 6215e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 6225e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 623372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner/// isSafeUseOfBitCastedAllocation - Return true if all users of this bitcast 624372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner/// are 62539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattnervoid SROA::isSafeUseOfBitCastedAllocation(BitCastInst *BC, AllocationInst *AI, 62639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info) { 627372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner for (Value::use_iterator UI = BC->use_begin(), E = BC->use_end(); 628372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner UI != E; ++UI) { 629372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner if (BitCastInst *BCU = dyn_cast<BitCastInst>(UI)) { 63039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeUseOfBitCastedAllocation(BCU, AI, Info); 631372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(UI)) { 63239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeMemIntrinsicOnAllocation(MI, AI, UI.getOperandNo(), Info); 633d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 6346e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (SI->isVolatile()) 6356e733d34ca487ab7ff8a6def018a933620393869Chris Lattner return MarkUnsafe(Info); 6366e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 637d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // If storing the entire alloca in one chunk through a bitcasted pointer 638d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // to integer, we can transform it. This happens (for example) when you 639d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // cast a {i32,i32}* to i64* and store through it. This is similar to the 640d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // memcpy case and occurs in various "byval" cases and emulated memcpys. 641d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (isa<IntegerType>(SI->getOperand(0)->getType()) && 642777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands TD->getTypeAllocSize(SI->getOperand(0)->getType()) == 643777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands TD->getTypeAllocSize(AI->getType()->getElementType())) { 644d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Info.isMemCpyDst = true; 645d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner continue; 646d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 647d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner return MarkUnsafe(Info); 6485ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(UI)) { 6496e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LI->isVolatile()) 6506e733d34ca487ab7ff8a6def018a933620393869Chris Lattner return MarkUnsafe(Info); 6516e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 6525ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If loading the entire alloca in one chunk through a bitcasted pointer 6535ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // to integer, we can transform it. This happens (for example) when you 6545ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // cast a {i32,i32}* to i64* and load through it. This is similar to the 6555ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // memcpy case and occurs in various "byval" cases and emulated memcpys. 6565ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (isa<IntegerType>(LI->getType()) && 657777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands TD->getTypeAllocSize(LI->getType()) == 658777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands TD->getTypeAllocSize(AI->getType()->getElementType())) { 6595ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Info.isMemCpySrc = true; 6605ffe6acd577696a41932c7b82db06a04687e07baChris Lattner continue; 6615ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 6625ffe6acd577696a41932c7b82db06a04687e07baChris Lattner return MarkUnsafe(Info); 6634afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } else if (isa<DbgInfoIntrinsic>(UI)) { 6644afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // If one user is DbgInfoIntrinsic then check if all users are 6654afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // DbgInfoIntrinsics. 6664afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (OnlyUsedByDbgInfoIntrinsics(BC)) { 6674afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Info.needsCleanup = true; 6684afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel return; 6694afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 6704afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel else 6714afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel MarkUnsafe(Info); 6724afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 6734afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel else { 67439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 675372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 67639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) return; 677372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 678372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 679372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 6808bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// RewriteBitCastUserOfAlloca - BCInst (transitively) bitcasts AI, or indexes 6818bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// to its first element. Transform users of the cast to use the new values 6828bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// instead. 6838bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattnervoid SROA::RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI, 684372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 6858bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner Value::use_iterator UI = BCInst->use_begin(), UE = BCInst->use_end(); 6868bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner while (UI != UE) { 687d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Instruction *User = cast<Instruction>(*UI++); 688d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BitCastInst *BCU = dyn_cast<BitCastInst>(User)) { 689372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner RewriteBitCastUserOfAlloca(BCU, AI, NewElts); 690d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (BCU->use_empty()) BCU->eraseFromParent(); 691372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner continue; 692372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 693372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 694d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 695d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // This must be memcpy/memmove/memset of the entire aggregate. 696d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Split into one per element. 697d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner RewriteMemIntrinUserOfAlloca(MI, BCInst, AI, NewElts); 698d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 699d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 700d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 701d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 7025ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If this is a store of the entire alloca from an integer, rewrite it. 703d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner RewriteStoreUserOfWholeAlloca(SI, AI, NewElts); 704d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner continue; 705d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 7065ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 7075ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 7085ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If this is a load of the entire alloca to an integer, rewrite it. 7095ffe6acd577696a41932c7b82db06a04687e07baChris Lattner RewriteLoadUserOfWholeAlloca(LI, AI, NewElts); 7105ffe6acd577696a41932c7b82db06a04687e07baChris Lattner continue; 7115ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 712d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 713d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Otherwise it must be some other user of a gep of the first pointer. Just 714d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // leave these alone. 715d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 7165ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 717d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner} 718d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 719d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner/// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI. 720d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner/// Rewrite it to copy or set the elements of the scalarized memory. 721d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattnervoid SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *BCInst, 722d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner AllocationInst *AI, 723d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 724d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 725d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If this is a memcpy/memmove, construct the other pointer as the 72688fe1ad187041e2ca636e0f86204e30fc6e14300Chris Lattner // appropriate type. The "Other" pointer is the pointer that goes to memory 72788fe1ad187041e2ca636e0f86204e30fc6e14300Chris Lattner // that doesn't have anything to do with the alloca that we are promoting. For 72888fe1ad187041e2ca636e0f86204e30fc6e14300Chris Lattner // memset, this Value* stays null. 729d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *OtherPtr = 0; 730dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner unsigned MemAlignment = MI->getAlignment(); 7313ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { // memmove/memcopy 7323ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (BCInst == MTI->getRawDest()) 7333ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner OtherPtr = MTI->getRawSource(); 734d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner else { 7353ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner assert(BCInst == MTI->getRawSource()); 7363ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner OtherPtr = MTI->getRawDest(); 737372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 738d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 739d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 740d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If there is an other pointer, we want to convert it to the same pointer 741d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // type as AI has, so we can GEP through it safely. 742d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherPtr) { 743d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // It is likely that OtherPtr is a bitcast, if so, remove it. 744d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(OtherPtr)) 745d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = BC->getOperand(0); 746d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // All zero GEPs are effectively bitcasts. 747d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(OtherPtr)) 748d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (GEP->hasAllZeroIndices()) 749d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = GEP->getOperand(0); 750372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 751d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (ConstantExpr *BCE = dyn_cast<ConstantExpr>(OtherPtr)) 752d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BCE->getOpcode() == Instruction::BitCast) 753d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = BCE->getOperand(0); 754d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 755d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the pointer is not the right type, insert a bitcast to the right 756d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // type. 757d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherPtr->getType() != AI->getType()) 758d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = new BitCastInst(OtherPtr, AI->getType(), OtherPtr->getName(), 759d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 760d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 761d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 762d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Process each element of the aggregate. 763d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *TheFn = MI->getOperand(0); 764d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner const Type *BytePtrTy = MI->getRawDest()->getType(); 765d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner bool SROADest = MI->getRawDest() == BCInst; 766d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 767fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Constant *Zero = Context->getNullValue(Type::Int32Ty); 768372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 769d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 770d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If this is a memcpy/memmove, emit a GEP of the other element address. 771d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *OtherElt = 0; 7721541e0f7da2de6ae84434060df81e93b64000924Chris Lattner unsigned OtherEltAlign = MemAlignment; 7731541e0f7da2de6ae84434060df81e93b64000924Chris Lattner 774d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherPtr) { 775fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *Idx[2] = { Zero, Context->getConstantInt(Type::Int32Ty, i) }; 776d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherElt = GetElementPtrInst::Create(OtherPtr, Idx, Idx + 2, 777963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner OtherPtr->getNameStr()+"."+utostr(i), 778d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 7791541e0f7da2de6ae84434060df81e93b64000924Chris Lattner uint64_t EltOffset; 7801541e0f7da2de6ae84434060df81e93b64000924Chris Lattner const PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType()); 7811541e0f7da2de6ae84434060df81e93b64000924Chris Lattner if (const StructType *ST = 7821541e0f7da2de6ae84434060df81e93b64000924Chris Lattner dyn_cast<StructType>(OtherPtrTy->getElementType())) { 7831541e0f7da2de6ae84434060df81e93b64000924Chris Lattner EltOffset = TD->getStructLayout(ST)->getElementOffset(i); 7841541e0f7da2de6ae84434060df81e93b64000924Chris Lattner } else { 7851541e0f7da2de6ae84434060df81e93b64000924Chris Lattner const Type *EltTy = 7861541e0f7da2de6ae84434060df81e93b64000924Chris Lattner cast<SequentialType>(OtherPtr->getType())->getElementType(); 787777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands EltOffset = TD->getTypeAllocSize(EltTy)*i; 7881541e0f7da2de6ae84434060df81e93b64000924Chris Lattner } 7891541e0f7da2de6ae84434060df81e93b64000924Chris Lattner 7901541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // The alignment of the other pointer is the guaranteed alignment of the 7911541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // element, which is affected by both the known alignment of the whole 7921541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // mem intrinsic and the alignment of the element. If the alignment of 7931541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // the memcpy (f.e.) is 32 but the element is at a 4-byte offset, then the 7941541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // known alignment is just 4 bytes. 7951541e0f7da2de6ae84434060df81e93b64000924Chris Lattner OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset); 796d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 797d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 798d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *EltPtr = NewElts[i]; 7991541e0f7da2de6ae84434060df81e93b64000924Chris Lattner const Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType(); 800d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 801d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If we got down to a scalar, insert a load or store as appropriate. 802d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltTy->isSingleValueType()) { 8033ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (isa<MemTransferInst>(MI)) { 8041541e0f7da2de6ae84434060df81e93b64000924Chris Lattner if (SROADest) { 8051541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // From Other to Alloca. 8061541e0f7da2de6ae84434060df81e93b64000924Chris Lattner Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI); 8071541e0f7da2de6ae84434060df81e93b64000924Chris Lattner new StoreInst(Elt, EltPtr, MI); 8081541e0f7da2de6ae84434060df81e93b64000924Chris Lattner } else { 8091541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // From Alloca to Other. 8101541e0f7da2de6ae84434060df81e93b64000924Chris Lattner Value *Elt = new LoadInst(EltPtr, "tmp", MI); 8111541e0f7da2de6ae84434060df81e93b64000924Chris Lattner new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI); 8121541e0f7da2de6ae84434060df81e93b64000924Chris Lattner } 813d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 814372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 815d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(isa<MemSetInst>(MI)); 816c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 817d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the stored element is zero (common case), just store a null 818d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // constant. 819d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Constant *StoreVal; 820d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getOperand(2))) { 821d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (CI->isZero()) { 822fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson StoreVal = Context->getNullValue(EltTy); // 0.0, null, 0, <0,0> 823c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } else { 824d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If EltTy is a vector type, get the element type. 82544118f0e25c25fedda1ccdd6a72f072c0b5c96e7Dan Gohman const Type *ValTy = EltTy->getScalarType(); 82644118f0e25c25fedda1ccdd6a72f072c0b5c96e7Dan Gohman 827d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Construct an integer with the right value. 828d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner unsigned EltSize = TD->getTypeSizeInBits(ValTy); 829d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner APInt OneVal(EltSize, CI->getZExtValue()); 830d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner APInt TotalVal(OneVal); 831d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Set each byte. 832d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner for (unsigned i = 0; 8*i < EltSize; ++i) { 833d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner TotalVal = TotalVal.shl(8); 834d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner TotalVal |= OneVal; 835d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 836d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 837d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Convert the integer value to the appropriate type. 838fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson StoreVal = Context->getConstantInt(TotalVal); 839d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (isa<PointerType>(ValTy)) 840fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson StoreVal = Context->getConstantExprIntToPtr(StoreVal, ValTy); 841d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner else if (ValTy->isFloatingPoint()) 842fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson StoreVal = Context->getConstantExprBitCast(StoreVal, ValTy); 843d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(StoreVal->getType() == ValTy && "Type mismatch!"); 844d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 845d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the requested value was a vector constant, create it. 846d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltTy != ValTy) { 847d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner unsigned NumElts = cast<VectorType>(ValTy)->getNumElements(); 848d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<Constant*, 16> Elts(NumElts, StoreVal); 849fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson StoreVal = Context->getConstantVector(&Elts[0], NumElts); 850c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 851c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 852d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner new StoreInst(StoreVal, EltPtr, MI); 853d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 854c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 855d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Otherwise, if we're storing a byte variable, use a memset call for 856d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // this element. 857d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 858c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 859d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Cast the element pointer to BytePtrTy. 860d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltPtr->getType() != BytePtrTy) 861d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner EltPtr = new BitCastInst(EltPtr, BytePtrTy, EltPtr->getNameStr(), MI); 862c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 863d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Cast the other pointer (if we have one) to BytePtrTy. 864d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherElt && OtherElt->getType() != BytePtrTy) 865d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherElt = new BitCastInst(OtherElt, BytePtrTy,OtherElt->getNameStr(), 866d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 867d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 868777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands unsigned EltSize = TD->getTypeAllocSize(EltTy); 869d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 870d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Finally, insert the meminst for this element. 8713ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (isa<MemTransferInst>(MI)) { 872d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *Ops[] = { 873d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SROADest ? EltPtr : OtherElt, // Dest ptr 874d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SROADest ? OtherElt : EltPtr, // Src ptr 875fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getConstantInt(MI->getOperand(3)->getType(), EltSize), // Size 876fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getConstantInt(Type::Int32Ty, OtherEltAlign) // Align 877d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner }; 878d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner CallInst::Create(TheFn, Ops, Ops + 4, "", MI); 879d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } else { 880d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(isa<MemSetInst>(MI)); 881d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *Ops[] = { 882d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner EltPtr, MI->getOperand(2), // Dest, Value, 883fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getConstantInt(MI->getOperand(3)->getType(), EltSize), // Size 884d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Zero // Align 885d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner }; 886d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner CallInst::Create(TheFn, Ops, Ops + 4, "", MI); 887c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 888372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 889d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner MI->eraseFromParent(); 890372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 891d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 892d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner/// RewriteStoreUserOfWholeAlloca - We found an store of an integer that 893d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner/// overwrites the entire allocation. Extract out the pieces of the stored 894d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner/// integer and store them individually. 895d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattnervoid SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, 896d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner AllocationInst *AI, 897d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts){ 898d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Extract each element out of the integer according to its structure offset 899d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // and store the element value to the individual alloca. 900d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *SrcVal = SI->getOperand(0); 901d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const Type *AllocaEltTy = AI->getType()->getElementType(); 902777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 903d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 904d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // If this isn't a store of an integer to the whole alloca, it may be a store 905d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // to the first element. Just ignore the store in this case and normal SROA 90641b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman // will handle it. 907d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (!isa<IntegerType>(SrcVal->getType()) || 90841b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman TD->getTypeAllocSizeInBits(SrcVal->getType()) != AllocaSizeBits) 909d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner return; 91041b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman // Handle tail padding by extending the operand 91141b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits) 912fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson SrcVal = new ZExtInst(SrcVal, 913fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getIntegerType(AllocaSizeBits), "", SI); 914d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 915d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner DOUT << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << *SI; 916d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 917d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // There are two forms here: AI could be an array or struct. Both cases 918d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // have different ways to compute the element offset. 919d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 920d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const StructLayout *Layout = TD->getStructLayout(EltSTy); 921d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 922d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 923d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Get the number of bits to shift SrcVal to get the value. 924d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const Type *FieldTy = EltSTy->getElementType(i); 925d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t Shift = Layout->getElementOffsetInBits(i); 926d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 927d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 928777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands Shift = AllocaSizeBits-Shift-TD->getTypeAllocSizeInBits(FieldTy); 929d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 930d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *EltVal = SrcVal; 931d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (Shift) { 932fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *ShiftVal = Context->getConstantInt(EltVal->getType(), Shift); 933d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 934d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "sroa.store.elt", SI); 935d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 936d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 937d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Truncate down to an integer of the right size. 938d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 939583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 940583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 941583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (FieldSizeBits == 0) continue; 942583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 943d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (FieldSizeBits != AllocaSizeBits) 944fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson EltVal = new TruncInst(EltVal, 945fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getIntegerType(FieldSizeBits), "", SI); 946d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *DestField = NewElts[i]; 947d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (EltVal->getType() == FieldTy) { 948d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Storing to an integer field of this size, just do it. 949d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else if (FieldTy->isFloatingPoint() || isa<VectorType>(FieldTy)) { 950d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Bitcast to the right element type (for fp/vector values). 951d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = new BitCastInst(EltVal, FieldTy, "", SI); 952d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 953d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 954d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner DestField = new BitCastInst(DestField, 955fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getPointerTypeUnqual(EltVal->getType()), 956d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "", SI); 957d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 958d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner new StoreInst(EltVal, DestField, SI); 959d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 960d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 961d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 962d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const ArrayType *ATy = cast<ArrayType>(AllocaEltTy); 963d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const Type *ArrayEltTy = ATy->getElementType(); 964777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t ElementOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 965d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy); 966d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 967d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t Shift; 968d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 969d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 970d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift = AllocaSizeBits-ElementOffset; 971d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner else 972d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift = 0; 973d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 974d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 975583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 976583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (ElementSizeBits == 0) continue; 977d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 978d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *EltVal = SrcVal; 979d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (Shift) { 980fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *ShiftVal = Context->getConstantInt(EltVal->getType(), Shift); 981d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 982d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "sroa.store.elt", SI); 983d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 984d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 985d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Truncate down to an integer of the right size. 986d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (ElementSizeBits != AllocaSizeBits) 987fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson EltVal = new TruncInst(EltVal, 988fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getIntegerType(ElementSizeBits),"",SI); 989d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *DestField = NewElts[i]; 990d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (EltVal->getType() == ArrayEltTy) { 991d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Storing to an integer field of this size, just do it. 992d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else if (ArrayEltTy->isFloatingPoint() || isa<VectorType>(ArrayEltTy)) { 993d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Bitcast to the right element type (for fp/vector values). 994d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI); 995d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 996d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 997d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner DestField = new BitCastInst(DestField, 998fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getPointerTypeUnqual(EltVal->getType()), 999d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "", SI); 1000d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1001d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner new StoreInst(EltVal, DestField, SI); 1002d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1003d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 1004d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift -= ElementOffset; 1005d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner else 1006d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift += ElementOffset; 1007d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1008d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1009d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1010d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SI->eraseFromParent(); 1011d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner} 1012d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 10135ffe6acd577696a41932c7b82db06a04687e07baChris Lattner/// RewriteLoadUserOfWholeAlloca - We found an load of the entire allocation to 10145ffe6acd577696a41932c7b82db06a04687e07baChris Lattner/// an integer. Load the individual pieces to form the aggregate value. 10155ffe6acd577696a41932c7b82db06a04687e07baChris Lattnervoid SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocationInst *AI, 10165ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 10175ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Extract each element out of the NewElts according to its structure offset 10185ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // and form the result value. 10195ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const Type *AllocaEltTy = AI->getType()->getElementType(); 1020777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 10215ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10225ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If this isn't a load of the whole alloca to an integer, it may be a load 10235ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // of the first element. Just ignore the load in this case and normal SROA 102441b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman // will handle it. 10255ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (!isa<IntegerType>(LI->getType()) || 102641b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman TD->getTypeAllocSizeInBits(LI->getType()) != AllocaSizeBits) 10275ffe6acd577696a41932c7b82db06a04687e07baChris Lattner return; 10285ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10295ffe6acd577696a41932c7b82db06a04687e07baChris Lattner DOUT << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << *LI; 10305ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10315ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // There are two forms here: AI could be an array or struct. Both cases 10325ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // have different ways to compute the element offset. 10335ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const StructLayout *Layout = 0; 10345ffe6acd577696a41932c7b82db06a04687e07baChris Lattner uint64_t ArrayEltBitOffset = 0; 10355ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 10365ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Layout = TD->getStructLayout(EltSTy); 10375ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } else { 10385ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType(); 1039777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands ArrayEltBitOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 10405ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 10415ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 1042fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *ResultVal = 1043fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getNullValue(Context->getIntegerType(AllocaSizeBits)); 10445ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10455ffe6acd577696a41932c7b82db06a04687e07baChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 10465ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Load the value from the alloca. If the NewElt is an aggregate, cast 10475ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // the pointer to an integer of the same size before doing the load. 10485ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Value *SrcField = NewElts[i]; 10495ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const Type *FieldTy = 10505ffe6acd577696a41932c7b82db06a04687e07baChris Lattner cast<PointerType>(SrcField->getType())->getElementType(); 1051583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 1052583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 1053583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 1054583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (FieldSizeBits == 0) continue; 1055583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 1056fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson const IntegerType *FieldIntTy = Context->getIntegerType(FieldSizeBits); 10575ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (!isa<IntegerType>(FieldTy) && !FieldTy->isFloatingPoint() && 10585ffe6acd577696a41932c7b82db06a04687e07baChris Lattner !isa<VectorType>(FieldTy)) 1059fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson SrcField = new BitCastInst(SrcField, 1060fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getPointerTypeUnqual(FieldIntTy), 10615ffe6acd577696a41932c7b82db06a04687e07baChris Lattner "", LI); 10625ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new LoadInst(SrcField, "sroa.load.elt", LI); 10635ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10645ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If SrcField is a fp or vector of the right size but that isn't an 10655ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // integer type, bitcast to an integer so we can shift it. 10665ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (SrcField->getType() != FieldIntTy) 10675ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI); 10685ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10695ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Zero extend the field to be the same size as the final alloca so that 10705ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // we can shift and insert it. 10715ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (SrcField->getType() != ResultVal->getType()) 10725ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI); 10735ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10745ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Determine the number of bits to shift SrcField. 10755ffe6acd577696a41932c7b82db06a04687e07baChris Lattner uint64_t Shift; 10765ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (Layout) // Struct case. 10775ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = Layout->getElementOffsetInBits(i); 10785ffe6acd577696a41932c7b82db06a04687e07baChris Lattner else // Array case. 10795ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = i*ArrayEltBitOffset; 10805ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10815ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (TD->isBigEndian()) 10825ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth(); 10835ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10845ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (Shift) { 1085fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *ShiftVal = Context->getConstantInt(SrcField->getType(), Shift); 10865ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI); 10875ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 10885ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10895ffe6acd577696a41932c7b82db06a04687e07baChris Lattner ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI); 10905ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 109141b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 109241b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman // Handle tail padding by truncating the result 109341b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits) 109441b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI); 109541b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 10965ffe6acd577696a41932c7b82db06a04687e07baChris Lattner LI->replaceAllUsesWith(ResultVal); 10975ffe6acd577696a41932c7b82db06a04687e07baChris Lattner LI->eraseFromParent(); 10985ffe6acd577696a41932c7b82db06a04687e07baChris Lattner} 10995ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 1100372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 11013cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands/// HasPadding - Return true if the specified type has any structure or 11023cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands/// alignment padding, false otherwise. 1103a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sandsstatic bool HasPadding(const Type *Ty, const TargetData &TD) { 110439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (const StructType *STy = dyn_cast<StructType>(Ty)) { 110539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner const StructLayout *SL = TD.getStructLayout(STy); 110639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned PrevFieldBitOffset = 0; 110739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 11083cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands unsigned FieldBitOffset = SL->getElementOffsetInBits(i); 11093cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 111039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Padding in sub-elements? 1111a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands if (HasPadding(STy->getElementType(i), TD)) 111239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 11133cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 111439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Check to see if there is any padding between this element and the 111539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // previous one. 111639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (i) { 11173cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands unsigned PrevFieldEnd = 111839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1)); 111939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (PrevFieldEnd < FieldBitOffset) 112039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 112139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 11223cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 112339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner PrevFieldBitOffset = FieldBitOffset; 112439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 11253cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 112639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Check for tail padding. 112739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (unsigned EltCount = STy->getNumElements()) { 112839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned PrevFieldEnd = PrevFieldBitOffset + 112939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner TD.getTypeSizeInBits(STy->getElementType(EltCount-1)); 11303cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands if (PrevFieldEnd < SL->getSizeInBits()) 113139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 113239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 113339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 113439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 1135a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands return HasPadding(ATy->getElementType(), TD); 11363cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands } else if (const VectorType *VTy = dyn_cast<VectorType>(Ty)) { 1137a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands return HasPadding(VTy->getElementType(), TD); 113839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 1139777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands return TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty); 114039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner} 1141372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 1142f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 1143f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 1144f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// or 1 if safe after canonicalization has been performed. 11455e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 1146f5990edc877c4e63503c589928a00ec6ec751830Chris Lattnerint SROA::isSafeAllocaToScalarRepl(AllocationInst *AI) { 11475e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // Loop over the use list of the alloca. We can only transform it if all of 11485e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // the users are safe to transform. 114939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo Info; 115039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 11515e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 1152f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner I != E; ++I) { 115339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeUseOfAllocation(cast<Instruction>(*I), AI, Info); 115439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) { 1155b7427031372337e6d67f9573ec6c722ab5ea913eBill Wendling DOUT << "Cannot transform: " << *AI << " due to user: " << **I; 1156f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return 0; 11575e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 1158f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 115939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 116039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Okay, we know all the users are promotable. If the aggregate is a memcpy 116139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // source and destination, we have to be careful. In particular, the memcpy 116239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // could be moving around elements that live in structure padding of the LLVM 116339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // types, but may actually be used. In these cases, we refuse to promote the 116439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // struct. 116539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isMemCpySrc && Info.isMemCpyDst && 116656c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner HasPadding(AI->getType()->getElementType(), *TD)) 116739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return 0; 11683cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 116939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // If we require cleanup, return 1, otherwise return 3. 11704afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel return Info.needsCleanup ? 1 : 3; 1171f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner} 1172f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner 11734afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// CleanupGEP - GEP is used by an Alloca, which can be prompted after the GEP 11744afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// is canonicalized here. 11754afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patelvoid SROA::CleanupGEP(GetElementPtrInst *GEPI) { 11764afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel gep_type_iterator I = gep_type_begin(GEPI); 11774afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel ++I; 11784afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 11797afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel const ArrayType *AT = dyn_cast<ArrayType>(*I); 11807afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel if (!AT) 11817afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel return; 11827afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel 11837afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel uint64_t NumElements = AT->getNumElements(); 11847afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel 11857afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel if (isa<ConstantInt>(I.getOperand())) 11867afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel return; 11877afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel 11887afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel if (NumElements == 1) { 1189fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson GEPI->setOperand(2, Context->getNullValue(Type::Int32Ty)); 11907afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel return; 11917afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel } 11924afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 11937afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel assert(NumElements == 2 && "Unhandled case!"); 11947afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // All users of the GEP must be loads. At each use of the GEP, insert 11957afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // two loads of the appropriate indexed GEP and select between them. 11967afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *IsOne = new ICmpInst(ICmpInst::ICMP_NE, I.getOperand(), 1197fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getNullValue(I.getOperand()->getType()), 11987afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel "isone", GEPI); 11997afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // Insert the new GEP instructions, which are properly indexed. 12007afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel SmallVector<Value*, 8> Indices(GEPI->op_begin()+1, GEPI->op_end()); 1201fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Indices[1] = Context->getNullValue(Type::Int32Ty); 12027afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *ZeroIdx = GetElementPtrInst::Create(GEPI->getOperand(0), 12037afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Indices.begin(), 12047afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Indices.end(), 12057afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel GEPI->getName()+".0", GEPI); 1206fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Indices[1] = Context->getConstantInt(Type::Int32Ty, 1); 12077afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *OneIdx = GetElementPtrInst::Create(GEPI->getOperand(0), 12087afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Indices.begin(), 12097afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Indices.end(), 12107afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel GEPI->getName()+".1", GEPI); 12117afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // Replace all loads of the variable index GEP with loads from both 12127afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // indexes and a select. 12137afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel while (!GEPI->use_empty()) { 12147afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel LoadInst *LI = cast<LoadInst>(GEPI->use_back()); 12157afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI); 12167afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *One = new LoadInst(OneIdx , LI->getName()+".1", LI); 12177afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *R = SelectInst::Create(IsOne, One, Zero, LI->getName(), LI); 12187afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel LI->replaceAllUsesWith(R); 12197afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel LI->eraseFromParent(); 12204afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 12217afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel GEPI->eraseFromParent(); 12224afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel} 12234afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 12247afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel 12254afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// CleanupAllocaUsers - If SROA reported that it can promote the specified 1226f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// allocation, but only if cleaned up, perform the cleanups required. 12274afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patelvoid SROA::CleanupAllocaUsers(AllocationInst *AI) { 1228d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // At this point, we know that the end result will be SROA'd and promoted, so 1229d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // we can insert ugly code if required so long as sroa+mem2reg will clean it 1230d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // up. 1231d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 1232d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner UI != E; ) { 12334afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel User *U = *UI++; 12344afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) 12354afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel CleanupGEP(GEPI); 12360906b1bf09769d5301e62d372b363b4cd0b5a6c7Jay Foad else { 12370906b1bf09769d5301e62d372b363b4cd0b5a6c7Jay Foad Instruction *I = cast<Instruction>(U); 12384afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel SmallVector<DbgInfoIntrinsic *, 2> DbgInUses; 1239b0c4199a55d72fb9560f00b84a92a062fb8e79eaZhou Sheng if (!isa<StoreInst>(I) && OnlyUsedByDbgInfoIntrinsics(I, &DbgInUses)) { 12404afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // Safe to remove debug info uses. 12414afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel while (!DbgInUses.empty()) { 12424afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DbgInfoIntrinsic *DI = DbgInUses.back(); DbgInUses.pop_back(); 12434afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DI->eraseFromParent(); 1244d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 12454afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel I->eraseFromParent(); 1246d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 1247d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 1248d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 12495e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 1250a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 12512e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// MergeInType - Add the 'In' type to the accumulated type (Accum) so far at 12522e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// the offset specified by Offset (which is specified in bytes). 1253de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 12542e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// There are two cases we handle here: 12552e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// 1) A union of vector types of the same size and potentially its elements. 1256d22dbdf60652536d44dc4a380059368bea75b5cdChris Lattner/// Here we turn element accesses into insert/extract element operations. 12572e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// This promotes a <4 x float> with a store of float to the third element 12582e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// into a <4 x float> that uses insert element. 12592e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// 2) A fully general blob of memory, which we turn into some (potentially 12602e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// large) integer type with extract and insert operations where the loads 12612e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// and stores would mutate the memory. 12627809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattnerstatic void MergeInType(const Type *In, uint64_t Offset, const Type *&VecTy, 1263fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson unsigned AllocaSize, const TargetData &TD, 1264fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson LLVMContext* Context) { 12657809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If this could be contributing to a vector, analyze it. 12667809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VecTy != Type::VoidTy) { // either null or a vector type. 12677809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 12687809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If the In type is a vector that is the same size as the alloca, see if it 12697809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // matches the existing VecTy. 12707809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (const VectorType *VInTy = dyn_cast<VectorType>(In)) { 12717809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) { 12727809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If we're storing/loading a vector of the right size, allow it as a 12737809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // vector. If this the first vector we see, remember the type so that 12747809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // we know the element size. 12757809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VecTy == 0) 12767809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner VecTy = VInTy; 12777809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return; 12787809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 12797809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } else if (In == Type::FloatTy || In == Type::DoubleTy || 12807809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner (isa<IntegerType>(In) && In->getPrimitiveSizeInBits() >= 8 && 12817809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner isPowerOf2_32(In->getPrimitiveSizeInBits()))) { 12827809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If we're accessing something that could be an element of a vector, see 12837809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // if the implied vector agrees with what we already have and if Offset is 12847809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // compatible with it. 12857809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner unsigned EltSize = In->getPrimitiveSizeInBits()/8; 12867809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (Offset % EltSize == 0 && 12877809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaSize % EltSize == 0 && 12887809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner (VecTy == 0 || 12897809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner cast<VectorType>(VecTy)->getElementType() 12907809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ->getPrimitiveSizeInBits()/8 == EltSize)) { 12917809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VecTy == 0) 1292fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson VecTy = Context->getVectorType(In, AllocaSize/EltSize); 12937809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return; 12947809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 12952e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 12962e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 12972e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner 12987809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Otherwise, we have a case that we can't handle with an optimized vector 12997809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // form. We can still turn this into a large integer. 13007809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner VecTy = Type::VoidTy; 1301a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1302a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 13032e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// CanConvertToScalar - V is a pointer. If we can convert the pointee and all 13047809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// its accesses to use a to single vector type, return true, and set VecTy to 13057809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// the new type. If we could convert the alloca into a single promotable 13067809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// integer, return true but set VecTy to VoidTy. Further, if the use is not a 13077809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// completely trivial use that mem2reg could promote, set IsNotTrivial. Offset 13087809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// is the current offset from the base of the alloca being analyzed. 1309a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// 13101a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner/// If we see at least one access to the value that is as a vector type, set the 13111a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner/// SawVec flag. 13121a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner/// 13131a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattnerbool SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy, 13141a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool &SawVec, uint64_t Offset, 13157809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner unsigned AllocaSize) { 1316a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 1317a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Instruction *User = cast<Instruction>(*UI); 1318a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1319a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 13202e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Don't break volatile loads. 13216e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LI->isVolatile()) 13222e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1323fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson MergeInType(LI->getType(), Offset, VecTy, AllocaSize, *TD, Context); 13241a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner SawVec |= isa<VectorType>(LI->getType()); 1325cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1326cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 1327cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 1328cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 132924d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer // Storing the pointer, not into the value? 13306e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (SI->getOperand(0) == V || SI->isVolatile()) return 0; 1331fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson MergeInType(SI->getOperand(0)->getType(), Offset, 1332fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson VecTy, AllocaSize, *TD, Context); 13331a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner SawVec |= isa<VectorType>(SI->getOperand(0)->getType()); 1334cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1335cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 13362e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner 13372e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { 13381a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (!CanConvertToScalar(BCI, IsNotTrivial, VecTy, SawVec, Offset, 13391a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner AllocaSize)) 13402e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1341a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner IsNotTrivial = true; 1342cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1343cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 1344cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 1345cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 13462e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If this is a GEP with a variable indices, we can't handle it. 13472e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (!GEP->hasAllConstantIndices()) 13482e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1349cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 13502e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Compute the offset that this GEP adds to the pointer. 13512e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 13522e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner uint64_t GEPOffset = TD->getIndexedOffset(GEP->getOperand(0)->getType(), 13532e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner &Indices[0], Indices.size()); 13542e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // See if all uses can be converted. 13551a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (!CanConvertToScalar(GEP, IsNotTrivial, VecTy, SawVec,Offset+GEPOffset, 13567809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaSize)) 13572e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 13582e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner IsNotTrivial = true; 13592e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner continue; 1360a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 13613ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner 13623d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 13633d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // handle it. 13643ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 13653ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner // Store of constant value and constant size. 13663ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (isa<ConstantInt>(MSI->getValue()) && 13673ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner isa<ConstantInt>(MSI->getLength())) { 13683ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner IsNotTrivial = true; 13693ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner continue; 13703ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner } 13713d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner } 1372c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1373c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 1374c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // can handle it like a load or store of the scalar type. 1375c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 1376c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength())) 1377c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (Len->getZExtValue() == AllocaSize && Offset == 0) { 1378c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner IsNotTrivial = true; 1379c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner continue; 1380c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1381c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1382dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner 138300e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel // Ignore dbg intrinsic. 138400e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel if (isa<DbgInfoIntrinsic>(User)) 138500e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel continue; 138600e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel 13872e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Otherwise, we cannot handle this! 13882e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1389a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1390a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 13912e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return true; 1392a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1393a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1394a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1395a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 1396de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// directly. This happens when we are converting an "integer union" to a 1397de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// single integer scalar, or when we are converting a "vector union" to a 1398de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// vector with insert/extractelement instructions. 1399de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 1400de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// Offset is an offset from the original alloca, in bits that need to be 1401de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// shifted to the right. By the end of this, there should be no uses of Ptr. 14022e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattnervoid SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset) { 1403a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner while (!Ptr->use_empty()) { 1404a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Instruction *User = cast<Instruction>(Ptr->use_back()); 14054b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1406cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) { 1407b10e0da065fc2c18b5bee9011eb249e223a23108Chris Lattner ConvertUsesToScalar(CI, NewAI, Offset); 1408a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner CI->eraseFromParent(); 1409cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1410cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 14114b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1412cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 14132e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Compute the offset that this GEP adds to the pointer. 14142e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 14152e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner uint64_t GEPOffset = TD->getIndexedOffset(GEP->getOperand(0)->getType(), 14162e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner &Indices[0], Indices.size()); 14172e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8); 1418a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner GEP->eraseFromParent(); 1419cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1420a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 14213d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 14229bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner IRBuilder<> Builder(User->getParent(), User); 14239bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 14249bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 14256e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner // The load is a bit extract from NewAI shifted right by Offset bits. 14266e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp"); 14276e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *NewLoadVal 14286e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder); 14296e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner LI->replaceAllUsesWith(NewLoadVal); 14309bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner LI->eraseFromParent(); 14319bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner continue; 14329bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 14339bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 14349bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 14359bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner assert(SI->getOperand(0) != Ptr && "Consistency error!"); 14369bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Value *Old = Builder.CreateLoad(NewAI, (NewAI->getName()+".in").c_str()); 14379bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset, 14389bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Builder); 14399bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Builder.CreateStore(New, NewAI); 14409bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner SI->eraseFromParent(); 14419bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner continue; 14429bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 14439bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 14443d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 14453d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // transform it into a store of the expanded constant value. 14463d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 14473d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner assert(MSI->getRawDest() == Ptr && "Consistency error!"); 14483d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 144933e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner if (NumBytes != 0) { 145033e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue(); 145133e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner 145233e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner // Compute the value replicated the right number of times. 145333e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner APInt APVal(NumBytes*8, Val); 14543d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 145533e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner // Splat the value if non-zero. 145633e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner if (Val) 145733e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner for (unsigned i = 1; i != NumBytes; ++i) 145833e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner APVal |= APVal << 8; 145933e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner 146033e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner Value *Old = Builder.CreateLoad(NewAI, (NewAI->getName()+".in").c_str()); 1461fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *New = ConvertScalar_InsertValue(Context->getConstantInt(APVal), 1462fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Old, Offset, Builder); 146333e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner Builder.CreateStore(New, NewAI); 146433e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner } 14653d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner MSI->eraseFromParent(); 14663d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner continue; 14673d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner } 1468c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1469c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 1470c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // can handle it like a load or store of the scalar type. 1471c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 1472c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner assert(Offset == 0 && "must be store to start of alloca"); 1473c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1474c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // If the source and destination are both to the same alloca, then this is 1475c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // a noop copy-to-self, just delete it. Otherwise, emit a load and store 1476c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // as appropriate. 1477c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner AllocaInst *OrigAI = cast<AllocaInst>(Ptr->getUnderlyingObject()); 1478c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1479c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (MTI->getSource()->getUnderlyingObject() != OrigAI) { 1480c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // Dest must be OrigAI, change this to be a load from the original 1481c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // pointer (bitcasted), then a store to our new alloca. 1482c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?"); 1483c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner Value *SrcPtr = MTI->getSource(); 1484c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner SrcPtr = Builder.CreateBitCast(SrcPtr, NewAI->getType()); 1485c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1486c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval"); 1487c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner SrcVal->setAlignment(MTI->getAlignment()); 1488c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner Builder.CreateStore(SrcVal, NewAI); 1489c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } else if (MTI->getDest()->getUnderlyingObject() != OrigAI) { 1490c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // Src must be OrigAI, change this to be a load from NewAI then a store 1491c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // through the original dest pointer (bitcasted). 1492c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?"); 1493c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval"); 1494c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1495c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), NewAI->getType()); 1496c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr); 1497c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner NewStore->setAlignment(MTI->getAlignment()); 1498c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } else { 1499c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // Noop transfer. Src == Dst 1500c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1501c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1502c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1503c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner MTI->eraseFromParent(); 1504c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner continue; 1505c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1506dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner 150700e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel // If user is a dbg info intrinsic then it is safe to remove it. 150800e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel if (isa<DbgInfoIntrinsic>(User)) { 150900e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel User->eraseFromParent(); 151000e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel continue; 151100e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel } 151200e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel 1513cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner assert(0 && "Unsupported operation!"); 1514cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner abort(); 1515a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1516a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 151779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 15186e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer 15196e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// or vector value FromVal, extracting the bits from the offset specified by 15206e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// Offset. This returns the value, which is of type ToType. 15216e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// 15226e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// This happens when we are converting an "integer union" to a single 15234b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// integer scalar, or when we are converting a "vector union" to a vector with 15244b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// insert/extractelement instructions. 1525800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// 15264b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// Offset is an offset from the original alloca, in bits that need to be 15276e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// shifted to the right. 15286e01115bb122ef82daa6c8133a1d199d6b8ff767Chris LattnerValue *SROA::ConvertScalar_ExtractValue(Value *FromVal, const Type *ToType, 15296e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner uint64_t Offset, IRBuilder<> &Builder) { 15302e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If the load is of the whole new alloca, no conversion is needed. 15316e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (FromVal->getType() == ToType && Offset == 0) 15326e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return FromVal; 15339d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner 15342e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If the result alloca is a vector type, this is either an element 15352e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // access or a bitcast to another vector type of the same size. 15366e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) { 15376e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (isa<VectorType>(ToType)) 15386e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return Builder.CreateBitCast(FromVal, ToType, "tmp"); 15399d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner 15409d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Otherwise it must be an element access. 15419d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner unsigned Elt = 0; 15429d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (Offset) { 1543777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands unsigned EltSize = TD->getTypeAllocSizeInBits(VTy->getElementType()); 15449d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner Elt = Offset/EltSize; 15452e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner assert(EltSize*Elt == Offset && "Invalid modulus in validity checking"); 1546800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 15472e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Return the element extracted out of it. 15486e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *V = Builder.CreateExtractElement(FromVal, 1549fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getConstantInt(Type::Int32Ty,Elt), 15509bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner "tmp"); 15516e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (V->getType() != ToType) 15526e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner V = Builder.CreateBitCast(V, ToType, "tmp"); 15537809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return V; 15549d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } 15551aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner 15561aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner // If ToType is a first class aggregate, extract out each of the pieces and 15571aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner // use insertvalue's to form the FCA. 15581aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner if (const StructType *ST = dyn_cast<StructType>(ToType)) { 15591aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner const StructLayout &Layout = *TD->getStructLayout(ST); 1560fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *Res = Context->getUndef(ST); 15611aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 15621aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i), 1563e991ced7cb5cb86d1c33b8d400b1be41185bc69fChris Lattner Offset+Layout.getElementOffsetInBits(i), 15641aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Builder); 15651aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 15661aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 15671aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner return Res; 15681aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 15691aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner 15701aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(ToType)) { 1571777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t EltSize = TD->getTypeAllocSizeInBits(AT->getElementType()); 1572fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Value *Res = Context->getUndef(AT); 15731aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 15741aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(), 15751aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Offset+i*EltSize, Builder); 15761aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 15771aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 15781aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner return Res; 15791aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 15804b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15812e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Otherwise, this must be a union that was converted to an integer value. 15826e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner const IntegerType *NTy = cast<IntegerType>(FromVal->getType()); 15834b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15849d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // If this is a big-endian system and the load is narrower than the 15859d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // full alloca type, we need to do a shift to get the right bits. 15869d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner int ShAmt = 0; 158756c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner if (TD->isBigEndian()) { 15889d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 15899d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 15909d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // integers with a bitwidth that is not a multiple of 8. 159156c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner ShAmt = TD->getTypeStoreSizeInBits(NTy) - 15926e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner TD->getTypeStoreSizeInBits(ToType) - Offset; 15939d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 15949d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner ShAmt = Offset; 15959d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } 15964b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15979d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Note: we support negative bitwidths (with shl) which are not defined. 15989d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // We do this to support (f.e.) loads off the end of a structure where 15999d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // only some bits are used. 16009d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth()) 1601fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson FromVal = Builder.CreateLShr(FromVal, 1602fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getConstantInt(FromVal->getType(), 16031aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner ShAmt), "tmp"); 16049d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth()) 1605fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson FromVal = Builder.CreateShl(FromVal, 1606fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getConstantInt(FromVal->getType(), 16071aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner -ShAmt), "tmp"); 16084b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16099d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Finally, unconditionally truncate the integer to the right width. 16106e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner unsigned LIBitWidth = TD->getTypeSizeInBits(ToType); 16119d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (LIBitWidth < NTy->getBitWidth()) 1612fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson FromVal = 1613fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Builder.CreateTrunc(FromVal, Context->getIntegerType(LIBitWidth), "tmp"); 161455a683d7f03b0acaf7807545fd7be319498277ffChris Lattner else if (LIBitWidth > NTy->getBitWidth()) 1615fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson FromVal = 1616fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Builder.CreateZExt(FromVal, Context->getIntegerType(LIBitWidth), "tmp"); 16174b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16189d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // If the result is an integer, this is a trunc or bitcast. 16196e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (isa<IntegerType>(ToType)) { 16209d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Should be done. 16216e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner } else if (ToType->isFloatingPoint() || isa<VectorType>(ToType)) { 16229d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Just do a bitcast, we know the sizes match up. 16236e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp"); 16249d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 16259d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Otherwise must be a pointer. 16266e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp"); 1627800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 16286e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner assert(FromVal->getType() == ToType && "Didn't convert right?"); 16296e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return FromVal; 1630800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1631800de31776356910eb877e71df9f32b0a6215324Chris Lattner 1632800de31776356910eb877e71df9f32b0a6215324Chris Lattner 16339b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer 16349b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// or vector value "Old" at the offset specified by Offset. 16359b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// 16369b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// This happens when we are converting an "integer union" to a 1637800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// single integer scalar, or when we are converting a "vector union" to a 1638800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// vector with insert/extractelement instructions. 1639800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// 1640800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// Offset is an offset from the original alloca, in bits that need to be 16419b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// shifted to the right. 16429b872db775797dea4b391a9347cfbd2ca9c558e2Chris LattnerValue *SROA::ConvertScalar_InsertValue(Value *SV, Value *Old, 164365a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner uint64_t Offset, IRBuilder<> &Builder) { 16444b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1645800de31776356910eb877e71df9f32b0a6215324Chris Lattner // Convert the stored type to the actual type, shift it left to insert 1646800de31776356910eb877e71df9f32b0a6215324Chris Lattner // then 'or' into place. 16479b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner const Type *AllocaType = Old->getType(); 16484b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16492e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(AllocaType)) { 1650777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t VecSize = TD->getTypeAllocSizeInBits(VTy); 1651777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t ValSize = TD->getTypeAllocSizeInBits(SV->getType()); 165229e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 165329e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner // Changing the whole vector with memset or with an access of a different 165429e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner // vector type? 165529e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner if (ValSize == VecSize) 165629e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner return Builder.CreateBitCast(SV, AllocaType, "tmp"); 165729e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 1658777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t EltSize = TD->getTypeAllocSizeInBits(VTy->getElementType()); 165929e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 166029e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner // Must be an element insertion. 166129e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner unsigned Elt = Offset/EltSize; 166229e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 166329e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner if (SV->getType() != VTy->getElementType()) 166429e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp"); 166529e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 166629e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner SV = Builder.CreateInsertElement(Old, SV, 1667fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Context->getConstantInt(Type::Int32Ty, Elt), 166829e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner "tmp"); 16692e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return SV; 16702e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 16719b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner 16729b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner // If SV is a first-class aggregate value, insert each value recursively. 16739b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner if (const StructType *ST = dyn_cast<StructType>(SV->getType())) { 16749b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner const StructLayout &Layout = *TD->getStructLayout(ST); 16759b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 167665a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 16779b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner Old = ConvertScalar_InsertValue(Elt, Old, 1678e991ced7cb5cb86d1c33b8d400b1be41185bc69fChris Lattner Offset+Layout.getElementOffsetInBits(i), 167965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Builder); 16809b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 16819b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner return Old; 16829b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 16839b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner 16849b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) { 1685777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t EltSize = TD->getTypeAllocSizeInBits(AT->getElementType()); 16869b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 168765a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 168865a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder); 16899b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 16909b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner return Old; 16919b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 16924b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16932e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If SV is a float, convert it to the appropriate integer type. 16949b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner // If it is a pointer, do the same. 16952e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned SrcWidth = TD->getTypeSizeInBits(SV->getType()); 16962e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned DestWidth = TD->getTypeSizeInBits(AllocaType); 16972e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned SrcStoreWidth = TD->getTypeStoreSizeInBits(SV->getType()); 16982e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned DestStoreWidth = TD->getTypeStoreSizeInBits(AllocaType); 16992e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (SV->getType()->isFloatingPoint() || isa<VectorType>(SV->getType())) 1700fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson SV = Builder.CreateBitCast(SV, Context->getIntegerType(SrcWidth), "tmp"); 17012e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner else if (isa<PointerType>(SV->getType())) 170265a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreatePtrToInt(SV, TD->getIntPtrType(), "tmp"); 17034b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17047809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Zero extend or truncate the value if needed. 17057809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (SV->getType() != AllocaType) { 17067809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (SV->getType()->getPrimitiveSizeInBits() < 17077809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaType->getPrimitiveSizeInBits()) 170865a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateZExt(SV, AllocaType, "tmp"); 17097809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner else { 17107809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Truncation may be needed if storing more than the alloca can hold 17117809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // (undefined behavior). 171265a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateTrunc(SV, AllocaType, "tmp"); 17137809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner SrcWidth = DestWidth; 17147809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner SrcStoreWidth = DestStoreWidth; 17157809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 17167809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 17174b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17182e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If this is a big-endian system and the store is narrower than the 17192e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // full alloca type, we need to do a shift to get the right bits. 17202e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner int ShAmt = 0; 17212e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (TD->isBigEndian()) { 17222e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 17232e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 17242e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // integers with a bitwidth that is not a multiple of 8. 17252e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ShAmt = DestStoreWidth - SrcStoreWidth - Offset; 1726800de31776356910eb877e71df9f32b0a6215324Chris Lattner } else { 17272e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ShAmt = Offset; 17282e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 17294b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17302e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Note: we support negative bitwidths (with shr) which are not defined. 17312e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // We do this to support (f.e.) stores off the end of a structure where 17322e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // only some bits in the structure are set. 17332e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth)); 17342e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) { 1735fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson SV = Builder.CreateShl(SV, Context->getConstantInt(SV->getType(), 1736fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson ShAmt), "tmp"); 17372e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner Mask <<= ShAmt; 17382e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) { 1739fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson SV = Builder.CreateLShr(SV, Context->getConstantInt(SV->getType(), 1740fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson -ShAmt), "tmp"); 17410e7c46bc7eb68099eecd1244390dccd0a77d0875Duncan Sands Mask = Mask.lshr(-ShAmt); 17422e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 17434b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17442e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Mask out the bits we are about to insert from the old value, and or 17452e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // in the new bits. 17462e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (SrcWidth != DestWidth) { 17472e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner assert(DestWidth > SrcWidth); 1748fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Old = Builder.CreateAnd(Old, Context->getConstantInt(~Mask), "mask"); 174965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateOr(Old, SV, "ins"); 1750800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 1751800de31776356910eb877e71df9f32b0a6215324Chris Lattner return SV; 1752800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1753800de31776356910eb877e71df9f32b0a6215324Chris Lattner 1754800de31776356910eb877e71df9f32b0a6215324Chris Lattner 175579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 175679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// PointsToConstantGlobal - Return true if V (possibly indirectly) points to 175779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// some part of a constant global variable. This intentionally only accepts 175879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// constant expressions because we don't can't rewrite arbitrary instructions. 175979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool PointsToConstantGlobal(Value *V) { 176079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 176179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return GV->isConstant(); 176279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 176379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (CE->getOpcode() == Instruction::BitCast || 176479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner CE->getOpcode() == Instruction::GetElementPtr) 176579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return PointsToConstantGlobal(CE->getOperand(0)); 176679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 176779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 176879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 176979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) 177079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// pointer to an alloca. Ignore any reads of the pointer, return false if we 177179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// see any stores or other unknown uses. If we see pointer arithmetic, keep 177279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// track of whether it moves the pointer (with isOffset) but otherwise traverse 177379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to 177479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the alloca, and if the source pointer is a pointer to a constant global, we 177579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// can optimize this. 177679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool isOnlyCopiedFromConstantGlobal(Value *V, Instruction *&TheCopy, 177779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner bool isOffset) { 177879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 17796e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) 17806e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // Ignore non-volatile loads, they are always ok. 17816e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (!LI->isVolatile()) 17826e733d34ca487ab7ff8a6def018a933620393869Chris Lattner continue; 17836e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 178479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) { 178579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If uses of the bitcast are ok, we are ok. 178679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset)) 178779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 178879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 178979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 179079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { 179179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the GEP has all zero indices, it doesn't offset the pointer. If it 179279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // doesn't, it does. 179379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy, 179479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner isOffset || !GEP->hasAllZeroIndices())) 179579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 179679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 179779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 179879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 179979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If this is isn't our memcpy/memmove, reject it as something we can't 180079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // handle. 18013ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (!isa<MemTransferInst>(*UI)) 180279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 180379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 180479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If we already have seen a copy, reject the second one. 180579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (TheCopy) return false; 180679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 180779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the pointer has been offset from the start of the alloca, we can't 180879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // safely handle this. 180979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (isOffset) return false; 181079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 181179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the memintrinsic isn't using the alloca as the dest, reject it. 181279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (UI.getOperandNo() != 1) return false; 181379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 181479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner MemIntrinsic *MI = cast<MemIntrinsic>(*UI); 181579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 181679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the source of the memcpy/move is not a constant global, reject it. 181779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!PointsToConstantGlobal(MI->getOperand(2))) 181879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 181979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 182079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Otherwise, the transform is safe. Remember the copy instruction. 182179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner TheCopy = MI; 182279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 182379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return true; 182479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 182579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 182679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only 182779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// modified by a copy from a constant global. If we can prove this, we can 182879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// replace any uses of the alloca with uses of the global directly. 182979b3bd395dc3303cde65e18e0524ed2f70268c99Chris LattnerInstruction *SROA::isOnlyCopiedFromConstantGlobal(AllocationInst *AI) { 183079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner Instruction *TheCopy = 0; 183179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false)) 183279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return TheCopy; 183379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return 0; 183479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 1835