ScalarReplAggregates.cpp revision b742defa0a8f3e477c3ed641da49aab276937556
1ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 10ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// This transformation implements the well known scalar replacement of 11ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregates transformation. This xform breaks up alloca instructions of 12ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregate type (structure or array) into individual alloca instructions for 1338aec325604635380421a27e39ab06d55ed2458dChris Lattner// each member (if possible). Then, if possible, it transforms the individual 1438aec325604635380421a27e39ab06d55ed2458dChris Lattner// alloca instructions into nice clean scalar SSA form. 1538aec325604635380421a27e39ab06d55ed2458dChris Lattner// 1638aec325604635380421a27e39ab06d55ed2458dChris Lattner// This combines a simple SRoA algorithm with the Mem2Reg algorithm because 1738aec325604635380421a27e39ab06d55ed2458dChris Lattner// often interact, especially for C++ programs. As such, iterating between 1838aec325604635380421a27e39ab06d55ed2458dChris Lattner// SRoA, then Mem2Reg until we run out of things to promote works well. 19ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 20ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===----------------------------------------------------------------------===// 21ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 220e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner#define DEBUG_TYPE "scalarrepl" 23ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Transforms/Scalar.h" 2438aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Constants.h" 2538aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/DerivedTypes.h" 26ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Function.h" 2779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner#include "llvm/GlobalVariable.h" 28d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 29372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/IntrinsicInst.h" 30fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson#include "llvm/LLVMContext.h" 31372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/Pass.h" 3238aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Analysis/Dominators.h" 3338aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Target/TargetData.h" 3438aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 354afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel#include "llvm/Transforms/Utils/Local.h" 369525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Debug.h" 377d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 38a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 3965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner#include "llvm/Support/IRBuilder.h" 40a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/MathExtras.h" 41bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 421ccd185cb49d81465a2901622e58ceae046d1d83Chris Lattner#include "llvm/ADT/SmallVector.h" 43551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 44d8664730942beb911327336d1f9db8e7efcd6813Chris Lattnerusing namespace llvm; 45d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 460e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of allocas broken up"); 470e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted, "Number of allocas promoted"); 480e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumConverted, "Number of aggregates converted to scalar"); 4979b3bd395dc3303cde65e18e0524ed2f70268c99Chris LattnerSTATISTIC(NumGlobals, "Number of allocas copied from constant global"); 50ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 510e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 523e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct SROA : public FunctionPass { 53ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 54ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman explicit SROA(signed T = -1) : FunctionPass(&ID) { 55ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel if (T == -1) 56b0e71edb6b33f822e001500dac90acf95faacea8Chris Lattner SRThreshold = 128; 57ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel else 58ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel SRThreshold = T; 59ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel } 60794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 61ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 62ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 6338aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performScalarRepl(Function &F); 6438aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performPromotion(Function &F); 6538aec325604635380421a27e39ab06d55ed2458dChris Lattner 66a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 67a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner // will not alter the CFG, so say so. 68a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 69326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel AU.addRequired<DominatorTree>(); 7038aec325604635380421a27e39ab06d55ed2458dChris Lattner AU.addRequired<DominanceFrontier>(); 71a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner AU.setPreservesCFG(); 72a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner } 73a15854c9febcb60eb107048640b04abff8cc47e5Chris Lattner 74ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 7556c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner TargetData *TD; 7656c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner 77b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson /// DeadInsts - Keep track of instructions we have made dead, so that 78b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson /// we can remove them after we are done working. 79b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<Value*, 32> DeadInsts; 80b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 8139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// AllocaInfo - When analyzing uses of an alloca instruction, this captures 8239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// information about the uses. All these fields are initialized to false 8339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// and set to true when something is learned. 8439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner struct AllocaInfo { 8539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isUnsafe - This is set to true if the alloca cannot be SROA'd. 8639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isUnsafe : 1; 8739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 884afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel /// needsCleanup - This is set to true if there is some use of the alloca 894afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel /// that requires cleanup. 904afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel bool needsCleanup : 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() 994afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel : isUnsafe(false), needsCleanup(false), 10039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner isMemCpySrc(false), isMemCpyDst(false) {} 10139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner }; 10239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 103ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel unsigned SRThreshold; 104ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel 10539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; } 10639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1077b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez int isSafeAllocaToScalarRepl(AllocaInst *AI); 10839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 109b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 110b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t ArrayOffset, AllocaInfo &Info); 111b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t &Offset, 112b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t &ArrayOffset, AllocaInfo &Info); 113b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t ArrayOffset, 114b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t MemSize, const Type *MemOpType, bool isStore, 115b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson AllocaInfo &Info); 116b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson bool TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size); 117b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson unsigned FindElementAndOffset(const Type *&T, uint64_t &Offset); 11839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1197b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void DoScalarReplacement(AllocaInst *AI, 1207b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez std::vector<AllocaInst*> &WorkList); 121b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void DeleteDeadInstructions(); 1224afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel void CleanupGEP(GetElementPtrInst *GEP); 123b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void CleanupAllocaUsers(Value *V); 1247b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocaInst *Base); 125a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 126b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 127b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 128b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 129b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 130b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 131b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 132b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 1337b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI, 134d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1357b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 136d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1377b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 1386e733d34ca487ab7ff8a6def018a933620393869Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 139d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 1407809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner bool CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy, 1411a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool &SawVec, uint64_t Offset, unsigned AllocaSize); 1422e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset); 1436e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType, 1449bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 1459b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal, 14665a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 1477b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez static Instruction *isOnlyCopiedFromConstantGlobal(AllocaInst *AI); 148ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 149ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 150ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 151844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar SROA::ID = 0; 152844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<SROA> X("scalarrepl", "Scalar Replacement of Aggregates"); 153844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 154d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the ScalarReplAggregates pass 155ff366850aa9956e167e78d4f5b57aae10d8c5779Devang PatelFunctionPass *llvm::createScalarReplAggregatesPass(signed int Threshold) { 156ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel return new SROA(Threshold); 157ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel} 158ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 159ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 160ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattnerbool SROA::runOnFunction(Function &F) { 161e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman TD = getAnalysisIfAvailable<TargetData>(); 162e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman 163fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = performPromotion(F); 164e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman 165e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman // FIXME: ScalarRepl currently depends on TargetData more than it 166e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman // theoretically needs to. It should be refactored in order to support 167e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman // target-independent IR. Until this is done, just skip the actual 168e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman // scalar-replacement portion of this pass. 169e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman if (!TD) return Changed; 170e4af1cf4027d19cbe52d70858353dc1765ea3aefDan Gohman 171fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner while (1) { 172fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool LocalChange = performScalarRepl(F); 173fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to repromote if no scalarrepl 174fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner Changed = true; 175fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner LocalChange = performPromotion(F); 176fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner if (!LocalChange) break; // No need to re-scalarrepl if no promotion 177fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner } 17838aec325604635380421a27e39ab06d55ed2458dChris Lattner 17938aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 18038aec325604635380421a27e39ab06d55ed2458dChris Lattner} 18138aec325604635380421a27e39ab06d55ed2458dChris Lattner 18238aec325604635380421a27e39ab06d55ed2458dChris Lattner 18338aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performPromotion(Function &F) { 18438aec325604635380421a27e39ab06d55ed2458dChris Lattner std::vector<AllocaInst*> Allocas; 185326821ef12c911af1d785e305e81dc3c07e456a5Devang Patel DominatorTree &DT = getAnalysis<DominatorTree>(); 18643f820d1f7638656be2158efac7dd8f5b08b8b77Chris Lattner DominanceFrontier &DF = getAnalysis<DominanceFrontier>(); 18738aec325604635380421a27e39ab06d55ed2458dChris Lattner 18802a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 18938aec325604635380421a27e39ab06d55ed2458dChris Lattner 190fe7ea0da17a1b5150aabbc2e82c5f4a0750dc23eChris Lattner bool Changed = false; 191fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 19238aec325604635380421a27e39ab06d55ed2458dChris Lattner while (1) { 19338aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.clear(); 19438aec325604635380421a27e39ab06d55ed2458dChris Lattner 19538aec325604635380421a27e39ab06d55ed2458dChris Lattner // Find allocas that are safe to promote, by looking at all instructions in 19638aec325604635380421a27e39ab06d55ed2458dChris Lattner // the entry node 19738aec325604635380421a27e39ab06d55ed2458dChris Lattner for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 19838aec325604635380421a27e39ab06d55ed2458dChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 19941968df51e11f581eb19c8f68a8cb2f4e8acc1c5Devang Patel if (isAllocaPromotable(AI)) 20038aec325604635380421a27e39ab06d55ed2458dChris Lattner Allocas.push_back(AI); 20138aec325604635380421a27e39ab06d55ed2458dChris Lattner 20238aec325604635380421a27e39ab06d55ed2458dChris Lattner if (Allocas.empty()) break; 20338aec325604635380421a27e39ab06d55ed2458dChris Lattner 204ce2c51b6701c06f701efa2871794b7710cb64b41Nick Lewycky PromoteMemToReg(Allocas, DT, DF); 20538aec325604635380421a27e39ab06d55ed2458dChris Lattner NumPromoted += Allocas.size(); 20638aec325604635380421a27e39ab06d55ed2458dChris Lattner Changed = true; 20738aec325604635380421a27e39ab06d55ed2458dChris Lattner } 20838aec325604635380421a27e39ab06d55ed2458dChris Lattner 20938aec325604635380421a27e39ab06d55ed2458dChris Lattner return Changed; 21038aec325604635380421a27e39ab06d55ed2458dChris Lattner} 21138aec325604635380421a27e39ab06d55ed2458dChris Lattner 212963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner/// getNumSAElements - Return the number of elements in the specific struct or 213963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner/// array. 214963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattnerstatic uint64_t getNumSAElements(const Type *T) { 215963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) 216963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner return ST->getNumElements(); 217963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner return cast<ArrayType>(T)->getNumElements(); 218963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner} 219963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner 22038aec325604635380421a27e39ab06d55ed2458dChris Lattner// performScalarRepl - This algorithm is a simple worklist driven algorithm, 22138aec325604635380421a27e39ab06d55ed2458dChris Lattner// which runs on all of the malloc/alloca instructions in the function, removing 22238aec325604635380421a27e39ab06d55ed2458dChris Lattner// them if they are only used by getelementptr instructions. 22338aec325604635380421a27e39ab06d55ed2458dChris Lattner// 22438aec325604635380421a27e39ab06d55ed2458dChris Lattnerbool SROA::performScalarRepl(Function &F) { 2257b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez std::vector<AllocaInst*> WorkList; 226ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 227ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Scan the entry basic block, adding any alloca's and mallocs to the worklist 22802a3be020a6b4eedb4b489959997d23a22cdf22eChris Lattner BasicBlock &BB = F.getEntryBlock(); 229ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 2307b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez if (AllocaInst *A = dyn_cast<AllocaInst>(I)) 231ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.push_back(A); 232ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 233ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner // Process the worklist 234ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool Changed = false; 235ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner while (!WorkList.empty()) { 2367b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI = WorkList.back(); 237ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner WorkList.pop_back(); 238a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 239add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner // Handle dead allocas trivially. These can be formed by SROA'ing arrays 240add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner // with unused elements. 241add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner if (AI->use_empty()) { 242add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner AI->eraseFromParent(); 243add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner continue; 244add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner } 2457809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 2467809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If this alloca is impossible for us to promote, reject it early. 2477809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized()) 2487809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 2497809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 2507809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Check to see if this allocation is only modified by a memcpy/memmove from 2517809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // a constant global. If this is the case, we can change all users to use 2527809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // the constant global instead. This is commonly produced by the CFE by 2537809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A' 2547809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // is only subsequently read. 2557809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (Instruction *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) { 25659136251f348a02a26f7a711a0e7fc459a727093Nick Lewycky DEBUG(errs() << "Found alloca equal to global: " << *AI << '\n'); 25759136251f348a02a26f7a711a0e7fc459a727093Nick Lewycky DEBUG(errs() << " memcpy = " << *TheCopy << '\n'); 2587809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Constant *TheSrc = cast<Constant>(TheCopy->getOperand(2)); 259baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType())); 2607809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner TheCopy->eraseFromParent(); // Don't mutate the global. 2617809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AI->eraseFromParent(); 2627809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ++NumGlobals; 2637809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Changed = true; 2647809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 2657809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 266add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner 26779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Check to see if we can perform the core SROA transformation. We cannot 26879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // transform the allocation instruction if it is an array allocation 26979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // (allocations OF arrays are ok though), and an allocation of a scalar 27079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // value cannot be decomposed at all. 271777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType()); 2725a377cb27bb65ea608b63716454c9ae214ef81c9Bill Wendling 273d3aa25e2a8b04853f03341b6275ef7718659b915Nick Lewycky // Do not promote [0 x %struct]. 274d3aa25e2a8b04853f03341b6275ef7718659b915Nick Lewycky if (AllocaSize == 0) continue; 275d3aa25e2a8b04853f03341b6275ef7718659b915Nick Lewycky 2765a377cb27bb65ea608b63716454c9ae214ef81c9Bill Wendling // Do not promote any struct whose size is too big. 2773aaf5d993365c803dad9a8815b6c9864505af5b6Bill Wendling if (AllocaSize > SRThreshold) continue; 278d3aa25e2a8b04853f03341b6275ef7718659b915Nick Lewycky 2797809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if ((isa<StructType>(AI->getAllocatedType()) || 2807139406707eb3869183fd6a3329fe4a77d309692Chris Lattner isa<ArrayType>(AI->getAllocatedType())) && 281963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner // Do not promote any struct into more than "32" separate vars. 28267fca63da267da491de9526b09a7de0a2e99ece2Evan Cheng getNumSAElements(AI->getAllocatedType()) <= SRThreshold/4) { 283a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // Check that all of the users of the allocation are capable of being 284a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // transformed. 285a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner switch (isSafeAllocaToScalarRepl(AI)) { 286c23197a26f34f559ea9797de51e187087c039c42Torok Edwin default: llvm_unreachable("Unexpected value!"); 287a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 0: // Not safe to scalar replace. 288a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner break; 289a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 1: // Safe, but requires cleanup/canonicalizations first 2904afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel CleanupAllocaUsers(AI); 291a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner // FALL THROUGH. 292a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner case 3: // Safe to scalar replace. 293a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner DoScalarReplacement(AI, WorkList); 294a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner Changed = true; 295a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner continue; 296a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 297f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 2986e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 2996e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // If we can turn this aggregate value (potentially with casts) into a 3006e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // simple scalar value that can be mem2reg'd into a register value. 3012e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // IsNotTrivial tracks whether this is something that mem2reg could have 3022e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // promoted itself. If so, we don't want to transform it needlessly. Note 3032e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // that we can't just check based on the type: the alloca may be of an i32 3042e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // but that has pointer arithmetic to set byte 3 of it or something. 3056e733d34ca487ab7ff8a6def018a933620393869Chris Lattner bool IsNotTrivial = false; 3067809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner const Type *VectorTy = 0; 3071a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool HadAVector = false; 3081a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (CanConvertToScalar(AI, IsNotTrivial, VectorTy, HadAVector, 3090ff83ab9858d56fb37ea634c52eafb3de641d733Chris Lattner 0, unsigned(AllocaSize)) && IsNotTrivial) { 3107809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaInst *NewAI; 3111a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // If we were able to find a vector type that can handle this with 3121a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // insert/extract elements, and if there was at least one use that had 3131a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // a vector type, promote this to a vector. We don't want to promote 3141a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // random stuff that doesn't use vectors (e.g. <9 x double>) because then 3151a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // we just get a lot of insert/extracts. If at least one vector is 3161a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner // involved, then we probably really do have a union of vector/array. 3171a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (VectorTy && isa<VectorType>(VectorTy) && HadAVector) { 31859136251f348a02a26f7a711a0e7fc459a727093Nick Lewycky DEBUG(errs() << "CONVERT TO VECTOR: " << *AI << "\n TYPE = " 319bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << *VectorTy << '\n'); 32015c82779033826a0958182b746b03a22ad04a16aChris Lattner 3217809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Create and insert the vector alloca. 32250dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson NewAI = new AllocaInst(VectorTy, 0, "", AI->getParent()->begin()); 3237809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ConvertUsesToScalar(AI, NewAI, 0); 3247809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } else { 325bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner DEBUG(errs() << "CONVERT TO SCALAR INTEGER: " << *AI << "\n"); 3267809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 3277809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Create and insert the integer alloca. 3281d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson const Type *NewTy = IntegerType::get(AI->getContext(), AllocaSize*8); 32950dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin()); 33015c82779033826a0958182b746b03a22ad04a16aChris Lattner ConvertUsesToScalar(AI, NewAI, 0); 3316e733d34ca487ab7ff8a6def018a933620393869Chris Lattner } 3327809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner NewAI->takeName(AI); 3337809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AI->eraseFromParent(); 3347809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ++NumConverted; 3357809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner Changed = true; 3367809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 3377809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 3386e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 3397809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Otherwise, couldn't process this alloca. 340a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 341ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 342a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner return Changed; 343a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner} 344fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 345a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner/// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl 346a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner/// predicate, do SROA now. 3477b929dad59785f62a66f7c58615082f98441e95eVictor Hernandezvoid SROA::DoScalarReplacement(AllocaInst *AI, 3487b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez std::vector<AllocaInst*> &WorkList) { 349ff1147072a0c9dbe91572bbbbf93031c6451bbaeChris Lattner DEBUG(errs() << "Found inst to SROA: " << *AI << '\n'); 350a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner SmallVector<AllocaInst*, 32> ElementAllocas; 351a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 352a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 353a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 35450dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 355a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner AI->getAlignment(), 356fe09b2098ac483f6d6ce6ea4ab237a9539bdb6b9Daniel Dunbar AI->getName() + "." + Twine(i), AI); 357a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.push_back(NA); 358a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 359a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 360a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } else { 361a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 362a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.reserve(AT->getNumElements()); 363a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner const Type *ElTy = AT->getElementType(); 364a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 36550dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), 366fe09b2098ac483f6d6ce6ea4ab237a9539bdb6b9Daniel Dunbar AI->getName() + "." + Twine(i), AI); 367a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner ElementAllocas.push_back(NA); 368a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 369ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 370a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 371fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 372b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Now that we have created the new alloca instructions, rewrite all the 373b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // uses of the old alloca. 374b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson RewriteForScalarRepl(AI, AI, 0, ElementAllocas); 375a59adc40153f3e0f9843952c127d179b5ebe6c4cChris Lattner 376b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Now erase any instructions that were made dead while rewriting the alloca. 377b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeleteDeadInstructions(); 37839c88a641b6bf9cea7d270ccee85992f9c30f40fBob Wilson AI->eraseFromParent(); 379b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 380a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner NumReplaced++; 381ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 382a59adc40153f3e0f9843952c127d179b5ebe6c4cChris Lattner 383b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// DeleteDeadInstructions - Erase instructions on the DeadInstrs list, 384b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// recursively including all their operands that become trivially dead. 385b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::DeleteDeadInstructions() { 386b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson while (!DeadInsts.empty()) { 387b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Instruction *I = cast<Instruction>(DeadInsts.pop_back_val()); 388b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 389b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 390b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Instruction *U = dyn_cast<Instruction>(*OI)) { 391b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Zero out the operand and see if it becomes trivially dead. 392b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // (But, don't add allocas to the dead instruction list -- they are 393b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // already on the worklist and will be deleted separately.) 394b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson *OI = 0; 395b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (isInstructionTriviallyDead(U) && !isa<AllocaInst>(U)) 396b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeadInsts.push_back(U); 397a59adc40153f3e0f9843952c127d179b5ebe6c4cChris Lattner } 398b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 399b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson I->eraseFromParent(); 400a59adc40153f3e0f9843952c127d179b5ebe6c4cChris Lattner } 401a59adc40153f3e0f9843952c127d179b5ebe6c4cChris Lattner} 402b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 403d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner/// AllUsersAreLoads - Return true if all users of this value are loads. 404d878ecd904e4469344a2274f9784422c2c68b81cChris Lattnerstatic bool AllUsersAreLoads(Value *Ptr) { 405d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end(); 406d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner I != E; ++I) 407d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner if (cast<Instruction>(*I)->getOpcode() != Instruction::Load) 408d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner return false; 409fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman return true; 410d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner} 411d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner 412b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// isSafeForScalarRepl - Check if instruction I is a safe use with regard to 413b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// performing scalar replacement of alloca AI. The results are flagged in 414b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// the Info parameter. Offset and ArrayOffset indicate the position within 415b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// AI that is referenced by this instruction. 416b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 417b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t ArrayOffset, AllocaInfo &Info) { 418b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) { 419b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Instruction *User = cast<Instruction>(*UI); 4202674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 421b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 422b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson isSafeForScalarRepl(BC, AI, Offset, ArrayOffset, Info); 423b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 424b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t GEPArrayOffset = ArrayOffset; 425b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t GEPOffset = Offset; 426b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson isSafeGEP(GEPI, AI, GEPOffset, GEPArrayOffset, Info); 427b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!Info.isUnsafe) 428b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson isSafeForScalarRepl(GEPI, AI, GEPOffset, GEPArrayOffset, Info); 429b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(UI)) { 430b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 431b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Length) 432b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson isSafeMemAccess(AI, Offset, ArrayOffset, Length->getZExtValue(), 0, 433b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson UI.getOperandNo() == 1, Info); 434b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson else 435b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MarkUnsafe(Info); 436b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 437b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!LI->isVolatile()) { 438b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *LIType = LI->getType(); 439b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson isSafeMemAccess(AI, Offset, ArrayOffset, TD->getTypeAllocSize(LIType), 440b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson LIType, false, Info); 441b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else 442b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MarkUnsafe(Info); 443b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 444b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Store is ok if storing INTO the pointer, not storing the pointer 445b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!SI->isVolatile() && SI->getOperand(0) != I) { 446b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *SIType = SI->getOperand(0)->getType(); 447b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson isSafeMemAccess(AI, Offset, ArrayOffset, TD->getTypeAllocSize(SIType), 448b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SIType, true, Info); 449b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else 450b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MarkUnsafe(Info); 451b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (isa<DbgInfoIntrinsic>(UI)) { 452b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // If one user is DbgInfoIntrinsic then check if all users are 453b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // DbgInfoIntrinsics. 454b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (OnlyUsedByDbgInfoIntrinsics(I)) { 455b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Info.needsCleanup = true; 456b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return; 457b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 458b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MarkUnsafe(Info); 459b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 460b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DEBUG(errs() << " Transformation preventing inst: " << *User << '\n'); 461b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MarkUnsafe(Info); 462b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 463b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Info.isUnsafe) return; 46439c88a641b6bf9cea7d270ccee85992f9c30f40fBob Wilson } 465b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson} 466fca55c8ac7d12e4139ad0ab7d74b76c47935aef6Daniel Dunbar 467b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// isSafeGEP - Check if a GEP instruction can be handled for scalar 468b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// replacement. It is safe when all the indices are constant, in-bounds 469b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// references, and when the resulting offset corresponds to an element within 470b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// the alloca type. The results are flagged in the Info parameter. Upon 471b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// return, Offset is adjusted as specified by the GEP indices. For the 472b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// special case of a variable index to a 2-element array, ArrayOffset is set 473b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// to the array element size. 474b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI, 475b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t &Offset, uint64_t &ArrayOffset, 476b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson AllocaInfo &Info) { 477b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson gep_type_iterator GEPIt = gep_type_begin(GEPI), E = gep_type_end(GEPI); 478b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (GEPIt == E) 479b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return; 480b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 481b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // The first GEP index must be zero. 482b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!isa<ConstantInt>(GEPIt.getOperand()) || 483b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson !cast<ConstantInt>(GEPIt.getOperand())->isZero()) 484b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return MarkUnsafe(Info); 485b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (++GEPIt == E) 486b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return; 48739c88a641b6bf9cea7d270ccee85992f9c30f40fBob Wilson 48888e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // If the first index is a non-constant index into an array, see if we can 48988e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // handle it as a special case. 490b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *ArrayEltTy = 0; 491b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (ArrayOffset == 0 && Offset == 0) { 492b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (const ArrayType *AT = dyn_cast<ArrayType>(*GEPIt)) { 493b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!isa<ConstantInt>(GEPIt.getOperand())) { 494b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t NumElements = AT->getNumElements(); 495b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 496b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // If this is an array index and the index is not constant, we cannot 497b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // promote... that is unless the array has exactly one or two elements 498b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // in it, in which case we CAN promote it, but we have to canonicalize 499b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // this out if this is the only problem. 500b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if ((NumElements != 1 && NumElements != 2) || !AllUsersAreLoads(GEPI)) 501b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return MarkUnsafe(Info); 5024afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel Info.needsCleanup = true; 503b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson ArrayOffset = TD->getTypeAllocSizeInBits(AT->getElementType()); 504b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson ArrayEltTy = AT->getElementType(); 505b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson ++GEPIt; 50639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 507d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 5085e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner } 509b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 51088e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // Walk through the GEP type indices, checking the types that this indexes 51188e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // into. 512b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson for (; GEPIt != E; ++GEPIt) { 51388e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner // Ignore struct elements, no extra checking needed for these. 514b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (isa<StructType>(*GEPIt)) 51588e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner continue; 5165fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 517b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPIt.getOperand()); 518b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!IdxVal) 519b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return MarkUnsafe(Info); 520b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 521b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (const ArrayType *AT = dyn_cast<ArrayType>(*GEPIt)) { 5225fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // This GEP indexes an array. Verify that this is an in-range constant 5235fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // integer. Specifically, consider A[0][i]. We cannot know that the user 5245fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // isn't doing invalid things like allowing i to index an out-of-range 5255fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman // subscript that accesses A[1]. Because of this, we have to reject SROA 526d614a1f0a89927639db37efd8840fe006dacd7a1Bob Wilson // of any accesses into structs where any of the components are variables. 5275fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman if (IdxVal->getZExtValue() >= AT->getNumElements()) 5285fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman return MarkUnsafe(Info); 529b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 530b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const VectorType *VT = dyn_cast<VectorType>(*GEPIt); 531b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson assert(VT && "unexpected type in GEP type iterator"); 532c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen if (IdxVal->getZExtValue() >= VT->getNumElements()) 533c0bc547c99bd97088e950b3074d917091abe3f51Dale Johannesen return MarkUnsafe(Info); 5345fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman } 53588e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner } 5362674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 537b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // All the indices are safe. Now compute the offset due to this GEP and 538b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // check if the alloca has a component element at that offset. 539b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (ArrayOffset == 0) { 540b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 541b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), 542b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson &Indices[0], Indices.size()); 543b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 544b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Both array elements have the same type, so it suffices to check one of 545b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // them. Copy the GEP indices starting from the array index, but replace 546b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // that variable index with a constant zero. 547b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<Value*, 8> Indices(GEPI->op_begin() + 2, GEPI->op_end()); 548b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Indices[0] = Constant::getNullValue(Type::getInt32Ty(GEPI->getContext())); 549b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *ArrayEltPtr = PointerType::getUnqual(ArrayEltTy); 550b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Offset += TD->getIndexedOffset(ArrayEltPtr, &Indices[0], Indices.size()); 5512674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar } 552b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!TypeHasComponent(AI->getAllocatedType(), Offset, 0)) 553b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MarkUnsafe(Info); 5542674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar} 5552674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 556b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// isSafeMemAccess - Check if a load/store/memcpy operates on the entire AI 557b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// alloca or has an offset and size that corresponds to a component element 558b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// within it. The offset checked here may have been formed from a GEP with a 559b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// pointer bitcasted to a different type. 560b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::isSafeMemAccess(AllocaInst *AI, uint64_t Offset, 561b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t ArrayOffset, uint64_t MemSize, 562b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *MemOpType, bool isStore, 563b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson AllocaInfo &Info) { 564b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Check if this is a load/store of the entire alloca. 565b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Offset == 0 && ArrayOffset == 0 && 566b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) { 567b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson bool UsesAggregateType = (MemOpType == AI->getAllocatedType()); 568b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // This is safe for MemIntrinsics (where MemOpType is 0), integer types 569b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // (which are essentially the same as the MemIntrinsics, especially with 570b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // regard to copying padding between elements), or references using the 571b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // aggregate type of the alloca. 572b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!MemOpType || isa<IntegerType>(MemOpType) || UsesAggregateType) { 573b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (!UsesAggregateType) { 574b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (isStore) 575b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Info.isMemCpyDst = true; 576b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson else 577b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Info.isMemCpySrc = true; 57839c88a641b6bf9cea7d270ccee85992f9c30f40fBob Wilson } 579b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return; 580b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 581b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 582b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Check if the offset/size correspond to a component within the alloca type. 583b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *T = AI->getAllocatedType(); 584b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (TypeHasComponent(T, Offset, MemSize) && 585b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson (ArrayOffset == 0 || TypeHasComponent(T, Offset + ArrayOffset, MemSize))) 586b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return; 5872674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 588b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return MarkUnsafe(Info); 589b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson} 590b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 591b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// TypeHasComponent - Return true if T has a component type with the 592b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// specified offset and size. If Size is zero, do not check the size. 593b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonbool SROA::TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size) { 594b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *EltTy; 595b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t EltSize; 596b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (const StructType *ST = dyn_cast<StructType>(T)) { 597b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const StructLayout *Layout = TD->getStructLayout(ST); 598b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson unsigned EltIdx = Layout->getElementContainingOffset(Offset); 599b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson EltTy = ST->getContainedType(EltIdx); 600b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson EltSize = TD->getTypeAllocSize(EltTy); 601b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Offset -= Layout->getElementOffset(EltIdx); 602b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (const ArrayType *AT = dyn_cast<ArrayType>(T)) { 603b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson EltTy = AT->getElementType(); 604b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson EltSize = TD->getTypeAllocSize(EltTy); 605b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Offset %= EltSize; 606b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 607b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return false; 608b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 609b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Offset == 0 && (Size == 0 || EltSize == Size)) 610b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return true; 611b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Check if the component spans multiple elements. 612b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Offset + Size > EltSize) 613b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return false; 614b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return TypeHasComponent(EltTy, Offset, Size); 615b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson} 616b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 617b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// RewriteForScalarRepl - Alloca AI is being split into NewElts, so rewrite 618b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// the instruction I, which references it, to use the separate elements. 619b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// Offset indicates the position within AI that is referenced by this 620b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// instruction. 621b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 622b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts) { 623b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) { 624b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Instruction *User = cast<Instruction>(*UI); 625b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 626b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 627b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson RewriteBitCast(BC, AI, Offset, NewElts); 628b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 629b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson RewriteGEP(GEPI, AI, Offset, NewElts); 630b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 631b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 632b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t MemSize = Length->getZExtValue(); 633b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Offset == 0 && 634b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) 635b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson RewriteMemIntrinUserOfAlloca(MI, I, AI, NewElts); 636b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 637b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *LIType = LI->getType(); 638b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (LIType == AI->getAllocatedType()) { 639b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Replace: 640b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // %res = load { i32, i32 }* %alloc 641b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // with: 642b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // %load.0 = load i32* %alloc.0 643b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0 644b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // %load.1 = load i32* %alloc.1 645b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1 646b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // (Also works for arrays instead of structs) 647b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Value *Insert = UndefValue::get(LIType); 648b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 649b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Value *Load = new LoadInst(NewElts[i], "load", LI); 650b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI); 651b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 652b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson LI->replaceAllUsesWith(Insert); 653b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeadInsts.push_back(LI); 654b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (isa<IntegerType>(LIType) && 655b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson TD->getTypeAllocSize(LIType) == 656b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson TD->getTypeAllocSize(AI->getAllocatedType())) { 657b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // If this is a load of the entire alloca to an integer, rewrite it. 658b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson RewriteLoadUserOfWholeAlloca(LI, AI, NewElts); 6595ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 660b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 661b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Value *Val = SI->getOperand(0); 662b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *SIType = Val->getType(); 663b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (SIType == AI->getAllocatedType()) { 664b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Replace: 665b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // store { i32, i32 } %val, { i32, i32 }* %alloc 666b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // with: 667b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // %val.0 = extractvalue { i32, i32 } %val, 0 668b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // store i32 %val.0, i32* %alloc.0 669b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // %val.1 = extractvalue { i32, i32 } %val, 1 670b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // store i32 %val.1, i32* %alloc.1 671b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // (Also works for arrays instead of structs) 672b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 673b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI); 674b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson new StoreInst(Extract, NewElts[i], SI); 675b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 676b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeadInsts.push_back(SI); 677b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (isa<IntegerType>(SIType) && 678b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson TD->getTypeAllocSize(SIType) == 679b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson TD->getTypeAllocSize(AI->getAllocatedType())) { 680b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // If this is a store of the entire alloca from an integer, rewrite it. 681b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson RewriteStoreUserOfWholeAlloca(SI, AI, NewElts); 6824afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 68339c88a641b6bf9cea7d270ccee85992f9c30f40fBob Wilson } 684372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 685372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 686372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 687b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// RewriteBitCast - Update a bitcast reference to the alloca being replaced 688b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// and recursively continue updating all of its uses. 689b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 690b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts) { 691b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson RewriteForScalarRepl(BC, AI, Offset, NewElts); 692b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (BC->getOperand(0) != AI) 693b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return; 6942674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 695b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // The bitcast references the original alloca. Replace its uses with 696b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // references to the first new element alloca. 697b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Instruction *Val = NewElts[0]; 698b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Val->getType() != BC->getDestTy()) { 699b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Val = new BitCastInst(Val, BC->getDestTy(), "", BC); 700b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Val->takeName(BC); 701b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 702b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson BC->replaceAllUsesWith(Val); 703b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeadInsts.push_back(BC); 704b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson} 7052674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 706b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// FindElementAndOffset - Return the index of the element containing Offset 707b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// within the specified type, which must be either a struct or an array. 708b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// Sets T to the type of the element and Offset to the offset within that 709b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// element. 710b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonunsigned SROA::FindElementAndOffset(const Type *&T, uint64_t &Offset) { 711b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson unsigned Idx = 0; 712b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (const StructType *ST = dyn_cast<StructType>(T)) { 713b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const StructLayout *Layout = TD->getStructLayout(ST); 714b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Idx = Layout->getElementContainingOffset(Offset); 715b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson T = ST->getContainedType(Idx); 716b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Offset -= Layout->getElementOffset(Idx); 717b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 718b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const ArrayType *AT = dyn_cast<ArrayType>(T); 719b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson assert(AT && "unexpected type for scalar replacement"); 720b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson T = AT->getElementType(); 721b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t EltSize = TD->getTypeAllocSize(T); 722b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Idx = (unsigned)(Offset / EltSize); 723b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Offset -= Idx * EltSize; 724b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 725b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return Idx; 726b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson} 727b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 728b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// RewriteGEP - Check if this GEP instruction moves the pointer across 729b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// elements of the alloca that are being split apart, and if so, rewrite 730b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson/// the GEP to be relative to the new element. 731b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 732b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts) { 733b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t OldOffset = Offset; 734b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 735b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), 736b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson &Indices[0], Indices.size()); 737b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 738b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson RewriteForScalarRepl(GEPI, AI, Offset, NewElts); 739b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 740b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *T = AI->getAllocatedType(); 741b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson unsigned OldIdx = FindElementAndOffset(T, OldOffset); 742b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (GEPI->getOperand(0) == AI) 743b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson OldIdx = ~0U; // Force the GEP to be rewritten. 744b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 745b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson T = AI->getAllocatedType(); 746b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t EltOffset = Offset; 747b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson unsigned Idx = FindElementAndOffset(T, EltOffset); 748b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 749b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // If this GEP does not move the pointer across elements of the alloca 750b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // being split, then it does not needs to be rewritten. 751b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Idx == OldIdx) 752b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return; 753b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 754b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *i32Ty = Type::getInt32Ty(AI->getContext()); 755b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<Value*, 8> NewArgs; 756b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson NewArgs.push_back(Constant::getNullValue(i32Ty)); 757b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson while (EltOffset != 0) { 758b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson unsigned EltIdx = FindElementAndOffset(T, EltOffset); 759b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson NewArgs.push_back(ConstantInt::get(i32Ty, EltIdx)); 760b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 761b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Instruction *Val = NewElts[Idx]; 762b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (NewArgs.size() > 1) { 763b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Val = GetElementPtrInst::CreateInBounds(Val, NewArgs.begin(), 764b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson NewArgs.end(), "", GEPI); 765b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Val->takeName(GEPI); 7662674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar } 767b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Val->getType() != GEPI->getType()) 768b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Val = new BitCastInst(Val, GEPI->getType(), Val->getNameStr(), GEPI); 769b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson GEPI->replaceAllUsesWith(Val); 770b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeadInsts.push_back(GEPI); 771d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner} 772d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 773d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner/// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI. 774d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner/// Rewrite it to copy or set the elements of the scalarized memory. 775b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 7767b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI, 777d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 778d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If this is a memcpy/memmove, construct the other pointer as the 77988fe1ad187041e2ca636e0f86204e30fc6e14300Chris Lattner // appropriate type. The "Other" pointer is the pointer that goes to memory 78088fe1ad187041e2ca636e0f86204e30fc6e14300Chris Lattner // that doesn't have anything to do with the alloca that we are promoting. For 78188fe1ad187041e2ca636e0f86204e30fc6e14300Chris Lattner // memset, this Value* stays null. 782d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *OtherPtr = 0; 783e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context = MI->getContext(); 784dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner unsigned MemAlignment = MI->getAlignment(); 7853ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { // memmove/memcopy 786b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Inst == MTI->getRawDest()) 7873ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner OtherPtr = MTI->getRawSource(); 788d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner else { 789b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson assert(Inst == MTI->getRawSource()); 7903ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner OtherPtr = MTI->getRawDest(); 791372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 792d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 79378c50b8cd68d266d4ed6f8eca443cf8142a01204Bob Wilson 794d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If there is an other pointer, we want to convert it to the same pointer 795d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // type as AI has, so we can GEP through it safely. 796d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherPtr) { 797b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 798b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // Remove bitcasts and all-zero GEPs from OtherPtr. This is an 799b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // optimization, but it's also required to detect the corner case where 800b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // both pointer operands are referencing the same memory, and where 801b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // OtherPtr may be a bitcast or GEP that currently being rewritten. (This 802b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // function is only called for mem intrinsics that access the whole 803b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // aggregate, so non-zero GEPs are not an issue here.) 804b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson while (1) { 805b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (BitCastInst *BC = dyn_cast<BitCastInst>(OtherPtr)) { 806b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson OtherPtr = BC->getOperand(0); 807b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson continue; 808b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 809b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(OtherPtr)) { 810b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // All zero GEPs are effectively bitcasts. 811b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (GEP->hasAllZeroIndices()) { 812b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson OtherPtr = GEP->getOperand(0); 813b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson continue; 814b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 815b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 816b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson break; 817b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 818b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson // If OtherPtr has already been rewritten, this intrinsic will be dead. 819b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (OtherPtr == NewElts[0]) 820b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return; 821372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 822d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (ConstantExpr *BCE = dyn_cast<ConstantExpr>(OtherPtr)) 823d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (BCE->getOpcode() == Instruction::BitCast) 824d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = BCE->getOperand(0); 825d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 826d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the pointer is not the right type, insert a bitcast to the right 827d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // type. 828d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherPtr->getType() != AI->getType()) 829d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherPtr = new BitCastInst(OtherPtr, AI->getType(), OtherPtr->getName(), 830d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 831d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 832d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 833d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Process each element of the aggregate. 834d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *TheFn = MI->getOperand(0); 835d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner const Type *BytePtrTy = MI->getRawDest()->getType(); 836b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson bool SROADest = MI->getRawDest() == Inst; 837d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 8381d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Constant *Zero = Constant::getNullValue(Type::getInt32Ty(MI->getContext())); 839372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 840d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 841d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If this is a memcpy/memmove, emit a GEP of the other element address. 842d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *OtherElt = 0; 8431541e0f7da2de6ae84434060df81e93b64000924Chris Lattner unsigned OtherEltAlign = MemAlignment; 8441541e0f7da2de6ae84434060df81e93b64000924Chris Lattner 845b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (OtherPtr == AI) { 846b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson OtherElt = NewElts[i]; 847b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson OtherEltAlign = 0; 848b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (OtherPtr) { 8491d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Value *Idx[2] = { Zero, 8501d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(MI->getContext()), i) }; 851b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson OtherElt = GetElementPtrInst::CreateInBounds(OtherPtr, Idx, Idx + 2, 852fe09b2098ac483f6d6ce6ea4ab237a9539bdb6b9Daniel Dunbar OtherPtr->getNameStr()+"."+Twine(i), 853b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson MI); 8541541e0f7da2de6ae84434060df81e93b64000924Chris Lattner uint64_t EltOffset; 8551541e0f7da2de6ae84434060df81e93b64000924Chris Lattner const PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType()); 8561541e0f7da2de6ae84434060df81e93b64000924Chris Lattner if (const StructType *ST = 8571541e0f7da2de6ae84434060df81e93b64000924Chris Lattner dyn_cast<StructType>(OtherPtrTy->getElementType())) { 8581541e0f7da2de6ae84434060df81e93b64000924Chris Lattner EltOffset = TD->getStructLayout(ST)->getElementOffset(i); 8591541e0f7da2de6ae84434060df81e93b64000924Chris Lattner } else { 8601541e0f7da2de6ae84434060df81e93b64000924Chris Lattner const Type *EltTy = 8611541e0f7da2de6ae84434060df81e93b64000924Chris Lattner cast<SequentialType>(OtherPtr->getType())->getElementType(); 862777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands EltOffset = TD->getTypeAllocSize(EltTy)*i; 8631541e0f7da2de6ae84434060df81e93b64000924Chris Lattner } 8641541e0f7da2de6ae84434060df81e93b64000924Chris Lattner 8651541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // The alignment of the other pointer is the guaranteed alignment of the 8661541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // element, which is affected by both the known alignment of the whole 8671541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // mem intrinsic and the alignment of the element. If the alignment of 8681541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // the memcpy (f.e.) is 32 but the element is at a 4-byte offset, then the 8691541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // known alignment is just 4 bytes. 8701541e0f7da2de6ae84434060df81e93b64000924Chris Lattner OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset); 871d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 872d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 873d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *EltPtr = NewElts[i]; 8741541e0f7da2de6ae84434060df81e93b64000924Chris Lattner const Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType(); 875d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 876d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If we got down to a scalar, insert a load or store as appropriate. 877d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltTy->isSingleValueType()) { 8783ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (isa<MemTransferInst>(MI)) { 8791541e0f7da2de6ae84434060df81e93b64000924Chris Lattner if (SROADest) { 8801541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // From Other to Alloca. 8811541e0f7da2de6ae84434060df81e93b64000924Chris Lattner Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI); 8821541e0f7da2de6ae84434060df81e93b64000924Chris Lattner new StoreInst(Elt, EltPtr, MI); 8831541e0f7da2de6ae84434060df81e93b64000924Chris Lattner } else { 8841541e0f7da2de6ae84434060df81e93b64000924Chris Lattner // From Alloca to Other. 8851541e0f7da2de6ae84434060df81e93b64000924Chris Lattner Value *Elt = new LoadInst(EltPtr, "tmp", MI); 8861541e0f7da2de6ae84434060df81e93b64000924Chris Lattner new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI); 8871541e0f7da2de6ae84434060df81e93b64000924Chris Lattner } 888d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 889372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 890d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(isa<MemSetInst>(MI)); 891c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 892d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the stored element is zero (common case), just store a null 893d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // constant. 894d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Constant *StoreVal; 895d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getOperand(2))) { 896d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (CI->isZero()) { 897a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson StoreVal = Constant::getNullValue(EltTy); // 0.0, null, 0, <0,0> 898c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } else { 899d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If EltTy is a vector type, get the element type. 90044118f0e25c25fedda1ccdd6a72f072c0b5c96e7Dan Gohman const Type *ValTy = EltTy->getScalarType(); 90144118f0e25c25fedda1ccdd6a72f072c0b5c96e7Dan Gohman 902d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Construct an integer with the right value. 903d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner unsigned EltSize = TD->getTypeSizeInBits(ValTy); 904d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner APInt OneVal(EltSize, CI->getZExtValue()); 905d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner APInt TotalVal(OneVal); 906d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Set each byte. 907d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner for (unsigned i = 0; 8*i < EltSize; ++i) { 908d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner TotalVal = TotalVal.shl(8); 909d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner TotalVal |= OneVal; 910d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 911d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 912d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Convert the integer value to the appropriate type. 913eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson StoreVal = ConstantInt::get(Context, TotalVal); 914d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (isa<PointerType>(ValTy)) 915baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy); 916d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner else if (ValTy->isFloatingPoint()) 917baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy); 918d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(StoreVal->getType() == ValTy && "Type mismatch!"); 919d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 920d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // If the requested value was a vector constant, create it. 921d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltTy != ValTy) { 922d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner unsigned NumElts = cast<VectorType>(ValTy)->getNumElements(); 923d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<Constant*, 16> Elts(NumElts, StoreVal); 924af7ec975870f92245f1f1484ac80a1e2db6a0afaOwen Anderson StoreVal = ConstantVector::get(&Elts[0], NumElts); 925c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 926c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 927d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner new StoreInst(StoreVal, EltPtr, MI); 928d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner continue; 929c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 930d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Otherwise, if we're storing a byte variable, use a memset call for 931d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // this element. 932d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 933c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 934d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Cast the element pointer to BytePtrTy. 935d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (EltPtr->getType() != BytePtrTy) 936d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner EltPtr = new BitCastInst(EltPtr, BytePtrTy, EltPtr->getNameStr(), MI); 937c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner 938d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Cast the other pointer (if we have one) to BytePtrTy. 939d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner if (OtherElt && OtherElt->getType() != BytePtrTy) 940d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner OtherElt = new BitCastInst(OtherElt, BytePtrTy,OtherElt->getNameStr(), 941d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner MI); 942d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 943777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands unsigned EltSize = TD->getTypeAllocSize(EltTy); 944d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 945d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner // Finally, insert the meminst for this element. 9463ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (isa<MemTransferInst>(MI)) { 947d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *Ops[] = { 948d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SROADest ? EltPtr : OtherElt, // Dest ptr 949d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SROADest ? OtherElt : EltPtr, // Src ptr 950eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size 9511d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson // Align 9521d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(MI->getContext()), OtherEltAlign) 953d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner }; 954d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner CallInst::Create(TheFn, Ops, Ops + 4, "", MI); 955d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } else { 956d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner assert(isa<MemSetInst>(MI)); 957d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Value *Ops[] = { 958d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner EltPtr, MI->getOperand(2), // Dest, Value, 959eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size 960d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner Zero // Align 961d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner }; 962d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner CallInst::Create(TheFn, Ops, Ops + 4, "", MI); 963c14d3cac4bb5c798fbcc4b9cad87841ca087b017Chris Lattner } 964372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 965b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeadInsts.push_back(MI); 966372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 967d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 96839fdd6947cb800a0db7f7012fe843c98b414602fBob Wilson/// RewriteStoreUserOfWholeAlloca - We found a store of an integer that 969d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner/// overwrites the entire allocation. Extract out the pieces of the stored 970d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner/// integer and store them individually. 9717b929dad59785f62a66f7c58615082f98441e95eVictor Hernandezvoid SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 972d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts){ 973d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Extract each element out of the integer according to its structure offset 974d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // and store the element value to the individual alloca. 975d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *SrcVal = SI->getOperand(0); 976b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *AllocaEltTy = AI->getAllocatedType(); 977777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 978d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 97941b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman // Handle tail padding by extending the operand 98041b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits) 981fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson SrcVal = new ZExtInst(SrcVal, 9821d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson IntegerType::get(SI->getContext(), AllocaSizeBits), 9831d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "", SI); 984d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 98559136251f348a02a26f7a711a0e7fc459a727093Nick Lewycky DEBUG(errs() << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << '\n' << *SI 98659136251f348a02a26f7a711a0e7fc459a727093Nick Lewycky << '\n'); 987d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 988d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // There are two forms here: AI could be an array or struct. Both cases 989d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // have different ways to compute the element offset. 990d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 991d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const StructLayout *Layout = TD->getStructLayout(EltSTy); 992d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 993d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 994d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Get the number of bits to shift SrcVal to get the value. 995d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const Type *FieldTy = EltSTy->getElementType(i); 996d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t Shift = Layout->getElementOffsetInBits(i); 997d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 998d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 999777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands Shift = AllocaSizeBits-Shift-TD->getTypeAllocSizeInBits(FieldTy); 1000d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1001d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *EltVal = SrcVal; 1002d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (Shift) { 1003eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 1004d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 1005d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "sroa.store.elt", SI); 1006d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1007d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1008d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Truncate down to an integer of the right size. 1009d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 1010583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 1011583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 1012583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (FieldSizeBits == 0) continue; 1013583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 1014d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (FieldSizeBits != AllocaSizeBits) 1015fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson EltVal = new TruncInst(EltVal, 10161d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson IntegerType::get(SI->getContext(), FieldSizeBits), 10171d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "", SI); 1018d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *DestField = NewElts[i]; 1019d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (EltVal->getType() == FieldTy) { 1020d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Storing to an integer field of this size, just do it. 1021d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else if (FieldTy->isFloatingPoint() || isa<VectorType>(FieldTy)) { 1022d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Bitcast to the right element type (for fp/vector values). 1023d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = new BitCastInst(EltVal, FieldTy, "", SI); 1024d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 1025d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 1026d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner DestField = new BitCastInst(DestField, 1027debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson PointerType::getUnqual(EltVal->getType()), 1028d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "", SI); 1029d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1030d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner new StoreInst(EltVal, DestField, SI); 1031d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1032d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1033d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 1034d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const ArrayType *ATy = cast<ArrayType>(AllocaEltTy); 1035d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner const Type *ArrayEltTy = ATy->getElementType(); 1036777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t ElementOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 1037d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy); 1038d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1039d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner uint64_t Shift; 1040d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1041d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 1042d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift = AllocaSizeBits-ElementOffset; 1043d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner else 1044d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift = 0; 1045d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1046d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 1047583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 1048583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (ElementSizeBits == 0) continue; 1049d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1050d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *EltVal = SrcVal; 1051d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (Shift) { 1052eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 1053d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal, 1054d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "sroa.store.elt", SI); 1055d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1056d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1057d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Truncate down to an integer of the right size. 1058d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (ElementSizeBits != AllocaSizeBits) 1059fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson EltVal = new TruncInst(EltVal, 10601d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson IntegerType::get(SI->getContext(), 10611d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ElementSizeBits),"",SI); 1062d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Value *DestField = NewElts[i]; 1063d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (EltVal->getType() == ArrayEltTy) { 1064d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Storing to an integer field of this size, just do it. 1065d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else if (ArrayEltTy->isFloatingPoint() || isa<VectorType>(ArrayEltTy)) { 1066d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Bitcast to the right element type (for fp/vector values). 1067d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI); 1068d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } else { 1069d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 1070d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner DestField = new BitCastInst(DestField, 1071debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson PointerType::getUnqual(EltVal->getType()), 1072d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner "", SI); 1073d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1074d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner new StoreInst(EltVal, DestField, SI); 1075d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1076d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner if (TD->isBigEndian()) 1077d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift -= ElementOffset; 1078d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner else 1079d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner Shift += ElementOffset; 1080d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1081d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1082d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 1083b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeadInsts.push_back(SI); 1084d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner} 1085d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 108639fdd6947cb800a0db7f7012fe843c98b414602fBob Wilson/// RewriteLoadUserOfWholeAlloca - We found a load of the entire allocation to 10875ffe6acd577696a41932c7b82db06a04687e07baChris Lattner/// an integer. Load the individual pieces to form the aggregate value. 10887b929dad59785f62a66f7c58615082f98441e95eVictor Hernandezvoid SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 10895ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 10905ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Extract each element out of the NewElts according to its structure offset 10915ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // and form the result value. 1092b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson const Type *AllocaEltTy = AI->getAllocatedType(); 1093777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 10945ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 109559136251f348a02a26f7a711a0e7fc459a727093Nick Lewycky DEBUG(errs() << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << '\n' << *LI 109659136251f348a02a26f7a711a0e7fc459a727093Nick Lewycky << '\n'); 10975ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 10985ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // There are two forms here: AI could be an array or struct. Both cases 10995ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // have different ways to compute the element offset. 11005ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const StructLayout *Layout = 0; 11015ffe6acd577696a41932c7b82db06a04687e07baChris Lattner uint64_t ArrayEltBitOffset = 0; 11025ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 11035ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Layout = TD->getStructLayout(EltSTy); 11045ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } else { 11055ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType(); 1106777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands ArrayEltBitOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 11075ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 1108e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson 1109e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson Value *ResultVal = 11101d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Constant::getNullValue(IntegerType::get(LI->getContext(), AllocaSizeBits)); 11115ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11125ffe6acd577696a41932c7b82db06a04687e07baChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 11135ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Load the value from the alloca. If the NewElt is an aggregate, cast 11145ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // the pointer to an integer of the same size before doing the load. 11155ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Value *SrcField = NewElts[i]; 11165ffe6acd577696a41932c7b82db06a04687e07baChris Lattner const Type *FieldTy = 11175ffe6acd577696a41932c7b82db06a04687e07baChris Lattner cast<PointerType>(SrcField->getType())->getElementType(); 1118583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 1119583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 1120583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 1121583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner if (FieldSizeBits == 0) continue; 1122583dd6072eed7a446dad8f0e796fa34aec40aa12Chris Lattner 11231d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson const IntegerType *FieldIntTy = IntegerType::get(LI->getContext(), 11241d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson FieldSizeBits); 11255ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (!isa<IntegerType>(FieldTy) && !FieldTy->isFloatingPoint() && 11265ffe6acd577696a41932c7b82db06a04687e07baChris Lattner !isa<VectorType>(FieldTy)) 1127fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson SrcField = new BitCastInst(SrcField, 1128debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson PointerType::getUnqual(FieldIntTy), 11295ffe6acd577696a41932c7b82db06a04687e07baChris Lattner "", LI); 11305ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new LoadInst(SrcField, "sroa.load.elt", LI); 11315ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11325ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // If SrcField is a fp or vector of the right size but that isn't an 11335ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // integer type, bitcast to an integer so we can shift it. 11345ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (SrcField->getType() != FieldIntTy) 11355ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI); 11365ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11375ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Zero extend the field to be the same size as the final alloca so that 11385ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // we can shift and insert it. 11395ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (SrcField->getType() != ResultVal->getType()) 11405ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI); 11415ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11425ffe6acd577696a41932c7b82db06a04687e07baChris Lattner // Determine the number of bits to shift SrcField. 11435ffe6acd577696a41932c7b82db06a04687e07baChris Lattner uint64_t Shift; 11445ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (Layout) // Struct case. 11455ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = Layout->getElementOffsetInBits(i); 11465ffe6acd577696a41932c7b82db06a04687e07baChris Lattner else // Array case. 11475ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = i*ArrayEltBitOffset; 11485ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11495ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (TD->isBigEndian()) 11505ffe6acd577696a41932c7b82db06a04687e07baChris Lattner Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth(); 11515ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11525ffe6acd577696a41932c7b82db06a04687e07baChris Lattner if (Shift) { 1153eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift); 11545ffe6acd577696a41932c7b82db06a04687e07baChris Lattner SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI); 11555ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 11565ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11575ffe6acd577696a41932c7b82db06a04687e07baChris Lattner ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI); 11585ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 115941b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 116041b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman // Handle tail padding by truncating the result 116141b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits) 116241b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI); 116341b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 11645ffe6acd577696a41932c7b82db06a04687e07baChris Lattner LI->replaceAllUsesWith(ResultVal); 1165b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DeadInsts.push_back(LI); 11665ffe6acd577696a41932c7b82db06a04687e07baChris Lattner} 11675ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 11683cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands/// HasPadding - Return true if the specified type has any structure or 11693cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands/// alignment padding, false otherwise. 1170a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sandsstatic bool HasPadding(const Type *Ty, const TargetData &TD) { 117139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (const StructType *STy = dyn_cast<StructType>(Ty)) { 117239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner const StructLayout *SL = TD.getStructLayout(STy); 117339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned PrevFieldBitOffset = 0; 117439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 11753cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands unsigned FieldBitOffset = SL->getElementOffsetInBits(i); 11763cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 117739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Padding in sub-elements? 1178a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands if (HasPadding(STy->getElementType(i), TD)) 117939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 11803cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 118139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Check to see if there is any padding between this element and the 118239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // previous one. 118339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (i) { 11843cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands unsigned PrevFieldEnd = 118539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1)); 118639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (PrevFieldEnd < FieldBitOffset) 118739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 118839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 11893cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 119039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner PrevFieldBitOffset = FieldBitOffset; 119139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 11923cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 119339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Check for tail padding. 119439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (unsigned EltCount = STy->getNumElements()) { 119539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner unsigned PrevFieldEnd = PrevFieldBitOffset + 119639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner TD.getTypeSizeInBits(STy->getElementType(EltCount-1)); 11973cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands if (PrevFieldEnd < SL->getSizeInBits()) 119839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return true; 119939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 120039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 120139a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 1202a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands return HasPadding(ATy->getElementType(), TD); 12033cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands } else if (const VectorType *VTy = dyn_cast<VectorType>(Ty)) { 1204a0fcc08e6542a0376917b5c76a0af3eb2650c535Duncan Sands return HasPadding(VTy->getElementType(), TD); 120539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 1206777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands return TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty); 120739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner} 1208372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 1209f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 1210f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 1211f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// or 1 if safe after canonicalization has been performed. 12127b929dad59785f62a66f7c58615082f98441e95eVictor Hernandezint SROA::isSafeAllocaToScalarRepl(AllocaInst *AI) { 12135e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // Loop over the use list of the alloca. We can only transform it if all of 12145e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner // the users are safe to transform. 121539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner AllocaInfo Info; 121639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1217b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson isSafeForScalarRepl(AI, AI, 0, 0, Info); 1218b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (Info.isUnsafe) { 1219b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson DEBUG(errs() << "Cannot transform: " << *AI << '\n'); 1220b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson return 0; 1221f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 122239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 122339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // Okay, we know all the users are promotable. If the aggregate is a memcpy 122439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // source and destination, we have to be careful. In particular, the memcpy 122539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // could be moving around elements that live in structure padding of the LLVM 122639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // types, but may actually be used. In these cases, we refuse to promote the 122739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // struct. 122839a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner if (Info.isMemCpySrc && Info.isMemCpyDst && 1229b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson HasPadding(AI->getAllocatedType(), *TD)) 123039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner return 0; 12313cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 123239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner // If we require cleanup, return 1, otherwise return 3. 12334afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel return Info.needsCleanup ? 1 : 3; 1234f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner} 1235f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner 123665ab34f3f29f8e4efb10b2cc40e58c5ce63a76d7Bob Wilson/// CleanupGEP - GEP is used by an Alloca, which can be promoted after the GEP 12374afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// is canonicalized here. 12384afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patelvoid SROA::CleanupGEP(GetElementPtrInst *GEPI) { 12394afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel gep_type_iterator I = gep_type_begin(GEPI); 12404afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel ++I; 12414afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 12427afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel const ArrayType *AT = dyn_cast<ArrayType>(*I); 12437afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel if (!AT) 12447afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel return; 12457afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel 12467afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel uint64_t NumElements = AT->getNumElements(); 12477afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel 12487afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel if (isa<ConstantInt>(I.getOperand())) 12497afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel return; 12507afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel 12517afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel if (NumElements == 1) { 12521d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson GEPI->setOperand(2, 12531d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Constant::getNullValue(Type::getInt32Ty(GEPI->getContext()))); 12547afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel return; 12557afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel } 12564afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 12577afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel assert(NumElements == 2 && "Unhandled case!"); 12587afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // All users of the GEP must be loads. At each use of the GEP, insert 12597afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // two loads of the appropriate indexed GEP and select between them. 1260333c40096561218bc3597cf153c0a3895274414cOwen Anderson Value *IsOne = new ICmpInst(GEPI, ICmpInst::ICMP_NE, I.getOperand(), 1261a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Constant::getNullValue(I.getOperand()->getType()), 1262333c40096561218bc3597cf153c0a3895274414cOwen Anderson "isone"); 12637afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // Insert the new GEP instructions, which are properly indexed. 12647afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel SmallVector<Value*, 8> Indices(GEPI->op_begin()+1, GEPI->op_end()); 12651d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Indices[1] = Constant::getNullValue(Type::getInt32Ty(GEPI->getContext())); 1266b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Value *ZeroIdx = GetElementPtrInst::CreateInBounds(GEPI->getOperand(0), 1267b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Indices.begin(), 1268b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Indices.end(), 1269b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson GEPI->getName()+".0",GEPI); 12701d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Indices[1] = ConstantInt::get(Type::getInt32Ty(GEPI->getContext()), 1); 1271b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Value *OneIdx = GetElementPtrInst::CreateInBounds(GEPI->getOperand(0), 1272b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Indices.begin(), 1273b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson Indices.end(), 1274b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson GEPI->getName()+".1", GEPI); 12757afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // Replace all loads of the variable index GEP with loads from both 12767afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel // indexes and a select. 12777afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel while (!GEPI->use_empty()) { 12787afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel LoadInst *LI = cast<LoadInst>(GEPI->use_back()); 12797afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI); 12807afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *One = new LoadInst(OneIdx , LI->getName()+".1", LI); 12817afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel Value *R = SelectInst::Create(IsOne, One, Zero, LI->getName(), LI); 12827afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel LI->replaceAllUsesWith(R); 12837afe8fa066b227bb2683b6890d6cfdc4ebac0205Devang Patel LI->eraseFromParent(); 12844afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel } 12854afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel} 12864afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel 12874afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel/// CleanupAllocaUsers - If SROA reported that it can promote the specified 1288f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner/// allocation, but only if cleaned up, perform the cleanups required. 1289b742defa0a8f3e477c3ed641da49aab276937556Bob Wilsonvoid SROA::CleanupAllocaUsers(Value *V) { 1290d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // At this point, we know that the end result will be SROA'd and promoted, so 1291d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // we can insert ugly code if required so long as sroa+mem2reg will clean it 1292d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner // up. 1293b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); 1294d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner UI != E; ) { 12954afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel User *U = *UI++; 1296b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (isa<BitCastInst>(U)) { 1297b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson CleanupAllocaUsers(U); 1298b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 12994afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel CleanupGEP(GEPI); 1300b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson CleanupAllocaUsers(GEPI); 1301b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson if (GEPI->use_empty()) GEPI->eraseFromParent(); 1302b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 13030906b1bf09769d5301e62d372b363b4cd0b5a6c7Jay Foad Instruction *I = cast<Instruction>(U); 13044afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel SmallVector<DbgInfoIntrinsic *, 2> DbgInUses; 1305b0c4199a55d72fb9560f00b84a92a062fb8e79eaZhou Sheng if (!isa<StoreInst>(I) && OnlyUsedByDbgInfoIntrinsics(I, &DbgInUses)) { 13064afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel // Safe to remove debug info uses. 13074afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel while (!DbgInUses.empty()) { 13084afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DbgInfoIntrinsic *DI = DbgInUses.back(); DbgInUses.pop_back(); 13094afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel DI->eraseFromParent(); 1310d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 13114afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel I->eraseFromParent(); 1312d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 1313d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 1314d878ecd904e4469344a2274f9784422c2c68b81cChris Lattner } 13155e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 1316a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 13172e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// MergeInType - Add the 'In' type to the accumulated type (Accum) so far at 13182e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// the offset specified by Offset (which is specified in bytes). 1319de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 13202e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// There are two cases we handle here: 13212e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// 1) A union of vector types of the same size and potentially its elements. 1322d22dbdf60652536d44dc4a380059368bea75b5cdChris Lattner/// Here we turn element accesses into insert/extract element operations. 13232e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// This promotes a <4 x float> with a store of float to the third element 13242e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// into a <4 x float> that uses insert element. 13252e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// 2) A fully general blob of memory, which we turn into some (potentially 13262e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// large) integer type with extract and insert operations where the loads 13272e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// and stores would mutate the memory. 13287809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattnerstatic void MergeInType(const Type *In, uint64_t Offset, const Type *&VecTy, 1329fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson unsigned AllocaSize, const TargetData &TD, 1330e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context) { 13317809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If this could be contributing to a vector, analyze it. 13321d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson if (VecTy != Type::getVoidTy(Context)) { // either null or a vector type. 13337809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner 13347809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If the In type is a vector that is the same size as the alloca, see if it 13357809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // matches the existing VecTy. 13367809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (const VectorType *VInTy = dyn_cast<VectorType>(In)) { 13377809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) { 13387809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If we're storing/loading a vector of the right size, allow it as a 13397809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // vector. If this the first vector we see, remember the type so that 13407809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // we know the element size. 13417809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VecTy == 0) 13427809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner VecTy = VInTy; 13437809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return; 13447809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 1345cf0fe8d813727383d630055bb9d1cde21b00b7e7Chris Lattner } else if (In->isFloatTy() || In->isDoubleTy() || 13467809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner (isa<IntegerType>(In) && In->getPrimitiveSizeInBits() >= 8 && 13477809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner isPowerOf2_32(In->getPrimitiveSizeInBits()))) { 13487809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // If we're accessing something that could be an element of a vector, see 13497809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // if the implied vector agrees with what we already have and if Offset is 13507809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // compatible with it. 13517809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner unsigned EltSize = In->getPrimitiveSizeInBits()/8; 13527809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (Offset % EltSize == 0 && 13537809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaSize % EltSize == 0 && 13547809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner (VecTy == 0 || 13557809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner cast<VectorType>(VecTy)->getElementType() 13567809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner ->getPrimitiveSizeInBits()/8 == EltSize)) { 13577809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (VecTy == 0) 1358debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson VecTy = VectorType::get(In, AllocaSize/EltSize); 13597809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return; 13607809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 13612e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 13622e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 13632e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner 13647809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Otherwise, we have a case that we can't handle with an optimized vector 13657809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // form. We can still turn this into a large integer. 13661d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson VecTy = Type::getVoidTy(Context); 1367a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1368a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 13692e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner/// CanConvertToScalar - V is a pointer. If we can convert the pointee and all 1370efc58e793370597eb3e3100e284453c5eddc6099Bob Wilson/// its accesses to a single vector type, return true and set VecTy to 13717809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// the new type. If we could convert the alloca into a single promotable 13727809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// integer, return true but set VecTy to VoidTy. Further, if the use is not a 13737809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// completely trivial use that mem2reg could promote, set IsNotTrivial. Offset 13747809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner/// is the current offset from the base of the alloca being analyzed. 1375a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// 13761a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner/// If we see at least one access to the value that is as a vector type, set the 13771a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner/// SawVec flag. 13781a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattnerbool SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy, 13791a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner bool &SawVec, uint64_t Offset, 13807809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner unsigned AllocaSize) { 1381a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 1382a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Instruction *User = cast<Instruction>(*UI); 1383a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1384a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 13852e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Don't break volatile loads. 13866e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LI->isVolatile()) 13872e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1388e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson MergeInType(LI->getType(), Offset, VecTy, 1389e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson AllocaSize, *TD, V->getContext()); 13901a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner SawVec |= isa<VectorType>(LI->getType()); 1391cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1392cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 1393cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 1394cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 139524d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer // Storing the pointer, not into the value? 13966e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (SI->getOperand(0) == V || SI->isVolatile()) return 0; 1397fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson MergeInType(SI->getOperand(0)->getType(), Offset, 1398e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson VecTy, AllocaSize, *TD, V->getContext()); 13991a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner SawVec |= isa<VectorType>(SI->getOperand(0)->getType()); 1400cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1401cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 14022e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner 14032e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { 14041a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (!CanConvertToScalar(BCI, IsNotTrivial, VecTy, SawVec, Offset, 14051a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner AllocaSize)) 14062e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1407a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner IsNotTrivial = true; 1408cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1409cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 1410cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 1411cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 14122e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If this is a GEP with a variable indices, we can't handle it. 14132e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (!GEP->hasAllConstantIndices()) 14142e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1415cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner 14162e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Compute the offset that this GEP adds to the pointer. 14172e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 1418b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t GEPOffset = TD->getIndexedOffset(GEP->getPointerOperandType(), 14192e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner &Indices[0], Indices.size()); 14202e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // See if all uses can be converted. 14211a3257bbf53eff4c7cfcbef972dd382f7baa7592Chris Lattner if (!CanConvertToScalar(GEP, IsNotTrivial, VecTy, SawVec,Offset+GEPOffset, 14227809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaSize)) 14232e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 14242e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner IsNotTrivial = true; 14252e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner continue; 1426a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 14273ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner 14283d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 14293d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // handle it. 14303ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 14313ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner // Store of constant value and constant size. 14323ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (isa<ConstantInt>(MSI->getValue()) && 14333ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner isa<ConstantInt>(MSI->getLength())) { 14343ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner IsNotTrivial = true; 14353ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner continue; 14363ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner } 14373d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner } 1438c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1439c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 1440c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // can handle it like a load or store of the scalar type. 1441c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 1442c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength())) 1443c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (Len->getZExtValue() == AllocaSize && Offset == 0) { 1444c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner IsNotTrivial = true; 1445c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner continue; 1446c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1447c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1448dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner 144900e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel // Ignore dbg intrinsic. 145000e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel if (isa<DbgInfoIntrinsic>(User)) 145100e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel continue; 145200e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel 14532e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Otherwise, we cannot handle this! 14542e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return false; 1455a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1456a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 14572e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return true; 1458a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1459a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 1460a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner/// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 1461de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// directly. This happens when we are converting an "integer union" to a 1462de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// single integer scalar, or when we are converting a "vector union" to a 1463de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// vector with insert/extractelement instructions. 1464de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// 1465de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// Offset is an offset from the original alloca, in bits that need to be 1466de6df88529e20541dcfab7824af2eb0776194f01Chris Lattner/// shifted to the right. By the end of this, there should be no uses of Ptr. 14672e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattnervoid SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset) { 1468a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner while (!Ptr->use_empty()) { 1469a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner Instruction *User = cast<Instruction>(Ptr->use_back()); 14704b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1471cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) { 1472b10e0da065fc2c18b5bee9011eb249e223a23108Chris Lattner ConvertUsesToScalar(CI, NewAI, Offset); 1473a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner CI->eraseFromParent(); 1474cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1475cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner } 14764b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1477cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 14782e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Compute the offset that this GEP adds to the pointer. 14792e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 1480b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson uint64_t GEPOffset = TD->getIndexedOffset(GEP->getPointerOperandType(), 14812e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner &Indices[0], Indices.size()); 14822e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8); 1483a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner GEP->eraseFromParent(); 1484cf3218640969175634b82e4e3fde1b9e680a5dc6Chris Lattner continue; 1485a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 14863d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 14879bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner IRBuilder<> Builder(User->getParent(), User); 14889bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 14899bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 14906e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner // The load is a bit extract from NewAI shifted right by Offset bits. 14916e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp"); 14926e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner Value *NewLoadVal 14936e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder); 14946e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner LI->replaceAllUsesWith(NewLoadVal); 14959bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner LI->eraseFromParent(); 14969bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner continue; 14979bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 14989bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 14999bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 15009bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner assert(SI->getOperand(0) != Ptr && "Consistency error!"); 1501e6f329476c6598db1b45c3d573eac9cf65179831Benjamin Kramer // FIXME: Remove once builder has Twine API. 1502d614a1f0a89927639db37efd8840fe006dacd7a1Bob Wilson Value *Old = Builder.CreateLoad(NewAI, 1503d614a1f0a89927639db37efd8840fe006dacd7a1Bob Wilson (NewAI->getName()+".in").str().c_str()); 15049bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset, 15059bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Builder); 15069bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner Builder.CreateStore(New, NewAI); 15079bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner SI->eraseFromParent(); 15089bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner continue; 15099bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 15109bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner 15113d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 15123d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner // transform it into a store of the expanded constant value. 15133d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 15143d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner assert(MSI->getRawDest() == Ptr && "Consistency error!"); 15153d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 151633e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner if (NumBytes != 0) { 151733e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue(); 151833e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner 151933e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner // Compute the value replicated the right number of times. 152033e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner APInt APVal(NumBytes*8, Val); 15213d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner 152233e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner // Splat the value if non-zero. 152333e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner if (Val) 152433e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner for (unsigned i = 1; i != NumBytes; ++i) 152533e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner APVal |= APVal << 8; 1526e6f329476c6598db1b45c3d573eac9cf65179831Benjamin Kramer 1527e6f329476c6598db1b45c3d573eac9cf65179831Benjamin Kramer // FIXME: Remove once builder has Twine API. 1528d614a1f0a89927639db37efd8840fe006dacd7a1Bob Wilson Value *Old = Builder.CreateLoad(NewAI, 1529d614a1f0a89927639db37efd8840fe006dacd7a1Bob Wilson (NewAI->getName()+".in").str().c_str()); 1530e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson Value *New = ConvertScalar_InsertValue( 1531eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(User->getContext(), APVal), 1532fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson Old, Offset, Builder); 153333e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner Builder.CreateStore(New, NewAI); 153433e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner } 15353d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner MSI->eraseFromParent(); 15363d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner continue; 15373d730f7453af5ecb1be4b8c5d48843ad5637de37Chris Lattner } 1538c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1539c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 1540c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // can handle it like a load or store of the scalar type. 1541c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 1542c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner assert(Offset == 0 && "must be store to start of alloca"); 1543c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1544c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // If the source and destination are both to the same alloca, then this is 1545c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // a noop copy-to-self, just delete it. Otherwise, emit a load and store 1546c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // as appropriate. 1547c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner AllocaInst *OrigAI = cast<AllocaInst>(Ptr->getUnderlyingObject()); 1548c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1549c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner if (MTI->getSource()->getUnderlyingObject() != OrigAI) { 1550c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // Dest must be OrigAI, change this to be a load from the original 1551c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // pointer (bitcasted), then a store to our new alloca. 1552c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?"); 1553c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner Value *SrcPtr = MTI->getSource(); 1554c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner SrcPtr = Builder.CreateBitCast(SrcPtr, NewAI->getType()); 1555c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1556c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval"); 1557c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner SrcVal->setAlignment(MTI->getAlignment()); 1558c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner Builder.CreateStore(SrcVal, NewAI); 1559c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } else if (MTI->getDest()->getUnderlyingObject() != OrigAI) { 1560c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // Src must be OrigAI, change this to be a load from NewAI then a store 1561c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // through the original dest pointer (bitcasted). 1562c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?"); 1563c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval"); 1564c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1565c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), NewAI->getType()); 1566c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr); 1567c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner NewStore->setAlignment(MTI->getAlignment()); 1568c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } else { 1569c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner // Noop transfer. Src == Dst 1570c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1571c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1572c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 1573c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner MTI->eraseFromParent(); 1574c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner continue; 1575c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 1576dfe964ce8c367248e587f2d9ecc7fac5ee2c6fdcChris Lattner 157700e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel // If user is a dbg info intrinsic then it is safe to remove it. 157800e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel if (isa<DbgInfoIntrinsic>(User)) { 157900e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel User->eraseFromParent(); 158000e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel continue; 158100e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel } 158200e389c8c8874be352358f2cbd23f98d3df5ebadDevang Patel 1583c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unsupported operation!"); 1584a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 1585a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 158679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 15876e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer 15886e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// or vector value FromVal, extracting the bits from the offset specified by 15896e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// Offset. This returns the value, which is of type ToType. 15906e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// 15916e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// This happens when we are converting an "integer union" to a single 15924b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// integer scalar, or when we are converting a "vector union" to a vector with 15934b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// insert/extractelement instructions. 1594800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// 15954b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands/// Offset is an offset from the original alloca, in bits that need to be 15966e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner/// shifted to the right. 15976e01115bb122ef82daa6c8133a1d199d6b8ff767Chris LattnerValue *SROA::ConvertScalar_ExtractValue(Value *FromVal, const Type *ToType, 15986e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner uint64_t Offset, IRBuilder<> &Builder) { 15992e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If the load is of the whole new alloca, no conversion is needed. 16006e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (FromVal->getType() == ToType && Offset == 0) 16016e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return FromVal; 16029d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner 16032e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If the result alloca is a vector type, this is either an element 16042e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // access or a bitcast to another vector type of the same size. 16056e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) { 16066e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (isa<VectorType>(ToType)) 16076e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return Builder.CreateBitCast(FromVal, ToType, "tmp"); 16089d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner 16099d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Otherwise it must be an element access. 16109d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner unsigned Elt = 0; 16119d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (Offset) { 1612777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands unsigned EltSize = TD->getTypeAllocSizeInBits(VTy->getElementType()); 16139d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner Elt = Offset/EltSize; 16142e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner assert(EltSize*Elt == Offset && "Invalid modulus in validity checking"); 1615800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 16162e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Return the element extracted out of it. 16171d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Value *V = Builder.CreateExtractElement(FromVal, ConstantInt::get( 16181d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Type::getInt32Ty(FromVal->getContext()), Elt), "tmp"); 16196e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (V->getType() != ToType) 16206e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner V = Builder.CreateBitCast(V, ToType, "tmp"); 16217809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner return V; 16229d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } 16231aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner 16241aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner // If ToType is a first class aggregate, extract out each of the pieces and 16251aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner // use insertvalue's to form the FCA. 16261aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner if (const StructType *ST = dyn_cast<StructType>(ToType)) { 16271aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner const StructLayout &Layout = *TD->getStructLayout(ST); 16289e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *Res = UndefValue::get(ST); 16291aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 16301aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i), 1631e991ced7cb5cb86d1c33b8d400b1be41185bc69fChris Lattner Offset+Layout.getElementOffsetInBits(i), 16321aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Builder); 16331aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 16341aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 16351aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner return Res; 16361aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 16371aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner 16381aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(ToType)) { 1639777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t EltSize = TD->getTypeAllocSizeInBits(AT->getElementType()); 16409e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *Res = UndefValue::get(AT); 16411aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 16421aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(), 16431aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Offset+i*EltSize, Builder); 16441aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 16451aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 16461aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner return Res; 16471aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner } 16484b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16492e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Otherwise, this must be a union that was converted to an integer value. 16506e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner const IntegerType *NTy = cast<IntegerType>(FromVal->getType()); 16514b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16529d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // If this is a big-endian system and the load is narrower than the 16539d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // full alloca type, we need to do a shift to get the right bits. 16549d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner int ShAmt = 0; 165556c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner if (TD->isBigEndian()) { 16569d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 16579d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 16589d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // integers with a bitwidth that is not a multiple of 8. 165956c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner ShAmt = TD->getTypeStoreSizeInBits(NTy) - 16606e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner TD->getTypeStoreSizeInBits(ToType) - Offset; 16619d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 16629d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner ShAmt = Offset; 16639d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } 16644b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16659d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Note: we support negative bitwidths (with shl) which are not defined. 16669d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // We do this to support (f.e.) loads off the end of a structure where 16679d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // only some bits are used. 16689d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth()) 1669fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson FromVal = Builder.CreateLShr(FromVal, 1670eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(FromVal->getType(), 16711aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner ShAmt), "tmp"); 16729d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth()) 1673fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson FromVal = Builder.CreateShl(FromVal, 1674eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(FromVal->getType(), 16751aa7056b13ac9e0f3fe176d37739ec484d4fe4daChris Lattner -ShAmt), "tmp"); 16764b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16779d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Finally, unconditionally truncate the integer to the right width. 16786e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner unsigned LIBitWidth = TD->getTypeSizeInBits(ToType); 16799d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner if (LIBitWidth < NTy->getBitWidth()) 1680fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson FromVal = 16811d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Builder.CreateTrunc(FromVal, IntegerType::get(FromVal->getContext(), 16821d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson LIBitWidth), "tmp"); 168355a683d7f03b0acaf7807545fd7be319498277ffChris Lattner else if (LIBitWidth > NTy->getBitWidth()) 1684fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson FromVal = 16851d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Builder.CreateZExt(FromVal, IntegerType::get(FromVal->getContext(), 16861d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson LIBitWidth), "tmp"); 16874b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 16889d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // If the result is an integer, this is a trunc or bitcast. 16896e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner if (isa<IntegerType>(ToType)) { 16909d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Should be done. 16916e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner } else if (ToType->isFloatingPoint() || isa<VectorType>(ToType)) { 16929d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Just do a bitcast, we know the sizes match up. 16936e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp"); 16949d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 16959d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner // Otherwise must be a pointer. 16966e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp"); 1697800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 16986e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner assert(FromVal->getType() == ToType && "Didn't convert right?"); 16996e01115bb122ef82daa6c8133a1d199d6b8ff767Chris Lattner return FromVal; 1700800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1701800de31776356910eb877e71df9f32b0a6215324Chris Lattner 17029b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer 17039b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// or vector value "Old" at the offset specified by Offset. 17049b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// 17059b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// This happens when we are converting an "integer union" to a 1706800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// single integer scalar, or when we are converting a "vector union" to a 1707800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// vector with insert/extractelement instructions. 1708800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// 1709800de31776356910eb877e71df9f32b0a6215324Chris Lattner/// Offset is an offset from the original alloca, in bits that need to be 17109b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner/// shifted to the right. 17119b872db775797dea4b391a9347cfbd2ca9c558e2Chris LattnerValue *SROA::ConvertScalar_InsertValue(Value *SV, Value *Old, 171265a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner uint64_t Offset, IRBuilder<> &Builder) { 17134b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 1714800de31776356910eb877e71df9f32b0a6215324Chris Lattner // Convert the stored type to the actual type, shift it left to insert 1715800de31776356910eb877e71df9f32b0a6215324Chris Lattner // then 'or' into place. 17169b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner const Type *AllocaType = Old->getType(); 1717e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson LLVMContext &Context = Old->getContext(); 17184b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17192e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(AllocaType)) { 1720777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t VecSize = TD->getTypeAllocSizeInBits(VTy); 1721777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t ValSize = TD->getTypeAllocSizeInBits(SV->getType()); 172229e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 172329e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner // Changing the whole vector with memset or with an access of a different 172429e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner // vector type? 172529e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner if (ValSize == VecSize) 172629e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner return Builder.CreateBitCast(SV, AllocaType, "tmp"); 172729e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 1728777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t EltSize = TD->getTypeAllocSizeInBits(VTy->getElementType()); 172929e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 173029e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner // Must be an element insertion. 173129e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner unsigned Elt = Offset/EltSize; 173229e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 173329e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner if (SV->getType() != VTy->getElementType()) 173429e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp"); 173529e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 173629e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner SV = Builder.CreateInsertElement(Old, SV, 17371d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(SV->getContext()), Elt), 173829e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner "tmp"); 17392e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner return SV; 17402e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 17419b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner 17429b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner // If SV is a first-class aggregate value, insert each value recursively. 17439b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner if (const StructType *ST = dyn_cast<StructType>(SV->getType())) { 17449b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner const StructLayout &Layout = *TD->getStructLayout(ST); 17459b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 174665a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 17479b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner Old = ConvertScalar_InsertValue(Elt, Old, 1748e991ced7cb5cb86d1c33b8d400b1be41185bc69fChris Lattner Offset+Layout.getElementOffsetInBits(i), 174965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Builder); 17509b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 17519b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner return Old; 17529b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 17539b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner 17549b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) { 1755777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t EltSize = TD->getTypeAllocSizeInBits(AT->getElementType()); 17569b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 175765a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 175865a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder); 17599b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 17609b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner return Old; 17619b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 17624b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17632e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If SV is a float, convert it to the appropriate integer type. 17649b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner // If it is a pointer, do the same. 17652e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned SrcWidth = TD->getTypeSizeInBits(SV->getType()); 17662e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned DestWidth = TD->getTypeSizeInBits(AllocaType); 17672e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned SrcStoreWidth = TD->getTypeStoreSizeInBits(SV->getType()); 17682e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner unsigned DestStoreWidth = TD->getTypeStoreSizeInBits(AllocaType); 17692e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (SV->getType()->isFloatingPoint() || isa<VectorType>(SV->getType())) 17701d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson SV = Builder.CreateBitCast(SV, 17711d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson IntegerType::get(SV->getContext(),SrcWidth), "tmp"); 17722e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner else if (isa<PointerType>(SV->getType())) 17731d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson SV = Builder.CreatePtrToInt(SV, TD->getIntPtrType(SV->getContext()), "tmp"); 17744b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17757809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Zero extend or truncate the value if needed. 17767809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (SV->getType() != AllocaType) { 17777809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner if (SV->getType()->getPrimitiveSizeInBits() < 17787809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner AllocaType->getPrimitiveSizeInBits()) 177965a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateZExt(SV, AllocaType, "tmp"); 17807809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner else { 17817809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // Truncation may be needed if storing more than the alloca can hold 17827809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner // (undefined behavior). 178365a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateTrunc(SV, AllocaType, "tmp"); 17847809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner SrcWidth = DestWidth; 17857809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner SrcStoreWidth = DestStoreWidth; 17867809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 17877809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 17884b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17892e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // If this is a big-endian system and the store is narrower than the 17902e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // full alloca type, we need to do a shift to get the right bits. 17912e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner int ShAmt = 0; 17922e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (TD->isBigEndian()) { 17932e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 17942e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 17952e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // integers with a bitwidth that is not a multiple of 8. 17962e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ShAmt = DestStoreWidth - SrcStoreWidth - Offset; 1797800de31776356910eb877e71df9f32b0a6215324Chris Lattner } else { 17982e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner ShAmt = Offset; 17992e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 18004b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 18012e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Note: we support negative bitwidths (with shr) which are not defined. 18022e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // We do this to support (f.e.) stores off the end of a structure where 18032e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // only some bits in the structure are set. 18042e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth)); 18052e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) { 1806eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(), 1807fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson ShAmt), "tmp"); 18082e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner Mask <<= ShAmt; 18092e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) { 1810eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(), 1811fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson -ShAmt), "tmp"); 18120e7c46bc7eb68099eecd1244390dccd0a77d0875Duncan Sands Mask = Mask.lshr(-ShAmt); 18132e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 18144b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 18152e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // Mask out the bits we are about to insert from the old value, and or 18162e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner // in the new bits. 18172e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner if (SrcWidth != DestWidth) { 18182e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner assert(DestWidth > SrcWidth); 1819eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Old = Builder.CreateAnd(Old, ConstantInt::get(Context, ~Mask), "mask"); 182065a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner SV = Builder.CreateOr(Old, SV, "ins"); 1821800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 1822800de31776356910eb877e71df9f32b0a6215324Chris Lattner return SV; 1823800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1824800de31776356910eb877e71df9f32b0a6215324Chris Lattner 1825800de31776356910eb877e71df9f32b0a6215324Chris Lattner 182679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 182779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// PointsToConstantGlobal - Return true if V (possibly indirectly) points to 182879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// some part of a constant global variable. This intentionally only accepts 182979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// constant expressions because we don't can't rewrite arbitrary instructions. 183079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool PointsToConstantGlobal(Value *V) { 183179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 183279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return GV->isConstant(); 183379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 183479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (CE->getOpcode() == Instruction::BitCast || 183579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner CE->getOpcode() == Instruction::GetElementPtr) 183679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return PointsToConstantGlobal(CE->getOperand(0)); 183779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 183879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 183979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 184079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) 184179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// pointer to an alloca. Ignore any reads of the pointer, return false if we 184279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// see any stores or other unknown uses. If we see pointer arithmetic, keep 184379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// track of whether it moves the pointer (with isOffset) but otherwise traverse 184479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to 184579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the alloca, and if the source pointer is a pointer to a constant global, we 184679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// can optimize this. 184779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool isOnlyCopiedFromConstantGlobal(Value *V, Instruction *&TheCopy, 184879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner bool isOffset) { 184979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 18506e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) 18516e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // Ignore non-volatile loads, they are always ok. 18526e733d34ca487ab7ff8a6def018a933620393869Chris Lattner if (!LI->isVolatile()) 18536e733d34ca487ab7ff8a6def018a933620393869Chris Lattner continue; 18546e733d34ca487ab7ff8a6def018a933620393869Chris Lattner 185579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) { 185679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If uses of the bitcast are ok, we are ok. 185779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset)) 185879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 185979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 186079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 186179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) { 186279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the GEP has all zero indices, it doesn't offset the pointer. If it 186379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // doesn't, it does. 186479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy, 186579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner isOffset || !GEP->hasAllZeroIndices())) 186679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 186779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 186879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 186979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 187079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If this is isn't our memcpy/memmove, reject it as something we can't 187179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // handle. 18723ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner if (!isa<MemTransferInst>(*UI)) 187379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 187479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 187579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If we already have seen a copy, reject the second one. 187679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (TheCopy) return false; 187779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 187879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the pointer has been offset from the start of the alloca, we can't 187979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // safely handle this. 188079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (isOffset) return false; 188179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 188279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the memintrinsic isn't using the alloca as the dest, reject it. 188379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (UI.getOperandNo() != 1) return false; 188479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 188579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner MemIntrinsic *MI = cast<MemIntrinsic>(*UI); 188679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 188779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the source of the memcpy/move is not a constant global, reject it. 188879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!PointsToConstantGlobal(MI->getOperand(2))) 188979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 189079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 189179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Otherwise, the transform is safe. Remember the copy instruction. 189279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner TheCopy = MI; 189379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 189479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return true; 189579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 189679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 189779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only 189879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// modified by a copy from a constant global. If we can prove this, we can 189979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// replace any uses of the alloca with uses of the global directly. 19007b929dad59785f62a66f7c58615082f98441e95eVictor HernandezInstruction *SROA::isOnlyCopiedFromConstantGlobal(AllocaInst *AI) { 190179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner Instruction *TheCopy = 0; 190279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false)) 190379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return TheCopy; 190479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return 0; 190579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 1906