ScalarReplAggregates.cpp revision 081f80078dccf02c1f9c61378ff88bbf1b4afb5e
1ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 10ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// This transformation implements the well known scalar replacement of 11ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregates transformation. This xform breaks up alloca instructions of 12ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregate type (structure or array) into individual alloca instructions for 1338aec325604635380421a27e39ab06d55ed2458dChris Lattner// each member (if possible). Then, if possible, it transforms the individual 1438aec325604635380421a27e39ab06d55ed2458dChris Lattner// alloca instructions into nice clean scalar SSA form. 1538aec325604635380421a27e39ab06d55ed2458dChris Lattner// 1638aec325604635380421a27e39ab06d55ed2458dChris Lattner// This combines a simple SRoA algorithm with the Mem2Reg algorithm because 1738aec325604635380421a27e39ab06d55ed2458dChris Lattner// often interact, especially for C++ programs. As such, iterating between 1838aec325604635380421a27e39ab06d55ed2458dChris Lattner// SRoA, then Mem2Reg until we run out of things to promote works well. 19ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 20ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===----------------------------------------------------------------------===// 21ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 220e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner#define DEBUG_TYPE "scalarrepl" 23ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Transforms/Scalar.h" 2438aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Constants.h" 2538aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/DerivedTypes.h" 26ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Function.h" 2779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner#include "llvm/GlobalVariable.h" 28d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 29372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/IntrinsicInst.h" 30fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson#include "llvm/LLVMContext.h" 3172eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner#include "llvm/Module.h" 32372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/Pass.h" 3338aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Analysis/Dominators.h" 3438aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Target/TargetData.h" 3538aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 364afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel#include "llvm/Transforms/Utils/Local.h" 37a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner#include "llvm/Support/CallSite.h" 389525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Debug.h" 397d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 40a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 4165a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner#include "llvm/Support/IRBuilder.h" 42a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/MathExtras.h" 43bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 441ccd185cb49d81465a2901622e58ceae046d1d83Chris Lattner#include "llvm/ADT/SmallVector.h" 45551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 46d8664730942beb911327336d1f9db8e7efcd6813Chris Lattnerusing namespace llvm; 47d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 480e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of allocas broken up"); 490e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted, "Number of allocas promoted"); 500e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumConverted, "Number of aggregates converted to scalar"); 5179b3bd395dc3303cde65e18e0524ed2f70268c99Chris LattnerSTATISTIC(NumGlobals, "Number of allocas copied from constant global"); 52ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 530e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 543e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct SROA : public FunctionPass { 55ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 5690c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson explicit SROA(signed T = -1) : FunctionPass(ID) { 57081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeSROAPass(*PassRegistry::getPassRegistry()); 58ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel if (T == -1) 59b0e71edb6b33f822e001500dac90acf95faacea8Chris Lattner SRThreshold = 128; 60ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel else 61ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel SRThreshold = T; 62ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel } 63794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 64ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 65ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 6638aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performScalarRepl(Function &F); 6738aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performPromotion(Function &F); 6838aec325604635380421a27e39ab06d55ed2458dChris Lattner 69a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 70a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // will not alter the CFG, so say so. 71a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 72326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel AU.addRequired<DominatorTree>(); 7338aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<DominanceFrontier>(); 74a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner AU.setPreservesCFG(); 75a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner } 76a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner 77ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 7856c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner TargetData *TD; 7956c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner 80b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson /// DeadInsts - Keep track of instructions we have made dead, so that 81b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson /// we can remove them after we are done working. 82b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<Value*, 32> DeadInsts; 83b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 8439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// AllocaInfo - When analyzing uses of an alloca instruction, this captures 8539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// information about the uses. All these fields are initialized to false 8639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// and set to true when something is learned. 8739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner struct AllocaInfo { 8839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isUnsafe - This is set to true if the alloca cannot be SROA'd. 8939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isUnsafe : 1; 9039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isMemCpySrc - This is true if this aggregate is memcpy'd from. 9239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpySrc : 1; 9339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9433b0b8d242de8d428f11e77ea734a08b47797216Zhou Sheng /// isMemCpyDst - This is true if this aggregate is memcpy'd into. 9539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpyDst : 1; 9639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo() 986c146eefbf75875250af37a0f1ea70fc6b4716eeVictor Hernandez : isUnsafe(false), isMemCpySrc(false), isMemCpyDst(false) {} 9939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner }; 10039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 101ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel unsigned SRThreshold; 102ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel 10339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; } 10439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1056c146eefbf75875250af37a0f1ea70fc6b4716eeVictor Hernandez bool isSafeAllocaToScalarRepl(AllocaInst *AI); 10639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 107b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 1083c3af5d15569d708d2dc8f13351bc77056b4d70dBob Wilson AllocaInfo &Info); 109b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t &Offset, 1103c3af5d15569d708d2dc8f13351bc77056b4d70dBob Wilson AllocaInfo &Info); 1113c3af5d15569d708d2dc8f13351bc77056b4d70dBob Wilson void isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t MemSize, 1123c3af5d15569d708d2dc8f13351bc77056b4d70dBob Wilson const Type *MemOpType, bool isStore, AllocaInfo &Info); 113b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson bool TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size); 114e88728d757d3090f1c0885b78d3675a7e143a2f9Bob Wilson uint64_t FindElementAndOffset(const Type *&T, uint64_t &Offset, 115e88728d757d3090f1c0885b78d3675a7e143a2f9Bob Wilson const Type *&IdxTy); 11639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1177b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void DoScalarReplacement(AllocaInst *AI, 1187b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez std::vector<AllocaInst*> &WorkList); 119b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void DeleteDeadInstructions(); 1203126f1c02895a9d18a504a5ad4af9ef2029c0dcaChris Lattner 121b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 122b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 123b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 124b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 125b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 126b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 127b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 1287b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI, 129d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1307b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 131d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1327b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 1336e733d34ca487ab7ff8a6def018a933620393869Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 134d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 13531d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner static MemTransferInst *isOnlyCopiedFromConstantGlobal(AllocaInst *AI); 136ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 137ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 138ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 139844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar SROA::ID = 0; 1402ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(SROA, "scalarrepl", 1412ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Scalar Replacement of Aggregates", false, false) 1422ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1432ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominanceFrontier) 1442ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(SROA, "scalarrepl", 145ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Scalar Replacement of Aggregates", false, false) 146844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 147d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the ScalarReplAggregates pass 148ff366850aa9956e167e78d4f5b57aae10d8c5779Devang PatelFunctionPass *llvm::createScalarReplAggregatesPass(signed int Threshold) { 149ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel return new SROA(Threshold); 150ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel} 151ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 152ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 1534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 1544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// Convert To Scalar Optimization. 1554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 156963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner 157c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattnernamespace { 158a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// ConvertToScalarInfo - This class implements the "Convert To Scalar" 159a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// optimization, which scans the uses of an alloca and determines if it can 160a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// rewrite it in terms of a single new alloca that can be mem2reg'd. 1614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerclass ConvertToScalarInfo { 162c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner /// AllocaSize - The size of the alloca being considered. 163c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner unsigned AllocaSize; 164593375d04ab32be0161607a741d310172f142b93Chris Lattner const TargetData &TD; 165c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 166a0bada729ffaa1bfc80ef25935bdc5a67432708fChris Lattner /// IsNotTrivial - This is set to true if there is some access to the object 167a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// which means that mem2reg can't promote it. 168c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner bool IsNotTrivial; 169a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 170a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// VectorTy - This tracks the type that we should promote the vector to if 171a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// it is possible to turn it into a vector. This starts out null, and if it 172a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// isn't possible to turn into a vector type, it gets set to VoidTy. 173c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner const Type *VectorTy; 174a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 175a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// HadAVector - True if there is at least one vector access to the alloca. 176a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// We don't want to turn random arrays into vectors and use vector element 177a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// insert/extract, but if there are element accesses to something that is 178a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// also declared as a vector, we do want to promote to a vector. 179c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner bool HadAVector; 180c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 1814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerpublic: 182593375d04ab32be0161607a741d310172f142b93Chris Lattner explicit ConvertToScalarInfo(unsigned Size, const TargetData &td) 183593375d04ab32be0161607a741d310172f142b93Chris Lattner : AllocaSize(Size), TD(td) { 184c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner IsNotTrivial = false; 185c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner VectorTy = 0; 186c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner HadAVector = false; 187c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner } 188c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 189a001b664988f759d194f3d5d880c61449219fc2eChris Lattner AllocaInst *TryConvert(AllocaInst *AI); 190593375d04ab32be0161607a741d310172f142b93Chris Lattner 1914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerprivate: 192593375d04ab32be0161607a741d310172f142b93Chris Lattner bool CanConvertToScalar(Value *V, uint64_t Offset); 193593375d04ab32be0161607a741d310172f142b93Chris Lattner void MergeInType(const Type *In, uint64_t Offset); 194593375d04ab32be0161607a741d310172f142b93Chris Lattner void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset); 195593375d04ab32be0161607a741d310172f142b93Chris Lattner 196593375d04ab32be0161607a741d310172f142b93Chris Lattner Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType, 197593375d04ab32be0161607a741d310172f142b93Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 198593375d04ab32be0161607a741d310172f142b93Chris Lattner Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal, 199593375d04ab32be0161607a741d310172f142b93Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 200c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner}; 201c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner} // end anonymous namespace. 202c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 20391abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 20491abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner/// IsVerbotenVectorType - Return true if this is a vector type ScalarRepl isn't 20591abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner/// allowed to form. We do this to avoid MMX types, which is a complete hack, 20691abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner/// but is required until the backend is fixed. 20772eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattnerstatic bool IsVerbotenVectorType(const VectorType *VTy, const Instruction *I) { 20872eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner StringRef Triple(I->getParent()->getParent()->getParent()->getTargetTriple()); 20972eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner if (!Triple.startswith("i386") && 21072eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner !Triple.startswith("x86_64")) 21172eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner return false; 21272eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner 21391abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner // Reject all the MMX vector types. 21491abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner switch (VTy->getNumElements()) { 21591abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner default: return false; 21691abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner case 1: return VTy->getElementType()->isIntegerTy(64); 21791abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner case 2: return VTy->getElementType()->isIntegerTy(32); 21891abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner case 4: return VTy->getElementType()->isIntegerTy(16); 21991abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner case 8: return VTy->getElementType()->isIntegerTy(8); 22091abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner } 22191abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner} 22291abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 22391abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 224a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// TryConvert - Analyze the specified alloca, and if it is safe to do so, 225a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// rewrite it to be a new alloca which is mem2reg'able. This returns the new 226a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// alloca if possible or null if not. 227a001b664988f759d194f3d5d880c61449219fc2eChris LattnerAllocaInst *ConvertToScalarInfo::TryConvert(AllocaInst *AI) { 228a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we can't convert this scalar, or if mem2reg can trivially do it, bail 229a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // out. 230a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (!CanConvertToScalar(AI, 0) || !IsNotTrivial) 231a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return 0; 232a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 233a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we were able to find a vector type that can handle this with 234a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // insert/extract elements, and if there was at least one use that had 235a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // a vector type, promote this to a vector. We don't want to promote 236a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // random stuff that doesn't use vectors (e.g. <9 x double>) because then 237a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // we just get a lot of insert/extracts. If at least one vector is 238a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // involved, then we probably really do have a union of vector/array. 239a001b664988f759d194f3d5d880c61449219fc2eChris Lattner const Type *NewTy; 24091abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner if (VectorTy && VectorTy->isVectorTy() && HadAVector && 24172eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner !IsVerbotenVectorType(cast<VectorType>(VectorTy), AI)) { 242a001b664988f759d194f3d5d880c61449219fc2eChris Lattner DEBUG(dbgs() << "CONVERT TO VECTOR: " << *AI << "\n TYPE = " 243a001b664988f759d194f3d5d880c61449219fc2eChris Lattner << *VectorTy << '\n'); 244a001b664988f759d194f3d5d880c61449219fc2eChris Lattner NewTy = VectorTy; // Use the vector type. 245a001b664988f759d194f3d5d880c61449219fc2eChris Lattner } else { 246a001b664988f759d194f3d5d880c61449219fc2eChris Lattner DEBUG(dbgs() << "CONVERT TO SCALAR INTEGER: " << *AI << "\n"); 247a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // Create and insert the integer alloca. 248a001b664988f759d194f3d5d880c61449219fc2eChris Lattner NewTy = IntegerType::get(AI->getContext(), AllocaSize*8); 249a001b664988f759d194f3d5d880c61449219fc2eChris Lattner } 250a001b664988f759d194f3d5d880c61449219fc2eChris Lattner AllocaInst *NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin()); 251a001b664988f759d194f3d5d880c61449219fc2eChris Lattner ConvertUsesToScalar(AI, NewAI, 0); 252a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return NewAI; 253a001b664988f759d194f3d5d880c61449219fc2eChris Lattner} 254a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 255a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// MergeInType - Add the 'In' type to the accumulated vector type (VectorTy) 256a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// so far at the offset specified by Offset (which is specified in bytes). 2574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 2584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// There are two cases we handle here: 2594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 1) A union of vector types of the same size and potentially its elements. 2604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Here we turn element accesses into insert/extract element operations. 2614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This promotes a <4 x float> with a store of float to the third element 2624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// into a <4 x float> that uses insert element. 2634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 2) A fully general blob of memory, which we turn into some (potentially 2644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// large) integer type with extract and insert operations where the loads 265a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// and stores would mutate the memory. We mark this by setting VectorTy 266a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// to VoidTy. 2674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid ConvertToScalarInfo::MergeInType(const Type *In, uint64_t Offset) { 268a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we already decided to turn this into a blob of integer memory, there is 269a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // nothing to be done. 2704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy && VectorTy->isVoidTy()) 2714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 2724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 2734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this could be contributing to a vector, analyze it. 274c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 2754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the In type is a vector that is the same size as the alloca, see if it 2764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // matches the existing VecTy. 2774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VInTy = dyn_cast<VectorType>(In)) { 278a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // Remember if we saw a vector type. 279a001b664988f759d194f3d5d880c61449219fc2eChris Lattner HadAVector = true; 280a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 2814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) { 2824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we're storing/loading a vector of the right size, allow it as a 2834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // vector. If this the first vector we see, remember the type so that 284a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // we know the element size. If this is a subsequent access, ignore it 285a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // even if it is a differing type but the same size. Worst case we can 286a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // bitcast the resultant vectors. 2874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy == 0) 2884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = VInTy; 2894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 2904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 2914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (In->isFloatTy() || In->isDoubleTy() || 2924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner (In->isIntegerTy() && In->getPrimitiveSizeInBits() >= 8 && 2934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isPowerOf2_32(In->getPrimitiveSizeInBits()))) { 2944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we're accessing something that could be an element of a vector, see 2954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // if the implied vector agrees with what we already have and if Offset is 2964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // compatible with it. 2974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = In->getPrimitiveSizeInBits()/8; 2984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset % EltSize == 0 && AllocaSize % EltSize == 0 && 2994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner (VectorTy == 0 || 3004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner cast<VectorType>(VectorTy)->getElementType() 3014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ->getPrimitiveSizeInBits()/8 == EltSize)) { 3024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy == 0) 3034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = VectorType::get(In, AllocaSize/EltSize); 3044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 3054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 3064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 3074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 3084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, we have a case that we can't handle with an optimized vector 3094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // form. We can still turn this into a large integer. 3104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = Type::getVoidTy(In->getContext()); 3114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 312c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 3134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// CanConvertToScalar - V is a pointer. If we can convert the pointee and all 3144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// its accesses to a single vector type, return true and set VecTy to 3154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the new type. If we could convert the alloca into a single promotable 3164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer, return true but set VecTy to VoidTy. Further, if the use is not a 3174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// completely trivial use that mem2reg could promote, set IsNotTrivial. Offset 3184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// is the current offset from the base of the alloca being analyzed. 3194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 3204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// If we see at least one access to the value that is as a vector type, set the 3214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// SawVec flag. 3224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool ConvertToScalarInfo::CanConvertToScalar(Value *V, uint64_t Offset) { 3234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 3244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(*UI); 325a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 3264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 3274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Don't break volatile loads. 3284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LI->isVolatile()) 3294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3300488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen // Don't touch MMX operations. 3310488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen if (LI->getType()->isX86_MMXTy()) 3320488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen return false; 3334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MergeInType(LI->getType(), Offset); 334add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner continue; 335add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner } 3367809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 3374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 3384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing the pointer, not into the value? 3394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SI->getOperand(0) == V || SI->isVolatile()) return false; 3400488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen // Don't touch MMX operations. 3410488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen if (SI->getOperand(0)->getType()->isX86_MMXTy()) 3420488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen return false; 3434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MergeInType(SI->getOperand(0)->getType(), Offset); 3447809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 3457809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 346add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner 3474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { 348a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 3494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!CanConvertToScalar(BCI, Offset)) 3504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3513992feb075b27ff37b63017078a977206f97d10dBob Wilson continue; 3523992feb075b27ff37b63017078a977206f97d10dBob Wilson } 3533992feb075b27ff37b63017078a977206f97d10dBob Wilson 3544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 3554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a GEP with a variable indices, we can't handle it. 3564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!GEP->hasAllConstantIndices()) 3574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 3594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset that this GEP adds to the pointer. 3604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 3614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(), 3624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 3634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // See if all uses can be converted. 3644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!CanConvertToScalar(GEP, Offset+GEPOffset)) 3654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 366a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 3677809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 3684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 369ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 3704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 3714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // handle it. 3724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 3734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Store of constant value and constant size. 374a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (!isa<ConstantInt>(MSI->getValue()) || 375a001b664988f759d194f3d5d880c61449219fc2eChris Lattner !isa<ConstantInt>(MSI->getLength())) 376a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return false; 377a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 378a001b664988f759d194f3d5d880c61449219fc2eChris Lattner continue; 3794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 380fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 3824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // can handle it like a load or store of the scalar type. 3834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 384a001b664988f759d194f3d5d880c61449219fc2eChris Lattner ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength()); 385a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (Len == 0 || Len->getZExtValue() != AllocaSize || Offset != 0) 386a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return false; 387a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 388a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 389a001b664988f759d194f3d5d880c61449219fc2eChris Lattner continue; 390ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 3914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 3924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, we cannot handle this! 3934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 394a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 3954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 3964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 397ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 398a59adc40153f3e0f9843952c127d179b5ebe6c4cChris Lattner 3994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 4004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// directly. This happens when we are converting an "integer union" to a 4014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// single integer scalar, or when we are converting a "vector union" to a 4024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// vector with insert/extractelement instructions. 4034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 4044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 4054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. By the end of this, there should be no uses of Ptr. 4064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid ConvertToScalarInfo::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, 4074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset) { 4084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!Ptr->use_empty()) { 4094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(Ptr->use_back()); 410b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 4114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) { 4124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertUsesToScalar(CI, NewAI, Offset); 4134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner CI->eraseFromParent(); 4144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 416b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 4174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 4184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset that this GEP adds to the pointer. 4194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 4204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(), 4214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 4224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8); 4234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner GEP->eraseFromParent(); 4244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 426b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 4274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IRBuilder<> Builder(User->getParent(), User); 4284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 4304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The load is a bit extract from NewAI shifted right by Offset bits. 4314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp"); 4324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *NewLoadVal 4334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder); 4344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(NewLoadVal); 4354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->eraseFromParent(); 4364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 4404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(SI->getOperand(0) != Ptr && "Consistency error!"); 4414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in"); 4424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset, 4434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 4444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(New, NewAI); 4454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SI->eraseFromParent(); 4464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load we just inserted is now dead, then the inserted store 4484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // overwrote the entire thing. 4494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Old->use_empty()) 4504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old->eraseFromParent(); 4514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 4554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // transform it into a store of the expanded constant value. 4564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 4574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MSI->getRawDest() == Ptr && "Consistency error!"); 4584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 4594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (NumBytes != 0) { 4604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue(); 4614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the value replicated the right number of times. 4634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt APVal(NumBytes*8, Val); 4642674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 4654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Splat the value if non-zero. 4664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val) 4674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 1; i != NumBytes; ++i) 4684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APVal |= APVal << 8; 4694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in"); 4714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *New = ConvertScalar_InsertValue( 4724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(User->getContext(), APVal), 4734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old, Offset, Builder); 4744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(New, NewAI); 4754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load we just inserted is now dead, then the memset overwrote 4774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the entire thing. 4784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Old->use_empty()) 4794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old->eraseFromParent(); 4804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MSI->eraseFromParent(); 4824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 483b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 484fca55c8ac7d12e4139ad0ab7d74b76c47935aef6Daniel Dunbar 4854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 4864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // can handle it like a load or store of the scalar type. 4874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 4884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(Offset == 0 && "must be store to start of alloca"); 4894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the source and destination are both to the same alloca, then this is 4914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // a noop copy-to-self, just delete it. Otherwise, emit a load and store 4924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // as appropriate. 4934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *OrigAI = cast<AllocaInst>(Ptr->getUnderlyingObject(0)); 4944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MTI->getSource()->getUnderlyingObject(0) != OrigAI) { 4964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Dest must be OrigAI, change this to be a load from the original 4974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // pointer (bitcasted), then a store to our new alloca. 4984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?"); 4994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcPtr = MTI->getSource(); 5004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcPtr = Builder.CreateBitCast(SrcPtr, NewAI->getType()); 5014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval"); 5034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcVal->setAlignment(MTI->getAlignment()); 5044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(SrcVal, NewAI); 5054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (MTI->getDest()->getUnderlyingObject(0) != OrigAI) { 5064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Src must be OrigAI, change this to be a load from NewAI then a store 5074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // through the original dest pointer (bitcasted). 5084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?"); 5094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval"); 510b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 5114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), NewAI->getType()); 5124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr); 5134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewStore->setAlignment(MTI->getAlignment()); 5144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 5154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Noop transfer. Src == Dst 5164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5175fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 5184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MTI->eraseFromParent(); 5194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 5204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner llvm_unreachable("Unsupported operation!"); 52388e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner } 5242674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar} 5252674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 5264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer 5274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or vector value FromVal, extracting the bits from the offset specified by 5284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset. This returns the value, which is of type ToType. 5294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 5304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This happens when we are converting an "integer union" to a single 5314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer scalar, or when we are converting a "vector union" to a vector with 5324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// insert/extractelement instructions. 5334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 5344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 5354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. 5364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerValue *ConvertToScalarInfo:: 5374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerConvertScalar_ExtractValue(Value *FromVal, const Type *ToType, 5384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset, IRBuilder<> &Builder) { 5394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load is of the whole new alloca, no conversion is needed. 5404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FromVal->getType() == ToType && Offset == 0) 5414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return FromVal; 5424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the result alloca is a vector type, this is either an element 5444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // access or a bitcast to another vector type of the same size. 5454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) { 5464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ToType->isVectorTy()) 5474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Builder.CreateBitCast(FromVal, ToType, "tmp"); 5484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise it must be an element access. 5504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Elt = 0; 5514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset) { 5524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType()); 5534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Elt = Offset/EltSize; 5544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(EltSize*Elt == Offset && "Invalid modulus in validity checking"); 555b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 5564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Return the element extracted out of it. 5574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *V = Builder.CreateExtractElement(FromVal, ConstantInt::get( 5584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Type::getInt32Ty(FromVal->getContext()), Elt), "tmp"); 5594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (V->getType() != ToType) 5604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner V = Builder.CreateBitCast(V, ToType, "tmp"); 5614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return V; 5624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If ToType is a first class aggregate, extract out each of the pieces and 5654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // use insertvalue's to form the FCA. 5664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(ToType)) { 5674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout &Layout = *TD.getStructLayout(ST); 5684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Res = UndefValue::get(ST); 5694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 5704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i), 5714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+Layout.getElementOffsetInBits(i), 5724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 5734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 5744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Res; 5764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(ToType)) { 5794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType()); 5804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Res = UndefValue::get(AT); 5814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 5824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(), 5834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+i*EltSize, Builder); 5844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 5854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Res; 587b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 5882674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 5894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, this must be a union that was converted to an integer value. 5904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const IntegerType *NTy = cast<IntegerType>(FromVal->getType()); 591b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 5924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a big-endian system and the load is narrower than the 5934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // full alloca type, we need to do a shift to get the right bits. 5944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner int ShAmt = 0; 5954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD.isBigEndian()) { 5964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 5974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 5984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integers with a bitwidth that is not a multiple of 8. 5994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = TD.getTypeStoreSizeInBits(NTy) - 6004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD.getTypeStoreSizeInBits(ToType) - Offset; 601b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 6024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = Offset; 603b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 604b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 6054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Note: we support negative bitwidths (with shl) which are not defined. 6064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // We do this to support (f.e.) loads off the end of a structure where 6074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // only some bits are used. 6084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth()) 6094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateLShr(FromVal, 6104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(FromVal->getType(), 6114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt), "tmp"); 6124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth()) 6134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateShl(FromVal, 6144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(FromVal->getType(), 6154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner -ShAmt), "tmp"); 616b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 6174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Finally, unconditionally truncate the integer to the right width. 6184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned LIBitWidth = TD.getTypeSizeInBits(ToType); 6194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LIBitWidth < NTy->getBitWidth()) 6204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = 6214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateTrunc(FromVal, IntegerType::get(FromVal->getContext(), 6224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LIBitWidth), "tmp"); 6234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (LIBitWidth > NTy->getBitWidth()) 6244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = 6254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateZExt(FromVal, IntegerType::get(FromVal->getContext(), 6264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LIBitWidth), "tmp"); 6274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the result is an integer, this is a trunc or bitcast. 6294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ToType->isIntegerTy()) { 6304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Should be done. 6314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ToType->isFloatingPointTy() || ToType->isVectorTy()) { 6324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Just do a bitcast, we know the sizes match up. 6334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp"); 6344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 6354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise must be a pointer. 6364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp"); 637372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 6384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(FromVal->getType() == ToType && "Didn't convert right?"); 6394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return FromVal; 640372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 641372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 6424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer 6434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or vector value "Old" at the offset specified by Offset. 6444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 6454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This happens when we are converting an "integer union" to a 6464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// single integer scalar, or when we are converting a "vector union" to a 6474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// vector with insert/extractelement instructions. 6484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 6494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 6504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. 6514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerValue *ConvertToScalarInfo:: 6524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerConvertScalar_InsertValue(Value *SV, Value *Old, 6534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset, IRBuilder<> &Builder) { 6544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Convert the stored type to the actual type, shift it left to insert 6554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // then 'or' into place. 6564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaType = Old->getType(); 6574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LLVMContext &Context = Old->getContext(); 6582674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 6594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(AllocaType)) { 6604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t VecSize = TD.getTypeAllocSizeInBits(VTy); 6614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ValSize = TD.getTypeAllocSizeInBits(SV->getType()); 6624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Changing the whole vector with memset or with an access of a different 6644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // vector type? 6654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ValSize == VecSize) 6664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Builder.CreateBitCast(SV, AllocaType, "tmp"); 6672674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 6684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType()); 6694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Must be an element insertion. 6714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Elt = Offset/EltSize; 6724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType() != VTy->getElementType()) 6744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp"); 6754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateInsertElement(Old, SV, 6774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(Type::getInt32Ty(SV->getContext()), Elt), 6784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "tmp"); 6794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return SV; 680b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 6814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SV is a first-class aggregate value, insert each value recursively. 6834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(SV->getType())) { 6844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout &Layout = *TD.getStructLayout(ST); 6854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 6864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 6874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old = ConvertScalar_InsertValue(Elt, Old, 6884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+Layout.getElementOffsetInBits(i), 6894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 6904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 6914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Old; 6924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 6934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) { 6954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType()); 6964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 6974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 6984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder); 6994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Old; 7014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SV is a float, convert it to the appropriate integer type. 7044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If it is a pointer, do the same. 7054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned SrcWidth = TD.getTypeSizeInBits(SV->getType()); 7064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned DestWidth = TD.getTypeSizeInBits(AllocaType); 7074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned SrcStoreWidth = TD.getTypeStoreSizeInBits(SV->getType()); 7084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned DestStoreWidth = TD.getTypeStoreSizeInBits(AllocaType); 7094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType()->isFloatingPointTy() || SV->getType()->isVectorTy()) 7104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateBitCast(SV, 7114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SV->getContext(),SrcWidth), "tmp"); 7124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (SV->getType()->isPointerTy()) 7134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreatePtrToInt(SV, TD.getIntPtrType(SV->getContext()), "tmp"); 7144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero extend or truncate the value if needed. 7164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType() != AllocaType) { 7174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType()->getPrimitiveSizeInBits() < 7184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaType->getPrimitiveSizeInBits()) 7194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateZExt(SV, AllocaType, "tmp"); 7204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else { 7214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncation may be needed if storing more than the alloca can hold 7224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (undefined behavior). 7234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateTrunc(SV, AllocaType, "tmp"); 7244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcWidth = DestWidth; 7254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcStoreWidth = DestStoreWidth; 7264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a big-endian system and the store is narrower than the 7304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // full alloca type, we need to do a shift to get the right bits. 7314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner int ShAmt = 0; 7324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD.isBigEndian()) { 7334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 7344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 7354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integers with a bitwidth that is not a multiple of 8. 7364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = DestStoreWidth - SrcStoreWidth - Offset; 7374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 7384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = Offset; 7394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Note: we support negative bitwidths (with shr) which are not defined. 7424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // We do this to support (f.e.) stores off the end of a structure where 7434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // only some bits in the structure are set. 7444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth)); 7454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) { 7464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(), 7474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt), "tmp"); 7484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Mask <<= ShAmt; 7494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) { 7504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(), 7514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner -ShAmt), "tmp"); 7524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Mask = Mask.lshr(-ShAmt); 7534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Mask out the bits we are about to insert from the old value, and or 7564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // in the new bits. 7574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcWidth != DestWidth) { 7584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(DestWidth > SrcWidth); 7594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old = Builder.CreateAnd(Old, ConstantInt::get(Context, ~Mask), "mask"); 7604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateOr(Old, SV, "ins"); 7614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return SV; 763b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson} 764b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 765b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 7674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// SRoA Driver 7684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 769b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 770b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::runOnFunction(Function &F) { 7724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD = getAnalysisIfAvailable<TargetData>(); 773b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = performPromotion(F); 775b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // FIXME: ScalarRepl currently depends on TargetData more than it 7774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // theoretically needs to. It should be refactored in order to support 7784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // target-independent IR. Until this is done, just skip the actual 7794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // scalar-replacement portion of this pass. 7804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!TD) return Changed; 7814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (1) { 7834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool LocalChange = performScalarRepl(F); 7844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!LocalChange) break; // No need to repromote if no scalarrepl 7854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 7864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LocalChange = performPromotion(F); 7874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!LocalChange) break; // No need to re-scalarrepl if no promotion 7882674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar } 7894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 791d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner} 792d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 79378c50b8cd68d266d4ed6f8eca443cf8142a01204Bob Wilson 7944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::performPromotion(Function &F) { 7954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> Allocas; 7964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 7974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); 798b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 800372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 8014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = false; 8024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (1) { 8044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Allocas.clear(); 8054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Find allocas that are safe to promote, by looking at all instructions in 8074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the entry node 8084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 8094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 8104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isAllocaPromotable(AI)) 8114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Allocas.push_back(AI); 8124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Allocas.empty()) break; 8144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PromoteMemToReg(Allocas, DT, DF); 8164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NumPromoted += Allocas.size(); 8174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 8184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 8194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 8214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 8224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ShouldAttemptScalarRepl - Decide if an alloca is a good candidate for 8254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// SROA. It must be a struct or array type with a small number of elements. 8264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerstatic bool ShouldAttemptScalarRepl(AllocaInst *AI) { 8274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *T = AI->getAllocatedType(); 8284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote any struct into more than 32 separate vars. 8294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) 8304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return ST->getNumElements() <= 32; 8314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Arrays are much less likely to be safe for SROA; only consider 8324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // them if they are very small. 8334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(T)) 8344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return AT->getNumElements() <= 8; 8354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 8364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 8374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// performScalarRepl - This algorithm is a simple worklist driven algorithm, 8404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// which runs on all of the malloc/alloca instructions in the function, removing 8414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// them if they are only used by getelementptr instructions. 8424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// 8434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::performScalarRepl(Function &F) { 8444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> WorkList; 8454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Scan the entry basic block, adding allocas to the worklist. 8474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BasicBlock &BB = F.getEntryBlock(); 8484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 8494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *A = dyn_cast<AllocaInst>(I)) 8504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(A); 8514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Process the worklist 8534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = false; 8544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!WorkList.empty()) { 8554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *AI = WorkList.back(); 8564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.pop_back(); 8574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle dead allocas trivially. These can be formed by SROA'ing arrays 8594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with unused elements. 8604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AI->use_empty()) { 8614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 8624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 8634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 864d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 8654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this alloca is impossible for us to promote, reject it early. 8674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized()) 8684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 869d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 8704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check to see if this allocation is only modified by a memcpy/memmove from 8714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // a constant global. If this is the case, we can change all users to use 8724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the constant global instead. This is commonly produced by the CFE by 8734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A' 8744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // is only subsequently read. 8754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) { 8764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Found alloca equal to global: " << *AI << '\n'); 8774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << " memcpy = " << *TheCopy << '\n'); 8784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *TheSrc = cast<Constant>(TheCopy->getSource()); 8794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType())); 8804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TheCopy->eraseFromParent(); // Don't mutate the global. 8814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 8824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ++NumGlobals; 8834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 8844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 8854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 886d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 8874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check to see if we can perform the core SROA transformation. We cannot 8884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // transform the allocation instruction if it is an array allocation 8894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (allocations OF arrays are ok though), and an allocation of a scalar 8904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // value cannot be decomposed at all. 8914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType()); 89244118f0e25c25fedda1ccdd6a72f072c0b5c96e7Dan Gohman 8934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote [0 x %struct]. 8944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaSize == 0) continue; 895c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 8964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote any struct whose size is too big. 8974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaSize > SRThreshold) continue; 898c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 8994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the alloca looks like a good candidate for scalar replacement, and if 9004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // all its users can be transformed, then split up the aggregate into its 9014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // separate elements. 9024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShouldAttemptScalarRepl(AI) && isSafeAllocaToScalarRepl(AI)) { 9034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DoScalarReplacement(AI, WorkList); 9044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 9054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 90620adc9dc4650313f017b27d9818eb2176238113dMon P Wang } 9074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we can turn this aggregate value (potentially with casts) into a 9094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // simple scalar value that can be mem2reg'd into a register value. 9104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // IsNotTrivial tracks whether this is something that mem2reg could have 9114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // promoted itself. If so, we don't want to transform it needlessly. Note 9124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // that we can't just check based on the type: the alloca may be of an i32 9134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // but that has pointer arithmetic to set byte 3 of it or something. 9144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *NewAI = 9154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertToScalarInfo((unsigned)AllocaSize, *TD).TryConvert(AI)) { 9164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewAI->takeName(AI); 9174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 9184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ++NumConverted; 9194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 9204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 9214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 922d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 9234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, couldn't process this alloca. 924372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 9254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 927372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 928d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl 9304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// predicate, do SROA now. 9314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::DoScalarReplacement(AllocaInst *AI, 9324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> &WorkList) { 9334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Found inst to SROA: " << *AI << '\n'); 9344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> ElementAllocas; 9354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 9364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 9374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 9384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 9394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getAlignment(), 9404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getName() + "." + Twine(i), AI); 9414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.push_back(NA); 9424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 9434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 9444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 9454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 9464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.reserve(AT->getNumElements()); 9474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ElTy = AT->getElementType(); 9484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 9494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), 9504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getName() + "." + Twine(i), AI); 9514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.push_back(NA); 9524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 9534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 9544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 955d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Now that we have created the new alloca instructions, rewrite all the 9574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // uses of the old alloca. 9584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(AI, AI, 0, ElementAllocas); 959d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Now erase any instructions that were made dead while rewriting the alloca. 9614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeleteDeadInstructions(); 9624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 9634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 964fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumReplaced; 9654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 9664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// DeleteDeadInstructions - Erase instructions on the DeadInstrs list, 9684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// recursively including all their operands that become trivially dead. 9694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::DeleteDeadInstructions() { 9704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!DeadInsts.empty()) { 9714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *I = cast<Instruction>(DeadInsts.pop_back_val()); 9724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 9744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Instruction *U = dyn_cast<Instruction>(*OI)) { 9754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero out the operand and see if it becomes trivially dead. 9764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (But, don't add allocas to the dead instruction list -- they are 9774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // already on the worklist and will be deleted separately.) 9784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner *OI = 0; 9794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isInstructionTriviallyDead(U) && !isa<AllocaInst>(U)) 9804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(U); 981d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 982d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner I->eraseFromParent(); 9844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 9854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 986d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeForScalarRepl - Check if instruction I is a safe use with regard to 9884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// performing scalar replacement of alloca AI. The results are flagged in 9894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the Info parameter. Offset indicates the position within AI that is 9904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// referenced by this instruction. 9914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 9924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInfo &Info) { 9934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) { 9944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(*UI); 9954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 9974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeForScalarRepl(BC, AI, Offset, Info); 9984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 9994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = Offset; 10004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeGEP(GEPI, AI, GEPOffset, Info); 10014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!Info.isUnsafe) 10024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeForScalarRepl(GEPI, AI, GEPOffset, Info); 100319101c7585c191376d898e3e66e35acd9bd777c2Gabor Greif } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 10044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 10054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Length) 10064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeMemAccess(AI, Offset, Length->getZExtValue(), 0, 1007a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif UI.getOperandNo() == 0, Info); 10084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else 10094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 10104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 10114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!LI->isVolatile()) { 10124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *LIType = LI->getType(); 10134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeMemAccess(AI, Offset, TD->getTypeAllocSize(LIType), 10144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LIType, false, Info); 10154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else 10164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 10174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 10184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Store is ok if storing INTO the pointer, not storing the pointer 10194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!SI->isVolatile() && SI->getOperand(0) != I) { 10204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *SIType = SI->getOperand(0)->getType(); 10214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeMemAccess(AI, Offset, TD->getTypeAllocSize(SIType), 10224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SIType, true, Info); 10234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else 10244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 10254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 10264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(errs() << " Transformation preventing inst: " << *User << '\n'); 10274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 1028d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 10294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isUnsafe) return; 1030d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1031d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner} 1032d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 10334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeGEP - Check if a GEP instruction can be handled for scalar 10344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// replacement. It is safe when all the indices are constant, in-bounds 10354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// references, and when the resulting offset corresponds to an element within 10364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the alloca type. The results are flagged in the Info parameter. Upon 10374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// return, Offset is adjusted as specified by the GEP indices. 10384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI, 10394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t &Offset, AllocaInfo &Info) { 10404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner gep_type_iterator GEPIt = gep_type_begin(GEPI), E = gep_type_end(GEPI); 10414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GEPIt == E) 10424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 10435ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Walk through the GEP type indices, checking the types that this indexes 10454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // into. 10464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (; GEPIt != E; ++GEPIt) { 10474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore struct elements, no extra checking needed for these. 10484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if ((*GEPIt)->isStructTy()) 10494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 10505ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPIt.getOperand()); 10524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!IdxVal) 10534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return MarkUnsafe(Info); 10545ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 105541b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 10564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset due to this GEP and check if the alloca has a 10574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // component element at that offset. 10584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 10594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), 10604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 10614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!TypeHasComponent(AI->getAllocatedType(), Offset, 0)) 10624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 10634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 106441b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 10654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeMemAccess - Check if a load/store/memcpy operates on the entire AI 10664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// alloca or has an offset and size that corresponds to a component element 10674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// within it. The offset checked here may have been formed from a GEP with a 10684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// pointer bitcasted to a different type. 10694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t MemSize, 10704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *MemOpType, bool isStore, 10714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInfo &Info) { 10724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if this is a load/store of the entire alloca. 10734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset == 0 && MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) { 10744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool UsesAggregateType = (MemOpType == AI->getAllocatedType()); 10754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // This is safe for MemIntrinsics (where MemOpType is 0), integer types 10764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (which are essentially the same as the MemIntrinsics, especially with 10774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // regard to copying padding between elements), or references using the 10784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // aggregate type of the alloca. 10794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!MemOpType || MemOpType->isIntegerTy() || UsesAggregateType) { 10804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!UsesAggregateType) { 10814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isStore) 10824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Info.isMemCpyDst = true; 10834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else 10844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Info.isMemCpySrc = true; 10854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 10864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 10874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 10884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 10894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if the offset/size correspond to a component within the alloca type. 10904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *T = AI->getAllocatedType(); 10914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TypeHasComponent(T, Offset, MemSize)) 10924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 10934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return MarkUnsafe(Info); 10955ffe6acd577696a41932c7b82db06a04687e07baChris Lattner} 10965ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// TypeHasComponent - Return true if T has a component type with the 10984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// specified offset and size. If Size is zero, do not check the size. 10994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size) { 11004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *EltTy; 11014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize; 11024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) { 11034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(ST); 11044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltIdx = Layout->getElementContainingOffset(Offset); 11054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltTy = ST->getContainedType(EltIdx); 11064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltSize = TD->getTypeAllocSize(EltTy); 11074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Layout->getElementOffset(EltIdx); 11084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (const ArrayType *AT = dyn_cast<ArrayType>(T)) { 11094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltTy = AT->getElementType(); 11104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltSize = TD->getTypeAllocSize(EltTy); 11114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset >= AT->getNumElements() * EltSize) 11124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 11134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset %= EltSize; 11144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 11154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 11164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset == 0 && (Size == 0 || EltSize == Size)) 11184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 11194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if the component spans multiple elements. 11204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset + Size > EltSize) 11214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 11224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return TypeHasComponent(EltTy, Offset, Size); 11234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 11243cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 11254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteForScalarRepl - Alloca AI is being split into NewElts, so rewrite 11264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the instruction I, which references it, to use the separate elements. 11274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset indicates the position within AI that is referenced by this 11284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// instruction. 11294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 11304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 11314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) { 11324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(*UI); 11333cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 11344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 11354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteBitCast(BC, AI, Offset, NewElts); 11364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 11374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteGEP(GEPI, AI, Offset, NewElts); 11384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 11394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 11404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t MemSize = Length->getZExtValue(); 11414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset == 0 && 11424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) 11434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteMemIntrinUserOfAlloca(MI, I, AI, NewElts); 11444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise the intrinsic can only touch a single element and the 11454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // address operand will be updated, so nothing else needs to be done. 11464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 11474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *LIType = LI->getType(); 11484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LIType == AI->getAllocatedType()) { 11494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Replace: 11504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %res = load { i32, i32 }* %alloc 11514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with: 11524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %load.0 = load i32* %alloc.0 11534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0 11544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %load.1 = load i32* %alloc.1 11554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1 11564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (Also works for arrays instead of structs) 11574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Insert = UndefValue::get(LIType); 11584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 11594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Load = new LoadInst(NewElts[i], "load", LI); 11604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI); 11614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(Insert); 11634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(LI); 11644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (LIType->isIntegerTy() && 11654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(LIType) == 11664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(AI->getAllocatedType())) { 11674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a load of the entire alloca to an integer, rewrite it. 11684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteLoadUserOfWholeAlloca(LI, AI, NewElts); 11694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 11714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Val = SI->getOperand(0); 11724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *SIType = Val->getType(); 11734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SIType == AI->getAllocatedType()) { 11744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Replace: 11754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store { i32, i32 } %val, { i32, i32 }* %alloc 11764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with: 11774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %val.0 = extractvalue { i32, i32 } %val, 0 11784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store i32 %val.0, i32* %alloc.0 11794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %val.1 = extractvalue { i32, i32 } %val, 1 11804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store i32 %val.1, i32* %alloc.1 11814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (Also works for arrays instead of structs) 11824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 11834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI); 11844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Extract, NewElts[i], SI); 11854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(SI); 11874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (SIType->isIntegerTy() && 11884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(SIType) == 11894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(AI->getAllocatedType())) { 11904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a store of the entire alloca from an integer, rewrite it. 11914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteStoreUserOfWholeAlloca(SI, AI, NewElts); 119239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 119339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 11944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 11963cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 11974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteBitCast - Update a bitcast reference to the alloca being replaced 11984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// and recursively continue updating all of its uses. 11994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 12004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 12014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(BC, AI, Offset, NewElts); 12024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BC->getOperand(0) != AI) 12034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 120439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 12054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The bitcast references the original alloca. Replace its uses with 12064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // references to the first new element alloca. 12074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Val = NewElts[0]; 12084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val->getType() != BC->getDestTy()) { 12094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = new BitCastInst(Val, BC->getDestTy(), "", BC); 12104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val->takeName(BC); 121139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 12124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BC->replaceAllUsesWith(Val); 12134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(BC); 121439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner} 1215372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 12164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// FindElementAndOffset - Return the index of the element containing Offset 12174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// within the specified type, which must be either a struct or an array. 12184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Sets T to the type of the element and Offset to the offset within that 12194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// element. IdxTy is set to the type of the index result to be used in a 12204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// GEP instruction. 12214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattneruint64_t SROA::FindElementAndOffset(const Type *&T, uint64_t &Offset, 12224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *&IdxTy) { 12234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Idx = 0; 12244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) { 12254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(ST); 12264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Idx = Layout->getElementContainingOffset(Offset); 12274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = ST->getContainedType(Idx); 12284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Layout->getElementOffset(Idx); 12294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IdxTy = Type::getInt32Ty(T->getContext()); 12304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Idx; 1231f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 12324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *AT = cast<ArrayType>(T); 12334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = AT->getElementType(); 12344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD->getTypeAllocSize(T); 12354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Idx = Offset / EltSize; 12364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Idx * EltSize; 12374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IdxTy = Type::getInt64Ty(T->getContext()); 12384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Idx; 12395e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 1240a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 12414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteGEP - Check if this GEP instruction moves the pointer across 12424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// elements of the alloca that are being split apart, and if so, rewrite 12434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the GEP to be relative to the new element. 12444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 12454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 12464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t OldOffset = Offset; 12474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 12484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), 12494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 12504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(GEPI, AI, Offset, NewElts); 12524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *T = AI->getAllocatedType(); 12544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *IdxTy; 12554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t OldIdx = FindElementAndOffset(T, OldOffset, IdxTy); 12564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GEPI->getOperand(0) == AI) 12574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OldIdx = ~0ULL; // Force the GEP to be rewritten. 12584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = AI->getAllocatedType(); 12604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltOffset = Offset; 12614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Idx = FindElementAndOffset(T, EltOffset, IdxTy); 12624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this GEP does not move the pointer across elements of the alloca 12644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // being split, then it does not needs to be rewritten. 12654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Idx == OldIdx) 1266c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner return; 1267c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 12684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *i32Ty = Type::getInt32Ty(AI->getContext()); 12694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> NewArgs; 12704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.push_back(Constant::getNullValue(i32Ty)); 12714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (EltOffset != 0) { 12724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltIdx = FindElementAndOffset(T, EltOffset, IdxTy); 12734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.push_back(ConstantInt::get(IdxTy, EltIdx)); 12742e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 12754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Val = NewElts[Idx]; 12764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (NewArgs.size() > 1) { 12774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = GetElementPtrInst::CreateInBounds(Val, NewArgs.begin(), 12784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.end(), "", GEPI); 12794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val->takeName(GEPI); 12804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 12814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val->getType() != GEPI->getType()) 12824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = new BitCastInst(Val, GEPI->getType(), Val->getName(), GEPI); 12834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner GEPI->replaceAllUsesWith(Val); 12844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(GEPI); 1285a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1286a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 12874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI. 12884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Rewrite it to copy or set the elements of the scalarized memory. 12894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 12904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *AI, 12914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 12924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy/memmove, construct the other pointer as the 12934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // appropriate type. The "Other" pointer is the pointer that goes to memory 12944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // that doesn't have anything to do with the alloca that we are promoting. For 12954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // memset, this Value* stays null. 12964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *OtherPtr = 0; 12974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned MemAlignment = MI->getAlignment(); 12984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { // memmove/memcopy 12994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Inst == MTI->getRawDest()) 13004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr = MTI->getRawSource(); 13014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else { 13024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(Inst == MTI->getRawSource()); 13034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr = MTI->getRawDest(); 1304a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 13054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 13063ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner 13074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If there is an other pointer, we want to convert it to the same pointer 13084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // type as AI has, so we can GEP through it safely. 13094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr) { 13100238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner unsigned AddrSpace = 13110238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner cast<PointerType>(OtherPtr->getType())->getAddressSpace(); 13124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 13134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Remove bitcasts and all-zero GEPs from OtherPtr. This is an 13144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // optimization, but it's also required to detect the corner case where 13154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // both pointer operands are referencing the same memory, and where 13164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // OtherPtr may be a bitcast or GEP that currently being rewritten. (This 13174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // function is only called for mem intrinsics that access the whole 13184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // aggregate, so non-zero GEPs are not an issue here.) 13190238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner OtherPtr = OtherPtr->stripPointerCasts(); 13200238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner 13214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Copying the alloca to itself is a no-op: just delete it. 13224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr == AI || OtherPtr == NewElts[0]) { 13234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // This code will run twice for a no-op memcpy -- once for each operand. 13244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Put only one reference to MI on the DeadInsts list. 13254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (SmallVector<Value*, 32>::const_iterator I = DeadInsts.begin(), 13264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner E = DeadInsts.end(); I != E; ++I) 13274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (*I == MI) return; 13284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(MI); 13294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 1330c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1331dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner 13324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the pointer is not the right type, insert a bitcast to the right 13334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // type. 13340238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner const Type *NewTy = 13350238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner PointerType::get(AI->getType()->getElementType(), AddrSpace); 13360238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner 13370238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner if (OtherPtr->getType() != NewTy) 13380238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner OtherPtr = new BitCastInst(OtherPtr, NewTy, OtherPtr->getName(), MI); 1339a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1340a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 13414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Process each element of the aggregate. 1342a9b2313c13a1bc8cbae751da03a9049ecaf0f918Gabor Greif Value *TheFn = MI->getCalledValue(); 13434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *BytePtrTy = MI->getRawDest()->getType(); 13444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool SROADest = MI->getRawDest() == Inst; 13454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 13464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *Zero = Constant::getNullValue(Type::getInt32Ty(MI->getContext())); 13474b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 13484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 13494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy/memmove, emit a GEP of the other element address. 13504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *OtherElt = 0; 13514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned OtherEltAlign = MemAlignment; 13529bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 13534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr) { 13544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Idx[2] = { Zero, 13554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(Type::getInt32Ty(MI->getContext()), i) }; 13564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherElt = GetElementPtrInst::CreateInBounds(OtherPtr, Idx, Idx + 2, 13574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr->getName()+"."+Twine(i), 13584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MI); 13594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltOffset; 13604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType()); 1361d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner const Type *OtherTy = OtherPtrTy->getElementType(); 1362d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner if (const StructType *ST = dyn_cast<StructType>(OtherTy)) { 13634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltOffset = TD->getStructLayout(ST)->getElementOffset(i); 13644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 1365d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner const Type *EltTy = cast<SequentialType>(OtherTy)->getElementType(); 13664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltOffset = TD->getTypeAllocSize(EltTy)*i; 13674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1368aadadb3973bb202cd4d2e20e842588162e780f13Chris Lattner 13694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The alignment of the other pointer is the guaranteed alignment of the 13704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // element, which is affected by both the known alignment of the whole 13714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // mem intrinsic and the alignment of the element. If the alignment of 13724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the memcpy (f.e.) is 32 but the element is at a 4-byte offset, then the 13734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // known alignment is just 4 bytes. 13744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset); 13759bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 13769bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 13774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltPtr = NewElts[i]; 13784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType(); 13794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 13804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we got down to a scalar, insert a load or store as appropriate. 13814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltTy->isSingleValueType()) { 13824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isa<MemTransferInst>(MI)) { 13834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SROADest) { 13844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // From Other to Alloca. 13854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI); 13864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Elt, EltPtr, MI); 13874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 13884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // From Alloca to Other. 13894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = new LoadInst(EltPtr, "tmp", MI); 13904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI); 13914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 13924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 139333e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner } 13944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(isa<MemSetInst>(MI)); 1395c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 13964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the stored element is zero (common case), just store a null 13974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // constant. 13984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *StoreVal; 13996f14c8c7c1ec97797a04631abad6885bfaabcc6dGabor Greif if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getArgOperand(1))) { 14004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (CI->isZero()) { 14014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = Constant::getNullValue(EltTy); // 0.0, null, 0, <0,0> 14024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 14034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If EltTy is a vector type, get the element type. 14044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ValTy = EltTy->getScalarType(); 1405c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 14064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Construct an integer with the right value. 14074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD->getTypeSizeInBits(ValTy); 14084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt OneVal(EltSize, CI->getZExtValue()); 14094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt TotalVal(OneVal); 14104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Set each byte. 14114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0; 8*i < EltSize; ++i) { 14124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TotalVal = TotalVal.shl(8); 14134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TotalVal |= OneVal; 14144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 14164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Convert the integer value to the appropriate type. 1417d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner StoreVal = ConstantInt::get(CI->getContext(), TotalVal); 14184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ValTy->isPointerTy()) 14194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy); 14204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (ValTy->isFloatingPointTy()) 14214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy); 14224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(StoreVal->getType() == ValTy && "Type mismatch!"); 14234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 14244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the requested value was a vector constant, create it. 14254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltTy != ValTy) { 14264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned NumElts = cast<VectorType>(ValTy)->getNumElements(); 14274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Constant*, 16> Elts(NumElts, StoreVal); 14284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantVector::get(&Elts[0], NumElts); 14294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(StoreVal, EltPtr, MI); 14324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 14334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, if we're storing a byte variable, use a memset call for 14354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // this element. 14364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 14384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Cast the element pointer to BytePtrTy. 14394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltPtr->getType() != BytePtrTy) 14404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltPtr = new BitCastInst(EltPtr, BytePtrTy, EltPtr->getName(), MI); 14414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 14424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Cast the other pointer (if we have one) to BytePtrTy. 14434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherElt && OtherElt->getType() != BytePtrTy) { 14444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Preserve address space of OtherElt 14454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const PointerType* OtherPTy = cast<PointerType>(OtherElt->getType()); 14464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const PointerType* PTy = cast<PointerType>(BytePtrTy); 14474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPTy->getElementType() != PTy->getElementType()) { 14484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Type *NewOtherPTy = PointerType::get(PTy->getElementType(), 14494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPTy->getAddressSpace()); 14504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherElt = new BitCastInst(OtherElt, NewOtherPTy, 1451af81235ef96a7a005b7fdfe5a64cce30df3d820dBenjamin Kramer OtherElt->getName(), MI); 1452c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1453c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1454dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner 14554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD->getTypeAllocSize(EltTy); 14564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 14574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Finally, insert the meminst for this element. 14584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isa<MemTransferInst>(MI)) { 14594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Ops[] = { 14604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SROADest ? EltPtr : OtherElt, // Dest ptr 14614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SROADest ? OtherElt : EltPtr, // Src ptr 14626f14c8c7c1ec97797a04631abad6885bfaabcc6dGabor Greif ConstantInt::get(MI->getArgOperand(2)->getType(), EltSize), // Size 14634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Align 14644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(Type::getInt32Ty(MI->getContext()), OtherEltAlign), 14654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MI->getVolatileCst() 14664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner }; 14674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // In case we fold the address space overloaded memcpy of A to B 14684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with memcpy of B to C, change the function to be a memcpy of A to C. 14694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *Tys[] = { Ops[0]->getType(), Ops[1]->getType(), 14704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Ops[2]->getType() }; 14714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Module *M = MI->getParent()->getParent()->getParent(); 14724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TheFn = Intrinsic::getDeclaration(M, MI->getIntrinsicID(), Tys, 3); 14734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner CallInst::Create(TheFn, Ops, Ops + 5, "", MI); 14744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 14754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(isa<MemSetInst>(MI)); 14764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Ops[] = { 14776f14c8c7c1ec97797a04631abad6885bfaabcc6dGabor Greif EltPtr, MI->getArgOperand(1), // Dest, Value, 14786f14c8c7c1ec97797a04631abad6885bfaabcc6dGabor Greif ConstantInt::get(MI->getArgOperand(2)->getType(), EltSize), // Size 14794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Zero, // Align 1480f601d6df6f43bb833461cbcee475c36998e6c259Benjamin Kramer ConstantInt::getFalse(MI->getContext()) // isVolatile 14814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner }; 14824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *Tys[] = { Ops[0]->getType(), Ops[2]->getType() }; 14834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Module *M = MI->getParent()->getParent()->getParent(); 14844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TheFn = Intrinsic::getDeclaration(M, Intrinsic::memset, Tys, 2); 14854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner CallInst::Create(TheFn, Ops, Ops + 5, "", MI); 14864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1487a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 14884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(MI); 1489a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 149079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 14914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteStoreUserOfWholeAlloca - We found a store of an integer that 14924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// overwrites the entire allocation. Extract out the pieces of the stored 14934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer and store them individually. 14944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 14954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts){ 14964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Extract each element out of the integer according to its structure offset 14974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // and store the element value to the individual alloca. 14984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcVal = SI->getOperand(0); 14994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaEltTy = AI->getAllocatedType(); 15004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 15011aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner 15024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle tail padding by extending the operand 15034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits) 15044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcVal = new ZExtInst(SrcVal, 15054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SI->getContext(), AllocaSizeBits), 15064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", SI); 15074b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << '\n' << *SI 15094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner << '\n'); 15104b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // There are two forms here: AI could be an array or struct. Both cases 15124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // have different ways to compute the element offset. 15134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 15144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(EltSTy); 15154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 15174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Get the number of bits to shift SrcVal to get the value. 15184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *FieldTy = EltSTy->getElementType(i); 15194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift = Layout->getElementOffsetInBits(i); 15204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 15224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-Shift-TD->getTypeAllocSizeInBits(FieldTy); 15234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltVal = SrcVal; 15254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 15264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 15274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 15284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "sroa.store.elt", SI); 15294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncate down to an integer of the right size. 15324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 15334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 15354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits == 0) continue; 15364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits != AllocaSizeBits) 15384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = new TruncInst(EltVal, 15394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SI->getContext(), FieldSizeBits), 15404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", SI); 15414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *DestField = NewElts[i]; 15424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltVal->getType() == FieldTy) { 15434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing to an integer field of this size, just do it. 15444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (FieldTy->isFloatingPointTy() || FieldTy->isVectorTy()) { 15454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Bitcast to the right element type (for fp/vector values). 15464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = new BitCastInst(EltVal, FieldTy, "", SI); 15474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 15484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 15494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DestField = new BitCastInst(DestField, 15504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PointerType::getUnqual(EltVal->getType()), 15514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", SI); 15524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(EltVal, DestField, SI); 15544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15569d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 15574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *ATy = cast<ArrayType>(AllocaEltTy); 15584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ArrayEltTy = ATy->getElementType(); 15594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ElementOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 15604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy); 15614b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift; 15634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 15654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-ElementOffset; 15664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else 15674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = 0; 15684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 15704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 15714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ElementSizeBits == 0) continue; 15724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltVal = SrcVal; 15744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 15754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 15764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 15774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "sroa.store.elt", SI); 15784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncate down to an integer of the right size. 15814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ElementSizeBits != AllocaSizeBits) 15824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = new TruncInst(EltVal, 15834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SI->getContext(), 15844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementSizeBits),"",SI); 15854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *DestField = NewElts[i]; 15864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltVal->getType() == ArrayEltTy) { 15874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing to an integer field of this size, just do it. 15884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ArrayEltTy->isFloatingPointTy() || 15894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ArrayEltTy->isVectorTy()) { 15904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Bitcast to the right element type (for fp/vector values). 15914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI); 15924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 15934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 15944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DestField = new BitCastInst(DestField, 15954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PointerType::getUnqual(EltVal->getType()), 15964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", SI); 15974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(EltVal, DestField, SI); 15994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 16014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift -= ElementOffset; 16024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else 16034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift += ElementOffset; 16044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1605800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 16064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(SI); 1608800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1609800de31776356910eb877e71df9f32b0a6215324Chris Lattner 16104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteLoadUserOfWholeAlloca - We found a load of the entire allocation to 16114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// an integer. Load the individual pieces to form the aggregate value. 16124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 16134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 16144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Extract each element out of the NewElts according to its structure offset 16154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // and form the result value. 16164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaEltTy = AI->getAllocatedType(); 16174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 16184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << '\n' << *LI 16204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner << '\n'); 16214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // There are two forms here: AI could be an array or struct. Both cases 16234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // have different ways to compute the element offset. 16244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = 0; 16254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ArrayEltBitOffset = 0; 16264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 16274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Layout = TD->getStructLayout(EltSTy); 16284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 16294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType(); 16304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ArrayEltBitOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 16314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 16324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ResultVal = 16344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant::getNullValue(IntegerType::get(LI->getContext(), AllocaSizeBits)); 16354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 16374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Load the value from the alloca. If the NewElt is an aggregate, cast 16384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the pointer to an integer of the same size before doing the load. 16394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcField = NewElts[i]; 16404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *FieldTy = 16414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner cast<PointerType>(SrcField->getType())->getElementType(); 16424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 164329e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 16454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits == 0) continue; 16464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const IntegerType *FieldIntTy = IntegerType::get(LI->getContext(), 16484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FieldSizeBits); 16494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!FieldTy->isIntegerTy() && !FieldTy->isFloatingPointTy() && 16504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner !FieldTy->isVectorTy()) 16514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new BitCastInst(SrcField, 16524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PointerType::getUnqual(FieldIntTy), 16534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", LI); 16544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new LoadInst(SrcField, "sroa.load.elt", LI); 165529e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SrcField is a fp or vector of the right size but that isn't an 16574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integer type, bitcast to an integer so we can shift it. 16584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcField->getType() != FieldIntTy) 16594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI); 166029e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero extend the field to be the same size as the final alloca so that 16624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // we can shift and insert it. 16634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcField->getType() != ResultVal->getType()) 16644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI); 166529e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Determine the number of bits to shift SrcField. 16674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift; 16684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Layout) // Struct case. 16694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = Layout->getElementOffsetInBits(i); 16704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else // Array case. 16714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = i*ArrayEltBitOffset; 167229e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 16744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth(); 16754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 16774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift); 16784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI); 16799b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 16804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16811495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner // Don't create an 'or x, 0' on the first iteration. 16821495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner if (!isa<Constant>(ResultVal) || 16831495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner !cast<Constant>(ResultVal)->isNullValue()) 16841495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI); 16851495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner else 16861495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner ResultVal = SrcField; 16879b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 16884b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle tail padding by truncating the result 16904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits) 16914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI); 16924b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(ResultVal); 16944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(LI); 16954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 16964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// HasPadding - Return true if the specified type has any structure or 16984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// alignment padding, false otherwise. 16994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerstatic bool HasPadding(const Type *Ty, const TargetData &TD) { 170091abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) 170191abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner return HasPadding(ATy->getElementType(), TD); 170291abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 170391abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(Ty)) 170491abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner return HasPadding(VTy->getElementType(), TD); 170591abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 17064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *STy = dyn_cast<StructType>(Ty)) { 17074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *SL = TD.getStructLayout(STy); 17084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned PrevFieldBitOffset = 0; 17094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 17104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned FieldBitOffset = SL->getElementOffsetInBits(i); 17114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Padding in sub-elements? 17134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (HasPadding(STy->getElementType(i), TD)) 17144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 17154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check to see if there is any padding between this element and the 17174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // previous one. 17184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (i) { 17194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned PrevFieldEnd = 17204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1)); 17214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (PrevFieldEnd < FieldBitOffset) 17224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 17234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PrevFieldBitOffset = FieldBitOffset; 17267809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 17274b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check for tail padding. 17294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (unsigned EltCount = STy->getNumElements()) { 17304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned PrevFieldEnd = PrevFieldBitOffset + 17314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD.getTypeSizeInBits(STy->getElementType(EltCount-1)); 17324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (PrevFieldEnd < SL->getSizeInBits()) 17334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 17344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17352e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 173691abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 17374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty); 17384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 17394b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 17414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 17424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or 1 if safe after canonicalization has been performed. 17434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::isSafeAllocaToScalarRepl(AllocaInst *AI) { 17444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Loop over the use list of the alloca. We can only transform it if all of 17454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the users are safe to transform. 17464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInfo Info; 17474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeForScalarRepl(AI, AI, 0, Info); 17494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isUnsafe) { 17504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Cannot transform: " << *AI << '\n'); 17514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 1752800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 17534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Okay, we know all the users are promotable. If the aggregate is a memcpy 17554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // source and destination, we have to be careful. In particular, the memcpy 17564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // could be moving around elements that live in structure padding of the LLVM 17574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // types, but may actually be used. In these cases, we refuse to promote the 17584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // struct. 17594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isMemCpySrc && Info.isMemCpyDst && 17604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner HasPadding(AI->getAllocatedType(), *TD)) 17614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 17624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 1764800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1765800de31776356910eb877e71df9f32b0a6215324Chris Lattner 1766800de31776356910eb877e71df9f32b0a6215324Chris Lattner 176779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 176879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// PointsToConstantGlobal - Return true if V (possibly indirectly) points to 176979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// some part of a constant global variable. This intentionally only accepts 177079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// constant expressions because we don't can't rewrite arbitrary instructions. 177179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool PointsToConstantGlobal(Value *V) { 177279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 177379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return GV->isConstant(); 177479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 177579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (CE->getOpcode() == Instruction::BitCast || 177679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner CE->getOpcode() == Instruction::GetElementPtr) 177779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return PointsToConstantGlobal(CE->getOperand(0)); 177879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 177979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 178079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 178179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) 178279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// pointer to an alloca. Ignore any reads of the pointer, return false if we 178379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// see any stores or other unknown uses. If we see pointer arithmetic, keep 178479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// track of whether it moves the pointer (with isOffset) but otherwise traverse 178579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to 1786081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky/// the alloca, and if the source pointer is a pointer to a constant global, we 178779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// can optimize this. 178831d80103d56c026403d7fb6c50833664ff63ddcbChris Lattnerstatic bool isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy, 178979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner bool isOffset) { 179079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 17918a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif User *U = cast<Instruction>(*UI); 17928a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif 17932e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 17946e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // Ignore non-volatile loads, they are always ok. 17952e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (LI->isVolatile()) return false; 17962e61849f45144f2f05d57b00947df7e101610694Chris Lattner continue; 17972e61849f45144f2f05d57b00947df7e101610694Chris Lattner } 17986e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 17998a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { 180079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If uses of the bitcast are ok, we are ok. 180179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset)) 180279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 180379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 180479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 18058a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 180679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the GEP has all zero indices, it doesn't offset the pointer. If it 180779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // doesn't, it does. 180879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy, 180979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner isOffset || !GEP->hasAllZeroIndices())) 181079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 181179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 181279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 181379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 18146248065194778c866164b0c10f09f0f0d91b91acChris Lattner if (CallSite CS = U) { 18156248065194778c866164b0c10f09f0f0d91b91acChris Lattner // If this is a readonly/readnone call site, then we know it is just a 18166248065194778c866164b0c10f09f0f0d91b91acChris Lattner // load and we can ignore it. 1817a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner if (CS.onlyReadsMemory()) 1818a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner continue; 1819081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky 1820081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky // If this is the function being called then we treat it like a load and 1821081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky // ignore it. 1822081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky if (CS.isCallee(UI)) 1823081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky continue; 18246248065194778c866164b0c10f09f0f0d91b91acChris Lattner 18256248065194778c866164b0c10f09f0f0d91b91acChris Lattner // If this is being passed as a byval argument, the caller is making a 18266248065194778c866164b0c10f09f0f0d91b91acChris Lattner // copy, so it is only a read of the alloca. 18276248065194778c866164b0c10f09f0f0d91b91acChris Lattner unsigned ArgNo = CS.getArgumentNo(UI); 18286248065194778c866164b0c10f09f0f0d91b91acChris Lattner if (CS.paramHasAttr(ArgNo+1, Attribute::ByVal)) 18296248065194778c866164b0c10f09f0f0d91b91acChris Lattner continue; 18306248065194778c866164b0c10f09f0f0d91b91acChris Lattner } 1831a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner 183279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If this is isn't our memcpy/memmove, reject it as something we can't 183379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // handle. 183431d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner MemTransferInst *MI = dyn_cast<MemTransferInst>(U); 183531d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner if (MI == 0) 183679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 18372e61849f45144f2f05d57b00947df7e101610694Chris Lattner 18382e61849f45144f2f05d57b00947df7e101610694Chris Lattner // If the transfer is using the alloca as a source of the transfer, then 18392e29ebd9e8efefe3ff926aa99cf2e5323665998eChris Lattner // ignore it since it is a load (unless the transfer is volatile). 18402e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (UI.getOperandNo() == 1) { 18412e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (MI->isVolatile()) return false; 18422e61849f45144f2f05d57b00947df7e101610694Chris Lattner continue; 18432e61849f45144f2f05d57b00947df7e101610694Chris Lattner } 184479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 184579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If we already have seen a copy, reject the second one. 184679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (TheCopy) return false; 184779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 184879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the pointer has been offset from the start of the alloca, we can't 184979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // safely handle this. 185079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (isOffset) return false; 185179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 185279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the memintrinsic isn't using the alloca as the dest, reject it. 1853a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif if (UI.getOperandNo() != 0) return false; 185479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 185579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the source of the memcpy/move is not a constant global, reject it. 185631d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner if (!PointsToConstantGlobal(MI->getSource())) 185779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 185879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 185979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Otherwise, the transform is safe. Remember the copy instruction. 186079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner TheCopy = MI; 186179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 186279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return true; 186379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 186479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 186579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only 186679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// modified by a copy from a constant global. If we can prove this, we can 186779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// replace any uses of the alloca with uses of the global directly. 186831d80103d56c026403d7fb6c50833664ff63ddcbChris LattnerMemTransferInst *SROA::isOnlyCopiedFromConstantGlobal(AllocaInst *AI) { 186931d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner MemTransferInst *TheCopy = 0; 187079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false)) 187179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return TheCopy; 187279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return 0; 187379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 1874