ScalarReplAggregates.cpp revision 61db1f56d0b717d67557bbb2a9d83af1449458cb
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" 345034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman#include "llvm/Analysis/ValueTracking.h" 3538aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Target/TargetData.h" 3638aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 374afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel#include "llvm/Transforms/Utils/Local.h" 38a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner#include "llvm/Support/CallSite.h" 399525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Debug.h" 407d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 41a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 4265a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner#include "llvm/Support/IRBuilder.h" 43a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/MathExtras.h" 44bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 451ccd185cb49d81465a2901622e58ceae046d1d83Chris Lattner#include "llvm/ADT/SmallVector.h" 46551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 47d8664730942beb911327336d1f9db8e7efcd6813Chris Lattnerusing namespace llvm; 48d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 490e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of allocas broken up"); 500e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted, "Number of allocas promoted"); 510e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumConverted, "Number of aggregates converted to scalar"); 5279b3bd395dc3303cde65e18e0524ed2f70268c99Chris LattnerSTATISTIC(NumGlobals, "Number of allocas copied from constant global"); 53ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 540e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 553e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct SROA : public FunctionPass { 56ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 5790c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson explicit SROA(signed T = -1) : FunctionPass(ID) { 58081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeSROAPass(*PassRegistry::getPassRegistry()); 59ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel if (T == -1) 60b0e71edb6b33f822e001500dac90acf95faacea8Chris Lattner SRThreshold = 128; 61ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel else 62ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel SRThreshold = T; 63ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel } 64794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 65ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 66ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 6738aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performScalarRepl(Function &F); 6838aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performPromotion(Function &F); 6938aec325604635380421a27e39ab06d55ed2458dChris Lattner 70a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 71a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // will not alter the CFG, so say so. 72a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 73326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel AU.addRequired<DominatorTree>(); 7438aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<DominanceFrontier>(); 75a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner AU.setPreservesCFG(); 76a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner } 77a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner 78ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 7956c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner TargetData *TD; 8056c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner 81b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson /// DeadInsts - Keep track of instructions we have made dead, so that 82b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson /// we can remove them after we are done working. 83b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<Value*, 32> DeadInsts; 84b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 8539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// AllocaInfo - When analyzing uses of an alloca instruction, this captures 8639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// information about the uses. All these fields are initialized to false 8739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// and set to true when something is learned. 8839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner struct AllocaInfo { 8939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isUnsafe - This is set to true if the alloca cannot be SROA'd. 9039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isUnsafe : 1; 9139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isMemCpySrc - This is true if this aggregate is memcpy'd from. 9339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpySrc : 1; 9439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9533b0b8d242de8d428f11e77ea734a08b47797216Zhou Sheng /// isMemCpyDst - This is true if this aggregate is memcpy'd into. 9639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpyDst : 1; 9739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo() 996c146eefbf75875250af37a0f1ea70fc6b4716eeVictor Hernandez : isUnsafe(false), isMemCpySrc(false), isMemCpyDst(false) {} 10039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner }; 10139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 102ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel unsigned SRThreshold; 103ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel 10439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; } 10539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1066c146eefbf75875250af37a0f1ea70fc6b4716eeVictor Hernandez bool isSafeAllocaToScalarRepl(AllocaInst *AI); 10739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 108b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 1093c3af5d15569d708d2dc8f13351bc77056b4d70dBob Wilson AllocaInfo &Info); 110b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t &Offset, 1113c3af5d15569d708d2dc8f13351bc77056b4d70dBob Wilson AllocaInfo &Info); 1123c3af5d15569d708d2dc8f13351bc77056b4d70dBob Wilson void isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t MemSize, 1133c3af5d15569d708d2dc8f13351bc77056b4d70dBob Wilson const Type *MemOpType, bool isStore, AllocaInfo &Info); 114b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson bool TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size); 115e88728d757d3090f1c0885b78d3675a7e143a2f9Bob Wilson uint64_t FindElementAndOffset(const Type *&T, uint64_t &Offset, 116e88728d757d3090f1c0885b78d3675a7e143a2f9Bob Wilson const Type *&IdxTy); 11739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1187b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void DoScalarReplacement(AllocaInst *AI, 1197b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez std::vector<AllocaInst*> &WorkList); 120b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void DeleteDeadInstructions(); 1213126f1c02895a9d18a504a5ad4af9ef2029c0dcaChris Lattner 122b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 123b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 124b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 125b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 126b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 127b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 128b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 1297b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI, 130d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1317b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 132d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1337b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 1346e733d34ca487ab7ff8a6def018a933620393869Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 135d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 13631d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner static MemTransferInst *isOnlyCopiedFromConstantGlobal(AllocaInst *AI); 137ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 138ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 139ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 140844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar SROA::ID = 0; 1412ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(SROA, "scalarrepl", 1422ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Scalar Replacement of Aggregates", false, false) 1432ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 1442ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominanceFrontier) 1452ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(SROA, "scalarrepl", 146ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Scalar Replacement of Aggregates", false, false) 147844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 148d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the ScalarReplAggregates pass 149ff366850aa9956e167e78d4f5b57aae10d8c5779Devang PatelFunctionPass *llvm::createScalarReplAggregatesPass(signed int Threshold) { 150ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel return new SROA(Threshold); 151ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel} 152ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 153ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 1544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 1554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// Convert To Scalar Optimization. 1564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 157963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner 158c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattnernamespace { 159a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// ConvertToScalarInfo - This class implements the "Convert To Scalar" 160a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// optimization, which scans the uses of an alloca and determines if it can 161a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// rewrite it in terms of a single new alloca that can be mem2reg'd. 1624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerclass ConvertToScalarInfo { 163c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner /// AllocaSize - The size of the alloca being considered. 164c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner unsigned AllocaSize; 165593375d04ab32be0161607a741d310172f142b93Chris Lattner const TargetData &TD; 166c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 167a0bada729ffaa1bfc80ef25935bdc5a67432708fChris Lattner /// IsNotTrivial - This is set to true if there is some access to the object 168a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// which means that mem2reg can't promote it. 169c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner bool IsNotTrivial; 170a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 171a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// VectorTy - This tracks the type that we should promote the vector to if 172a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// it is possible to turn it into a vector. This starts out null, and if it 173a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// isn't possible to turn into a vector type, it gets set to VoidTy. 174c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner const Type *VectorTy; 175a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 176a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// HadAVector - True if there is at least one vector access to the alloca. 177a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// We don't want to turn random arrays into vectors and use vector element 178a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// insert/extract, but if there are element accesses to something that is 179a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// also declared as a vector, we do want to promote to a vector. 180c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner bool HadAVector; 181c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 1824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerpublic: 183593375d04ab32be0161607a741d310172f142b93Chris Lattner explicit ConvertToScalarInfo(unsigned Size, const TargetData &td) 184593375d04ab32be0161607a741d310172f142b93Chris Lattner : AllocaSize(Size), TD(td) { 185c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner IsNotTrivial = false; 186c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner VectorTy = 0; 187c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner HadAVector = false; 188c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner } 189c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 190a001b664988f759d194f3d5d880c61449219fc2eChris Lattner AllocaInst *TryConvert(AllocaInst *AI); 191593375d04ab32be0161607a741d310172f142b93Chris Lattner 1924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerprivate: 193593375d04ab32be0161607a741d310172f142b93Chris Lattner bool CanConvertToScalar(Value *V, uint64_t Offset); 194593375d04ab32be0161607a741d310172f142b93Chris Lattner void MergeInType(const Type *In, uint64_t Offset); 195593375d04ab32be0161607a741d310172f142b93Chris Lattner void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset); 196593375d04ab32be0161607a741d310172f142b93Chris Lattner 197593375d04ab32be0161607a741d310172f142b93Chris Lattner Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType, 198593375d04ab32be0161607a741d310172f142b93Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 199593375d04ab32be0161607a741d310172f142b93Chris Lattner Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal, 200593375d04ab32be0161607a741d310172f142b93Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 201c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner}; 202c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner} // end anonymous namespace. 203c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 20491abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 20591abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner/// IsVerbotenVectorType - Return true if this is a vector type ScalarRepl isn't 20691abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner/// allowed to form. We do this to avoid MMX types, which is a complete hack, 20791abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner/// but is required until the backend is fixed. 20872eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattnerstatic bool IsVerbotenVectorType(const VectorType *VTy, const Instruction *I) { 20972eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner StringRef Triple(I->getParent()->getParent()->getParent()->getTargetTriple()); 21072eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner if (!Triple.startswith("i386") && 21172eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner !Triple.startswith("x86_64")) 21272eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner return false; 21372eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner 21491abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner // Reject all the MMX vector types. 21591abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner switch (VTy->getNumElements()) { 21691abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner default: return false; 21791abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner case 1: return VTy->getElementType()->isIntegerTy(64); 21891abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner case 2: return VTy->getElementType()->isIntegerTy(32); 21991abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner case 4: return VTy->getElementType()->isIntegerTy(16); 22091abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner case 8: return VTy->getElementType()->isIntegerTy(8); 22191abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner } 22291abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner} 22391abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 22491abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 225a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// TryConvert - Analyze the specified alloca, and if it is safe to do so, 226a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// rewrite it to be a new alloca which is mem2reg'able. This returns the new 227a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// alloca if possible or null if not. 228a001b664988f759d194f3d5d880c61449219fc2eChris LattnerAllocaInst *ConvertToScalarInfo::TryConvert(AllocaInst *AI) { 229a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we can't convert this scalar, or if mem2reg can trivially do it, bail 230a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // out. 231a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (!CanConvertToScalar(AI, 0) || !IsNotTrivial) 232a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return 0; 233a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 234a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we were able to find a vector type that can handle this with 235a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // insert/extract elements, and if there was at least one use that had 236a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // a vector type, promote this to a vector. We don't want to promote 237a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // random stuff that doesn't use vectors (e.g. <9 x double>) because then 238a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // we just get a lot of insert/extracts. If at least one vector is 239a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // involved, then we probably really do have a union of vector/array. 240a001b664988f759d194f3d5d880c61449219fc2eChris Lattner const Type *NewTy; 24191abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner if (VectorTy && VectorTy->isVectorTy() && HadAVector && 24272eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner !IsVerbotenVectorType(cast<VectorType>(VectorTy), AI)) { 243a001b664988f759d194f3d5d880c61449219fc2eChris Lattner DEBUG(dbgs() << "CONVERT TO VECTOR: " << *AI << "\n TYPE = " 244a001b664988f759d194f3d5d880c61449219fc2eChris Lattner << *VectorTy << '\n'); 245a001b664988f759d194f3d5d880c61449219fc2eChris Lattner NewTy = VectorTy; // Use the vector type. 246a001b664988f759d194f3d5d880c61449219fc2eChris Lattner } else { 247a001b664988f759d194f3d5d880c61449219fc2eChris Lattner DEBUG(dbgs() << "CONVERT TO SCALAR INTEGER: " << *AI << "\n"); 248a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // Create and insert the integer alloca. 249a001b664988f759d194f3d5d880c61449219fc2eChris Lattner NewTy = IntegerType::get(AI->getContext(), AllocaSize*8); 250a001b664988f759d194f3d5d880c61449219fc2eChris Lattner } 251a001b664988f759d194f3d5d880c61449219fc2eChris Lattner AllocaInst *NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin()); 252a001b664988f759d194f3d5d880c61449219fc2eChris Lattner ConvertUsesToScalar(AI, NewAI, 0); 253a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return NewAI; 254a001b664988f759d194f3d5d880c61449219fc2eChris Lattner} 255a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 256a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// MergeInType - Add the 'In' type to the accumulated vector type (VectorTy) 257a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// so far at the offset specified by Offset (which is specified in bytes). 2584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 2594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// There are two cases we handle here: 2604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 1) A union of vector types of the same size and potentially its elements. 2614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Here we turn element accesses into insert/extract element operations. 2624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This promotes a <4 x float> with a store of float to the third element 2634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// into a <4 x float> that uses insert element. 2644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 2) A fully general blob of memory, which we turn into some (potentially 2654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// large) integer type with extract and insert operations where the loads 266a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// and stores would mutate the memory. We mark this by setting VectorTy 267a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// to VoidTy. 2684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid ConvertToScalarInfo::MergeInType(const Type *In, uint64_t Offset) { 269a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we already decided to turn this into a blob of integer memory, there is 270a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // nothing to be done. 2714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy && VectorTy->isVoidTy()) 2724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 2734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 2744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this could be contributing to a vector, analyze it. 275c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 2764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the In type is a vector that is the same size as the alloca, see if it 2774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // matches the existing VecTy. 2784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VInTy = dyn_cast<VectorType>(In)) { 279a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // Remember if we saw a vector type. 280a001b664988f759d194f3d5d880c61449219fc2eChris Lattner HadAVector = true; 281a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 2824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) { 2834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we're storing/loading a vector of the right size, allow it as a 2844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // vector. If this the first vector we see, remember the type so that 285a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // we know the element size. If this is a subsequent access, ignore it 286a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // even if it is a differing type but the same size. Worst case we can 287a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // bitcast the resultant vectors. 2884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy == 0) 2894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = VInTy; 2904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 2914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 2924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (In->isFloatTy() || In->isDoubleTy() || 2934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner (In->isIntegerTy() && In->getPrimitiveSizeInBits() >= 8 && 2944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isPowerOf2_32(In->getPrimitiveSizeInBits()))) { 2954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we're accessing something that could be an element of a vector, see 2964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // if the implied vector agrees with what we already have and if Offset is 2974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // compatible with it. 2984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = In->getPrimitiveSizeInBits()/8; 2994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset % EltSize == 0 && AllocaSize % EltSize == 0 && 3004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner (VectorTy == 0 || 3014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner cast<VectorType>(VectorTy)->getElementType() 3024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ->getPrimitiveSizeInBits()/8 == EltSize)) { 3034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy == 0) 3044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = VectorType::get(In, AllocaSize/EltSize); 3054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 3064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 3074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 3084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 3094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, we have a case that we can't handle with an optimized vector 3104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // form. We can still turn this into a large integer. 3114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = Type::getVoidTy(In->getContext()); 3124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 313c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 3144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// CanConvertToScalar - V is a pointer. If we can convert the pointee and all 3154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// its accesses to a single vector type, return true and set VecTy to 3164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the new type. If we could convert the alloca into a single promotable 3174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer, return true but set VecTy to VoidTy. Further, if the use is not a 3184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// completely trivial use that mem2reg could promote, set IsNotTrivial. Offset 3194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// is the current offset from the base of the alloca being analyzed. 3204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 3214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// If we see at least one access to the value that is as a vector type, set the 3224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// SawVec flag. 3234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool ConvertToScalarInfo::CanConvertToScalar(Value *V, uint64_t Offset) { 3244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 3254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(*UI); 326a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 3274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 3284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Don't break volatile loads. 3294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LI->isVolatile()) 3304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3310488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen // Don't touch MMX operations. 3320488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen if (LI->getType()->isX86_MMXTy()) 3330488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen return false; 3344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MergeInType(LI->getType(), Offset); 335add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner continue; 336add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner } 3377809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 3384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 3394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing the pointer, not into the value? 3404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SI->getOperand(0) == V || SI->isVolatile()) return false; 3410488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen // Don't touch MMX operations. 3420488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen if (SI->getOperand(0)->getType()->isX86_MMXTy()) 3430488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen return false; 3444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MergeInType(SI->getOperand(0)->getType(), Offset); 3457809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 3467809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 347add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner 3484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { 349a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 3504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!CanConvertToScalar(BCI, Offset)) 3514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3523992feb075b27ff37b63017078a977206f97d10dBob Wilson continue; 3533992feb075b27ff37b63017078a977206f97d10dBob Wilson } 3543992feb075b27ff37b63017078a977206f97d10dBob Wilson 3554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 3564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a GEP with a variable indices, we can't handle it. 3574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!GEP->hasAllConstantIndices()) 3584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 3604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset that this GEP adds to the pointer. 3614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 3624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(), 3634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 3644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // See if all uses can be converted. 3654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!CanConvertToScalar(GEP, Offset+GEPOffset)) 3664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 367a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 3687809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 3694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 370ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 3714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 3724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // handle it. 3734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 3744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Store of constant value and constant size. 375a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (!isa<ConstantInt>(MSI->getValue()) || 376a001b664988f759d194f3d5d880c61449219fc2eChris Lattner !isa<ConstantInt>(MSI->getLength())) 377a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return false; 378a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 379a001b664988f759d194f3d5d880c61449219fc2eChris Lattner continue; 3804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 381fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 3834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // can handle it like a load or store of the scalar type. 3844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 385a001b664988f759d194f3d5d880c61449219fc2eChris Lattner ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength()); 386a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (Len == 0 || Len->getZExtValue() != AllocaSize || Offset != 0) 387a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return false; 388a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 389a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 390a001b664988f759d194f3d5d880c61449219fc2eChris Lattner continue; 391ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 3924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 3934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, we cannot handle this! 3944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 395a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 3964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 3974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 398ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 399a59adc40153f3e0f9843952c127d179b5ebe6c4cChris Lattner 4004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 4014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// directly. This happens when we are converting an "integer union" to a 4024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// single integer scalar, or when we are converting a "vector union" to a 4034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// vector with insert/extractelement instructions. 4044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 4054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 4064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. By the end of this, there should be no uses of Ptr. 4074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid ConvertToScalarInfo::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, 4084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset) { 4094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!Ptr->use_empty()) { 4104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(Ptr->use_back()); 411b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 4124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) { 4134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertUsesToScalar(CI, NewAI, Offset); 4144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner CI->eraseFromParent(); 4154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 417b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 4184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 4194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset that this GEP adds to the pointer. 4204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 4214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(), 4224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 4234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8); 4244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner GEP->eraseFromParent(); 4254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 427b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 42861db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner IRBuilder<> Builder(User); 4294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 4314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The load is a bit extract from NewAI shifted right by Offset bits. 4324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp"); 4334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *NewLoadVal 4344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder); 4354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(NewLoadVal); 4364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->eraseFromParent(); 4374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 4414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(SI->getOperand(0) != Ptr && "Consistency error!"); 4424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in"); 4434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset, 4444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 4454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(New, NewAI); 4464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SI->eraseFromParent(); 4474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load we just inserted is now dead, then the inserted store 4494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // overwrote the entire thing. 4504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Old->use_empty()) 4514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old->eraseFromParent(); 4524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 4564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // transform it into a store of the expanded constant value. 4574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 4584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MSI->getRawDest() == Ptr && "Consistency error!"); 4594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 4604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (NumBytes != 0) { 4614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue(); 4624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the value replicated the right number of times. 4644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt APVal(NumBytes*8, Val); 4652674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 4664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Splat the value if non-zero. 4674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val) 4684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 1; i != NumBytes; ++i) 4694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APVal |= APVal << 8; 4704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in"); 4724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *New = ConvertScalar_InsertValue( 4734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(User->getContext(), APVal), 4744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old, Offset, Builder); 4754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(New, NewAI); 4764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load we just inserted is now dead, then the memset overwrote 4784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the entire thing. 4794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Old->use_empty()) 4804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old->eraseFromParent(); 4814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MSI->eraseFromParent(); 4834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 484b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 485fca55c8ac7d12e4139ad0ab7d74b76c47935aef6Daniel Dunbar 4864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 4874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // can handle it like a load or store of the scalar type. 4884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 4894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(Offset == 0 && "must be store to start of alloca"); 4904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the source and destination are both to the same alloca, then this is 4924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // a noop copy-to-self, just delete it. Otherwise, emit a load and store 4934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // as appropriate. 4945034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman AllocaInst *OrigAI = cast<AllocaInst>(GetUnderlyingObject(Ptr, 0)); 4954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 4965034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman if (GetUnderlyingObject(MTI->getSource(), 0) != OrigAI) { 4974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Dest must be OrigAI, change this to be a load from the original 4984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // pointer (bitcasted), then a store to our new alloca. 4994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?"); 5004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcPtr = MTI->getSource(); 501e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang const PointerType* SPTy = cast<PointerType>(SrcPtr->getType()); 502e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang const PointerType* AIPTy = cast<PointerType>(NewAI->getType()); 503e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang if (SPTy->getAddressSpace() != AIPTy->getAddressSpace()) { 504e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang AIPTy = PointerType::get(AIPTy->getElementType(), 505e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang SPTy->getAddressSpace()); 506e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang } 507e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang SrcPtr = Builder.CreateBitCast(SrcPtr, AIPTy); 508e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang 5094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval"); 5104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcVal->setAlignment(MTI->getAlignment()); 5114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(SrcVal, NewAI); 5125034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } else if (GetUnderlyingObject(MTI->getDest(), 0) != OrigAI) { 5134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Src must be OrigAI, change this to be a load from NewAI then a store 5144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // through the original dest pointer (bitcasted). 5154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?"); 5164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval"); 517b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 518e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang const PointerType* DPTy = cast<PointerType>(MTI->getDest()->getType()); 519e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang const PointerType* AIPTy = cast<PointerType>(NewAI->getType()); 520e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang if (DPTy->getAddressSpace() != AIPTy->getAddressSpace()) { 521e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang AIPTy = PointerType::get(AIPTy->getElementType(), 522e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang DPTy->getAddressSpace()); 523e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang } 524e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), AIPTy); 525e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang 5264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr); 5274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewStore->setAlignment(MTI->getAlignment()); 5284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 5294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Noop transfer. Src == Dst 5304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5315fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 5324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MTI->eraseFromParent(); 5334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 5344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner llvm_unreachable("Unsupported operation!"); 53788e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner } 5382674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar} 5392674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 5404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer 5414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or vector value FromVal, extracting the bits from the offset specified by 5424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset. This returns the value, which is of type ToType. 5434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 5444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This happens when we are converting an "integer union" to a single 5454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer scalar, or when we are converting a "vector union" to a vector with 5464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// insert/extractelement instructions. 5474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 5484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 5494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. 5504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerValue *ConvertToScalarInfo:: 5514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerConvertScalar_ExtractValue(Value *FromVal, const Type *ToType, 5524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset, IRBuilder<> &Builder) { 5534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load is of the whole new alloca, no conversion is needed. 5544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FromVal->getType() == ToType && Offset == 0) 5554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return FromVal; 5564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the result alloca is a vector type, this is either an element 5584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // access or a bitcast to another vector type of the same size. 5594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) { 5604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ToType->isVectorTy()) 5614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Builder.CreateBitCast(FromVal, ToType, "tmp"); 5624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise it must be an element access. 5644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Elt = 0; 5654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset) { 5664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType()); 5674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Elt = Offset/EltSize; 5684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(EltSize*Elt == Offset && "Invalid modulus in validity checking"); 569b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 5704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Return the element extracted out of it. 5714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *V = Builder.CreateExtractElement(FromVal, ConstantInt::get( 5724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Type::getInt32Ty(FromVal->getContext()), Elt), "tmp"); 5734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (V->getType() != ToType) 5744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner V = Builder.CreateBitCast(V, ToType, "tmp"); 5754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return V; 5764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If ToType is a first class aggregate, extract out each of the pieces and 5794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // use insertvalue's to form the FCA. 5804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(ToType)) { 5814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout &Layout = *TD.getStructLayout(ST); 5824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Res = UndefValue::get(ST); 5834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 5844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i), 5854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+Layout.getElementOffsetInBits(i), 5864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 5874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 5884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Res; 5904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(ToType)) { 5934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType()); 5944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Res = UndefValue::get(AT); 5954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 5964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(), 5974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+i*EltSize, Builder); 5984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 5994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 6004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Res; 601b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 6022674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 6034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, this must be a union that was converted to an integer value. 6044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const IntegerType *NTy = cast<IntegerType>(FromVal->getType()); 605b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 6064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a big-endian system and the load is narrower than the 6074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // full alloca type, we need to do a shift to get the right bits. 6084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner int ShAmt = 0; 6094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD.isBigEndian()) { 6104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 6114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 6124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integers with a bitwidth that is not a multiple of 8. 6134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = TD.getTypeStoreSizeInBits(NTy) - 6144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD.getTypeStoreSizeInBits(ToType) - Offset; 615b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 6164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = Offset; 617b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 618b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 6194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Note: we support negative bitwidths (with shl) which are not defined. 6204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // We do this to support (f.e.) loads off the end of a structure where 6214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // only some bits are used. 6224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth()) 6234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateLShr(FromVal, 6244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(FromVal->getType(), 6254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt), "tmp"); 6264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth()) 6274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateShl(FromVal, 6284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(FromVal->getType(), 6294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner -ShAmt), "tmp"); 630b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 6314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Finally, unconditionally truncate the integer to the right width. 6324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned LIBitWidth = TD.getTypeSizeInBits(ToType); 6334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LIBitWidth < NTy->getBitWidth()) 6344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = 6354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateTrunc(FromVal, IntegerType::get(FromVal->getContext(), 6364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LIBitWidth), "tmp"); 6374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (LIBitWidth > NTy->getBitWidth()) 6384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = 6394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateZExt(FromVal, IntegerType::get(FromVal->getContext(), 6404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LIBitWidth), "tmp"); 6414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the result is an integer, this is a trunc or bitcast. 6434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ToType->isIntegerTy()) { 6444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Should be done. 6454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ToType->isFloatingPointTy() || ToType->isVectorTy()) { 6464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Just do a bitcast, we know the sizes match up. 6474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp"); 6484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 6494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise must be a pointer. 6504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp"); 651372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 6524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(FromVal->getType() == ToType && "Didn't convert right?"); 6534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return FromVal; 654372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 655372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 6564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer 6574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or vector value "Old" at the offset specified by Offset. 6584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 6594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This happens when we are converting an "integer union" to a 6604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// single integer scalar, or when we are converting a "vector union" to a 6614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// vector with insert/extractelement instructions. 6624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 6634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 6644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. 6654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerValue *ConvertToScalarInfo:: 6664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerConvertScalar_InsertValue(Value *SV, Value *Old, 6674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset, IRBuilder<> &Builder) { 6684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Convert the stored type to the actual type, shift it left to insert 6694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // then 'or' into place. 6704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaType = Old->getType(); 6714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LLVMContext &Context = Old->getContext(); 6722674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 6734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(AllocaType)) { 6744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t VecSize = TD.getTypeAllocSizeInBits(VTy); 6754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ValSize = TD.getTypeAllocSizeInBits(SV->getType()); 6764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Changing the whole vector with memset or with an access of a different 6784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // vector type? 6794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ValSize == VecSize) 6804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Builder.CreateBitCast(SV, AllocaType, "tmp"); 6812674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 6824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType()); 6834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Must be an element insertion. 6854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Elt = Offset/EltSize; 6864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType() != VTy->getElementType()) 6884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp"); 6894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateInsertElement(Old, SV, 6914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(Type::getInt32Ty(SV->getContext()), Elt), 6924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "tmp"); 6934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return SV; 694b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 6954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SV is a first-class aggregate value, insert each value recursively. 6974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(SV->getType())) { 6984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout &Layout = *TD.getStructLayout(ST); 6994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 7004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 7014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old = ConvertScalar_InsertValue(Elt, Old, 7024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+Layout.getElementOffsetInBits(i), 7034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 7044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Old; 7064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) { 7094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType()); 7104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 7114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 7124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder); 7134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Old; 7154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SV is a float, convert it to the appropriate integer type. 7184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If it is a pointer, do the same. 7194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned SrcWidth = TD.getTypeSizeInBits(SV->getType()); 7204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned DestWidth = TD.getTypeSizeInBits(AllocaType); 7214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned SrcStoreWidth = TD.getTypeStoreSizeInBits(SV->getType()); 7224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned DestStoreWidth = TD.getTypeStoreSizeInBits(AllocaType); 7234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType()->isFloatingPointTy() || SV->getType()->isVectorTy()) 7244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateBitCast(SV, 7254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SV->getContext(),SrcWidth), "tmp"); 7264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (SV->getType()->isPointerTy()) 7274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreatePtrToInt(SV, TD.getIntPtrType(SV->getContext()), "tmp"); 7284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero extend or truncate the value if needed. 7304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType() != AllocaType) { 7314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType()->getPrimitiveSizeInBits() < 7324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaType->getPrimitiveSizeInBits()) 7334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateZExt(SV, AllocaType, "tmp"); 7344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else { 7354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncation may be needed if storing more than the alloca can hold 7364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (undefined behavior). 7374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateTrunc(SV, AllocaType, "tmp"); 7384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcWidth = DestWidth; 7394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcStoreWidth = DestStoreWidth; 7404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a big-endian system and the store is narrower than the 7444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // full alloca type, we need to do a shift to get the right bits. 7454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner int ShAmt = 0; 7464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD.isBigEndian()) { 7474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 7484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 7494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integers with a bitwidth that is not a multiple of 8. 7504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = DestStoreWidth - SrcStoreWidth - Offset; 7514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 7524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = Offset; 7534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Note: we support negative bitwidths (with shr) which are not defined. 7564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // We do this to support (f.e.) stores off the end of a structure where 7574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // only some bits in the structure are set. 7584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth)); 7594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) { 7604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(), 7614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt), "tmp"); 7624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Mask <<= ShAmt; 7634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) { 7644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(), 7654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner -ShAmt), "tmp"); 7664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Mask = Mask.lshr(-ShAmt); 7674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Mask out the bits we are about to insert from the old value, and or 7704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // in the new bits. 7714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcWidth != DestWidth) { 7724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(DestWidth > SrcWidth); 7734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old = Builder.CreateAnd(Old, ConstantInt::get(Context, ~Mask), "mask"); 7744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateOr(Old, SV, "ins"); 7754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return SV; 777b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson} 778b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 779b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 7814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// SRoA Driver 7824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 783b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 784b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::runOnFunction(Function &F) { 7864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD = getAnalysisIfAvailable<TargetData>(); 787b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = performPromotion(F); 789b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 7904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // FIXME: ScalarRepl currently depends on TargetData more than it 7914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // theoretically needs to. It should be refactored in order to support 7924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // target-independent IR. Until this is done, just skip the actual 7934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // scalar-replacement portion of this pass. 7944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!TD) return Changed; 7954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (1) { 7974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool LocalChange = performScalarRepl(F); 7984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!LocalChange) break; // No need to repromote if no scalarrepl 7994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 8004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LocalChange = performPromotion(F); 8014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!LocalChange) break; // No need to re-scalarrepl if no promotion 8022674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar } 8034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 805d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner} 806d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 80778c50b8cd68d266d4ed6f8eca443cf8142a01204Bob Wilson 8084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::performPromotion(Function &F) { 8094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> Allocas; 8104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 8114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); 812b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 8134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 814372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 8154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = false; 8164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (1) { 8184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Allocas.clear(); 8194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Find allocas that are safe to promote, by looking at all instructions in 8214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the entry node 8224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 8234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 8244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isAllocaPromotable(AI)) 8254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Allocas.push_back(AI); 8264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Allocas.empty()) break; 8284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PromoteMemToReg(Allocas, DT, DF); 8304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NumPromoted += Allocas.size(); 8314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 8324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 8334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 8354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 8364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ShouldAttemptScalarRepl - Decide if an alloca is a good candidate for 8394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// SROA. It must be a struct or array type with a small number of elements. 8404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerstatic bool ShouldAttemptScalarRepl(AllocaInst *AI) { 8414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *T = AI->getAllocatedType(); 8424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote any struct into more than 32 separate vars. 8434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) 8444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return ST->getNumElements() <= 32; 8454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Arrays are much less likely to be safe for SROA; only consider 8464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // them if they are very small. 8474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(T)) 8484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return AT->getNumElements() <= 8; 8494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 8504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 8514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// performScalarRepl - This algorithm is a simple worklist driven algorithm, 8544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// which runs on all of the malloc/alloca instructions in the function, removing 8554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// them if they are only used by getelementptr instructions. 8564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// 8574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::performScalarRepl(Function &F) { 8584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> WorkList; 8594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Scan the entry basic block, adding allocas to the worklist. 8614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BasicBlock &BB = F.getEntryBlock(); 8624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 8634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *A = dyn_cast<AllocaInst>(I)) 8644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(A); 8654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Process the worklist 8674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = false; 8684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!WorkList.empty()) { 8694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *AI = WorkList.back(); 8704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.pop_back(); 8714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle dead allocas trivially. These can be formed by SROA'ing arrays 8734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with unused elements. 8744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AI->use_empty()) { 8754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 8764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 8774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 878d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 8794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this alloca is impossible for us to promote, reject it early. 8814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized()) 8824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 883d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 8844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check to see if this allocation is only modified by a memcpy/memmove from 8854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // a constant global. If this is the case, we can change all users to use 8864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the constant global instead. This is commonly produced by the CFE by 8874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A' 8884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // is only subsequently read. 8894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) { 8904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Found alloca equal to global: " << *AI << '\n'); 8914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << " memcpy = " << *TheCopy << '\n'); 8924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *TheSrc = cast<Constant>(TheCopy->getSource()); 8934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType())); 8944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TheCopy->eraseFromParent(); // Don't mutate the global. 8954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 8964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ++NumGlobals; 8974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 8984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 8994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 900d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 9014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check to see if we can perform the core SROA transformation. We cannot 9024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // transform the allocation instruction if it is an array allocation 9034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (allocations OF arrays are ok though), and an allocation of a scalar 9044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // value cannot be decomposed at all. 9054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType()); 90644118f0e25c25fedda1ccdd6a72f072c0b5c96e7Dan Gohman 9074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote [0 x %struct]. 9084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaSize == 0) continue; 909c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 9104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote any struct whose size is too big. 9114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaSize > SRThreshold) continue; 912c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 9134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the alloca looks like a good candidate for scalar replacement, and if 9144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // all its users can be transformed, then split up the aggregate into its 9154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // separate elements. 9164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShouldAttemptScalarRepl(AI) && isSafeAllocaToScalarRepl(AI)) { 9174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DoScalarReplacement(AI, WorkList); 9184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 9194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 92020adc9dc4650313f017b27d9818eb2176238113dMon P Wang } 9214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we can turn this aggregate value (potentially with casts) into a 9234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // simple scalar value that can be mem2reg'd into a register value. 9244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // IsNotTrivial tracks whether this is something that mem2reg could have 9254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // promoted itself. If so, we don't want to transform it needlessly. Note 9264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // that we can't just check based on the type: the alloca may be of an i32 9274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // but that has pointer arithmetic to set byte 3 of it or something. 9284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *NewAI = 9294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertToScalarInfo((unsigned)AllocaSize, *TD).TryConvert(AI)) { 9304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewAI->takeName(AI); 9314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 9324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ++NumConverted; 9334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 9344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 9354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 936d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 9374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, couldn't process this alloca. 938372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 9394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 941372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 942d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl 9444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// predicate, do SROA now. 9454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::DoScalarReplacement(AllocaInst *AI, 9464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> &WorkList) { 9474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Found inst to SROA: " << *AI << '\n'); 9484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> ElementAllocas; 9494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 9504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 9514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 9524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 9534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getAlignment(), 9544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getName() + "." + Twine(i), AI); 9554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.push_back(NA); 9564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 9574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 9584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 9594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 9604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.reserve(AT->getNumElements()); 9614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ElTy = AT->getElementType(); 9624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 9634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), 9644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getName() + "." + Twine(i), AI); 9654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.push_back(NA); 9664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 9674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 9684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 969d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Now that we have created the new alloca instructions, rewrite all the 9714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // uses of the old alloca. 9724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(AI, AI, 0, ElementAllocas); 973d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Now erase any instructions that were made dead while rewriting the alloca. 9754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeleteDeadInstructions(); 9764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 9774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 978fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumReplaced; 9794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 9804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// DeleteDeadInstructions - Erase instructions on the DeadInstrs list, 9824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// recursively including all their operands that become trivially dead. 9834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::DeleteDeadInstructions() { 9844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!DeadInsts.empty()) { 9854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *I = cast<Instruction>(DeadInsts.pop_back_val()); 9864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 9874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 9884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Instruction *U = dyn_cast<Instruction>(*OI)) { 9894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero out the operand and see if it becomes trivially dead. 9904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (But, don't add allocas to the dead instruction list -- they are 9914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // already on the worklist and will be deleted separately.) 9924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner *OI = 0; 9934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isInstructionTriviallyDead(U) && !isa<AllocaInst>(U)) 9944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(U); 995d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 996d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 9974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner I->eraseFromParent(); 9984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 9994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 1000d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 10014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeForScalarRepl - Check if instruction I is a safe use with regard to 10024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// performing scalar replacement of alloca AI. The results are flagged in 10034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the Info parameter. Offset indicates the position within AI that is 10044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// referenced by this instruction. 10054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 10064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInfo &Info) { 10074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) { 10084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(*UI); 10094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 10114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeForScalarRepl(BC, AI, Offset, Info); 10124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 10134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = Offset; 10144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeGEP(GEPI, AI, GEPOffset, Info); 10154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!Info.isUnsafe) 10164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeForScalarRepl(GEPI, AI, GEPOffset, Info); 101719101c7585c191376d898e3e66e35acd9bd777c2Gabor Greif } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 10184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 10194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Length) 10204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeMemAccess(AI, Offset, Length->getZExtValue(), 0, 1021a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif UI.getOperandNo() == 0, Info); 10224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else 10234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 10244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 10254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!LI->isVolatile()) { 10264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *LIType = LI->getType(); 10274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeMemAccess(AI, Offset, TD->getTypeAllocSize(LIType), 10284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LIType, false, Info); 10294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else 10304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 10314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 10324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Store is ok if storing INTO the pointer, not storing the pointer 10334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!SI->isVolatile() && SI->getOperand(0) != I) { 10344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *SIType = SI->getOperand(0)->getType(); 10354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeMemAccess(AI, Offset, TD->getTypeAllocSize(SIType), 10364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SIType, true, Info); 10374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else 10384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 10394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 10404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(errs() << " Transformation preventing inst: " << *User << '\n'); 10414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 1042d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 10434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isUnsafe) return; 1044d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1045d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner} 1046d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 10474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeGEP - Check if a GEP instruction can be handled for scalar 10484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// replacement. It is safe when all the indices are constant, in-bounds 10494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// references, and when the resulting offset corresponds to an element within 10504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the alloca type. The results are flagged in the Info parameter. Upon 10514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// return, Offset is adjusted as specified by the GEP indices. 10524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI, 10534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t &Offset, AllocaInfo &Info) { 10544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner gep_type_iterator GEPIt = gep_type_begin(GEPI), E = gep_type_end(GEPI); 10554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GEPIt == E) 10564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 10575ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Walk through the GEP type indices, checking the types that this indexes 10594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // into. 10604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (; GEPIt != E; ++GEPIt) { 10614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore struct elements, no extra checking needed for these. 10624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if ((*GEPIt)->isStructTy()) 10634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 10645ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPIt.getOperand()); 10664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!IdxVal) 10674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return MarkUnsafe(Info); 10685ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 106941b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 10704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset due to this GEP and check if the alloca has a 10714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // component element at that offset. 10724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 10734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), 10744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 10754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!TypeHasComponent(AI->getAllocatedType(), Offset, 0)) 10764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MarkUnsafe(Info); 10774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 107841b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 10794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeMemAccess - Check if a load/store/memcpy operates on the entire AI 10804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// alloca or has an offset and size that corresponds to a component element 10814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// within it. The offset checked here may have been formed from a GEP with a 10824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// pointer bitcasted to a different type. 10834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t MemSize, 10844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *MemOpType, bool isStore, 10854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInfo &Info) { 10864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if this is a load/store of the entire alloca. 10874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset == 0 && MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) { 10884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool UsesAggregateType = (MemOpType == AI->getAllocatedType()); 10894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // This is safe for MemIntrinsics (where MemOpType is 0), integer types 10904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (which are essentially the same as the MemIntrinsics, especially with 10914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // regard to copying padding between elements), or references using the 10924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // aggregate type of the alloca. 10934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!MemOpType || MemOpType->isIntegerTy() || UsesAggregateType) { 10944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!UsesAggregateType) { 10954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isStore) 10964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Info.isMemCpyDst = true; 10974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else 10984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Info.isMemCpySrc = true; 10994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 11014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if the offset/size correspond to a component within the alloca type. 11044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *T = AI->getAllocatedType(); 11054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TypeHasComponent(T, Offset, MemSize)) 11064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 11074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 11084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return MarkUnsafe(Info); 11095ffe6acd577696a41932c7b82db06a04687e07baChris Lattner} 11105ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// TypeHasComponent - Return true if T has a component type with the 11124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// specified offset and size. If Size is zero, do not check the size. 11134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size) { 11144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *EltTy; 11154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize; 11164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) { 11174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(ST); 11184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltIdx = Layout->getElementContainingOffset(Offset); 11194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltTy = ST->getContainedType(EltIdx); 11204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltSize = TD->getTypeAllocSize(EltTy); 11214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Layout->getElementOffset(EltIdx); 11224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (const ArrayType *AT = dyn_cast<ArrayType>(T)) { 11234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltTy = AT->getElementType(); 11244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltSize = TD->getTypeAllocSize(EltTy); 11254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset >= AT->getNumElements() * EltSize) 11264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 11274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset %= EltSize; 11284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 11294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 11304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset == 0 && (Size == 0 || EltSize == Size)) 11324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 11334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if the component spans multiple elements. 11344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset + Size > EltSize) 11354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 11364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return TypeHasComponent(EltTy, Offset, Size); 11374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 11383cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 11394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteForScalarRepl - Alloca AI is being split into NewElts, so rewrite 11404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the instruction I, which references it, to use the separate elements. 11414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset indicates the position within AI that is referenced by this 11424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// instruction. 11434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 11444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 11454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) { 11464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(*UI); 11473cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 11484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 11494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteBitCast(BC, AI, Offset, NewElts); 11504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 11514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteGEP(GEPI, AI, Offset, NewElts); 11524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 11534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 11544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t MemSize = Length->getZExtValue(); 11554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset == 0 && 11564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) 11574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteMemIntrinUserOfAlloca(MI, I, AI, NewElts); 11584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise the intrinsic can only touch a single element and the 11594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // address operand will be updated, so nothing else needs to be done. 11604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 11614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *LIType = LI->getType(); 11624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LIType == AI->getAllocatedType()) { 11634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Replace: 11644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %res = load { i32, i32 }* %alloc 11654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with: 11664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %load.0 = load i32* %alloc.0 11674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0 11684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %load.1 = load i32* %alloc.1 11694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1 11704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (Also works for arrays instead of structs) 11714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Insert = UndefValue::get(LIType); 11724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 11734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Load = new LoadInst(NewElts[i], "load", LI); 11744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI); 11754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(Insert); 11774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(LI); 11784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (LIType->isIntegerTy() && 11794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(LIType) == 11804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(AI->getAllocatedType())) { 11814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a load of the entire alloca to an integer, rewrite it. 11824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteLoadUserOfWholeAlloca(LI, AI, NewElts); 11834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 11854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Val = SI->getOperand(0); 11864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *SIType = Val->getType(); 11874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SIType == AI->getAllocatedType()) { 11884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Replace: 11894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store { i32, i32 } %val, { i32, i32 }* %alloc 11904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with: 11914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %val.0 = extractvalue { i32, i32 } %val, 0 11924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store i32 %val.0, i32* %alloc.0 11934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %val.1 = extractvalue { i32, i32 } %val, 1 11944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store i32 %val.1, i32* %alloc.1 11954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (Also works for arrays instead of structs) 11964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 11974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI); 11984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Extract, NewElts[i], SI); 11994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 12004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(SI); 12014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (SIType->isIntegerTy() && 12024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(SIType) == 12034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(AI->getAllocatedType())) { 12044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a store of the entire alloca from an integer, rewrite it. 12054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteStoreUserOfWholeAlloca(SI, AI, NewElts); 120639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 120739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 12084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 12094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 12103cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 12114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteBitCast - Update a bitcast reference to the alloca being replaced 12124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// and recursively continue updating all of its uses. 12134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 12144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 12154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(BC, AI, Offset, NewElts); 12164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BC->getOperand(0) != AI) 12174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 121839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 12194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The bitcast references the original alloca. Replace its uses with 12204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // references to the first new element alloca. 12214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Val = NewElts[0]; 12224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val->getType() != BC->getDestTy()) { 12234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = new BitCastInst(Val, BC->getDestTy(), "", BC); 12244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val->takeName(BC); 122539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 12264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BC->replaceAllUsesWith(Val); 12274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(BC); 122839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner} 1229372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 12304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// FindElementAndOffset - Return the index of the element containing Offset 12314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// within the specified type, which must be either a struct or an array. 12324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Sets T to the type of the element and Offset to the offset within that 12334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// element. IdxTy is set to the type of the index result to be used in a 12344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// GEP instruction. 12354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattneruint64_t SROA::FindElementAndOffset(const Type *&T, uint64_t &Offset, 12364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *&IdxTy) { 12374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Idx = 0; 12384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) { 12394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(ST); 12404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Idx = Layout->getElementContainingOffset(Offset); 12414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = ST->getContainedType(Idx); 12424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Layout->getElementOffset(Idx); 12434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IdxTy = Type::getInt32Ty(T->getContext()); 12444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Idx; 1245f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 12464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *AT = cast<ArrayType>(T); 12474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = AT->getElementType(); 12484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD->getTypeAllocSize(T); 12494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Idx = Offset / EltSize; 12504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Idx * EltSize; 12514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IdxTy = Type::getInt64Ty(T->getContext()); 12524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Idx; 12535e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 1254a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 12554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteGEP - Check if this GEP instruction moves the pointer across 12564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// elements of the alloca that are being split apart, and if so, rewrite 12574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the GEP to be relative to the new element. 12584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 12594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 12604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t OldOffset = Offset; 12614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 12624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), 12634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 12644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(GEPI, AI, Offset, NewElts); 12664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *T = AI->getAllocatedType(); 12684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *IdxTy; 12694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t OldIdx = FindElementAndOffset(T, OldOffset, IdxTy); 12704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GEPI->getOperand(0) == AI) 12714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OldIdx = ~0ULL; // Force the GEP to be rewritten. 12724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = AI->getAllocatedType(); 12744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltOffset = Offset; 12754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Idx = FindElementAndOffset(T, EltOffset, IdxTy); 12764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this GEP does not move the pointer across elements of the alloca 12784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // being split, then it does not needs to be rewritten. 12794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Idx == OldIdx) 1280c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner return; 1281c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 12824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *i32Ty = Type::getInt32Ty(AI->getContext()); 12834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> NewArgs; 12844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.push_back(Constant::getNullValue(i32Ty)); 12854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (EltOffset != 0) { 12864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltIdx = FindElementAndOffset(T, EltOffset, IdxTy); 12874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.push_back(ConstantInt::get(IdxTy, EltIdx)); 12882e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 12894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Val = NewElts[Idx]; 12904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (NewArgs.size() > 1) { 12914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = GetElementPtrInst::CreateInBounds(Val, NewArgs.begin(), 12924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.end(), "", GEPI); 12934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val->takeName(GEPI); 12944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 12954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val->getType() != GEPI->getType()) 12964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = new BitCastInst(Val, GEPI->getType(), Val->getName(), GEPI); 12974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner GEPI->replaceAllUsesWith(Val); 12984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(GEPI); 1299a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1300a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 13014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI. 13024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Rewrite it to copy or set the elements of the scalarized memory. 13034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 13044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *AI, 13054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 13064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy/memmove, construct the other pointer as the 13074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // appropriate type. The "Other" pointer is the pointer that goes to memory 13084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // that doesn't have anything to do with the alloca that we are promoting. For 13094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // memset, this Value* stays null. 13104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *OtherPtr = 0; 13114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned MemAlignment = MI->getAlignment(); 13124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { // memmove/memcopy 13134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Inst == MTI->getRawDest()) 13144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr = MTI->getRawSource(); 13154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else { 13164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(Inst == MTI->getRawSource()); 13174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr = MTI->getRawDest(); 1318a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 13194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 13203ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner 13214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If there is an other pointer, we want to convert it to the same pointer 13224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // type as AI has, so we can GEP through it safely. 13234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr) { 13240238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner unsigned AddrSpace = 13250238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner cast<PointerType>(OtherPtr->getType())->getAddressSpace(); 13264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 13274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Remove bitcasts and all-zero GEPs from OtherPtr. This is an 13284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // optimization, but it's also required to detect the corner case where 13294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // both pointer operands are referencing the same memory, and where 13304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // OtherPtr may be a bitcast or GEP that currently being rewritten. (This 13314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // function is only called for mem intrinsics that access the whole 13324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // aggregate, so non-zero GEPs are not an issue here.) 13330238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner OtherPtr = OtherPtr->stripPointerCasts(); 13340238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner 13354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Copying the alloca to itself is a no-op: just delete it. 13364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr == AI || OtherPtr == NewElts[0]) { 13374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // This code will run twice for a no-op memcpy -- once for each operand. 13384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Put only one reference to MI on the DeadInsts list. 13394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (SmallVector<Value*, 32>::const_iterator I = DeadInsts.begin(), 13404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner E = DeadInsts.end(); I != E; ++I) 13414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (*I == MI) return; 13424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(MI); 13434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 1344c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1345dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner 13464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the pointer is not the right type, insert a bitcast to the right 13474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // type. 13480238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner const Type *NewTy = 13490238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner PointerType::get(AI->getType()->getElementType(), AddrSpace); 13500238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner 13510238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner if (OtherPtr->getType() != NewTy) 13520238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner OtherPtr = new BitCastInst(OtherPtr, NewTy, OtherPtr->getName(), MI); 1353a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1354a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 13554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Process each element of the aggregate. 13564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool SROADest = MI->getRawDest() == Inst; 13574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 13584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *Zero = Constant::getNullValue(Type::getInt32Ty(MI->getContext())); 13594b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 13604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 13614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy/memmove, emit a GEP of the other element address. 13624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *OtherElt = 0; 13634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned OtherEltAlign = MemAlignment; 13649bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 13654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr) { 13664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Idx[2] = { Zero, 13674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(Type::getInt32Ty(MI->getContext()), i) }; 13684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherElt = GetElementPtrInst::CreateInBounds(OtherPtr, Idx, Idx + 2, 13694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr->getName()+"."+Twine(i), 13704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MI); 13714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltOffset; 13724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType()); 1373d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner const Type *OtherTy = OtherPtrTy->getElementType(); 1374d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner if (const StructType *ST = dyn_cast<StructType>(OtherTy)) { 13754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltOffset = TD->getStructLayout(ST)->getElementOffset(i); 13764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 1377d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner const Type *EltTy = cast<SequentialType>(OtherTy)->getElementType(); 13784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltOffset = TD->getTypeAllocSize(EltTy)*i; 13794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1380aadadb3973bb202cd4d2e20e842588162e780f13Chris Lattner 13814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The alignment of the other pointer is the guaranteed alignment of the 13824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // element, which is affected by both the known alignment of the whole 13834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // mem intrinsic and the alignment of the element. If the alignment of 13844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the memcpy (f.e.) is 32 but the element is at a 4-byte offset, then the 13854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // known alignment is just 4 bytes. 13864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset); 13879bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 13889bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 13894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltPtr = NewElts[i]; 13904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType(); 13914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 13924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we got down to a scalar, insert a load or store as appropriate. 13934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltTy->isSingleValueType()) { 13944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isa<MemTransferInst>(MI)) { 13954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SROADest) { 13964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // From Other to Alloca. 13974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI); 13984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Elt, EltPtr, MI); 13994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 14004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // From Alloca to Other. 14014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = new LoadInst(EltPtr, "tmp", MI); 14024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI); 14034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 140533e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner } 14064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(isa<MemSetInst>(MI)); 1407c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 14084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the stored element is zero (common case), just store a null 14094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // constant. 14104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *StoreVal; 14116f14c8c7c1ec97797a04631abad6885bfaabcc6dGabor Greif if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getArgOperand(1))) { 14124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (CI->isZero()) { 14134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = Constant::getNullValue(EltTy); // 0.0, null, 0, <0,0> 14144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 14154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If EltTy is a vector type, get the element type. 14164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ValTy = EltTy->getScalarType(); 1417c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 14184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Construct an integer with the right value. 14194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD->getTypeSizeInBits(ValTy); 14204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt OneVal(EltSize, CI->getZExtValue()); 14214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt TotalVal(OneVal); 14224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Set each byte. 14234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0; 8*i < EltSize; ++i) { 14244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TotalVal = TotalVal.shl(8); 14254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TotalVal |= OneVal; 14264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 14284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Convert the integer value to the appropriate type. 1429d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner StoreVal = ConstantInt::get(CI->getContext(), TotalVal); 14304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ValTy->isPointerTy()) 14314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy); 14324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (ValTy->isFloatingPointTy()) 14334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy); 14344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(StoreVal->getType() == ValTy && "Type mismatch!"); 14354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 14364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the requested value was a vector constant, create it. 14374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltTy != ValTy) { 14384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned NumElts = cast<VectorType>(ValTy)->getNumElements(); 14394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Constant*, 16> Elts(NumElts, StoreVal); 14404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantVector::get(&Elts[0], NumElts); 14414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(StoreVal, EltPtr, MI); 14444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 14454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, if we're storing a byte variable, use a memset call for 14474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // this element. 14484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 144961db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner 14504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD->getTypeAllocSize(EltTy); 14514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 145261db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner IRBuilder<> Builder(MI); 145361db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner 14544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Finally, insert the meminst for this element. 145561db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner if (isa<MemSetInst>(MI)) { 145661db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Builder.CreateMemSet(EltPtr, MI->getArgOperand(1), EltSize, 145761db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner MI->isVolatile()); 14584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 145961db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner assert(isa<MemTransferInst>(MI)); 146061db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Value *Dst = SROADest ? EltPtr : OtherElt; // Dest ptr 146161db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Value *Src = SROADest ? OtherElt : EltPtr; // Src ptr 146261db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner 146361db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner if (isa<MemCpyInst>(MI)) 146461db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Builder.CreateMemCpy(Dst, Src, EltSize, OtherEltAlign,MI->isVolatile()); 146561db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner else 146661db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Builder.CreateMemMove(Dst, Src, EltSize,OtherEltAlign,MI->isVolatile()); 14674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1468a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 14694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(MI); 1470a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 147179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 14724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteStoreUserOfWholeAlloca - We found a store of an integer that 14734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// overwrites the entire allocation. Extract out the pieces of the stored 14744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer and store them individually. 14754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 14764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts){ 14774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Extract each element out of the integer according to its structure offset 14784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // and store the element value to the individual alloca. 14794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcVal = SI->getOperand(0); 14804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaEltTy = AI->getAllocatedType(); 14814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 14821aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner 14834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle tail padding by extending the operand 14844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits) 14854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcVal = new ZExtInst(SrcVal, 14864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SI->getContext(), AllocaSizeBits), 14874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", SI); 14884b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 14894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << '\n' << *SI 14904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner << '\n'); 14914b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 14924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // There are two forms here: AI could be an array or struct. Both cases 14934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // have different ways to compute the element offset. 14944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 14954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(EltSTy); 14964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 14974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 14984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Get the number of bits to shift SrcVal to get the value. 14994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *FieldTy = EltSTy->getElementType(i); 15004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift = Layout->getElementOffsetInBits(i); 15014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 15034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-Shift-TD->getTypeAllocSizeInBits(FieldTy); 15044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltVal = SrcVal; 15064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 15074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 15084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 15094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "sroa.store.elt", SI); 15104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncate down to an integer of the right size. 15134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 15144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 15164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits == 0) continue; 15174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits != AllocaSizeBits) 15194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = new TruncInst(EltVal, 15204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SI->getContext(), FieldSizeBits), 15214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", SI); 15224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *DestField = NewElts[i]; 15234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltVal->getType() == FieldTy) { 15244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing to an integer field of this size, just do it. 15254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (FieldTy->isFloatingPointTy() || FieldTy->isVectorTy()) { 15264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Bitcast to the right element type (for fp/vector values). 15274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = new BitCastInst(EltVal, FieldTy, "", SI); 15284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 15294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 15304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DestField = new BitCastInst(DestField, 15314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PointerType::getUnqual(EltVal->getType()), 15324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", SI); 15334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(EltVal, DestField, SI); 15354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15379d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 15384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *ATy = cast<ArrayType>(AllocaEltTy); 15394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ArrayEltTy = ATy->getElementType(); 15404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ElementOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 15414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy); 15424b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 15434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift; 15444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 15464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-ElementOffset; 15474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else 15484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = 0; 15494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 15514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 15524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ElementSizeBits == 0) continue; 15534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltVal = SrcVal; 15554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 15564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 15574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 15584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "sroa.store.elt", SI); 15594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncate down to an integer of the right size. 15624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ElementSizeBits != AllocaSizeBits) 15634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = new TruncInst(EltVal, 15644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SI->getContext(), 15654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementSizeBits),"",SI); 15664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *DestField = NewElts[i]; 15674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltVal->getType() == ArrayEltTy) { 15684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing to an integer field of this size, just do it. 15694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ArrayEltTy->isFloatingPointTy() || 15704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ArrayEltTy->isVectorTy()) { 15714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Bitcast to the right element type (for fp/vector values). 15724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI); 15734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 15744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 15754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DestField = new BitCastInst(DestField, 15764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PointerType::getUnqual(EltVal->getType()), 15774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", SI); 15784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(EltVal, DestField, SI); 15804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 15824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift -= ElementOffset; 15834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else 15844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift += ElementOffset; 15854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1586800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 15874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 15884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(SI); 1589800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1590800de31776356910eb877e71df9f32b0a6215324Chris Lattner 15914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteLoadUserOfWholeAlloca - We found a load of the entire allocation to 15924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// an integer. Load the individual pieces to form the aggregate value. 15934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 15944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 15954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Extract each element out of the NewElts according to its structure offset 15964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // and form the result value. 15974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaEltTy = AI->getAllocatedType(); 15984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 15994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << '\n' << *LI 16014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner << '\n'); 16024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // There are two forms here: AI could be an array or struct. Both cases 16044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // have different ways to compute the element offset. 16054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = 0; 16064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ArrayEltBitOffset = 0; 16074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 16084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Layout = TD->getStructLayout(EltSTy); 16094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 16104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType(); 16114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ArrayEltBitOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 16124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 16134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ResultVal = 16154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant::getNullValue(IntegerType::get(LI->getContext(), AllocaSizeBits)); 16164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 16184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Load the value from the alloca. If the NewElt is an aggregate, cast 16194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the pointer to an integer of the same size before doing the load. 16204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcField = NewElts[i]; 16214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *FieldTy = 16224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner cast<PointerType>(SrcField->getType())->getElementType(); 16234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 162429e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 16264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits == 0) continue; 16274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const IntegerType *FieldIntTy = IntegerType::get(LI->getContext(), 16294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FieldSizeBits); 16304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!FieldTy->isIntegerTy() && !FieldTy->isFloatingPointTy() && 16314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner !FieldTy->isVectorTy()) 16324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new BitCastInst(SrcField, 16334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PointerType::getUnqual(FieldIntTy), 16344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", LI); 16354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new LoadInst(SrcField, "sroa.load.elt", LI); 163629e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SrcField is a fp or vector of the right size but that isn't an 16384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integer type, bitcast to an integer so we can shift it. 16394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcField->getType() != FieldIntTy) 16404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI); 164129e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero extend the field to be the same size as the final alloca so that 16434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // we can shift and insert it. 16444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcField->getType() != ResultVal->getType()) 16454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI); 164629e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Determine the number of bits to shift SrcField. 16484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift; 16494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Layout) // Struct case. 16504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = Layout->getElementOffsetInBits(i); 16514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else // Array case. 16524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = i*ArrayEltBitOffset; 165329e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 16544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 16554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth(); 16564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 16584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift); 16594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI); 16609b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 16614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16621495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner // Don't create an 'or x, 0' on the first iteration. 16631495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner if (!isa<Constant>(ResultVal) || 16641495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner !cast<Constant>(ResultVal)->isNullValue()) 16651495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI); 16661495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner else 16671495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner ResultVal = SrcField; 16689b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 16694b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle tail padding by truncating the result 16714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits) 16724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI); 16734b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(ResultVal); 16754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(LI); 16764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 16774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// HasPadding - Return true if the specified type has any structure or 16794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// alignment padding, false otherwise. 16804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerstatic bool HasPadding(const Type *Ty, const TargetData &TD) { 168191abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) 168291abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner return HasPadding(ATy->getElementType(), TD); 168391abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 168491abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(Ty)) 168591abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner return HasPadding(VTy->getElementType(), TD); 168691abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 16874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *STy = dyn_cast<StructType>(Ty)) { 16884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *SL = TD.getStructLayout(STy); 16894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned PrevFieldBitOffset = 0; 16904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 16914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned FieldBitOffset = SL->getElementOffsetInBits(i); 16924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Padding in sub-elements? 16944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (HasPadding(STy->getElementType(i), TD)) 16954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 16964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check to see if there is any padding between this element and the 16984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // previous one. 16994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (i) { 17004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned PrevFieldEnd = 17014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1)); 17024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (PrevFieldEnd < FieldBitOffset) 17034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 17044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PrevFieldBitOffset = FieldBitOffset; 17077809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 17084b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check for tail padding. 17104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (unsigned EltCount = STy->getNumElements()) { 17114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned PrevFieldEnd = PrevFieldBitOffset + 17124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD.getTypeSizeInBits(STy->getElementType(EltCount-1)); 17134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (PrevFieldEnd < SL->getSizeInBits()) 17144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 17154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17162e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 171791abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 17184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty); 17194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 17204b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 17224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 17234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or 1 if safe after canonicalization has been performed. 17244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::isSafeAllocaToScalarRepl(AllocaInst *AI) { 17254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Loop over the use list of the alloca. We can only transform it if all of 17264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the users are safe to transform. 17274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInfo Info; 17284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isSafeForScalarRepl(AI, AI, 0, Info); 17304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isUnsafe) { 17314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Cannot transform: " << *AI << '\n'); 17324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 1733800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 17344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Okay, we know all the users are promotable. If the aggregate is a memcpy 17364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // source and destination, we have to be careful. In particular, the memcpy 17374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // could be moving around elements that live in structure padding of the LLVM 17384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // types, but may actually be used. In these cases, we refuse to promote the 17394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // struct. 17404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isMemCpySrc && Info.isMemCpyDst && 17414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner HasPadding(AI->getAllocatedType(), *TD)) 17424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 17434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 17444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 1745800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1746800de31776356910eb877e71df9f32b0a6215324Chris Lattner 1747800de31776356910eb877e71df9f32b0a6215324Chris Lattner 174879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 174979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// PointsToConstantGlobal - Return true if V (possibly indirectly) points to 175079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// some part of a constant global variable. This intentionally only accepts 175179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// constant expressions because we don't can't rewrite arbitrary instructions. 175279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool PointsToConstantGlobal(Value *V) { 175379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 175479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return GV->isConstant(); 175579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 175679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (CE->getOpcode() == Instruction::BitCast || 175779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner CE->getOpcode() == Instruction::GetElementPtr) 175879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return PointsToConstantGlobal(CE->getOperand(0)); 175979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 176079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 176179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 176279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) 176379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// pointer to an alloca. Ignore any reads of the pointer, return false if we 176479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// see any stores or other unknown uses. If we see pointer arithmetic, keep 176579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// track of whether it moves the pointer (with isOffset) but otherwise traverse 176679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to 1767081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky/// the alloca, and if the source pointer is a pointer to a constant global, we 176879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// can optimize this. 176931d80103d56c026403d7fb6c50833664ff63ddcbChris Lattnerstatic bool isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy, 177079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner bool isOffset) { 177179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 17728a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif User *U = cast<Instruction>(*UI); 17738a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif 17742e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 17756e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // Ignore non-volatile loads, they are always ok. 17762e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (LI->isVolatile()) return false; 17772e61849f45144f2f05d57b00947df7e101610694Chris Lattner continue; 17782e61849f45144f2f05d57b00947df7e101610694Chris Lattner } 17796e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 17808a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { 178179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If uses of the bitcast are ok, we are ok. 178279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset)) 178379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 178479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 178579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 17868a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 178779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the GEP has all zero indices, it doesn't offset the pointer. If it 178879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // doesn't, it does. 178979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy, 179079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner isOffset || !GEP->hasAllZeroIndices())) 179179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 179279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 179379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 179479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 17956248065194778c866164b0c10f09f0f0d91b91acChris Lattner if (CallSite CS = U) { 17966248065194778c866164b0c10f09f0f0d91b91acChris Lattner // If this is a readonly/readnone call site, then we know it is just a 17976248065194778c866164b0c10f09f0f0d91b91acChris Lattner // load and we can ignore it. 1798a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner if (CS.onlyReadsMemory()) 1799a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner continue; 1800081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky 1801081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky // If this is the function being called then we treat it like a load and 1802081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky // ignore it. 1803081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky if (CS.isCallee(UI)) 1804081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky continue; 18056248065194778c866164b0c10f09f0f0d91b91acChris Lattner 18066248065194778c866164b0c10f09f0f0d91b91acChris Lattner // If this is being passed as a byval argument, the caller is making a 18076248065194778c866164b0c10f09f0f0d91b91acChris Lattner // copy, so it is only a read of the alloca. 18086248065194778c866164b0c10f09f0f0d91b91acChris Lattner unsigned ArgNo = CS.getArgumentNo(UI); 18096248065194778c866164b0c10f09f0f0d91b91acChris Lattner if (CS.paramHasAttr(ArgNo+1, Attribute::ByVal)) 18106248065194778c866164b0c10f09f0f0d91b91acChris Lattner continue; 18116248065194778c866164b0c10f09f0f0d91b91acChris Lattner } 1812a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner 181379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If this is isn't our memcpy/memmove, reject it as something we can't 181479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // handle. 181531d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner MemTransferInst *MI = dyn_cast<MemTransferInst>(U); 181631d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner if (MI == 0) 181779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 18182e61849f45144f2f05d57b00947df7e101610694Chris Lattner 18192e61849f45144f2f05d57b00947df7e101610694Chris Lattner // If the transfer is using the alloca as a source of the transfer, then 18202e29ebd9e8efefe3ff926aa99cf2e5323665998eChris Lattner // ignore it since it is a load (unless the transfer is volatile). 18212e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (UI.getOperandNo() == 1) { 18222e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (MI->isVolatile()) return false; 18232e61849f45144f2f05d57b00947df7e101610694Chris Lattner continue; 18242e61849f45144f2f05d57b00947df7e101610694Chris Lattner } 182579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 182679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If we already have seen a copy, reject the second one. 182779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (TheCopy) return false; 182879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 182979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the pointer has been offset from the start of the alloca, we can't 183079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // safely handle this. 183179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (isOffset) return false; 183279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 183379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the memintrinsic isn't using the alloca as the dest, reject it. 1834a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif if (UI.getOperandNo() != 0) return false; 183579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 183679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the source of the memcpy/move is not a constant global, reject it. 183731d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner if (!PointsToConstantGlobal(MI->getSource())) 183879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 183979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 184079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Otherwise, the transform is safe. Remember the copy instruction. 184179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner TheCopy = MI; 184279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 184379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return true; 184479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 184579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 184679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only 184779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// modified by a copy from a constant global. If we can prove this, we can 184879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// replace any uses of the alloca with uses of the global directly. 184931d80103d56c026403d7fb6c50833664ff63ddcbChris LattnerMemTransferInst *SROA::isOnlyCopiedFromConstantGlobal(AllocaInst *AI) { 185031d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner MemTransferInst *TheCopy = 0; 185179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false)) 185279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return TheCopy; 185379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return 0; 185479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 1855