ScalarReplAggregates.cpp revision 4afc90dacf309999d8b7f6c2b4b0c56af346bab5
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" 30372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/Pass.h" 3138aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Analysis/Dominators.h" 3238aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Target/TargetData.h" 3338aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 344afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel#include "llvm/Transforms/Utils/Local.h" 359525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Debug.h" 36a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 3765a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner#include "llvm/Support/IRBuilder.h" 38a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/MathExtras.h" 39a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 401ccd185cb49d81465a2901622e58ceae046d1d83Chris Lattner#include "llvm/ADT/SmallVector.h" 41551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 42551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/StringExtras.h" 43d8664730942beb911327336d1f9db8e7efcd6813Chris Lattnerusing namespace llvm; 44d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 450e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of allocas broken up"); 460e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted, "Number of allocas promoted"); 470e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumConverted, "Number of aggregates converted to scalar"); 4879b3bd395dc3303cde65e18e0524ed2f70268c99Chris LattnerSTATISTIC(NumGlobals, "Number of allocas copied from constant global"); 49ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 500e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 519525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN SROA : public FunctionPass { 52ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 53ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman explicit SROA(signed T = -1) : FunctionPass(&ID) { 54ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel if (T == -1) 55b0e71edb6b33f822e001500dac90acf95faacea8Chris Lattner SRThreshold = 128; 56ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel else 57ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel SRThreshold = T; 58ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel } 59794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 60ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 61ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 6238aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performScalarRepl(Function &F); 6338aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performPromotion(Function &F); 6438aec325604635380421a27e39ab06d55ed2458dChris Lattner 65a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 66a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // will not alter the CFG, so say so. 67a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 68326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel AU.addRequired<DominatorTree>(); 6938aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<DominanceFrontier>(); 7038aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<TargetData>(); 71a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner AU.setPreservesCFG(); 72a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner } 73a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner 74ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 7556c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner TargetData *TD; 7656c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner 7739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// AllocaInfo - When analyzing uses of an alloca instruction, this captures 7839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// information about the uses. All these fields are initialized to false 7939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// and set to true when something is learned. 8039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner struct AllocaInfo { 8139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isUnsafe - This is set to true if the alloca cannot be SROA'd. 8239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isUnsafe : 1; 8339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 844afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel /// needsCleanup - This is set to true if there is some use of the alloca 854afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel /// that requires cleanup. 864afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel bool needsCleanup : 1; 8739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 8839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isMemCpySrc - This is true if this aggregate is memcpy'd from. 8939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpySrc : 1; 9039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9133b0b8d242de8d428f11e77ea734a08b47797216Zhou Sheng /// isMemCpyDst - This is true if this aggregate is memcpy'd into. 9239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpyDst : 1; 9339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo() 954afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel : isUnsafe(false), needsCleanup(false), 9639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isMemCpySrc(false), isMemCpyDst(false) {} 9739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner }; 9839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 99ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel unsigned SRThreshold; 100ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel 10139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; } 10239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 103f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner int isSafeAllocaToScalarRepl(AllocationInst *AI); 10439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 10539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void isSafeUseOfAllocation(Instruction *User, AllocationInst *AI, 10639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info); 10739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI, 10839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info); 10939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI, 11039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned OpNo, AllocaInfo &Info); 11139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void isSafeUseOfBitCastedAllocation(BitCastInst *User, AllocationInst *AI, 11239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info); 11339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 114a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner void DoScalarReplacement(AllocationInst *AI, 115a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner std::vector<AllocationInst*> &WorkList); 1164afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel void CleanupGEP(GetElementPtrInst *GEP); 1174afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel void CleanupAllocaUsers(AllocationInst *AI); 118ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base); 119a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1208bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner void RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI, 121372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 122372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 123d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *BCInst, 124d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner AllocationInst *AI, 125d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts); 126d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocationInst *AI, 127d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1285ffe6acd577696a41932c7b82db06a04687e07baChris Lattner void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocationInst *AI, 1296e733d34ca487ab7ff8a6def018a933620393869Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 130d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 1317809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner bool CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy, 1321a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool &SawVec, uint64_t Offset, unsigned AllocaSize); 1332e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset); 1346e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType, 1359bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 1369b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal, 13765a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 13879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner static Instruction *isOnlyCopiedFromConstantGlobal(AllocationInst *AI); 139ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 140ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 141ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 142844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar SROA::ID = 0; 143844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); 144844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 145d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the ScalarReplAggregates pass 146ff366850aa9956e167e78d4f5b57aae10d8c5779Devang PatelFunctionPass *llvm::createScalarReplAggregatesPass(signed int Threshold) { 147ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel return new SROA(Threshold); 148ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel} 149ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 150ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 151ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnerbool SROA::runOnFunction(Function &F) { 15256c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner TD = &getAnalysis<TargetData>(); 15356c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner 154fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = performPromotion(F); 155fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner while (1) { 156fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool LocalChange = performScalarRepl(F); 157fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to repromote if no scalarrepl 158fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner Changed = true; 159fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner LocalChange = performPromotion(F); 160fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to re-scalarrepl if no promotion 161fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner } 16238aec325604635380421a27e39ab06d55ed2458dChris Lattner 16338aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 16438aec325604635380421a27e39ab06d55ed2458dChris Lattner} 16538aec325604635380421a27e39ab06d55ed2458dChris Lattner 16638aec325604635380421a27e39ab06d55ed2458dChris Lattner 16738aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performPromotion(Function &F) { 16838aec325604635380421a27e39ab06d55ed2458dChris Lattner std::vector<AllocaInst*> Allocas; 169326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel DominatorTree &DT = getAnalysis<DominatorTree>(); 17043f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); 17138aec325604635380421a27e39ab06d55ed2458dChris Lattner 17202a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 17338aec325604635380421a27e39ab06d55ed2458dChris Lattner 174fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = false; 175fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 17638aec325604635380421a27e39ab06d55ed2458dChris Lattner while (1) { 17738aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.clear(); 17838aec325604635380421a27e39ab06d55ed2458dChris Lattner 17938aec325604635380421a27e39ab06d55ed2458dChris Lattner // Find allocas that are safe to promote, by looking at all instructions in 18038aec325604635380421a27e39ab06d55ed2458dChris Lattner // the entry node 18138aec325604635380421a27e39ab06d55ed2458dChris Lattner for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 18238aec325604635380421a27e39ab06d55ed2458dChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 18341968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patel if (isAllocaPromotable(AI)) 18438aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.push_back(AI); 18538aec325604635380421a27e39ab06d55ed2458dChris Lattner 18638aec325604635380421a27e39ab06d55ed2458dChris Lattner if (Allocas.empty()) break; 18738aec325604635380421a27e39ab06d55ed2458dChris Lattner 188326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel PromoteMemToReg(Allocas, DT, DF); 18938aec325604635380421a27e39ab06d55ed2458dChris Lattner NumPromoted += Allocas.size(); 19038aec325604635380421a27e39ab06d55ed2458dChris Lattner Changed = true; 19138aec325604635380421a27e39ab06d55ed2458dChris Lattner } 19238aec325604635380421a27e39ab06d55ed2458dChris Lattner 19338aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 19438aec325604635380421a27e39ab06d55ed2458dChris Lattner} 19538aec325604635380421a27e39ab06d55ed2458dChris Lattner 196963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner/// getNumSAElements - Return the number of elements in the specific struct or 197963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner/// array. 198963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattnerstatic uint64_t getNumSAElements(const Type *T) { 199963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) 200963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner return ST->getNumElements(); 201963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner return cast<ArrayType>(T)->getNumElements(); 202963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner} 203963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner 20438aec325604635380421a27e39ab06d55ed2458dChris Lattner// performScalarRepl - This algorithm is a simple worklist driven algorithm, 20538aec325604635380421a27e39ab06d55ed2458dChris Lattner// which runs on all of the malloc/alloca instructions in the function, removing 20638aec325604635380421a27e39ab06d55ed2458dChris Lattner// them if they are only used by getelementptr instructions. 20738aec325604635380421a27e39ab06d55ed2458dChris Lattner// 20838aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performScalarRepl(Function &F) { 209ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner std::vector<AllocationInst*> WorkList; 210ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 211ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Scan the entry basic block, adding any alloca's and mallocs to the worklist 21202a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); 213ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 214ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner if (AllocationInst *A = dyn_cast<AllocationInst>(I)) 215ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(A); 216ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 217ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Process the worklist 218ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool Changed = false; 219ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner while (!WorkList.empty()) { 220ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner AllocationInst *AI = WorkList.back(); 221ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.pop_back(); 222a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 223add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner // Handle dead allocas trivially. These can be formed by SROA'ing arrays 224add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner // with unused elements. 225add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner if (AI->use_empty()) { 226add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner AI->eraseFromParent(); 227add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner continue; 228add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner } 2297809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 2307809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If this alloca is impossible for us to promote, reject it early. 2317809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized()) 2327809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 2337809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 2347809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Check to see if this allocation is only modified by a memcpy/memmove from 2357809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // a constant global. If this is the case, we can change all users to use 2367809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // the constant global instead. This is commonly produced by the CFE by 2377809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A' 2387809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // is only subsequently read. 2397809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (Instruction *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) { 2407809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner DOUT << "Found alloca equal to global: " << *AI; 2417809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner DOUT << " memcpy = " << *TheCopy; 2427809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Constant *TheSrc = cast<Constant>(TheCopy->getOperand(2)); 2437809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType())); 2447809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner TheCopy->eraseFromParent(); // Don't mutate the global. 2457809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AI->eraseFromParent(); 2467809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ++NumGlobals; 2477809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Changed = true; 2487809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 2497809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 250add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner 25179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Check to see if we can perform the core SROA transformation. We cannot 25279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // transform the allocation instruction if it is an array allocation 25379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // (allocations OF arrays are ok though), and an allocation of a scalar 25479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // value cannot be decomposed at all. 2557809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner uint64_t AllocaSize = TD->getTypePaddedSize(AI->getAllocatedType()); 2567809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 2577809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if ((isa<StructType>(AI->getAllocatedType()) || 2587139406707eb3869183fd6a3329fe4a77d309692Chris Lattner isa<ArrayType>(AI->getAllocatedType())) && 2597809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Do not promote any struct whose size is too big. 2607809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaSize < SRThreshold && 261963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner // Do not promote any struct into more than "32" separate vars. 262963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner getNumSAElements(AI->getAllocatedType()) < SRThreshold/4) { 263a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Check that all of the users of the allocation are capable of being 264a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // transformed. 265a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner switch (isSafeAllocaToScalarRepl(AI)) { 266a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner default: assert(0 && "Unexpected value!"); 267a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 0: // Not safe to scalar replace. 268a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner break; 269a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 1: // Safe, but requires cleanup/canonicalizations first 2704afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel CleanupAllocaUsers(AI); 271a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // FALL THROUGH. 272a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 3: // Safe to scalar replace. 273a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner DoScalarReplacement(AI, WorkList); 274a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner Changed = true; 275a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner continue; 276a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 277f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 2786e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 2796e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // If we can turn this aggregate value (potentially with casts) into a 2806e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // simple scalar value that can be mem2reg'd into a register value. 2812e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // IsNotTrivial tracks whether this is something that mem2reg could have 2822e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // promoted itself. If so, we don't want to transform it needlessly. Note 2832e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // that we can't just check based on the type: the alloca may be of an i32 2842e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // but that has pointer arithmetic to set byte 3 of it or something. 2856e733d34ca487ab7ff8a6def018a933620393869Chris Lattner bool IsNotTrivial = false; 2867809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner const Type *VectorTy = 0; 2871a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool HadAVector = false; 2881a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (CanConvertToScalar(AI, IsNotTrivial, VectorTy, HadAVector, 2897809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 0, unsigned(AllocaSize)) && IsNotTrivial) { 2907809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaInst *NewAI; 2911a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // If we were able to find a vector type that can handle this with 2921a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // insert/extract elements, and if there was at least one use that had 2931a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // a vector type, promote this to a vector. We don't want to promote 2941a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // random stuff that doesn't use vectors (e.g. <9 x double>) because then 2951a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // we just get a lot of insert/extracts. If at least one vector is 2961a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // involved, then we probably really do have a union of vector/array. 2971a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (VectorTy && isa<VectorType>(VectorTy) && HadAVector) { 2987809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner DOUT << "CONVERT TO VECTOR: " << *AI << " TYPE = " << *VectorTy <<"\n"; 29915c82779033826a0958182b746b03a22ad04a16aChris Lattner 3007809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Create and insert the vector alloca. 3017809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner NewAI = new AllocaInst(VectorTy, 0, "", AI->getParent()->begin()); 3027809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ConvertUsesToScalar(AI, NewAI, 0); 3037809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } else { 3047809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner DOUT << "CONVERT TO SCALAR INTEGER: " << *AI << "\n"; 3057809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 3067809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Create and insert the integer alloca. 3077809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner const Type *NewTy = IntegerType::get(AllocaSize*8); 3087809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin()); 30915c82779033826a0958182b746b03a22ad04a16aChris Lattner ConvertUsesToScalar(AI, NewAI, 0); 3106e733d34ca487ab7ff8a6def018a933620393869Chris Lattner } 3117809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner NewAI->takeName(AI); 3127809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AI->eraseFromParent(); 3137809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ++NumConverted; 3147809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Changed = true; 3157809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 3167809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 3176e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 3187809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Otherwise, couldn't process this alloca. 319a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 320ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 321a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner return Changed; 322a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner} 323fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 324a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner/// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl 325a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner/// predicate, do SROA now. 326a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattnervoid SROA::DoScalarReplacement(AllocationInst *AI, 327a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner std::vector<AllocationInst*> &WorkList) { 32879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner DOUT << "Found inst to SROA: " << *AI; 329a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner SmallVector<AllocaInst*, 32> ElementAllocas; 330a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 331a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 332a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 333a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 334a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->getAlignment(), 335a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->getName() + "." + utostr(i), AI); 336a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.push_back(NA); 337a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 338a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 339a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } else { 340a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 341a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.reserve(AT->getNumElements()); 342a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner const Type *ElTy = AT->getElementType(); 343a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 344a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), 345a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->getName() + "." + utostr(i), AI); 346a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.push_back(NA); 347a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 348ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 349a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 350fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 351a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Now that we have created the alloca instructions that we want to use, 352a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // expand the getelementptr instructions to use them. 353a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // 354a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner while (!AI->use_empty()) { 355a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner Instruction *User = cast<Instruction>(AI->use_back()); 356a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner if (BitCastInst *BCInst = dyn_cast<BitCastInst>(User)) { 357a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner RewriteBitCastUserOfAlloca(BCInst, AI, ElementAllocas); 358a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner BCInst->eraseFromParent(); 359a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner continue; 360a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 361a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner 3622a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // Replace: 3632a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %res = load { i32, i32 }* %alloc 3642a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // with: 3652a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %load.0 = load i32* %alloc.0 3662a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0 3672a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %load.1 = load i32* %alloc.1 3682a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1 36902518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman // (Also works for arrays instead of structs) 37002518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 37102518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Value *Insert = UndefValue::get(LI->getType()); 37202518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman for (unsigned i = 0, e = ElementAllocas.size(); i != e; ++i) { 37302518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Value *Load = new LoadInst(ElementAllocas[i], "load", LI); 37402518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI); 37502518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman } 37602518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman LI->replaceAllUsesWith(Insert); 37702518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman LI->eraseFromParent(); 37802518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman continue; 37902518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman } 38002518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman 3812a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // Replace: 3822a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // store { i32, i32 } %val, { i32, i32 }* %alloc 3832a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // with: 3842a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %val.0 = extractvalue { i32, i32 } %val, 0 3852a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // store i32 %val.0, i32* %alloc.0 3862a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // %val.1 = extractvalue { i32, i32 } %val, 1 3872a6a6457094e05e5f5ab34f90dbd25c13d61f8b5Chris Lattner // store i32 %val.1, i32* %alloc.1 38802518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman // (Also works for arrays instead of structs) 38902518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 39002518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Value *Val = SI->getOperand(0); 39102518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman for (unsigned i = 0, e = ElementAllocas.size(); i != e; ++i) { 39202518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI); 39302518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman new StoreInst(Extract, ElementAllocas[i], SI); 39402518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman } 39502518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman SI->eraseFromParent(); 39602518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman continue; 39702518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman } 39802518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman 399a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User); 400a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // We now know that the GEP is of the form: GEP <ptr>, 0, <cst> 401a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner unsigned Idx = 402a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner (unsigned)cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); 403a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner 404a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner assert(Idx < ElementAllocas.size() && "Index out of range?"); 405a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AllocaInst *AllocaToUse = ElementAllocas[Idx]; 406a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner 407a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner Value *RepValue; 408a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner if (GEPI->getNumOperands() == 3) { 409a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Do not insert a new getelementptr instruction with zero indices, only 410a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // to have it optimized out later. 411a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner RepValue = AllocaToUse; 412a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } else { 413a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // We are indexing deeply into the structure, so we still need a 414a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // getelement ptr instruction to finish the indexing. This may be 415a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // expanded itself once the worklist is rerun. 416a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // 417a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner SmallVector<Value*, 8> NewArgs; 418a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner NewArgs.push_back(Constant::getNullValue(Type::Int32Ty)); 419a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner NewArgs.append(GEPI->op_begin()+3, GEPI->op_end()); 420051a950000e21935165db56695e35bade668193bGabor Greif RepValue = GetElementPtrInst::Create(AllocaToUse, NewArgs.begin(), 421051a950000e21935165db56695e35bade668193bGabor Greif NewArgs.end(), "", GEPI); 422a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner RepValue->takeName(GEPI); 423a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 424a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner 425a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // If this GEP is to the start of the aggregate, check for memcpys. 426d356a7ee0ed7744857dcf497cb20b0128770fb0fChris Lattner if (Idx == 0 && GEPI->hasAllZeroIndices()) 427d356a7ee0ed7744857dcf497cb20b0128770fb0fChris Lattner RewriteBitCastUserOfAlloca(GEPI, AI, ElementAllocas); 428ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 429a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Move all of the users over to the new GEP. 430a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner GEPI->replaceAllUsesWith(RepValue); 431a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Delete the old GEP 432a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner GEPI->eraseFromParent(); 433ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 434ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 435a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Finally, delete the Alloca instruction 436a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->eraseFromParent(); 437a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner NumReplaced++; 438ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 4395e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 4405e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 441f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// isSafeElementUse - Check to see if this use is an allowed use for a 4428bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// getelementptr instruction of an array aggregate allocation. isFirstElt 4438bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// indicates whether Ptr is known to the start of the aggregate. 444f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// 44539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattnervoid SROA::isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI, 44639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info) { 447f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 448f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner I != E; ++I) { 449f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner Instruction *User = cast<Instruction>(*I); 450f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner switch (User->getOpcode()) { 451f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::Load: break; 452f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::Store: 453f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner // Store is ok if storing INTO the pointer, not storing the pointer 45439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (User->getOperand(0) == Ptr) return MarkUnsafe(Info); 455f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner break; 456f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner case Instruction::GetElementPtr: { 457f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner GetElementPtrInst *GEP = cast<GetElementPtrInst>(User); 4588bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner bool AreAllZeroIndices = isFirstElt; 459f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner if (GEP->getNumOperands() > 1) { 4608bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner if (!isa<ConstantInt>(GEP->getOperand(1)) || 4618bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner !cast<ConstantInt>(GEP->getOperand(1))->isZero()) 46239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Using pointer arithmetic to navigate the array. 46339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 4648bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 465d356a7ee0ed7744857dcf497cb20b0128770fb0fChris Lattner if (AreAllZeroIndices) 466d356a7ee0ed7744857dcf497cb20b0128770fb0fChris Lattner AreAllZeroIndices = GEP->hasAllZeroIndices(); 467f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 46839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeElementUse(GEP, AreAllZeroIndices, AI, Info); 46939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) return; 470f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner break; 471f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 4728bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner case Instruction::BitCast: 47339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (isFirstElt) { 47439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeUseOfBitCastedAllocation(cast<BitCastInst>(User), AI, Info); 47539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) return; 4768bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner break; 47739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 4788bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner DOUT << " Transformation preventing inst: " << *User; 47939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 4808bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner case Instruction::Call: 4818bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 48239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (isFirstElt) { 48339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeMemIntrinsicOnAllocation(MI, AI, I.getOperandNo(), Info); 48439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) return; 4858bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner break; 48639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 4878bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner } 4888bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner DOUT << " Transformation preventing inst: " << *User; 48939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 490f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner default: 491b7427031372337e6d67f9573ec6c722ab5ea913eBill Wendling DOUT << " Transformation preventing inst: " << *User; 49239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 493f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 494f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 49539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return; // All users look ok :) 496f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner} 497f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner 498d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner/// AllUsersAreLoads - Return true if all users of this value are loads. 499d878ecd904e4469344a2274f9784422c2c68b81cChris Lattnerstatic bool AllUsersAreLoads(Value *Ptr) { 500d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 501d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner I != E; ++I) 502d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (cast<Instruction>(*I)->getOpcode() != Instruction::Load) 503d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner return false; 504fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman return true; 505d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner} 506d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner 5075e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// isSafeUseOfAllocation - Check to see if this user is an allowed use for an 5085e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// aggregate allocation. 5095e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 51039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattnervoid SROA::isSafeUseOfAllocation(Instruction *User, AllocationInst *AI, 51139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info) { 512372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner if (BitCastInst *C = dyn_cast<BitCastInst>(User)) 51339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return isSafeUseOfBitCastedAllocation(C, AI, Info); 51439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 5156e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) 5166e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (!LI->isVolatile()) 5176e733d34ca487ab7ff8a6def018a933620393869Chris Lattner return;// Loads (returning a first class aggregrate) are always rewritable 51802518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman 5196e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) 5206e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (!SI->isVolatile() && SI->getOperand(0) != AI) 5216e733d34ca487ab7ff8a6def018a933620393869Chris Lattner return;// Store is ok if storing INTO the pointer, not storing the pointer 52202518140ac3310d0357c26a87b2372d85da9c2f4Matthijs Kooijman 52339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User); 52439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (GEPI == 0) 52539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 526546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 527be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner gep_type_iterator I = gep_type_begin(GEPI), E = gep_type_end(GEPI); 528be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner 52925de486263abc1882498a8701e3eb29ee0804c4eChris Lattner // The GEP is not safe to transform if not of the form "GEP <ptr>, 0, <cst>". 530be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner if (I == E || 53139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner I.getOperand() != Constant::getNullValue(I.getOperand()->getType())) { 53239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 53339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 534be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner 535be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner ++I; 53639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (I == E) return MarkUnsafe(Info); // ran out of GEP indices?? 537546fc40d69ce4051b48112aafedd1e41f4a13195Chris Lattner 5388bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner bool IsAllZeroIndices = true; 5398bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 54088e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // If the first index is a non-constant index into an array, see if we can 54188e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // handle it as a special case. 542be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 54388e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner if (!isa<ConstantInt>(I.getOperand())) { 5448bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner IsAllZeroIndices = 0; 54588e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner uint64_t NumElements = AT->getNumElements(); 5468bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 547d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // If this is an array index and the index is not constant, we cannot 548d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // promote... that is unless the array has exactly one or two elements in 549d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // it, in which case we CAN promote it, but we have to canonicalize this 550d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // out if this is the only problem. 55125de486263abc1882498a8701e3eb29ee0804c4eChris Lattner if ((NumElements == 1 || NumElements == 2) && 55239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllUsersAreLoads(GEPI)) { 5534afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Info.needsCleanup = true; 55439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return; // Canonicalization required! 55539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 55639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 557d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 5585e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 5595fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 56088e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // Walk through the GEP type indices, checking the types that this indexes 56188e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // into. 56288e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner for (; I != E; ++I) { 56388e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // Ignore struct elements, no extra checking needed for these. 56488e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner if (isa<StructType>(*I)) 56588e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner continue; 56688e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner 56788e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner ConstantInt *IdxVal = dyn_cast<ConstantInt>(I.getOperand()); 56888e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner if (!IdxVal) return MarkUnsafe(Info); 5695fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 5705fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // Are all indices still zero? 57188e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner IsAllZeroIndices &= IdxVal->isZero(); 5725fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 5735fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 5745fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // This GEP indexes an array. Verify that this is an in-range constant 5755fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // integer. Specifically, consider A[0][i]. We cannot know that the user 5765fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // isn't doing invalid things like allowing i to index an out-of-range 5775fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // subscript that accesses A[1]. Because of this, we have to reject SROA 578c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen // of any accesses into structs where any of the components are variables. 5795fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman if (IdxVal->getZExtValue() >= AT->getNumElements()) 5805fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman return MarkUnsafe(Info); 581c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen } else if (const VectorType *VT = dyn_cast<VectorType>(*I)) { 582c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen if (IdxVal->getZExtValue() >= VT->getNumElements()) 583c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen return MarkUnsafe(Info); 5845fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman } 58588e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner } 58688e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner 587be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner // If there are any non-simple uses of this getelementptr, make sure to reject 588be883a23ed64b83235d509ad0befc1d6aa6b0cd8Chris Lattner // them. 58939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return isSafeElementUse(GEPI, IsAllZeroIndices, AI, Info); 5908bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner} 5918bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 5928bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// isSafeMemIntrinsicOnAllocation - Return true if the specified memory 5938bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// intrinsic can be promoted by SROA. At this point, we know that the operand 5948bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// of the memintrinsic is a pointer to the beginning of the allocation. 59539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattnervoid SROA::isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI, 59639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned OpNo, AllocaInfo &Info) { 5978bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner // If not constant length, give up. 5988bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 59939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (!Length) return MarkUnsafe(Info); 6008bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 6018bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner // If not the whole aggregate, give up. 6023cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands if (Length->getZExtValue() != 603ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands TD->getTypePaddedSize(AI->getType()->getElementType())) 60439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 6058bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner 6068bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner // We only know about memcpy/memset/memmove. 6078bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner if (!isa<MemCpyInst>(MI) && !isa<MemSetInst>(MI) && !isa<MemMoveInst>(MI)) 60839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 60939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 61039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Otherwise, we can transform it. Determine whether this is a memcpy/set 61139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // into or out of the aggregate. 61239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (OpNo == 1) 61339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner Info.isMemCpyDst = true; 61439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner else { 61539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner assert(OpNo == 2); 61639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner Info.isMemCpySrc = true; 61739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 6185e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 6195e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner 620372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner/// isSafeUseOfBitCastedAllocation - Return true if all users of this bitcast 621372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner/// are 62239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattnervoid SROA::isSafeUseOfBitCastedAllocation(BitCastInst *BC, AllocationInst *AI, 62339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo &Info) { 624372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner for (Value::use_iterator UI = BC->use_begin(), E = BC->use_end(); 625372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner UI != E; ++UI) { 626372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner if (BitCastInst *BCU = dyn_cast<BitCastInst>(UI)) { 62739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeUseOfBitCastedAllocation(BCU, AI, Info); 628372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(UI)) { 62939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeMemIntrinsicOnAllocation(MI, AI, UI.getOperandNo(), Info); 630d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 6316e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (SI->isVolatile()) 6326e733d34ca487ab7ff8a6def018a933620393869Chris Lattner return MarkUnsafe(Info); 6336e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 634d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // If storing the entire alloca in one chunk through a bitcasted pointer 635d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // to integer, we can transform it. This happens (for example) when you 636d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // cast a {i32,i32}* to i64* and store through it. This is similar to the 637d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // memcpy case and occurs in various "byval" cases and emulated memcpys. 638d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (isa<IntegerType>(SI->getOperand(0)->getType()) && 639ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands TD->getTypePaddedSize(SI->getOperand(0)->getType()) == 640ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands TD->getTypePaddedSize(AI->getType()->getElementType())) { 641d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Info.isMemCpyDst = true; 642d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner continue; 643d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 644d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner return MarkUnsafe(Info); 6455ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(UI)) { 6466e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LI->isVolatile()) 6476e733d34ca487ab7ff8a6def018a933620393869Chris Lattner return MarkUnsafe(Info); 6486e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 6495ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If loading the entire alloca in one chunk through a bitcasted pointer 6505ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // to integer, we can transform it. This happens (for example) when you 6515ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // cast a {i32,i32}* to i64* and load through it. This is similar to the 6525ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // memcpy case and occurs in various "byval" cases and emulated memcpys. 6535ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (isa<IntegerType>(LI->getType()) && 654ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands TD->getTypePaddedSize(LI->getType()) == 655ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands TD->getTypePaddedSize(AI->getType()->getElementType())) { 6565ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Info.isMemCpySrc = true; 6575ffe6acd577696a41932c7b82db06a04687e07baChris Lattner continue; 6585ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 6595ffe6acd577696a41932c7b82db06a04687e07baChris Lattner return MarkUnsafe(Info); 6604afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } else if (isa<DbgInfoIntrinsic>(UI)) { 6614afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // If one user is DbgInfoIntrinsic then check if all users are 6624afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // DbgInfoIntrinsics. 6634afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (OnlyUsedByDbgInfoIntrinsics(BC)) { 6644afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Info.needsCleanup = true; 6654afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel return; 6664afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 6674afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel else 6684afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel MarkUnsafe(Info); 6694afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 6704afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel else { 67139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return MarkUnsafe(Info); 672372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 67339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) return; 674372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 675372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 676372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 6778bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// RewriteBitCastUserOfAlloca - BCInst (transitively) bitcasts AI, or indexes 6788bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// to its first element. Transform users of the cast to use the new values 6798bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner/// instead. 6808bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattnervoid SROA::RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI, 681372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 6828bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner Value::use_iterator UI = BCInst->use_begin(), UE = BCInst->use_end(); 6838bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner while (UI != UE) { 684d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Instruction *User = cast<Instruction>(*UI++); 685d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BitCastInst *BCU = dyn_cast<BitCastInst>(User)) { 686372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner RewriteBitCastUserOfAlloca(BCU, AI, NewElts); 687d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (BCU->use_empty()) BCU->eraseFromParent(); 688372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner continue; 689372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 690372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 691d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 692d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // This must be memcpy/memmove/memset of the entire aggregate. 693d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Split into one per element. 694d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner RewriteMemIntrinUserOfAlloca(MI, BCInst, AI, NewElts); 695d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 696d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 697d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 698d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 6995ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If this is a store of the entire alloca from an integer, rewrite it. 700d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner RewriteStoreUserOfWholeAlloca(SI, AI, NewElts); 701d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner continue; 702d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 7035ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 7045ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 7055ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If this is a load of the entire alloca to an integer, rewrite it. 7065ffe6acd577696a41932c7b82db06a04687e07baChris Lattner RewriteLoadUserOfWholeAlloca(LI, AI, NewElts); 7075ffe6acd577696a41932c7b82db06a04687e07baChris Lattner continue; 7085ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 709d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 710d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Otherwise it must be some other user of a gep of the first pointer. Just 711d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // leave these alone. 712d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 7135ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 714d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner} 715d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 716d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner/// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI. 717d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner/// Rewrite it to copy or set the elements of the scalarized memory. 718d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattnervoid SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *BCInst, 719d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner AllocationInst *AI, 720d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 721d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 722d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If this is a memcpy/memmove, construct the other pointer as the 723d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // appropriate type. 724d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *OtherPtr = 0; 725d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (MemCpyInst *MCI = dyn_cast<MemCpyInst>(MI)) { 726d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BCInst == MCI->getRawDest()) 727d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = MCI->getRawSource(); 728d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner else { 729d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(BCInst == MCI->getRawSource()); 730d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = MCI->getRawDest(); 7318bf991193245bb8b7e497e8c16545a206fbe5eefChris Lattner } 732d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } else if (MemMoveInst *MMI = dyn_cast<MemMoveInst>(MI)) { 733d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BCInst == MMI->getRawDest()) 734d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = MMI->getRawSource(); 735d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner else { 736d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(BCInst == MMI->getRawSource()); 737d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = MMI->getRawDest(); 738372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 739d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 740d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 741d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If there is an other pointer, we want to convert it to the same pointer 742d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // type as AI has, so we can GEP through it safely. 743d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherPtr) { 744d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // It is likely that OtherPtr is a bitcast, if so, remove it. 745d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(OtherPtr)) 746d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = BC->getOperand(0); 747d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // All zero GEPs are effectively bitcasts. 748d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(OtherPtr)) 749d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (GEP->hasAllZeroIndices()) 750d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = GEP->getOperand(0); 751372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 752d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (ConstantExpr *BCE = dyn_cast<ConstantExpr>(OtherPtr)) 753d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BCE->getOpcode() == Instruction::BitCast) 754d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = BCE->getOperand(0); 755d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 756d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the pointer is not the right type, insert a bitcast to the right 757d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // type. 758d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherPtr->getType() != AI->getType()) 759d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = new BitCastInst(OtherPtr, AI->getType(), OtherPtr->getName(), 760d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 761d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 762d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 763d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Process each element of the aggregate. 764d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *TheFn = MI->getOperand(0); 765d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner const Type *BytePtrTy = MI->getRawDest()->getType(); 766d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner bool SROADest = MI->getRawDest() == BCInst; 767d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 768d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Constant *Zero = Constant::getNullValue(Type::Int32Ty); 769372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 770d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 771d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If this is a memcpy/memmove, emit a GEP of the other element address. 772d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *OtherElt = 0; 773d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherPtr) { 774d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *Idx[2] = { Zero, ConstantInt::get(Type::Int32Ty, i) }; 775d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherElt = GetElementPtrInst::Create(OtherPtr, Idx, Idx + 2, 776963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner OtherPtr->getNameStr()+"."+utostr(i), 777d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 778d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 779d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 780d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *EltPtr = NewElts[i]; 781d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner const Type *EltTy =cast<PointerType>(EltPtr->getType())->getElementType(); 782d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 783d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If we got down to a scalar, insert a load or store as appropriate. 784d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltTy->isSingleValueType()) { 785d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (isa<MemCpyInst>(MI) || isa<MemMoveInst>(MI)) { 786d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *Elt = new LoadInst(SROADest ? OtherElt : EltPtr, "tmp", 787d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 788d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner new StoreInst(Elt, SROADest ? EltPtr : OtherElt, MI); 789d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 790372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 791d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(isa<MemSetInst>(MI)); 792c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 793d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the stored element is zero (common case), just store a null 794d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // constant. 795d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Constant *StoreVal; 796d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getOperand(2))) { 797d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (CI->isZero()) { 798d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner StoreVal = Constant::getNullValue(EltTy); // 0.0, null, 0, <0,0> 799c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } else { 800d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If EltTy is a vector type, get the element type. 801d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner const Type *ValTy = EltTy; 802d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(ValTy)) 803d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner ValTy = VTy->getElementType(); 804d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 805d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Construct an integer with the right value. 806d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner unsigned EltSize = TD->getTypeSizeInBits(ValTy); 807d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner APInt OneVal(EltSize, CI->getZExtValue()); 808d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner APInt TotalVal(OneVal); 809d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Set each byte. 810d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner for (unsigned i = 0; 8*i < EltSize; ++i) { 811d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner TotalVal = TotalVal.shl(8); 812d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner TotalVal |= OneVal; 813d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 814d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 815d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Convert the integer value to the appropriate type. 816d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner StoreVal = ConstantInt::get(TotalVal); 817d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (isa<PointerType>(ValTy)) 818d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy); 819d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner else if (ValTy->isFloatingPoint()) 820d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy); 821d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(StoreVal->getType() == ValTy && "Type mismatch!"); 822d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 823d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the requested value was a vector constant, create it. 824d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltTy != ValTy) { 825d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner unsigned NumElts = cast<VectorType>(ValTy)->getNumElements(); 826d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<Constant*, 16> Elts(NumElts, StoreVal); 827d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner StoreVal = ConstantVector::get(&Elts[0], NumElts); 828c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 829c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 830d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner new StoreInst(StoreVal, EltPtr, MI); 831d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 832c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 833d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Otherwise, if we're storing a byte variable, use a memset call for 834d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // this element. 835d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 836c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 837d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Cast the element pointer to BytePtrTy. 838d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltPtr->getType() != BytePtrTy) 839d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner EltPtr = new BitCastInst(EltPtr, BytePtrTy, EltPtr->getNameStr(), MI); 840c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 841d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Cast the other pointer (if we have one) to BytePtrTy. 842d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherElt && OtherElt->getType() != BytePtrTy) 843d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherElt = new BitCastInst(OtherElt, BytePtrTy,OtherElt->getNameStr(), 844d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 845d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 846ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands unsigned EltSize = TD->getTypePaddedSize(EltTy); 847d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 848d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Finally, insert the meminst for this element. 849d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (isa<MemCpyInst>(MI) || isa<MemMoveInst>(MI)) { 850d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *Ops[] = { 851d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SROADest ? EltPtr : OtherElt, // Dest ptr 852d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SROADest ? OtherElt : EltPtr, // Src ptr 853d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size 854d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Zero // Align 855d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner }; 856d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner CallInst::Create(TheFn, Ops, Ops + 4, "", MI); 857d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } else { 858d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(isa<MemSetInst>(MI)); 859d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *Ops[] = { 860d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner EltPtr, MI->getOperand(2), // Dest, Value, 861d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size 862d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Zero // Align 863d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner }; 864d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner CallInst::Create(TheFn, Ops, Ops + 4, "", MI); 865c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 866372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 867d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner MI->eraseFromParent(); 868372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 869d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 870d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner/// RewriteStoreUserOfWholeAlloca - We found an store of an integer that 871d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner/// overwrites the entire allocation. Extract out the pieces of the stored 872d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner/// integer and store them individually. 873d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattnervoid SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, 874d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner AllocationInst *AI, 875d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts){ 876d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Extract each element out of the integer according to its structure offset 877d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // and store the element value to the individual alloca. 878d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *SrcVal = SI->getOperand(0); 879d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const Type *AllocaEltTy = AI->getType()->getElementType(); 880ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands uint64_t AllocaSizeBits = TD->getTypePaddedSizeInBits(AllocaEltTy); 881d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 882d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // If this isn't a store of an integer to the whole alloca, it may be a store 883d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // to the first element. Just ignore the store in this case and normal SROA 884d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // will handle it. 885d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (!isa<IntegerType>(SrcVal->getType()) || 886ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands TD->getTypePaddedSizeInBits(SrcVal->getType()) != AllocaSizeBits) 887d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner return; 888d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 889d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner DOUT << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << *SI; 890d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 891d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // There are two forms here: AI could be an array or struct. Both cases 892d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // have different ways to compute the element offset. 893d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 894d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const StructLayout *Layout = TD->getStructLayout(EltSTy); 895d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 896d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 897d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Get the number of bits to shift SrcVal to get the value. 898d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const Type *FieldTy = EltSTy->getElementType(i); 899d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t Shift = Layout->getElementOffsetInBits(i); 900d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 901d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 902ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands Shift = AllocaSizeBits-Shift-TD->getTypePaddedSizeInBits(FieldTy); 903d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 904d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *EltVal = SrcVal; 905d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (Shift) { 906d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 907d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 908d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "sroa.store.elt", SI); 909d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 910d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 911d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Truncate down to an integer of the right size. 912d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 913583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 914583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 915583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (FieldSizeBits == 0) continue; 916583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 917d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (FieldSizeBits != AllocaSizeBits) 918d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = new TruncInst(EltVal, IntegerType::get(FieldSizeBits), "", SI); 919d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *DestField = NewElts[i]; 920d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (EltVal->getType() == FieldTy) { 921d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Storing to an integer field of this size, just do it. 922d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else if (FieldTy->isFloatingPoint() || isa<VectorType>(FieldTy)) { 923d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Bitcast to the right element type (for fp/vector values). 924d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = new BitCastInst(EltVal, FieldTy, "", SI); 925d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 926d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 927d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner DestField = new BitCastInst(DestField, 928d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner PointerType::getUnqual(EltVal->getType()), 929d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "", SI); 930d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 931d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner new StoreInst(EltVal, DestField, SI); 932d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 933d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 934d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 935d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const ArrayType *ATy = cast<ArrayType>(AllocaEltTy); 936d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const Type *ArrayEltTy = ATy->getElementType(); 937ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands uint64_t ElementOffset = TD->getTypePaddedSizeInBits(ArrayEltTy); 938d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy); 939d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 940d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t Shift; 941d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 942d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 943d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift = AllocaSizeBits-ElementOffset; 944d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner else 945d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift = 0; 946d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 947d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 948583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 949583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (ElementSizeBits == 0) continue; 950d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 951d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *EltVal = SrcVal; 952d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (Shift) { 953d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 954d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 955d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "sroa.store.elt", SI); 956d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 957d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 958d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Truncate down to an integer of the right size. 959d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (ElementSizeBits != AllocaSizeBits) 960d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = new TruncInst(EltVal, IntegerType::get(ElementSizeBits),"",SI); 961d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *DestField = NewElts[i]; 962d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (EltVal->getType() == ArrayEltTy) { 963d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Storing to an integer field of this size, just do it. 964d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else if (ArrayEltTy->isFloatingPoint() || isa<VectorType>(ArrayEltTy)) { 965d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Bitcast to the right element type (for fp/vector values). 966d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI); 967d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 968d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 969d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner DestField = new BitCastInst(DestField, 970d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner PointerType::getUnqual(EltVal->getType()), 971d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "", SI); 972d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 973d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner new StoreInst(EltVal, DestField, SI); 974d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 975d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 976d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift -= ElementOffset; 977d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner else 978d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift += ElementOffset; 979d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 980d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 981d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 982d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SI->eraseFromParent(); 983d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner} 984d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9855ffe6acd577696a41932c7b82db06a04687e07baChris Lattner/// RewriteLoadUserOfWholeAlloca - We found an load of the entire allocation to 9865ffe6acd577696a41932c7b82db06a04687e07baChris Lattner/// an integer. Load the individual pieces to form the aggregate value. 9875ffe6acd577696a41932c7b82db06a04687e07baChris Lattnervoid SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocationInst *AI, 9885ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 9895ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Extract each element out of the NewElts according to its structure offset 9905ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // and form the result value. 9915ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const Type *AllocaEltTy = AI->getType()->getElementType(); 992ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands uint64_t AllocaSizeBits = TD->getTypePaddedSizeInBits(AllocaEltTy); 9935ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 9945ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If this isn't a load of the whole alloca to an integer, it may be a load 9955ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // of the first element. Just ignore the load in this case and normal SROA 9965ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // will handle it. 9975ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (!isa<IntegerType>(LI->getType()) || 998ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands TD->getTypePaddedSizeInBits(LI->getType()) != AllocaSizeBits) 9995ffe6acd577696a41932c7b82db06a04687e07baChris Lattner return; 10005ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10015ffe6acd577696a41932c7b82db06a04687e07baChris Lattner DOUT << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << *LI; 10025ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10035ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // There are two forms here: AI could be an array or struct. Both cases 10045ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // have different ways to compute the element offset. 10055ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const StructLayout *Layout = 0; 10065ffe6acd577696a41932c7b82db06a04687e07baChris Lattner uint64_t ArrayEltBitOffset = 0; 10075ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 10085ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Layout = TD->getStructLayout(EltSTy); 10095ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } else { 10105ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType(); 1011ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands ArrayEltBitOffset = TD->getTypePaddedSizeInBits(ArrayEltTy); 10125ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 10135ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10145ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Value *ResultVal = Constant::getNullValue(LI->getType()); 10155ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10165ffe6acd577696a41932c7b82db06a04687e07baChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 10175ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Load the value from the alloca. If the NewElt is an aggregate, cast 10185ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // the pointer to an integer of the same size before doing the load. 10195ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Value *SrcField = NewElts[i]; 10205ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const Type *FieldTy = 10215ffe6acd577696a41932c7b82db06a04687e07baChris Lattner cast<PointerType>(SrcField->getType())->getElementType(); 1022583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 1023583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 1024583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 1025583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (FieldSizeBits == 0) continue; 1026583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 1027583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner const IntegerType *FieldIntTy = IntegerType::get(FieldSizeBits); 10285ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (!isa<IntegerType>(FieldTy) && !FieldTy->isFloatingPoint() && 10295ffe6acd577696a41932c7b82db06a04687e07baChris Lattner !isa<VectorType>(FieldTy)) 10305ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new BitCastInst(SrcField, PointerType::getUnqual(FieldIntTy), 10315ffe6acd577696a41932c7b82db06a04687e07baChris Lattner "", LI); 10325ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new LoadInst(SrcField, "sroa.load.elt", LI); 10335ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10345ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If SrcField is a fp or vector of the right size but that isn't an 10355ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // integer type, bitcast to an integer so we can shift it. 10365ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (SrcField->getType() != FieldIntTy) 10375ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI); 10385ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10395ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Zero extend the field to be the same size as the final alloca so that 10405ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // we can shift and insert it. 10415ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (SrcField->getType() != ResultVal->getType()) 10425ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI); 10435ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10445ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Determine the number of bits to shift SrcField. 10455ffe6acd577696a41932c7b82db06a04687e07baChris Lattner uint64_t Shift; 10465ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (Layout) // Struct case. 10475ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = Layout->getElementOffsetInBits(i); 10485ffe6acd577696a41932c7b82db06a04687e07baChris Lattner else // Array case. 10495ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = i*ArrayEltBitOffset; 10505ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10515ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (TD->isBigEndian()) 10525ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth(); 10535ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10545ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (Shift) { 10555ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift); 10565ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI); 10575ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 10585ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10595ffe6acd577696a41932c7b82db06a04687e07baChris Lattner ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI); 10605ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 10615ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10625ffe6acd577696a41932c7b82db06a04687e07baChris Lattner LI->replaceAllUsesWith(ResultVal); 10635ffe6acd577696a41932c7b82db06a04687e07baChris Lattner LI->eraseFromParent(); 10645ffe6acd577696a41932c7b82db06a04687e07baChris Lattner} 10655ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 1066372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 10673cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands/// HasPadding - Return true if the specified type has any structure or 10683cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands/// alignment padding, false otherwise. 1069a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sandsstatic bool HasPadding(const Type *Ty, const TargetData &TD) { 107039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (const StructType *STy = dyn_cast<StructType>(Ty)) { 107139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner const StructLayout *SL = TD.getStructLayout(STy); 107239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned PrevFieldBitOffset = 0; 107339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 10743cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands unsigned FieldBitOffset = SL->getElementOffsetInBits(i); 10753cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 107639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Padding in sub-elements? 1077a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands if (HasPadding(STy->getElementType(i), TD)) 107839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 10793cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 108039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Check to see if there is any padding between this element and the 108139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // previous one. 108239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (i) { 10833cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands unsigned PrevFieldEnd = 108439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1)); 108539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (PrevFieldEnd < FieldBitOffset) 108639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 108739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 10883cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 108939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner PrevFieldBitOffset = FieldBitOffset; 109039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 10913cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 109239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Check for tail padding. 109339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (unsigned EltCount = STy->getNumElements()) { 109439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned PrevFieldEnd = PrevFieldBitOffset + 109539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner TD.getTypeSizeInBits(STy->getElementType(EltCount-1)); 10963cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands if (PrevFieldEnd < SL->getSizeInBits()) 109739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 109839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 109939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 110039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 1101a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands return HasPadding(ATy->getElementType(), TD); 11023cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands } else if (const VectorType *VTy = dyn_cast<VectorType>(Ty)) { 1103a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands return HasPadding(VTy->getElementType(), TD); 110439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 1105ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands return TD.getTypeSizeInBits(Ty) != TD.getTypePaddedSizeInBits(Ty); 110639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner} 1107372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 1108f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 1109f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 1110f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// or 1 if safe after canonicalization has been performed. 11115e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner/// 1112f5990edc877c4e63503c589928a00ec6ec751830Chris Lattnerint SROA::isSafeAllocaToScalarRepl(AllocationInst *AI) { 11135e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // Loop over the use list of the alloca. We can only transform it if all of 11145e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // the users are safe to transform. 111539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo Info; 111639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 11175e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner for (Value::use_iterator I = AI->use_begin(), E = AI->use_end(); 1118f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner I != E; ++I) { 111939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isSafeUseOfAllocation(cast<Instruction>(*I), AI, Info); 112039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isUnsafe) { 1121b7427031372337e6d67f9573ec6c722ab5ea913eBill Wendling DOUT << "Cannot transform: " << *AI << " due to user: " << **I; 1122f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner return 0; 11235e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 1124f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 112539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 112639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Okay, we know all the users are promotable. If the aggregate is a memcpy 112739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // source and destination, we have to be careful. In particular, the memcpy 112839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // could be moving around elements that live in structure padding of the LLVM 112939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // types, but may actually be used. In these cases, we refuse to promote the 113039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // struct. 113139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isMemCpySrc && Info.isMemCpyDst && 113256c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner HasPadding(AI->getType()->getElementType(), *TD)) 113339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return 0; 11343cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 113539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // If we require cleanup, return 1, otherwise return 3. 11364afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel return Info.needsCleanup ? 1 : 3; 1137f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner} 1138f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner 11394afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// CleanupGEP - GEP is used by an Alloca, which can be prompted after the GEP 11404afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// is canonicalized here. 11414afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patelvoid SROA::CleanupGEP(GetElementPtrInst *GEPI) { 11424afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel gep_type_iterator I = gep_type_begin(GEPI); 11434afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel ++I; 11444afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 11454afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) { 11464afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel uint64_t NumElements = AT->getNumElements(); 11474afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 11484afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (!isa<ConstantInt>(I.getOperand())) { 11494afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (NumElements == 1) { 11504afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel GEPI->setOperand(2, Constant::getNullValue(Type::Int32Ty)); 11514afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } else { 11524afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel assert(NumElements == 2 && "Unhandled case!"); 11534afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // All users of the GEP must be loads. At each use of the GEP, insert 11544afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // two loads of the appropriate indexed GEP and select between them. 11554afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Value *IsOne = new ICmpInst(ICmpInst::ICMP_NE, I.getOperand(), 11564afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Constant::getNullValue(I.getOperand()->getType()), 11574afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel "isone", GEPI); 11584afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // Insert the new GEP instructions, which are properly indexed. 11594afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel SmallVector<Value*, 8> Indices(GEPI->op_begin()+1, GEPI->op_end()); 11604afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Indices[1] = Constant::getNullValue(Type::Int32Ty); 11614afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Value *ZeroIdx = GetElementPtrInst::Create(GEPI->getOperand(0), 11624afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Indices.begin(), 11634afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Indices.end(), 11644afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel GEPI->getName()+".0", GEPI); 11654afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Indices[1] = ConstantInt::get(Type::Int32Ty, 1); 11664afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Value *OneIdx = GetElementPtrInst::Create(GEPI->getOperand(0), 11674afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Indices.begin(), 11684afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Indices.end(), 11694afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel GEPI->getName()+".1", GEPI); 11704afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // Replace all loads of the variable index GEP with loads from both 11714afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // indexes and a select. 11724afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel while (!GEPI->use_empty()) { 11734afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel LoadInst *LI = cast<LoadInst>(GEPI->use_back()); 11744afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI); 11754afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Value *One = new LoadInst(OneIdx , LI->getName()+".1", LI); 11764afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Value *R = SelectInst::Create(IsOne, One, Zero, LI->getName(), LI); 11774afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel LI->replaceAllUsesWith(R); 11784afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel LI->eraseFromParent(); 11794afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 11804afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel GEPI->eraseFromParent(); 11814afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 11824afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 11834afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 11844afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel} 11854afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 11864afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// CleanupAllocaUsers - If SROA reported that it can promote the specified 1187f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// allocation, but only if cleaned up, perform the cleanups required. 11884afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patelvoid SROA::CleanupAllocaUsers(AllocationInst *AI) { 1189d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // At this point, we know that the end result will be SROA'd and promoted, so 1190d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // we can insert ugly code if required so long as sroa+mem2reg will clean it 1191d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // up. 1192d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 1193d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner UI != E; ) { 11944afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel User *U = *UI++; 11954afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) 11964afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel CleanupGEP(GEPI); 11974afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel else if (Instruction *I = dyn_cast<Instruction>(U)) { 11984afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel SmallVector<DbgInfoIntrinsic *, 2> DbgInUses; 11994afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel if (OnlyUsedByDbgInfoIntrinsics(I, &DbgInUses)) { 12004afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // Safe to remove debug info uses. 12014afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel while (!DbgInUses.empty()) { 12024afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DbgInfoIntrinsic *DI = DbgInUses.back(); DbgInUses.pop_back(); 12034afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DI->eraseFromParent(); 1204d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 12054afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel I->eraseFromParent(); 1206d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 1207d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 1208d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 12095e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 1210a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 12112e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// MergeInType - Add the 'In' type to the accumulated type (Accum) so far at 12122e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// the offset specified by Offset (which is specified in bytes). 1213de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 12142e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// There are two cases we handle here: 12152e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// 1) A union of vector types of the same size and potentially its elements. 1216d22dbdf60652536d44dc4a380059368bea75b5cdChris Lattner/// Here we turn element accesses into insert/extract element operations. 12172e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// This promotes a <4 x float> with a store of float to the third element 12182e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// into a <4 x float> that uses insert element. 12192e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// 2) A fully general blob of memory, which we turn into some (potentially 12202e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// large) integer type with extract and insert operations where the loads 12212e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// and stores would mutate the memory. 12227809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattnerstatic void MergeInType(const Type *In, uint64_t Offset, const Type *&VecTy, 12237809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner unsigned AllocaSize, const TargetData &TD) { 12247809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If this could be contributing to a vector, analyze it. 12257809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VecTy != Type::VoidTy) { // either null or a vector type. 12267809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 12277809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If the In type is a vector that is the same size as the alloca, see if it 12287809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // matches the existing VecTy. 12297809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (const VectorType *VInTy = dyn_cast<VectorType>(In)) { 12307809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) { 12317809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If we're storing/loading a vector of the right size, allow it as a 12327809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // vector. If this the first vector we see, remember the type so that 12337809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // we know the element size. 12347809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VecTy == 0) 12357809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner VecTy = VInTy; 12367809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return; 12377809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 12387809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } else if (In == Type::FloatTy || In == Type::DoubleTy || 12397809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner (isa<IntegerType>(In) && In->getPrimitiveSizeInBits() >= 8 && 12407809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner isPowerOf2_32(In->getPrimitiveSizeInBits()))) { 12417809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If we're accessing something that could be an element of a vector, see 12427809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // if the implied vector agrees with what we already have and if Offset is 12437809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // compatible with it. 12447809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner unsigned EltSize = In->getPrimitiveSizeInBits()/8; 12457809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (Offset % EltSize == 0 && 12467809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaSize % EltSize == 0 && 12477809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner (VecTy == 0 || 12487809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner cast<VectorType>(VecTy)->getElementType() 12497809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ->getPrimitiveSizeInBits()/8 == EltSize)) { 12507809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VecTy == 0) 12517809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner VecTy = VectorType::get(In, AllocaSize/EltSize); 12527809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return; 12537809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 12542e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 12552e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 12562e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner 12577809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Otherwise, we have a case that we can't handle with an optimized vector 12587809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // form. We can still turn this into a large integer. 12597809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner VecTy = Type::VoidTy; 1260a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1261a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 12622e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// CanConvertToScalar - V is a pointer. If we can convert the pointee and all 12637809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// its accesses to use a to single vector type, return true, and set VecTy to 12647809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// the new type. If we could convert the alloca into a single promotable 12657809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// integer, return true but set VecTy to VoidTy. Further, if the use is not a 12667809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// completely trivial use that mem2reg could promote, set IsNotTrivial. Offset 12677809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// is the current offset from the base of the alloca being analyzed. 1268a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// 12691a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner/// If we see at least one access to the value that is as a vector type, set the 12701a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner/// SawVec flag. 12711a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner/// 12721a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattnerbool SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy, 12731a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool &SawVec, uint64_t Offset, 12747809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner unsigned AllocaSize) { 1275a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 1276a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Instruction *User = cast<Instruction>(*UI); 1277a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1278a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 12792e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Don't break volatile loads. 12806e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LI->isVolatile()) 12812e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 12827809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner MergeInType(LI->getType(), Offset, VecTy, AllocaSize, *TD); 12831a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner SawVec |= isa<VectorType>(LI->getType()); 1284cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1285cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 1286cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 1287cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 128824d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer // Storing the pointer, not into the value? 12896e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (SI->getOperand(0) == V || SI->isVolatile()) return 0; 12907809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner MergeInType(SI->getOperand(0)->getType(), Offset, VecTy, AllocaSize, *TD); 12911a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner SawVec |= isa<VectorType>(SI->getOperand(0)->getType()); 1292cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1293cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 12942e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner 12952e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { 12961a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (!CanConvertToScalar(BCI, IsNotTrivial, VecTy, SawVec, Offset, 12971a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner AllocaSize)) 12982e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1299a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner IsNotTrivial = true; 1300cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1301cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 1302cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 1303cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 13042e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If this is a GEP with a variable indices, we can't handle it. 13052e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (!GEP->hasAllConstantIndices()) 13062e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1307cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 13082e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Compute the offset that this GEP adds to the pointer. 13092e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 13102e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner uint64_t GEPOffset = TD->getIndexedOffset(GEP->getOperand(0)->getType(), 13112e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner &Indices[0], Indices.size()); 13122e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // See if all uses can be converted. 13131a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (!CanConvertToScalar(GEP, IsNotTrivial, VecTy, SawVec,Offset+GEPOffset, 13147809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaSize)) 13152e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 13162e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner IsNotTrivial = true; 13172e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner continue; 1318a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1319cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 13203d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 13213d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // handle it. 13223d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner if (isa<MemSetInst>(User) && 13233d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // Store of constant value. 13243d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner isa<ConstantInt>(User->getOperand(2)) && 13253d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // Store with constant size. 13263d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner isa<ConstantInt>(User->getOperand(3))) { 13273d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner VecTy = Type::VoidTy; 13283d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner IsNotTrivial = true; 13293d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner continue; 13303d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner } 13313d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 13322e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Otherwise, we cannot handle this! 13332e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1334a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1335a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 13362e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return true; 1337a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1338a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1339a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1340a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 1341de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// directly. This happens when we are converting an "integer union" to a 1342de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// single integer scalar, or when we are converting a "vector union" to a 1343de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// vector with insert/extractelement instructions. 1344de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 1345de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// Offset is an offset from the original alloca, in bits that need to be 1346de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// shifted to the right. By the end of this, there should be no uses of Ptr. 13472e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattnervoid SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset) { 1348a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner while (!Ptr->use_empty()) { 1349a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Instruction *User = cast<Instruction>(Ptr->use_back()); 13504b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1351cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) { 1352b10e0da065fc2c18b5bee9011eb249e223a23108Chris Lattner ConvertUsesToScalar(CI, NewAI, Offset); 1353a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner CI->eraseFromParent(); 1354cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1355cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 13564b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1357cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 13582e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Compute the offset that this GEP adds to the pointer. 13592e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 13602e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner uint64_t GEPOffset = TD->getIndexedOffset(GEP->getOperand(0)->getType(), 13612e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner &Indices[0], Indices.size()); 13622e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8); 1363a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner GEP->eraseFromParent(); 1364cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1365a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 13663d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 13679bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner IRBuilder<> Builder(User->getParent(), User); 13689bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 13699bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 13706e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner // The load is a bit extract from NewAI shifted right by Offset bits. 13716e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp"); 13726e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *NewLoadVal 13736e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder); 13746e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner LI->replaceAllUsesWith(NewLoadVal); 13759bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner LI->eraseFromParent(); 13769bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner continue; 13779bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 13789bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 13799bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 13809bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner assert(SI->getOperand(0) != Ptr && "Consistency error!"); 13819bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Value *Old = Builder.CreateLoad(NewAI, (NewAI->getName()+".in").c_str()); 13829bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset, 13839bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Builder); 13849bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Builder.CreateStore(New, NewAI); 13859bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner SI->eraseFromParent(); 13869bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner continue; 13879bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 13889bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 13893d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 13903d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // transform it into a store of the expanded constant value. 13913d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 13923d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner assert(MSI->getRawDest() == Ptr && "Consistency error!"); 13933d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 13943d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue(); 13953d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 13963d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // Compute the value replicated the right number of times. 13973d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner APInt APVal(NumBytes*8, Val); 13983d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 13993d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // Splat the value if non-zero. 14003d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner if (Val) 14013d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner for (unsigned i = 1; i != NumBytes; ++i) 14023d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner APVal |= APVal << 8; 14033d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 140465a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Value *Old = Builder.CreateLoad(NewAI, (NewAI->getName()+".in").c_str()); 14059b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner Value *New = ConvertScalar_InsertValue(ConstantInt::get(APVal), Old, 140665a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Offset, Builder); 140765a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Builder.CreateStore(New, NewAI); 14083d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner MSI->eraseFromParent(); 14093d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner continue; 14103d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner } 14113d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 14123d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 1413cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner assert(0 && "Unsupported operation!"); 1414cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner abort(); 1415a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1416a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 141779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 14186e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer 14196e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// or vector value FromVal, extracting the bits from the offset specified by 14206e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// Offset. This returns the value, which is of type ToType. 14216e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// 14226e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// This happens when we are converting an "integer union" to a single 14234b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// integer scalar, or when we are converting a "vector union" to a vector with 14244b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// insert/extractelement instructions. 1425800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// 14264b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// Offset is an offset from the original alloca, in bits that need to be 14276e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// shifted to the right. 14286e01115bb122ef82daa6c8133a1d199d6b8ff767Chris LattnerValue *SROA::ConvertScalar_ExtractValue(Value *FromVal, const Type *ToType, 14296e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner uint64_t Offset, IRBuilder<> &Builder) { 14302e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If the load is of the whole new alloca, no conversion is needed. 14316e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (FromVal->getType() == ToType && Offset == 0) 14326e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return FromVal; 14339d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner 14342e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If the result alloca is a vector type, this is either an element 14352e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // access or a bitcast to another vector type of the same size. 14366e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) { 14376e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (isa<VectorType>(ToType)) 14386e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return Builder.CreateBitCast(FromVal, ToType, "tmp"); 14399d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner 14409d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Otherwise it must be an element access. 14419d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner unsigned Elt = 0; 14429d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (Offset) { 1443ceb4d1aecb9deffe59b3dcdc9a783ffde8477be9Duncan Sands unsigned EltSize = TD->getTypePaddedSizeInBits(VTy->getElementType()); 14449d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner Elt = Offset/EltSize; 14452e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner assert(EltSize*Elt == Offset && "Invalid modulus in validity checking"); 1446800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 14472e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Return the element extracted out of it. 14486e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *V = Builder.CreateExtractElement(FromVal, 14499bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner ConstantInt::get(Type::Int32Ty,Elt), 14509bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner "tmp"); 14516e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (V->getType() != ToType) 14526e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner V = Builder.CreateBitCast(V, ToType, "tmp"); 14537809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return V; 14549d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } 14551aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner 14561aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner // If ToType is a first class aggregate, extract out each of the pieces and 14571aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner // use insertvalue's to form the FCA. 14581aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner if (const StructType *ST = dyn_cast<StructType>(ToType)) { 14591aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner const StructLayout &Layout = *TD->getStructLayout(ST); 14601aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Value *Res = UndefValue::get(ST); 14611aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 14621aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i), 1463e991ced7cb5cb86d1c33b8d400b1be41185bc69fChris Lattner Offset+Layout.getElementOffsetInBits(i), 14641aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Builder); 14651aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 14661aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 14671aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner return Res; 14681aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 14691aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner 14701aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(ToType)) { 14711aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner uint64_t EltSize = TD->getTypePaddedSizeInBits(AT->getElementType()); 14721aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Value *Res = UndefValue::get(AT); 14731aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 14741aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(), 14751aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Offset+i*EltSize, Builder); 14761aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 14771aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 14781aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner return Res; 14791aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 14804b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 14812e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Otherwise, this must be a union that was converted to an integer value. 14826e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner const IntegerType *NTy = cast<IntegerType>(FromVal->getType()); 14834b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 14849d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // If this is a big-endian system and the load is narrower than the 14859d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // full alloca type, we need to do a shift to get the right bits. 14869d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner int ShAmt = 0; 148756c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner if (TD->isBigEndian()) { 14889d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 14899d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 14909d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // integers with a bitwidth that is not a multiple of 8. 149156c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner ShAmt = TD->getTypeStoreSizeInBits(NTy) - 14926e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner TD->getTypeStoreSizeInBits(ToType) - Offset; 14939d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 14949d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner ShAmt = Offset; 14959d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } 14964b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 14979d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Note: we support negative bitwidths (with shl) which are not defined. 14989d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // We do this to support (f.e.) loads off the end of a structure where 14999d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // only some bits are used. 15009d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth()) 15011aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner FromVal = Builder.CreateLShr(FromVal, ConstantInt::get(FromVal->getType(), 15021aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner ShAmt), "tmp"); 15039d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth()) 15041aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner FromVal = Builder.CreateShl(FromVal, ConstantInt::get(FromVal->getType(), 15051aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner -ShAmt), "tmp"); 15064b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15079d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Finally, unconditionally truncate the integer to the right width. 15086e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner unsigned LIBitWidth = TD->getTypeSizeInBits(ToType); 15099d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (LIBitWidth < NTy->getBitWidth()) 15106e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner FromVal = Builder.CreateTrunc(FromVal, IntegerType::get(LIBitWidth), "tmp"); 151155a683d7f03b0acaf7807545fd7be319498277ffChris Lattner else if (LIBitWidth > NTy->getBitWidth()) 15126e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner FromVal = Builder.CreateZExt(FromVal, IntegerType::get(LIBitWidth), "tmp"); 15134b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15149d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // If the result is an integer, this is a trunc or bitcast. 15156e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (isa<IntegerType>(ToType)) { 15169d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Should be done. 15176e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner } else if (ToType->isFloatingPoint() || isa<VectorType>(ToType)) { 15189d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Just do a bitcast, we know the sizes match up. 15196e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp"); 15209d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 15219d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Otherwise must be a pointer. 15226e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp"); 1523800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 15246e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner assert(FromVal->getType() == ToType && "Didn't convert right?"); 15256e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return FromVal; 1526800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1527800de31776356910eb877e71df9f32b0a6215324Chris Lattner 1528800de31776356910eb877e71df9f32b0a6215324Chris Lattner 15299b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer 15309b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// or vector value "Old" at the offset specified by Offset. 15319b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// 15329b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// This happens when we are converting an "integer union" to a 1533800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// single integer scalar, or when we are converting a "vector union" to a 1534800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// vector with insert/extractelement instructions. 1535800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// 1536800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// Offset is an offset from the original alloca, in bits that need to be 15379b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// shifted to the right. 15389b872db775797dea4b391a9347cfbd2ca9c558e2Chris LattnerValue *SROA::ConvertScalar_InsertValue(Value *SV, Value *Old, 153965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner uint64_t Offset, IRBuilder<> &Builder) { 15404b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1541800de31776356910eb877e71df9f32b0a6215324Chris Lattner // Convert the stored type to the actual type, shift it left to insert 1542800de31776356910eb877e71df9f32b0a6215324Chris Lattner // then 'or' into place. 15439b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner const Type *AllocaType = Old->getType(); 15444b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15452e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(AllocaType)) { 1546800de31776356910eb877e71df9f32b0a6215324Chris Lattner // If the result alloca is a vector type, this is either an element 1547800de31776356910eb877e71df9f32b0a6215324Chris Lattner // access or a bitcast to another vector type. 1548800de31776356910eb877e71df9f32b0a6215324Chris Lattner if (isa<VectorType>(SV->getType())) { 154965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateBitCast(SV, AllocaType, "tmp"); 1550800de31776356910eb877e71df9f32b0a6215324Chris Lattner } else { 1551800de31776356910eb877e71df9f32b0a6215324Chris Lattner // Must be an element insertion. 15522e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned Elt = Offset/TD->getTypePaddedSizeInBits(VTy->getElementType()); 15537809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 15547809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (SV->getType() != VTy->getElementType()) 155565a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp"); 15567809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 155765a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateInsertElement(Old, SV, 155865a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner ConstantInt::get(Type::Int32Ty, Elt), 155965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner "tmp"); 1560800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 15612e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return SV; 15622e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 15639b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner 15649b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner // If SV is a first-class aggregate value, insert each value recursively. 15659b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner if (const StructType *ST = dyn_cast<StructType>(SV->getType())) { 15669b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner const StructLayout &Layout = *TD->getStructLayout(ST); 15679b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 156865a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 15699b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner Old = ConvertScalar_InsertValue(Elt, Old, 1570e991ced7cb5cb86d1c33b8d400b1be41185bc69fChris Lattner Offset+Layout.getElementOffsetInBits(i), 157165a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Builder); 15729b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 15739b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner return Old; 15749b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 15759b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner 15769b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) { 15779b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner uint64_t EltSize = TD->getTypePaddedSizeInBits(AT->getElementType()); 15789b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 157965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 158065a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder); 15819b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 15829b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner return Old; 15839b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 15844b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15852e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If SV is a float, convert it to the appropriate integer type. 15869b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner // If it is a pointer, do the same. 15872e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned SrcWidth = TD->getTypeSizeInBits(SV->getType()); 15882e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned DestWidth = TD->getTypeSizeInBits(AllocaType); 15892e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned SrcStoreWidth = TD->getTypeStoreSizeInBits(SV->getType()); 15902e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned DestStoreWidth = TD->getTypeStoreSizeInBits(AllocaType); 15912e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (SV->getType()->isFloatingPoint() || isa<VectorType>(SV->getType())) 159265a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateBitCast(SV, IntegerType::get(SrcWidth), "tmp"); 15932e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner else if (isa<PointerType>(SV->getType())) 159465a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreatePtrToInt(SV, TD->getIntPtrType(), "tmp"); 15954b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15967809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Zero extend or truncate the value if needed. 15977809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (SV->getType() != AllocaType) { 15987809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (SV->getType()->getPrimitiveSizeInBits() < 15997809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaType->getPrimitiveSizeInBits()) 160065a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateZExt(SV, AllocaType, "tmp"); 16017809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner else { 16027809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Truncation may be needed if storing more than the alloca can hold 16037809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // (undefined behavior). 160465a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateTrunc(SV, AllocaType, "tmp"); 16057809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner SrcWidth = DestWidth; 16067809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner SrcStoreWidth = DestStoreWidth; 16077809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 16087809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 16094b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16102e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If this is a big-endian system and the store is narrower than the 16112e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // full alloca type, we need to do a shift to get the right bits. 16122e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner int ShAmt = 0; 16132e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (TD->isBigEndian()) { 16142e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 16152e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 16162e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // integers with a bitwidth that is not a multiple of 8. 16172e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ShAmt = DestStoreWidth - SrcStoreWidth - Offset; 1618800de31776356910eb877e71df9f32b0a6215324Chris Lattner } else { 16192e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ShAmt = Offset; 16202e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 16214b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16222e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Note: we support negative bitwidths (with shr) which are not defined. 16232e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // We do this to support (f.e.) stores off the end of a structure where 16242e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // only some bits in the structure are set. 16252e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth)); 16262e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) { 162765a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(), ShAmt), "tmp"); 16282e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner Mask <<= ShAmt; 16292e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) { 163065a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(), -ShAmt), "tmp"); 16310e7c46bc7eb68099eecd1244390dccd0a77d0875Duncan Sands Mask = Mask.lshr(-ShAmt); 16322e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 16334b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16342e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Mask out the bits we are about to insert from the old value, and or 16352e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // in the new bits. 16362e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (SrcWidth != DestWidth) { 16372e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner assert(DestWidth > SrcWidth); 163865a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Old = Builder.CreateAnd(Old, ConstantInt::get(~Mask), "mask"); 163965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateOr(Old, SV, "ins"); 1640800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 1641800de31776356910eb877e71df9f32b0a6215324Chris Lattner return SV; 1642800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1643800de31776356910eb877e71df9f32b0a6215324Chris Lattner 1644800de31776356910eb877e71df9f32b0a6215324Chris Lattner 164579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 164679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// PointsToConstantGlobal - Return true if V (possibly indirectly) points to 164779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// some part of a constant global variable. This intentionally only accepts 164879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// constant expressions because we don't can't rewrite arbitrary instructions. 164979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool PointsToConstantGlobal(Value *V) { 165079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 165179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return GV->isConstant(); 165279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 165379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (CE->getOpcode() == Instruction::BitCast || 165479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner CE->getOpcode() == Instruction::GetElementPtr) 165579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return PointsToConstantGlobal(CE->getOperand(0)); 165679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 165779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 165879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 165979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) 166079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// pointer to an alloca. Ignore any reads of the pointer, return false if we 166179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// see any stores or other unknown uses. If we see pointer arithmetic, keep 166279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// track of whether it moves the pointer (with isOffset) but otherwise traverse 166379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to 166479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the alloca, and if the source pointer is a pointer to a constant global, we 166579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// can optimize this. 166679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool isOnlyCopiedFromConstantGlobal(Value *V, Instruction *&TheCopy, 166779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner bool isOffset) { 166879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 16696e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) 16706e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // Ignore non-volatile loads, they are always ok. 16716e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (!LI->isVolatile()) 16726e733d34ca487ab7ff8a6def018a933620393869Chris Lattner continue; 16736e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 167479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) { 167579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If uses of the bitcast are ok, we are ok. 167679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset)) 167779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 167879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 167979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 168079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { 168179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the GEP has all zero indices, it doesn't offset the pointer. If it 168279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // doesn't, it does. 168379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy, 168479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner isOffset || !GEP->hasAllZeroIndices())) 168579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 168679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 168779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 168879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 168979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If this is isn't our memcpy/memmove, reject it as something we can't 169079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // handle. 169179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isa<MemCpyInst>(*UI) && !isa<MemMoveInst>(*UI)) 169279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 169379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 169479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If we already have seen a copy, reject the second one. 169579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (TheCopy) return false; 169679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 169779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the pointer has been offset from the start of the alloca, we can't 169879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // safely handle this. 169979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (isOffset) return false; 170079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 170179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the memintrinsic isn't using the alloca as the dest, reject it. 170279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (UI.getOperandNo() != 1) return false; 170379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 170479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner MemIntrinsic *MI = cast<MemIntrinsic>(*UI); 170579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 170679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the source of the memcpy/move is not a constant global, reject it. 170779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!PointsToConstantGlobal(MI->getOperand(2))) 170879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 170979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 171079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Otherwise, the transform is safe. Remember the copy instruction. 171179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner TheCopy = MI; 171279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 171379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return true; 171479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 171579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 171679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only 171779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// modified by a copy from a constant global. If we can prove this, we can 171879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// replace any uses of the alloca with uses of the global directly. 171979b3bd395dc3303cde65e18e0524ed2f70268c99Chris LattnerInstruction *SROA::isOnlyCopiedFromConstantGlobal(AllocationInst *AI) { 172079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner Instruction *TheCopy = 0; 172179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false)) 172279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return TheCopy; 172379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return 0; 172479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 1725