ScalarReplAggregates.cpp revision c87c50a39c1bc27437352feee0f6aba2d50fa1b5
1ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 10ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// This transformation implements the well known scalar replacement of 11ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregates transformation. This xform breaks up alloca instructions of 12ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// aggregate type (structure or array) into individual alloca instructions for 1338aec325604635380421a27e39ab06d55ed2458dChris Lattner// each member (if possible). Then, if possible, it transforms the individual 1438aec325604635380421a27e39ab06d55ed2458dChris Lattner// alloca instructions into nice clean scalar SSA form. 1538aec325604635380421a27e39ab06d55ed2458dChris Lattner// 1638aec325604635380421a27e39ab06d55ed2458dChris Lattner// This combines a simple SRoA algorithm with the Mem2Reg algorithm because 1738aec325604635380421a27e39ab06d55ed2458dChris Lattner// often interact, especially for C++ programs. As such, iterating between 1838aec325604635380421a27e39ab06d55ed2458dChris Lattner// SRoA, then Mem2Reg until we run out of things to promote works well. 19ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner// 20ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner//===----------------------------------------------------------------------===// 21ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 220e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattner#define DEBUG_TYPE "scalarrepl" 23ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Transforms/Scalar.h" 2438aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Constants.h" 2538aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/DerivedTypes.h" 26ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner#include "llvm/Function.h" 2779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner#include "llvm/GlobalVariable.h" 28d8e1eea678833cc2b15e4ea69a5a403ba9c3b013Misha Brukman#include "llvm/Instructions.h" 29372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/IntrinsicInst.h" 30fa5cbd6d0fbda23fd669c8718e07b19001b2d21aOwen Anderson#include "llvm/LLVMContext.h" 3172eaa0e5eb345a8483608675b86dfcfa465c784cChris Lattner#include "llvm/Module.h" 32372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner#include "llvm/Pass.h" 33b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich#include "llvm/Analysis/Dominators.h" 34c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner#include "llvm/Analysis/Loads.h" 355034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman#include "llvm/Analysis/ValueTracking.h" 3638aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Target/TargetData.h" 3738aec325604635380421a27e39ab06d55ed2458dChris Lattner#include "llvm/Transforms/Utils/PromoteMemToReg.h" 384afc90dacf309999d8b7f6c2b4b0c56af346bab5Devang Patel#include "llvm/Transforms/Utils/Local.h" 39e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner#include "llvm/Transforms/Utils/SSAUpdater.h" 40a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner#include "llvm/Support/CallSite.h" 419525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner#include "llvm/Support/Debug.h" 427d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 43a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 4465a650291d01638853aaf1e80fcc2fc86a785957Chris Lattner#include "llvm/Support/IRBuilder.h" 45a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner#include "llvm/Support/MathExtras.h" 46bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 47c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner#include "llvm/ADT/SetVector.h" 481ccd185cb49d81465a2901622e58ceae046d1d83Chris Lattner#include "llvm/ADT/SmallVector.h" 49551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 50d8664730942beb911327336d1f9db8e7efcd6813Chris Lattnerusing namespace llvm; 51d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 520e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumReplaced, "Number of allocas broken up"); 530e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumPromoted, "Number of allocas promoted"); 54c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris LattnerSTATISTIC(NumAdjusted, "Number of scalar allocas adjusted to allow promotion"); 550e5f499638c8d277b9dc4a4385712177c53b5681Chris LattnerSTATISTIC(NumConverted, "Number of aggregates converted to scalar"); 5679b3bd395dc3303cde65e18e0524ed2f70268c99Chris LattnerSTATISTIC(NumGlobals, "Number of allocas copied from constant global"); 57ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 580e5f499638c8d277b9dc4a4385712177c53b5681Chris Lattnernamespace { 593e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct SROA : public FunctionPass { 60b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich SROA(int T, bool hasDT, char &ID) 61b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich : FunctionPass(ID), HasDomTree(hasDT) { 62ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel if (T == -1) 63b0e71edb6b33f822e001500dac90acf95faacea8Chris Lattner SRThreshold = 128; 64ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel else 65ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel SRThreshold = T; 66ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel } 67794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 68ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner bool runOnFunction(Function &F); 69ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 7038aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performScalarRepl(Function &F); 7138aec325604635380421a27e39ab06d55ed2458dChris Lattner bool performPromotion(Function &F); 7238aec325604635380421a27e39ab06d55ed2458dChris Lattner 73ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner private: 74b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich bool HasDomTree; 7556c3852fb46b7754ad89b998b5968cff0c3937eeChris Lattner TargetData *TD; 766974302e3ff20746268721959efed807c7711bfcBob Wilson 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 { 856c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner /// The alloca to promote. 866c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner AllocaInst *AI; 876c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner 88145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner /// CheckedPHIs - This is a set of verified PHI nodes, to prevent infinite 89145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner /// looping and avoid redundant work. 90145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner SmallPtrSet<PHINode*, 8> CheckedPHIs; 91145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 9239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isUnsafe - This is set to true if the alloca cannot be SROA'd. 9339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isUnsafe : 1; 946974302e3ff20746268721959efed807c7711bfcBob Wilson 9539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner /// isMemCpySrc - This is true if this aggregate is memcpy'd from. 9639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpySrc : 1; 9739a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 9833b0b8d242de8d428f11e77ea734a08b47797216Zhou Sheng /// isMemCpyDst - This is true if this aggregate is memcpy'd into. 9939a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner bool isMemCpyDst : 1; 10039a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1017e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner /// hasSubelementAccess - This is true if a subelement of the alloca is 1027e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner /// ever accessed, or false if the alloca is only accessed with mem 1037e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner /// intrinsics or load/store that only access the entire alloca at once. 1047e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner bool hasSubelementAccess : 1; 1057e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner 1067e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner /// hasALoadOrStore - This is true if there are any loads or stores to it. 1077e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner /// The alloca may just be accessed with memcpy, for example, which would 1087e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner /// not set this. 1097e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner bool hasALoadOrStore : 1; 1107e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner 1116c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner explicit AllocaInfo(AllocaInst *ai) 1126c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner : AI(ai), isUnsafe(false), isMemCpySrc(false), isMemCpyDst(false), 1137e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner hasSubelementAccess(false), hasALoadOrStore(false) {} 11439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner }; 1156974302e3ff20746268721959efed807c7711bfcBob Wilson 116ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel unsigned SRThreshold; 117ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel 118d01a0da090407762fe3b770d84f049d72d06467eChris Lattner void MarkUnsafe(AllocaInfo &I, Instruction *User) { 119d01a0da090407762fe3b770d84f049d72d06467eChris Lattner I.isUnsafe = true; 120d01a0da090407762fe3b770d84f049d72d06467eChris Lattner DEBUG(dbgs() << " Transformation preventing inst: " << *User << '\n'); 121d01a0da090407762fe3b770d84f049d72d06467eChris Lattner } 12239a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1236c146eefbf75875250af37a0f1ea70fc6b4716eeVictor Hernandez bool isSafeAllocaToScalarRepl(AllocaInst *AI); 12439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 1256c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner void isSafeForScalarRepl(Instruction *I, uint64_t Offset, AllocaInfo &Info); 126145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner void isSafePHISelectUseForScalarRepl(Instruction *User, uint64_t Offset, 127145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner AllocaInfo &Info); 1286c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner void isSafeGEP(GetElementPtrInst *GEPI, uint64_t &Offset, AllocaInfo &Info); 1296c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner void isSafeMemAccess(uint64_t Offset, uint64_t MemSize, 130d01a0da090407762fe3b770d84f049d72d06467eChris Lattner const Type *MemOpType, bool isStore, AllocaInfo &Info, 131145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner Instruction *TheAccess, bool AllowWholeAccess); 132b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson bool TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size); 133e88728d757d3090f1c0885b78d3675a7e143a2f9Bob Wilson uint64_t FindElementAndOffset(const Type *&T, uint64_t &Offset, 134e88728d757d3090f1c0885b78d3675a7e143a2f9Bob Wilson const Type *&IdxTy); 1356974302e3ff20746268721959efed807c7711bfcBob Wilson 1366974302e3ff20746268721959efed807c7711bfcBob Wilson void DoScalarReplacement(AllocaInst *AI, 1377b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez std::vector<AllocaInst*> &WorkList); 138b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void DeleteDeadInstructions(); 1396974302e3ff20746268721959efed807c7711bfcBob Wilson 140b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 141b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 142b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 143b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 144b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 145b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson SmallVector<AllocaInst*, 32> &NewElts); 146b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 1477b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI, 148d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1497b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 150d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1517b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 1526e733d34ca487ab7ff8a6def018a933620393869Chris Lattner SmallVector<AllocaInst*, 32> &NewElts); 1536974302e3ff20746268721959efed807c7711bfcBob Wilson 15431d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner static MemTransferInst *isOnlyCopiedFromConstantGlobal(AllocaInst *AI); 155ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner }; 156b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner 157b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich // SROA_DT - SROA that uses DominatorTree. 158b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich struct SROA_DT : public SROA { 159b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner static char ID; 160b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner public: 161b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich SROA_DT(int T = -1) : SROA(T, true, ID) { 162b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich initializeSROA_DTPass(*PassRegistry::getPassRegistry()); 163b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner } 164b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner 165b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 166b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner // will not alter the CFG, so say so. 167b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 168b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner AU.addRequired<DominatorTree>(); 169b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner AU.setPreservesCFG(); 170b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner } 171b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner }; 172b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner 173b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner // SROA_SSAUp - SROA that uses SSAUpdater. 174b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner struct SROA_SSAUp : public SROA { 175b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner static char ID; 176b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner public: 177b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner SROA_SSAUp(int T = -1) : SROA(T, false, ID) { 178b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner initializeSROA_SSAUpPass(*PassRegistry::getPassRegistry()); 179b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner } 180b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner 181b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner // getAnalysisUsage - This pass does not require any passes, but we know it 182b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner // will not alter the CFG, so say so. 183b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 184b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner AU.setPreservesCFG(); 185b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner } 186b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner }; 187b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner 188ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 189ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 190b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarichchar SROA_DT::ID = 0; 191b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattnerchar SROA_SSAUp::ID = 0; 192b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner 193b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron ZwarichINITIALIZE_PASS_BEGIN(SROA_DT, "scalarrepl", 194b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich "Scalar Replacement of Aggregates (DT)", false, false) 1952ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 196b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron ZwarichINITIALIZE_PASS_END(SROA_DT, "scalarrepl", 197b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich "Scalar Replacement of Aggregates (DT)", false, false) 198b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner 199b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris LattnerINITIALIZE_PASS_BEGIN(SROA_SSAUp, "scalarrepl-ssa", 200b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner "Scalar Replacement of Aggregates (SSAUp)", false, false) 201b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris LattnerINITIALIZE_PASS_END(SROA_SSAUp, "scalarrepl-ssa", 202b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner "Scalar Replacement of Aggregates (SSAUp)", false, false) 203844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 204d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke// Public interface to the ScalarReplAggregates pass 205b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris LattnerFunctionPass *llvm::createScalarReplAggregatesPass(int Threshold, 206b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich bool UseDomTree) { 207b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich if (UseDomTree) 208b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich return new SROA_DT(Threshold); 209b352d6eb49927a7c707cbd9046cfc525b0c3f2d7Chris Lattner return new SROA_SSAUp(Threshold); 210ff366850aa9956e167e78d4f5b57aae10d8c5779Devang Patel} 211ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 212ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 2134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 2144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// Convert To Scalar Optimization. 2154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 216963a97f1a365c8d09ca681e922371f9ec3473ee8Chris Lattner 217c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattnernamespace { 218a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// ConvertToScalarInfo - This class implements the "Convert To Scalar" 219a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// optimization, which scans the uses of an alloca and determines if it can 220a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// rewrite it in terms of a single new alloca that can be mem2reg'd. 2214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerclass ConvertToScalarInfo { 222c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner /// AllocaSize - The size of the alloca being considered. 223c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner unsigned AllocaSize; 224593375d04ab32be0161607a741d310172f142b93Chris Lattner const TargetData &TD; 2256974302e3ff20746268721959efed807c7711bfcBob Wilson 226a0bada729ffaa1bfc80ef25935bdc5a67432708fChris Lattner /// IsNotTrivial - This is set to true if there is some access to the object 227a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// which means that mem2reg can't promote it. 228c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner bool IsNotTrivial; 2296974302e3ff20746268721959efed807c7711bfcBob Wilson 230a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// VectorTy - This tracks the type that we should promote the vector to if 231a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// it is possible to turn it into a vector. This starts out null, and if it 232a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// isn't possible to turn into a vector type, it gets set to VoidTy. 233c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner const Type *VectorTy; 2346974302e3ff20746268721959efed807c7711bfcBob Wilson 235a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// HadAVector - True if there is at least one vector access to the alloca. 236a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// We don't want to turn random arrays into vectors and use vector element 237a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// insert/extract, but if there are element accesses to something that is 238a001b664988f759d194f3d5d880c61449219fc2eChris Lattner /// also declared as a vector, we do want to promote to a vector. 239c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner bool HadAVector; 240c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 2414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerpublic: 242593375d04ab32be0161607a741d310172f142b93Chris Lattner explicit ConvertToScalarInfo(unsigned Size, const TargetData &td) 243593375d04ab32be0161607a741d310172f142b93Chris Lattner : AllocaSize(Size), TD(td) { 244c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner IsNotTrivial = false; 245c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner VectorTy = 0; 246c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner HadAVector = false; 247c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner } 2486974302e3ff20746268721959efed807c7711bfcBob Wilson 249a001b664988f759d194f3d5d880c61449219fc2eChris Lattner AllocaInst *TryConvert(AllocaInst *AI); 2506974302e3ff20746268721959efed807c7711bfcBob Wilson 2514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerprivate: 252593375d04ab32be0161607a741d310172f142b93Chris Lattner bool CanConvertToScalar(Value *V, uint64_t Offset); 253593375d04ab32be0161607a741d310172f142b93Chris Lattner void MergeInType(const Type *In, uint64_t Offset); 254593375d04ab32be0161607a741d310172f142b93Chris Lattner void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset); 2556974302e3ff20746268721959efed807c7711bfcBob Wilson 256593375d04ab32be0161607a741d310172f142b93Chris Lattner Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType, 257593375d04ab32be0161607a741d310172f142b93Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 258593375d04ab32be0161607a741d310172f142b93Chris Lattner Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal, 259593375d04ab32be0161607a741d310172f142b93Chris Lattner uint64_t Offset, IRBuilder<> &Builder); 260c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner}; 261c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner} // end anonymous namespace. 262c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 26391abace4ef6fdfe01bcebfb8e90938e71f8a5c4fChris Lattner 264a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// TryConvert - Analyze the specified alloca, and if it is safe to do so, 265a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// rewrite it to be a new alloca which is mem2reg'able. This returns the new 266a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// alloca if possible or null if not. 267a001b664988f759d194f3d5d880c61449219fc2eChris LattnerAllocaInst *ConvertToScalarInfo::TryConvert(AllocaInst *AI) { 268a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we can't convert this scalar, or if mem2reg can trivially do it, bail 269a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // out. 270a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (!CanConvertToScalar(AI, 0) || !IsNotTrivial) 271a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return 0; 2726974302e3ff20746268721959efed807c7711bfcBob Wilson 273a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we were able to find a vector type that can handle this with 274a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // insert/extract elements, and if there was at least one use that had 275a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // a vector type, promote this to a vector. We don't want to promote 276a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // random stuff that doesn't use vectors (e.g. <9 x double>) because then 277a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // we just get a lot of insert/extracts. If at least one vector is 278a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // involved, then we probably really do have a union of vector/array. 279a001b664988f759d194f3d5d880c61449219fc2eChris Lattner const Type *NewTy; 28085a7c690852d6151acff0d8821762d75bc774ab4Chris Lattner if (VectorTy && VectorTy->isVectorTy() && HadAVector) { 281a001b664988f759d194f3d5d880c61449219fc2eChris Lattner DEBUG(dbgs() << "CONVERT TO VECTOR: " << *AI << "\n TYPE = " 282a001b664988f759d194f3d5d880c61449219fc2eChris Lattner << *VectorTy << '\n'); 283a001b664988f759d194f3d5d880c61449219fc2eChris Lattner NewTy = VectorTy; // Use the vector type. 284a001b664988f759d194f3d5d880c61449219fc2eChris Lattner } else { 285a001b664988f759d194f3d5d880c61449219fc2eChris Lattner DEBUG(dbgs() << "CONVERT TO SCALAR INTEGER: " << *AI << "\n"); 286a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // Create and insert the integer alloca. 287a001b664988f759d194f3d5d880c61449219fc2eChris Lattner NewTy = IntegerType::get(AI->getContext(), AllocaSize*8); 288a001b664988f759d194f3d5d880c61449219fc2eChris Lattner } 289a001b664988f759d194f3d5d880c61449219fc2eChris Lattner AllocaInst *NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin()); 290a001b664988f759d194f3d5d880c61449219fc2eChris Lattner ConvertUsesToScalar(AI, NewAI, 0); 291a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return NewAI; 292a001b664988f759d194f3d5d880c61449219fc2eChris Lattner} 293a001b664988f759d194f3d5d880c61449219fc2eChris Lattner 294a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// MergeInType - Add the 'In' type to the accumulated vector type (VectorTy) 295a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// so far at the offset specified by Offset (which is specified in bytes). 2964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 2974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// There are two cases we handle here: 2984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 1) A union of vector types of the same size and potentially its elements. 2994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Here we turn element accesses into insert/extract element operations. 3004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This promotes a <4 x float> with a store of float to the third element 3014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// into a <4 x float> that uses insert element. 3024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 2) A fully general blob of memory, which we turn into some (potentially 3034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// large) integer type with extract and insert operations where the loads 304a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// and stores would mutate the memory. We mark this by setting VectorTy 305a001b664988f759d194f3d5d880c61449219fc2eChris Lattner/// to VoidTy. 3064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid ConvertToScalarInfo::MergeInType(const Type *In, uint64_t Offset) { 307a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // If we already decided to turn this into a blob of integer memory, there is 308a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // nothing to be done. 3094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy && VectorTy->isVoidTy()) 3104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 3116974302e3ff20746268721959efed807c7711bfcBob Wilson 3124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this could be contributing to a vector, analyze it. 313c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 3144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the In type is a vector that is the same size as the alloca, see if it 3154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // matches the existing VecTy. 3164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VInTy = dyn_cast<VectorType>(In)) { 317a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // Remember if we saw a vector type. 318a001b664988f759d194f3d5d880c61449219fc2eChris Lattner HadAVector = true; 3196974302e3ff20746268721959efed807c7711bfcBob Wilson 3204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) { 3214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we're storing/loading a vector of the right size, allow it as a 3224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // vector. If this the first vector we see, remember the type so that 323a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // we know the element size. If this is a subsequent access, ignore it 324a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // even if it is a differing type but the same size. Worst case we can 325a001b664988f759d194f3d5d880c61449219fc2eChris Lattner // bitcast the resultant vectors. 3264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy == 0) 3274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = VInTy; 3284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 3294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 3304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (In->isFloatTy() || In->isDoubleTy() || 3314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner (In->isIntegerTy() && In->getPrimitiveSizeInBits() >= 8 && 3324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner isPowerOf2_32(In->getPrimitiveSizeInBits()))) { 3334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we're accessing something that could be an element of a vector, see 3344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // if the implied vector agrees with what we already have and if Offset is 3354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // compatible with it. 3364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = In->getPrimitiveSizeInBits()/8; 3374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset % EltSize == 0 && AllocaSize % EltSize == 0 && 3386974302e3ff20746268721959efed807c7711bfcBob Wilson (VectorTy == 0 || 3394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner cast<VectorType>(VectorTy)->getElementType() 3404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ->getPrimitiveSizeInBits()/8 == EltSize)) { 3414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (VectorTy == 0) 3424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = VectorType::get(In, AllocaSize/EltSize); 3434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 3444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 3454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 3466974302e3ff20746268721959efed807c7711bfcBob Wilson 3474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, we have a case that we can't handle with an optimized vector 3484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // form. We can still turn this into a large integer. 3494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner VectorTy = Type::getVoidTy(In->getContext()); 3504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 351c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 3524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// CanConvertToScalar - V is a pointer. If we can convert the pointee and all 3534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// its accesses to a single vector type, return true and set VecTy to 3544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the new type. If we could convert the alloca into a single promotable 3554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer, return true but set VecTy to VoidTy. Further, if the use is not a 3564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// completely trivial use that mem2reg could promote, set IsNotTrivial. Offset 3574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// is the current offset from the base of the alloca being analyzed. 3584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 3594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// If we see at least one access to the value that is as a vector type, set the 3604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// SawVec flag. 3614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool ConvertToScalarInfo::CanConvertToScalar(Value *V, uint64_t Offset) { 3624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 3634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(*UI); 3646974302e3ff20746268721959efed807c7711bfcBob Wilson 3654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 3664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Don't break volatile loads. 3674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LI->isVolatile()) 3684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3690488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen // Don't touch MMX operations. 3700488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen if (LI->getType()->isX86_MMXTy()) 3710488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen return false; 3724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MergeInType(LI->getType(), Offset); 373add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner continue; 374add2bd7f5941537a97a41e037ae2277fbeed0b4fChris Lattner } 3756974302e3ff20746268721959efed807c7711bfcBob Wilson 3764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 3774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing the pointer, not into the value? 3784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SI->getOperand(0) == V || SI->isVolatile()) return false; 3790488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen // Don't touch MMX operations. 3800488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen if (SI->getOperand(0)->getType()->isX86_MMXTy()) 3810488fb649a56b7fc89a5814df5308813f9e5a85dDale Johannesen return false; 3824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MergeInType(SI->getOperand(0)->getType(), Offset); 3837809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 3847809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner } 3856974302e3ff20746268721959efed807c7711bfcBob Wilson 3864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { 387a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 3884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!CanConvertToScalar(BCI, Offset)) 3894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3903992feb075b27ff37b63017078a977206f97d10dBob Wilson continue; 3913992feb075b27ff37b63017078a977206f97d10dBob Wilson } 3923992feb075b27ff37b63017078a977206f97d10dBob Wilson 3934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 3944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a GEP with a variable indices, we can't handle it. 3954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!GEP->hasAllConstantIndices()) 3964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 3976974302e3ff20746268721959efed807c7711bfcBob Wilson 3984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset that this GEP adds to the pointer. 3994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 4004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(), 4014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 4024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // See if all uses can be converted. 4034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!CanConvertToScalar(GEP, Offset+GEPOffset)) 4044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 405a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 4067809ecd5b019d26498499121f4d9c0b7de2f0a14Chris Lattner continue; 4074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 408ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner 4094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 4104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // handle it. 4114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 4124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Store of constant value and constant size. 413a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (!isa<ConstantInt>(MSI->getValue()) || 414a001b664988f759d194f3d5d880c61449219fc2eChris Lattner !isa<ConstantInt>(MSI->getLength())) 415a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return false; 416a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 417a001b664988f759d194f3d5d880c61449219fc2eChris Lattner continue; 4184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 419fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 4204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 4214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // can handle it like a load or store of the scalar type. 4224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 423a001b664988f759d194f3d5d880c61449219fc2eChris Lattner ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength()); 424a001b664988f759d194f3d5d880c61449219fc2eChris Lattner if (Len == 0 || Len->getZExtValue() != AllocaSize || Offset != 0) 425a001b664988f759d194f3d5d880c61449219fc2eChris Lattner return false; 4266974302e3ff20746268721959efed807c7711bfcBob Wilson 427a001b664988f759d194f3d5d880c61449219fc2eChris Lattner IsNotTrivial = true; // Can't be mem2reg'd. 428a001b664988f759d194f3d5d880c61449219fc2eChris Lattner continue; 429ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner } 4306974302e3ff20746268721959efed807c7711bfcBob Wilson 4314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, we cannot handle this! 4324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 433a10b29b84b63c448b7cb423598d3a38b0f55cddbChris Lattner } 4346974302e3ff20746268721959efed807c7711bfcBob Wilson 4354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 436ed7b41ea90a17c826f195acbc456c4bb733113d6Chris Lattner} 437a59adc40153f3e0f9843952c127d179b5ebe6c4cChris Lattner 4384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca 4394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// directly. This happens when we are converting an "integer union" to a 4404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// single integer scalar, or when we are converting a "vector union" to a 4414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// vector with insert/extractelement instructions. 4424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 4434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 4444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. By the end of this, there should be no uses of Ptr. 4454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid ConvertToScalarInfo::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, 4464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset) { 4474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!Ptr->use_empty()) { 4484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(Ptr->use_back()); 449b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 4504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) { 4514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertUsesToScalar(CI, NewAI, Offset); 4524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner CI->eraseFromParent(); 4534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 455b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 4564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) { 4574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset that this GEP adds to the pointer. 4584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end()); 4594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(), 4604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 4614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8); 4624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner GEP->eraseFromParent(); 4634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4656974302e3ff20746268721959efed807c7711bfcBob Wilson 46661db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner IRBuilder<> Builder(User); 4676974302e3ff20746268721959efed807c7711bfcBob Wilson 4684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 4694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The load is a bit extract from NewAI shifted right by Offset bits. 4704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp"); 4714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *NewLoadVal 4724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder); 4734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(NewLoadVal); 4744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->eraseFromParent(); 4754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4776974302e3ff20746268721959efed807c7711bfcBob Wilson 4784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 4794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(SI->getOperand(0) != Ptr && "Consistency error!"); 4804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in"); 4814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset, 4824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 4834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(New, NewAI); 4844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SI->eraseFromParent(); 4856974302e3ff20746268721959efed807c7711bfcBob Wilson 4864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load we just inserted is now dead, then the inserted store 4874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // overwrote the entire thing. 4884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Old->use_empty()) 4894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old->eraseFromParent(); 4904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 4914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 4926974302e3ff20746268721959efed807c7711bfcBob Wilson 4934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a constant sized memset of a constant value (e.g. 0) we can 4944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // transform it into a store of the expanded constant value. 4954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) { 4964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MSI->getRawDest() == Ptr && "Consistency error!"); 4974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue(); 4984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (NumBytes != 0) { 4994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue(); 5006974302e3ff20746268721959efed807c7711bfcBob Wilson 5014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the value replicated the right number of times. 5024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt APVal(NumBytes*8, Val); 5032674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 5044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Splat the value if non-zero. 5054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val) 5064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 1; i != NumBytes; ++i) 5074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APVal |= APVal << 8; 5086974302e3ff20746268721959efed807c7711bfcBob Wilson 5094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in"); 5104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *New = ConvertScalar_InsertValue( 5114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(User->getContext(), APVal), 5124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old, Offset, Builder); 5134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(New, NewAI); 5146974302e3ff20746268721959efed807c7711bfcBob Wilson 5154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load we just inserted is now dead, then the memset overwrote 5164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the entire thing. 5174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Old->use_empty()) 5186974302e3ff20746268721959efed807c7711bfcBob Wilson Old->eraseFromParent(); 5194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MSI->eraseFromParent(); 5214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 522b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 523fca55c8ac7d12e4139ad0ab7d74b76c47935aef6Daniel Dunbar 5244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy or memmove into or out of the whole allocation, we 5254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // can handle it like a load or store of the scalar type. 5264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) { 5274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(Offset == 0 && "must be store to start of alloca"); 5286974302e3ff20746268721959efed807c7711bfcBob Wilson 5294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the source and destination are both to the same alloca, then this is 5304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // a noop copy-to-self, just delete it. Otherwise, emit a load and store 5314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // as appropriate. 5325034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman AllocaInst *OrigAI = cast<AllocaInst>(GetUnderlyingObject(Ptr, 0)); 5336974302e3ff20746268721959efed807c7711bfcBob Wilson 5345034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman if (GetUnderlyingObject(MTI->getSource(), 0) != OrigAI) { 5354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Dest must be OrigAI, change this to be a load from the original 5364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // pointer (bitcasted), then a store to our new alloca. 5374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?"); 5384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcPtr = MTI->getSource(); 539e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang const PointerType* SPTy = cast<PointerType>(SrcPtr->getType()); 540e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang const PointerType* AIPTy = cast<PointerType>(NewAI->getType()); 541e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang if (SPTy->getAddressSpace() != AIPTy->getAddressSpace()) { 542e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang AIPTy = PointerType::get(AIPTy->getElementType(), 543e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang SPTy->getAddressSpace()); 544e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang } 545e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang SrcPtr = Builder.CreateBitCast(SrcPtr, AIPTy); 546e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang 5474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval"); 5484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcVal->setAlignment(MTI->getAlignment()); 5494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder.CreateStore(SrcVal, NewAI); 5505034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman } else if (GetUnderlyingObject(MTI->getDest(), 0) != OrigAI) { 5514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Src must be OrigAI, change this to be a load from NewAI then a store 5524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // through the original dest pointer (bitcasted). 5534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?"); 5544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval"); 555b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 556e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang const PointerType* DPTy = cast<PointerType>(MTI->getDest()->getType()); 557e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang const PointerType* AIPTy = cast<PointerType>(NewAI->getType()); 558e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang if (DPTy->getAddressSpace() != AIPTy->getAddressSpace()) { 559e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang AIPTy = PointerType::get(AIPTy->getElementType(), 560e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang DPTy->getAddressSpace()); 561e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang } 562e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), AIPTy); 563e90a6333c3a4514f88c8a3dddd10d9bcddcd6d85Mon P Wang 5644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr); 5654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewStore->setAlignment(MTI->getAlignment()); 5664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 5674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Noop transfer. Src == Dst 5684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5695fac55fafb53fde5c548bcd08e07418e9d8e549fMatthijs Kooijman 5704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MTI->eraseFromParent(); 5714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 5724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 5736974302e3ff20746268721959efed807c7711bfcBob Wilson 5744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner llvm_unreachable("Unsupported operation!"); 57588e6dc8bf14e8a98888f62173a6581386b8d29a0Chris Lattner } 5762674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar} 5772674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 5784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer 5794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or vector value FromVal, extracting the bits from the offset specified by 5804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset. This returns the value, which is of type ToType. 5814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 5824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This happens when we are converting an "integer union" to a single 5834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer scalar, or when we are converting a "vector union" to a vector with 5844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// insert/extractelement instructions. 5854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 5864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 5874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. 5884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerValue *ConvertToScalarInfo:: 5894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerConvertScalar_ExtractValue(Value *FromVal, const Type *ToType, 5904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset, IRBuilder<> &Builder) { 5914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the load is of the whole new alloca, no conversion is needed. 5924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FromVal->getType() == ToType && Offset == 0) 5934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return FromVal; 5944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 5954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the result alloca is a vector type, this is either an element 5964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // access or a bitcast to another vector type of the same size. 5974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) { 5984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ToType->isVectorTy()) 5994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Builder.CreateBitCast(FromVal, ToType, "tmp"); 6004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise it must be an element access. 6024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Elt = 0; 6034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset) { 6044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType()); 6054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Elt = Offset/EltSize; 6064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(EltSize*Elt == Offset && "Invalid modulus in validity checking"); 607b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 6084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Return the element extracted out of it. 6094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *V = Builder.CreateExtractElement(FromVal, ConstantInt::get( 6104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Type::getInt32Ty(FromVal->getContext()), Elt), "tmp"); 6114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (V->getType() != ToType) 6124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner V = Builder.CreateBitCast(V, ToType, "tmp"); 6134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return V; 6144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 6156974302e3ff20746268721959efed807c7711bfcBob Wilson 6164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If ToType is a first class aggregate, extract out each of the pieces and 6174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // use insertvalue's to form the FCA. 6184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(ToType)) { 6194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout &Layout = *TD.getStructLayout(ST); 6204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Res = UndefValue::get(ST); 6214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 6224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i), 6234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+Layout.getElementOffsetInBits(i), 6244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 6254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 6264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 6274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Res; 6284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 6296974302e3ff20746268721959efed807c7711bfcBob Wilson 6304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(ToType)) { 6314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType()); 6324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Res = UndefValue::get(AT); 6334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 6344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(), 6354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+i*EltSize, Builder); 6364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Res = Builder.CreateInsertValue(Res, Elt, i, "tmp"); 6374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 6384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Res; 639b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 6402674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 6414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, this must be a union that was converted to an integer value. 6424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const IntegerType *NTy = cast<IntegerType>(FromVal->getType()); 643b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 6444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a big-endian system and the load is narrower than the 6454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // full alloca type, we need to do a shift to get the right bits. 6464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner int ShAmt = 0; 6474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD.isBigEndian()) { 6484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 6494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 6504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integers with a bitwidth that is not a multiple of 8. 6514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = TD.getTypeStoreSizeInBits(NTy) - 6524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD.getTypeStoreSizeInBits(ToType) - Offset; 653b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } else { 6544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = Offset; 655b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 656b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 6574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Note: we support negative bitwidths (with shl) which are not defined. 6584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // We do this to support (f.e.) loads off the end of a structure where 6594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // only some bits are used. 6604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth()) 6614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateLShr(FromVal, 6624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(FromVal->getType(), 6634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt), "tmp"); 6644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth()) 6656974302e3ff20746268721959efed807c7711bfcBob Wilson FromVal = Builder.CreateShl(FromVal, 6664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(FromVal->getType(), 6674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner -ShAmt), "tmp"); 668b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 6694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Finally, unconditionally truncate the integer to the right width. 6704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned LIBitWidth = TD.getTypeSizeInBits(ToType); 6714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (LIBitWidth < NTy->getBitWidth()) 6724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = 6736974302e3ff20746268721959efed807c7711bfcBob Wilson Builder.CreateTrunc(FromVal, IntegerType::get(FromVal->getContext(), 6744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LIBitWidth), "tmp"); 6754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (LIBitWidth > NTy->getBitWidth()) 6764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = 6776974302e3ff20746268721959efed807c7711bfcBob Wilson Builder.CreateZExt(FromVal, IntegerType::get(FromVal->getContext(), 6784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LIBitWidth), "tmp"); 6794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 6804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the result is an integer, this is a trunc or bitcast. 6814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ToType->isIntegerTy()) { 6824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Should be done. 6834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ToType->isFloatingPointTy() || ToType->isVectorTy()) { 6844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Just do a bitcast, we know the sizes match up. 6854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp"); 6864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 6874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise must be a pointer. 6884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp"); 689372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 6904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(FromVal->getType() == ToType && "Didn't convert right?"); 6914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return FromVal; 692372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 693372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 6944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer 6954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or vector value "Old" at the offset specified by Offset. 6964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 6974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// This happens when we are converting an "integer union" to a 6984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// single integer scalar, or when we are converting a "vector union" to a 6994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// vector with insert/extractelement instructions. 7004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// 7014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset is an offset from the original alloca, in bits that need to be 7024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// shifted to the right. 7034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerValue *ConvertToScalarInfo:: 7044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris LattnerConvertScalar_InsertValue(Value *SV, Value *Old, 7054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Offset, IRBuilder<> &Builder) { 7064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Convert the stored type to the actual type, shift it left to insert 7074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // then 'or' into place. 7084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaType = Old->getType(); 7094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LLVMContext &Context = Old->getContext(); 7102674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 7114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const VectorType *VTy = dyn_cast<VectorType>(AllocaType)) { 7124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t VecSize = TD.getTypeAllocSizeInBits(VTy); 7134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ValSize = TD.getTypeAllocSizeInBits(SV->getType()); 7146974302e3ff20746268721959efed807c7711bfcBob Wilson 7154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Changing the whole vector with memset or with an access of a different 7164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // vector type? 7174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ValSize == VecSize) 7184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Builder.CreateBitCast(SV, AllocaType, "tmp"); 7192674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar 7204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType()); 7214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Must be an element insertion. 7234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned Elt = Offset/EltSize; 7246974302e3ff20746268721959efed807c7711bfcBob Wilson 7254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType() != VTy->getElementType()) 7264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp"); 7276974302e3ff20746268721959efed807c7711bfcBob Wilson 7286974302e3ff20746268721959efed807c7711bfcBob Wilson SV = Builder.CreateInsertElement(Old, SV, 7294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(Type::getInt32Ty(SV->getContext()), Elt), 7304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "tmp"); 7314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return SV; 732b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson } 7336974302e3ff20746268721959efed807c7711bfcBob Wilson 7344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SV is a first-class aggregate value, insert each value recursively. 7354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(SV->getType())) { 7364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout &Layout = *TD.getStructLayout(ST); 7374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) { 7384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 7396974302e3ff20746268721959efed807c7711bfcBob Wilson Old = ConvertScalar_InsertValue(Elt, Old, 7404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset+Layout.getElementOffsetInBits(i), 7414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Builder); 7424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Old; 7444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7456974302e3ff20746268721959efed807c7711bfcBob Wilson 7464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) { 7474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType()); 7484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 7494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = Builder.CreateExtractValue(SV, i, "tmp"); 7504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder); 7514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Old; 7534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SV is a float, convert it to the appropriate integer type. 7564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If it is a pointer, do the same. 7574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned SrcWidth = TD.getTypeSizeInBits(SV->getType()); 7584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned DestWidth = TD.getTypeSizeInBits(AllocaType); 7594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned SrcStoreWidth = TD.getTypeStoreSizeInBits(SV->getType()); 7604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned DestStoreWidth = TD.getTypeStoreSizeInBits(AllocaType); 7614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType()->isFloatingPointTy() || SV->getType()->isVectorTy()) 7624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateBitCast(SV, 7634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IntegerType::get(SV->getContext(),SrcWidth), "tmp"); 7644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (SV->getType()->isPointerTy()) 7654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreatePtrToInt(SV, TD.getIntPtrType(SV->getContext()), "tmp"); 7664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero extend or truncate the value if needed. 7684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType() != AllocaType) { 7694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SV->getType()->getPrimitiveSizeInBits() < 7704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaType->getPrimitiveSizeInBits()) 7714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateZExt(SV, AllocaType, "tmp"); 7724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else { 7734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncation may be needed if storing more than the alloca can hold 7744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (undefined behavior). 7754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateTrunc(SV, AllocaType, "tmp"); 7764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcWidth = DestWidth; 7774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcStoreWidth = DestStoreWidth; 7784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a big-endian system and the store is narrower than the 7824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // full alloca type, we need to do a shift to get the right bits. 7834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner int ShAmt = 0; 7844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD.isBigEndian()) { 7854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // On big-endian machines, the lowest bit is stored at the bit offset 7864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // from the pointer given by getTypeStoreSizeInBits. This matters for 7874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integers with a bitwidth that is not a multiple of 8. 7884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = DestStoreWidth - SrcStoreWidth - Offset; 7894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 7904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt = Offset; 7914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 7924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 7934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Note: we support negative bitwidths (with shr) which are not defined. 7944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // We do this to support (f.e.) stores off the end of a structure where 7954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // only some bits in the structure are set. 7964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth)); 7974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) { 7984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(), 7994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ShAmt), "tmp"); 8004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Mask <<= ShAmt; 8014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) { 8024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(), 8034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner -ShAmt), "tmp"); 8044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Mask = Mask.lshr(-ShAmt); 8054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 8064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Mask out the bits we are about to insert from the old value, and or 8084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // in the new bits. 8094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcWidth != DestWidth) { 8104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(DestWidth > SrcWidth); 8114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Old = Builder.CreateAnd(Old, ConstantInt::get(Context, ~Mask), "mask"); 8124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SV = Builder.CreateOr(Old, SV, "ins"); 8134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 8144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return SV; 815b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson} 816b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 817b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 8184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 8194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// SRoA Driver 8204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner//===----------------------------------------------------------------------===// 821b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 822b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 8234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::runOnFunction(Function &F) { 8244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD = getAnalysisIfAvailable<TargetData>(); 825b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 8264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = performPromotion(F); 827b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 8284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // FIXME: ScalarRepl currently depends on TargetData more than it 8294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // theoretically needs to. It should be refactored in order to support 8304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // target-independent IR. Until this is done, just skip the actual 8314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // scalar-replacement portion of this pass. 8324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!TD) return Changed; 8334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (1) { 8354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool LocalChange = performScalarRepl(F); 8364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!LocalChange) break; // No need to repromote if no scalarrepl 8374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 8384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LocalChange = performPromotion(F); 8394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!LocalChange) break; // No need to re-scalarrepl if no promotion 8402674089cefe519195e00bdf879647438cfb1cb0fDaniel Dunbar } 8414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 8424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 843d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner} 844d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner 845d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattnernamespace { 846d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattnerclass AllocaPromoter : public LoadAndStorePromoter { 847d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner AllocaInst *AI; 848d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattnerpublic: 849deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner AllocaPromoter(const SmallVectorImpl<Instruction*> &Insts, SSAUpdater &S) 850deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner : LoadAndStorePromoter(Insts, S), AI(0) {} 851e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner 852deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner void run(AllocaInst *AI, const SmallVectorImpl<Instruction*> &Insts) { 853d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner // Remember which alloca we're promoting (for isInstInList). 854d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner this->AI = AI; 855deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner LoadAndStorePromoter::run(Insts); 856d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner AI->eraseFromParent(); 857e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner } 858e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner 859d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner virtual bool isInstInList(Instruction *I, 860d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner const SmallVectorImpl<Instruction*> &Insts) const { 861d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(I)) 862d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner return LI->getOperand(0) == AI; 863d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner return cast<StoreInst>(I)->getPointerOperand() == AI; 864e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner } 865d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner}; 866d0f56132cfa6e25fb9692e84ea12444c86b92ae4Chris Lattner} // end anon namespace 86778c50b8cd68d266d4ed6f8eca443cf8142a01204Bob Wilson 868c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// isSafeSelectToSpeculate - Select instructions that use an alloca and are 869c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// subsequently loaded can be rewritten to load both input pointers and then 870c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// select between the result, allowing the load of the alloca to be promoted. 871c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// From this: 872c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// %P2 = select i1 %cond, i32* %Alloca, i32* %Other 873c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// %V = load i32* %P2 874c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// to: 875c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// %V1 = load i32* %Alloca -> will be mem2reg'd 876c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// %V2 = load i32* %Other 877c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// %V = select i1 %cond, i32 %V1, i32* %V2 878c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// 879c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// We can do this to a select if its only uses are loads and if the operand to 880c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// the select can be loaded unconditionally. 881c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattnerstatic bool isSafeSelectToSpeculate(SelectInst *SI, const TargetData *TD) { 882c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner bool TDerefable = SI->getTrueValue()->isDereferenceablePointer(); 883c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner bool FDerefable = SI->getFalseValue()->isDereferenceablePointer(); 884c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 885c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner for (Value::use_iterator UI = SI->use_begin(), UE = SI->use_end(); 886c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner UI != UE; ++UI) { 887c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner LoadInst *LI = dyn_cast<LoadInst>(*UI); 888c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (LI == 0 || LI->isVolatile()) return false; 889c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 890c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // Both operands to the select need to be deferencable, either absolutely 891c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // (e.g. allocas) or at this point because we can see other accesses to it. 892c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (!TDerefable && !isSafeToLoadUnconditionally(SI->getTrueValue(), LI, 893c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner LI->getAlignment(), TD)) 894c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return false; 895c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (!FDerefable && !isSafeToLoadUnconditionally(SI->getFalseValue(), LI, 896c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner LI->getAlignment(), TD)) 897c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return false; 898c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 899c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 900c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return true; 901c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner} 902c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 903c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 904c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// tryToMakeAllocaBePromotable - This returns true if the alloca only has 905c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// direct (non-volatile) loads and stores to it. If the alloca is close but 906c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// not quite there, this will transform the code to allow promotion. As such, 907c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner/// it is a non-pure predicate. 908c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattnerstatic bool tryToMakeAllocaBePromotable(AllocaInst *AI, const TargetData *TD) { 909c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner SetVector<Instruction*, SmallVector<Instruction*, 4>, 910c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner SmallPtrSet<Instruction*, 4> > InstsToRewrite; 911c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 912c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end(); 913c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner UI != UE; ++UI) { 914c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner User *U = *UI; 915c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 916c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (LI->isVolatile()) 917c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return false; 918c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner continue; 919c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 920c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 921c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 922c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (SI->getOperand(0) == AI || SI->isVolatile()) 923c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return false; // Don't allow a store OF the AI, only INTO the AI. 924c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner continue; 925c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 926c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 927c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (SelectInst *SI = dyn_cast<SelectInst>(U)) { 928c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // If the condition being selected on is a constant, fold the select, yes 929c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // this does (rarely) happen early on. 930c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition())) { 931c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner Value *Result = SI->getOperand(1+CI->isZero()); 932c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner SI->replaceAllUsesWith(Result); 933c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner SI->eraseFromParent(); 934c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 935c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // This is very rare and we just scrambled the use list of AI, start 936c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // over completely. 937c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return tryToMakeAllocaBePromotable(AI, TD); 938c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 939c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 940c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // If it is safe to turn "load (select c, AI, ptr)" into a select of two 941c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // loads, then we can transform this by rewriting the select. 942c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (!isSafeSelectToSpeculate(SI, TD)) 943c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return false; 944c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 945c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner InstsToRewrite.insert(SI); 946c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner continue; 947c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 948c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 949c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return false; 950c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 951c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 952c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // If there are no instructions to rewrite, then all uses are load/stores and 953c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // we're done! 954c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (InstsToRewrite.empty()) 955c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return true; 956c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 957c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // If we have instructions that need to be rewritten for this to be promotable 958c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // take care of it now. 959c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner for (unsigned i = 0, e = InstsToRewrite.size(); i != e; ++i) { 960c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // Selects in InstsToRewrite only have load uses. Rewrite each as two 961c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // loads with a new select. 962c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner SelectInst *SI = cast<SelectInst>(InstsToRewrite[i]); 963c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 964c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner for (Value::use_iterator UI = SI->use_begin(), E = SI->use_end(); UI != E;){ 965c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner LoadInst *LI = cast<LoadInst>(*UI++); 966c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 967c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner IRBuilder<> Builder(LI); 968c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner LoadInst *TrueLoad = 969c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner Builder.CreateLoad(SI->getTrueValue(), LI->getName()+".t"); 970c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner LoadInst *FalseLoad = 971c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner Builder.CreateLoad(SI->getFalseValue(), LI->getName()+".t"); 972c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 973c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // Transfer alignment and TBAA info if present. 974c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner TrueLoad->setAlignment(LI->getAlignment()); 975c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner FalseLoad->setAlignment(LI->getAlignment()); 976c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (MDNode *Tag = LI->getMetadata(LLVMContext::MD_tbaa)) { 977c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner TrueLoad->setMetadata(LLVMContext::MD_tbaa, Tag); 978c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner FalseLoad->setMetadata(LLVMContext::MD_tbaa, Tag); 979c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 980c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 981c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner Value *V = Builder.CreateSelect(SI->getCondition(), TrueLoad, FalseLoad); 982c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner V->takeName(LI); 983c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner LI->replaceAllUsesWith(V); 984c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner LI->eraseFromParent(); 985c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 986c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 987c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner // Now that all the loads are gone, the select is gone too. 988c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner SI->eraseFromParent(); 989c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner } 990c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 991c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner ++NumAdjusted; 992c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner return true; 993c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner} 994c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 995c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner 9964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::performPromotion(Function &F) { 9974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> Allocas; 998e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner DominatorTree *DT = 0; 999b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich if (HasDomTree) 1000e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner DT = &getAnalysis<DominatorTree>(); 1001b742defa0a8f3e477c3ed641da49aab276937556Bob Wilson 10024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BasicBlock &BB = F.getEntryBlock(); // Get the entry node for the function 1003372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 10044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = false; 1005deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner SmallVector<Instruction*, 64> Insts; 10064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (1) { 10074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Allocas.clear(); 10084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Find allocas that are safe to promote, by looking at all instructions in 10104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the entry node 10114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) 10124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) // Is it an alloca? 1013c87c50a39c1bc27437352feee0f6aba2d50fa1b5Chris Lattner if (tryToMakeAllocaBePromotable(AI, TD)) 10144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Allocas.push_back(AI); 10154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Allocas.empty()) break; 10174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 1018b1686c32fc694636cbf15a59b23b2a741b65ecf4Cameron Zwarich if (HasDomTree) 1019419e8a62997987e0509efe721c1ea81ac29f09f3Cameron Zwarich PromoteMemToReg(Allocas, *DT); 1020e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner else { 1021e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner SSAUpdater SSA; 1022deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 1023deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner AllocaInst *AI = Allocas[i]; 1024deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 1025deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner // Build list of instructions to promote. 1026deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 1027deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner UI != E; ++UI) 1028deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Insts.push_back(cast<Instruction>(*UI)); 1029deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner 1030deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner AllocaPromoter(Insts, SSA).run(AI, Insts); 1031deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner Insts.clear(); 1032deaf55f69865bbc997a569c2a689ec5b0fbdefefChris Lattner } 1033e0a1a5ba91df6817f9ffae7af65ed0bda66f7620Chris Lattner } 10344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NumPromoted += Allocas.size(); 10354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 10364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 10374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 10394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 10404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// ShouldAttemptScalarRepl - Decide if an alloca is a good candidate for 10434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// SROA. It must be a struct or array type with a small number of elements. 10444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerstatic bool ShouldAttemptScalarRepl(AllocaInst *AI) { 10454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *T = AI->getAllocatedType(); 10464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote any struct into more than 32 separate vars. 10474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) 10484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return ST->getNumElements() <= 32; 10494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Arrays are much less likely to be safe for SROA; only consider 10504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // them if they are very small. 10514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(T)) 10524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return AT->getNumElements() <= 8; 10534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 10544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 10554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// performScalarRepl - This algorithm is a simple worklist driven algorithm, 10584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// which runs on all of the malloc/alloca instructions in the function, removing 10594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// them if they are only used by getelementptr instructions. 10604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner// 10614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::performScalarRepl(Function &F) { 10624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> WorkList; 10634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Scan the entry basic block, adding allocas to the worklist. 10654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BasicBlock &BB = F.getEntryBlock(); 10664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 10674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *A = dyn_cast<AllocaInst>(I)) 10684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(A); 10694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Process the worklist 10714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool Changed = false; 10724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!WorkList.empty()) { 10734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *AI = WorkList.back(); 10744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.pop_back(); 10756974302e3ff20746268721959efed807c7711bfcBob Wilson 10764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle dead allocas trivially. These can be formed by SROA'ing arrays 10774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with unused elements. 10784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AI->use_empty()) { 10794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 10804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 10814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 1082d93afec1dbbb1abb3df55e2e007b5f256d09f84aChris Lattner } 10834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 10844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this alloca is impossible for us to promote, reject it early. 10854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized()) 10864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 10876974302e3ff20746268721959efed807c7711bfcBob Wilson 10884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check to see if this allocation is only modified by a memcpy/memmove from 10894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // a constant global. If this is the case, we can change all users to use 10904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the constant global instead. This is commonly produced by the CFE by 10914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A' 10924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // is only subsequently read. 10934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) { 10944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Found alloca equal to global: " << *AI << '\n'); 10954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << " memcpy = " << *TheCopy << '\n'); 10964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *TheSrc = cast<Constant>(TheCopy->getSource()); 10974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType())); 10984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TheCopy->eraseFromParent(); // Don't mutate the global. 10994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 11004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ++NumGlobals; 11014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 11024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 11034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11046974302e3ff20746268721959efed807c7711bfcBob Wilson 11054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check to see if we can perform the core SROA transformation. We cannot 11064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // transform the allocation instruction if it is an array allocation 11074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (allocations OF arrays are ok though), and an allocation of a scalar 11084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // value cannot be decomposed at all. 11094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType()); 111044118f0e25c25fedda1ccdd6a72f072c0b5c96e7Dan Gohman 11114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote [0 x %struct]. 11124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaSize == 0) continue; 11136974302e3ff20746268721959efed807c7711bfcBob Wilson 11144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Do not promote any struct whose size is too big. 11154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaSize > SRThreshold) continue; 11166974302e3ff20746268721959efed807c7711bfcBob Wilson 11174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the alloca looks like a good candidate for scalar replacement, and if 11184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // all its users can be transformed, then split up the aggregate into its 11194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // separate elements. 11204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ShouldAttemptScalarRepl(AI) && isSafeAllocaToScalarRepl(AI)) { 11214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DoScalarReplacement(AI, WorkList); 11224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 11234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 112420adc9dc4650313f017b27d9818eb2176238113dMon P Wang } 11254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 11264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we can turn this aggregate value (potentially with casts) into a 11274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // simple scalar value that can be mem2reg'd into a register value. 11284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // IsNotTrivial tracks whether this is something that mem2reg could have 11294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // promoted itself. If so, we don't want to transform it needlessly. Note 11304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // that we can't just check based on the type: the alloca may be of an i32 11314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // but that has pointer arithmetic to set byte 3 of it or something. 11324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (AllocaInst *NewAI = 11334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConvertToScalarInfo((unsigned)AllocaSize, *TD).TryConvert(AI)) { 11344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewAI->takeName(AI); 11354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 11364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ++NumConverted; 11374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Changed = true; 11384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 11396974302e3ff20746268721959efed807c7711bfcBob Wilson } 11406974302e3ff20746268721959efed807c7711bfcBob Wilson 11414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, couldn't process this alloca. 1142372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner } 11434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 11444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Changed; 1145372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner} 1146d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 11474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl 11484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// predicate, do SROA now. 11496974302e3ff20746268721959efed807c7711bfcBob Wilsonvoid SROA::DoScalarReplacement(AllocaInst *AI, 11504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner std::vector<AllocaInst*> &WorkList) { 11514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Found inst to SROA: " << *AI << '\n'); 11524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> ElementAllocas; 11534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 11544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.reserve(ST->getNumContainedTypes()); 11554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) { 11566974302e3ff20746268721959efed807c7711bfcBob Wilson AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0, 11574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getAlignment(), 11584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getName() + "." + Twine(i), AI); 11594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.push_back(NA); 11604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 11614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 11634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType()); 11644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.reserve(AT->getNumElements()); 11654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ElTy = AT->getElementType(); 11664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) { 11674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(), 11684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->getName() + "." + Twine(i), AI); 11694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ElementAllocas.push_back(NA); 11704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner WorkList.push_back(NA); // Add to worklist for recursive processing 11714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 11724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1173d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 11744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Now that we have created the new alloca instructions, rewrite all the 11754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // uses of the old alloca. 11764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(AI, AI, 0, ElementAllocas); 1177d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 11784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Now erase any instructions that were made dead while rewriting the alloca. 11794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeleteDeadInstructions(); 11804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AI->eraseFromParent(); 11814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 1182fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumReplaced; 11834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 11844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 11854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// DeleteDeadInstructions - Erase instructions on the DeadInstrs list, 11864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// recursively including all their operands that become trivially dead. 11874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::DeleteDeadInstructions() { 11884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (!DeadInsts.empty()) { 11894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *I = cast<Instruction>(DeadInsts.pop_back_val()); 11904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 11914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 11924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Instruction *U = dyn_cast<Instruction>(*OI)) { 11934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero out the operand and see if it becomes trivially dead. 11944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (But, don't add allocas to the dead instruction list -- they are 11954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // already on the worklist and will be deleted separately.) 11964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner *OI = 0; 11974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isInstructionTriviallyDead(U) && !isa<AllocaInst>(U)) 11984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(U); 1199d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1200d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 12014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner I->eraseFromParent(); 12024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 12034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 12046974302e3ff20746268721959efed807c7711bfcBob Wilson 12054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeForScalarRepl - Check if instruction I is a safe use with regard to 12064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// performing scalar replacement of alloca AI. The results are flagged in 12074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the Info parameter. Offset indicates the position within AI that is 12084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// referenced by this instruction. 12096c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattnervoid SROA::isSafeForScalarRepl(Instruction *I, uint64_t Offset, 12104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInfo &Info) { 12114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) { 12124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *User = cast<Instruction>(*UI); 12134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 12144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 12156c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner isSafeForScalarRepl(BC, Offset, Info); 12164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 12174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t GEPOffset = Offset; 12186c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner isSafeGEP(GEPI, GEPOffset, Info); 12194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!Info.isUnsafe) 12206c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner isSafeForScalarRepl(GEPI, GEPOffset, Info); 122119101c7585c191376d898e3e66e35acd9bd777c2Gabor Greif } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 12224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 1223d01a0da090407762fe3b770d84f049d72d06467eChris Lattner if (Length == 0) 1224d01a0da090407762fe3b770d84f049d72d06467eChris Lattner return MarkUnsafe(Info, User); 12256c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner isSafeMemAccess(Offset, Length->getZExtValue(), 0, 1226145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner UI.getOperandNo() == 0, Info, MI, 1227145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner true /*AllowWholeAccess*/); 12284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 1229d01a0da090407762fe3b770d84f049d72d06467eChris Lattner if (LI->isVolatile()) 1230d01a0da090407762fe3b770d84f049d72d06467eChris Lattner return MarkUnsafe(Info, User); 1231d01a0da090407762fe3b770d84f049d72d06467eChris Lattner const Type *LIType = LI->getType(); 12326c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner isSafeMemAccess(Offset, TD->getTypeAllocSize(LIType), 1233145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner LIType, false, Info, LI, true /*AllowWholeAccess*/); 1234d01a0da090407762fe3b770d84f049d72d06467eChris Lattner Info.hasALoadOrStore = true; 1235d01a0da090407762fe3b770d84f049d72d06467eChris Lattner 12364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 12374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Store is ok if storing INTO the pointer, not storing the pointer 1238d01a0da090407762fe3b770d84f049d72d06467eChris Lattner if (SI->isVolatile() || SI->getOperand(0) == I) 1239d01a0da090407762fe3b770d84f049d72d06467eChris Lattner return MarkUnsafe(Info, User); 1240d01a0da090407762fe3b770d84f049d72d06467eChris Lattner 1241d01a0da090407762fe3b770d84f049d72d06467eChris Lattner const Type *SIType = SI->getOperand(0)->getType(); 12426c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner isSafeMemAccess(Offset, TD->getTypeAllocSize(SIType), 1243145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner SIType, true, Info, SI, true /*AllowWholeAccess*/); 1244145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner Info.hasALoadOrStore = true; 1245145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } else if (isa<PHINode>(User) || isa<SelectInst>(User)) { 1246145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner isSafePHISelectUseForScalarRepl(User, Offset, Info); 1247145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } else { 1248145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner return MarkUnsafe(Info, User); 1249145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } 1250145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (Info.isUnsafe) return; 1251145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } 1252145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner} 1253145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1254145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1255145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// isSafePHIUseForScalarRepl - If we see a PHI node or select using a pointer 1256145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// derived from the alloca, we can often still split the alloca into elements. 1257145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// This is useful if we have a large alloca where one element is phi'd 1258145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// together somewhere: we can SRoA and promote all the other elements even if 1259145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// we end up not being able to promote this one. 1260145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// 1261145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// All we require is that the uses of the PHI do not index into other parts of 1262145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// the alloca. The most important use case for this is single load and stores 1263145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// that are PHI'd together, which can happen due to code sinking. 1264145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattnervoid SROA::isSafePHISelectUseForScalarRepl(Instruction *I, uint64_t Offset, 1265145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner AllocaInfo &Info) { 1266145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // If we've already checked this PHI, don't do it again. 1267145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (PHINode *PN = dyn_cast<PHINode>(I)) 1268145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (!Info.CheckedPHIs.insert(PN)) 1269145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner return; 1270145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1271145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) { 1272145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner Instruction *User = cast<Instruction>(*UI); 1273145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1274145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 1275145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner isSafePHISelectUseForScalarRepl(BC, Offset, Info); 1276145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 1277145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // Only allow "bitcast" GEPs for simplicity. We could generalize this, 1278145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // but would have to prove that we're staying inside of an element being 1279145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // promoted. 1280145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (!GEPI->hasAllZeroIndices()) 1281145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner return MarkUnsafe(Info, User); 1282145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner isSafePHISelectUseForScalarRepl(GEPI, Offset, Info); 1283145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 1284145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (LI->isVolatile()) 1285145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner return MarkUnsafe(Info, User); 1286145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner const Type *LIType = LI->getType(); 1287145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner isSafeMemAccess(Offset, TD->getTypeAllocSize(LIType), 1288145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner LIType, false, Info, LI, false /*AllowWholeAccess*/); 1289145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner Info.hasALoadOrStore = true; 1290145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1291145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 1292145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // Store is ok if storing INTO the pointer, not storing the pointer 1293145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (SI->isVolatile() || SI->getOperand(0) == I) 1294145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner return MarkUnsafe(Info, User); 1295145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1296145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner const Type *SIType = SI->getOperand(0)->getType(); 1297145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner isSafeMemAccess(Offset, TD->getTypeAllocSize(SIType), 1298145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner SIType, true, Info, SI, false /*AllowWholeAccess*/); 1299d01a0da090407762fe3b770d84f049d72d06467eChris Lattner Info.hasALoadOrStore = true; 1300145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } else if (isa<PHINode>(User) || isa<SelectInst>(User)) { 1301145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner isSafePHISelectUseForScalarRepl(User, Offset, Info); 13024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 1303d01a0da090407762fe3b770d84f049d72d06467eChris Lattner return MarkUnsafe(Info, User); 1304d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 13054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isUnsafe) return; 1306d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner } 1307d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner} 1308d2fa781169175b827e50953a1d0b7edc6b0c4801Chris Lattner 13094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeGEP - Check if a GEP instruction can be handled for scalar 13104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// replacement. It is safe when all the indices are constant, in-bounds 13114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// references, and when the resulting offset corresponds to an element within 13124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the alloca type. The results are flagged in the Info parameter. Upon 13134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// return, Offset is adjusted as specified by the GEP indices. 13146c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattnervoid SROA::isSafeGEP(GetElementPtrInst *GEPI, 13154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t &Offset, AllocaInfo &Info) { 13164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner gep_type_iterator GEPIt = gep_type_begin(GEPI), E = gep_type_end(GEPI); 13174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GEPIt == E) 13184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 13195ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 13204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Walk through the GEP type indices, checking the types that this indexes 13214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // into. 13224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (; GEPIt != E; ++GEPIt) { 13234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore struct elements, no extra checking needed for these. 13244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if ((*GEPIt)->isStructTy()) 13254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 13265ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 13274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPIt.getOperand()); 13284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!IdxVal) 1329d01a0da090407762fe3b770d84f049d72d06467eChris Lattner return MarkUnsafe(Info, GEPI); 13305ffe6acd577696a41932c7b82db06a04687e07baChris Lattner } 133141b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 13324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Compute the offset due to this GEP and check if the alloca has a 13334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // component element at that offset. 13344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 13354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), 13364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 13376c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner if (!TypeHasComponent(Info.AI->getAllocatedType(), Offset, 0)) 1338d01a0da090407762fe3b770d84f049d72d06467eChris Lattner MarkUnsafe(Info, GEPI); 13394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 134041b33f437f70dcf63e35d08e5f4202258ef05c15Eli Friedman 1341704d1347c5009f674408fae6f78343b415891274Bob Wilson/// isHomogeneousAggregate - Check if type T is a struct or array containing 1342704d1347c5009f674408fae6f78343b415891274Bob Wilson/// elements of the same type (which is always true for arrays). If so, 1343704d1347c5009f674408fae6f78343b415891274Bob Wilson/// return true with NumElts and EltTy set to the number of elements and the 1344704d1347c5009f674408fae6f78343b415891274Bob Wilson/// element type, respectively. 1345704d1347c5009f674408fae6f78343b415891274Bob Wilsonstatic bool isHomogeneousAggregate(const Type *T, unsigned &NumElts, 1346704d1347c5009f674408fae6f78343b415891274Bob Wilson const Type *&EltTy) { 1347704d1347c5009f674408fae6f78343b415891274Bob Wilson if (const ArrayType *AT = dyn_cast<ArrayType>(T)) { 1348704d1347c5009f674408fae6f78343b415891274Bob Wilson NumElts = AT->getNumElements(); 1349f0908aeade2f41d2fed82de8d85448358b379328Bob Wilson EltTy = (NumElts == 0 ? 0 : AT->getElementType()); 1350704d1347c5009f674408fae6f78343b415891274Bob Wilson return true; 1351704d1347c5009f674408fae6f78343b415891274Bob Wilson } 1352704d1347c5009f674408fae6f78343b415891274Bob Wilson if (const StructType *ST = dyn_cast<StructType>(T)) { 1353704d1347c5009f674408fae6f78343b415891274Bob Wilson NumElts = ST->getNumContainedTypes(); 1354f0908aeade2f41d2fed82de8d85448358b379328Bob Wilson EltTy = (NumElts == 0 ? 0 : ST->getContainedType(0)); 1355704d1347c5009f674408fae6f78343b415891274Bob Wilson for (unsigned n = 1; n < NumElts; ++n) { 1356704d1347c5009f674408fae6f78343b415891274Bob Wilson if (ST->getContainedType(n) != EltTy) 1357704d1347c5009f674408fae6f78343b415891274Bob Wilson return false; 1358704d1347c5009f674408fae6f78343b415891274Bob Wilson } 1359704d1347c5009f674408fae6f78343b415891274Bob Wilson return true; 1360704d1347c5009f674408fae6f78343b415891274Bob Wilson } 1361704d1347c5009f674408fae6f78343b415891274Bob Wilson return false; 1362704d1347c5009f674408fae6f78343b415891274Bob Wilson} 1363704d1347c5009f674408fae6f78343b415891274Bob Wilson 1364704d1347c5009f674408fae6f78343b415891274Bob Wilson/// isCompatibleAggregate - Check if T1 and T2 are either the same type or are 1365704d1347c5009f674408fae6f78343b415891274Bob Wilson/// "homogeneous" aggregates with the same element type and number of elements. 1366704d1347c5009f674408fae6f78343b415891274Bob Wilsonstatic bool isCompatibleAggregate(const Type *T1, const Type *T2) { 1367704d1347c5009f674408fae6f78343b415891274Bob Wilson if (T1 == T2) 1368704d1347c5009f674408fae6f78343b415891274Bob Wilson return true; 1369704d1347c5009f674408fae6f78343b415891274Bob Wilson 1370704d1347c5009f674408fae6f78343b415891274Bob Wilson unsigned NumElts1, NumElts2; 1371704d1347c5009f674408fae6f78343b415891274Bob Wilson const Type *EltTy1, *EltTy2; 1372704d1347c5009f674408fae6f78343b415891274Bob Wilson if (isHomogeneousAggregate(T1, NumElts1, EltTy1) && 1373704d1347c5009f674408fae6f78343b415891274Bob Wilson isHomogeneousAggregate(T2, NumElts2, EltTy2) && 1374704d1347c5009f674408fae6f78343b415891274Bob Wilson NumElts1 == NumElts2 && 1375704d1347c5009f674408fae6f78343b415891274Bob Wilson EltTy1 == EltTy2) 1376704d1347c5009f674408fae6f78343b415891274Bob Wilson return true; 1377704d1347c5009f674408fae6f78343b415891274Bob Wilson 1378704d1347c5009f674408fae6f78343b415891274Bob Wilson return false; 1379704d1347c5009f674408fae6f78343b415891274Bob Wilson} 1380704d1347c5009f674408fae6f78343b415891274Bob Wilson 13814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeMemAccess - Check if a load/store/memcpy operates on the entire AI 13824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// alloca or has an offset and size that corresponds to a component element 13834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// within it. The offset checked here may have been formed from a GEP with a 13844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// pointer bitcasted to a different type. 1385145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// 1386145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// If AllowWholeAccess is true, then this allows uses of the entire alloca as a 1387145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner/// unit. If false, it only allows accesses known to be in a single element. 13886c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattnervoid SROA::isSafeMemAccess(uint64_t Offset, uint64_t MemSize, 13894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *MemOpType, bool isStore, 1390145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner AllocaInfo &Info, Instruction *TheAccess, 1391145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner bool AllowWholeAccess) { 13924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if this is a load/store of the entire alloca. 1393145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (Offset == 0 && AllowWholeAccess && 13946c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner MemSize == TD->getTypeAllocSize(Info.AI->getAllocatedType())) { 1395704d1347c5009f674408fae6f78343b415891274Bob Wilson // This can be safe for MemIntrinsics (where MemOpType is 0) and integer 1396704d1347c5009f674408fae6f78343b415891274Bob Wilson // loads/stores (which are essentially the same as the MemIntrinsics with 1397704d1347c5009f674408fae6f78343b415891274Bob Wilson // regard to copying padding between elements). But, if an alloca is 1398704d1347c5009f674408fae6f78343b415891274Bob Wilson // flagged as both a source and destination of such operations, we'll need 1399704d1347c5009f674408fae6f78343b415891274Bob Wilson // to check later for padding between elements. 1400704d1347c5009f674408fae6f78343b415891274Bob Wilson if (!MemOpType || MemOpType->isIntegerTy()) { 1401704d1347c5009f674408fae6f78343b415891274Bob Wilson if (isStore) 1402704d1347c5009f674408fae6f78343b415891274Bob Wilson Info.isMemCpyDst = true; 1403704d1347c5009f674408fae6f78343b415891274Bob Wilson else 1404704d1347c5009f674408fae6f78343b415891274Bob Wilson Info.isMemCpySrc = true; 14054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 14064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1407704d1347c5009f674408fae6f78343b415891274Bob Wilson // This is also safe for references using a type that is compatible with 1408704d1347c5009f674408fae6f78343b415891274Bob Wilson // the type of the alloca, so that loads/stores can be rewritten using 1409704d1347c5009f674408fae6f78343b415891274Bob Wilson // insertvalue/extractvalue. 14106c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner if (isCompatibleAggregate(MemOpType, Info.AI->getAllocatedType())) { 14117e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner Info.hasSubelementAccess = true; 1412704d1347c5009f674408fae6f78343b415891274Bob Wilson return; 14137e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner } 14144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if the offset/size correspond to a component within the alloca type. 14166c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner const Type *T = Info.AI->getAllocatedType(); 14177e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner if (TypeHasComponent(T, Offset, MemSize)) { 14187e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner Info.hasSubelementAccess = true; 14194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 14207e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner } 14214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 1422d01a0da090407762fe3b770d84f049d72d06467eChris Lattner return MarkUnsafe(Info, TheAccess); 14235ffe6acd577696a41932c7b82db06a04687e07baChris Lattner} 14245ffe6acd577696a41932c7b82db06a04687e07baChris Lattner 14254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// TypeHasComponent - Return true if T has a component type with the 14264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// specified offset and size. If Size is zero, do not check the size. 14274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size) { 14284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *EltTy; 14294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize; 14304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) { 14314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(ST); 14324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltIdx = Layout->getElementContainingOffset(Offset); 14334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltTy = ST->getContainedType(EltIdx); 14344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltSize = TD->getTypeAllocSize(EltTy); 14354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Layout->getElementOffset(EltIdx); 14364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (const ArrayType *AT = dyn_cast<ArrayType>(T)) { 14374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltTy = AT->getElementType(); 14384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltSize = TD->getTypeAllocSize(EltTy); 14394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset >= AT->getNumElements() * EltSize) 14404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 14414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset %= EltSize; 14424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 14434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 14444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 14454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset == 0 && (Size == 0 || EltSize == Size)) 14464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 14474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Check if the component spans multiple elements. 14484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset + Size > EltSize) 14494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 14504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return TypeHasComponent(EltTy, Offset, Size); 14514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 14523cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 14534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteForScalarRepl - Alloca AI is being split into NewElts, so rewrite 14544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the instruction I, which references it, to use the separate elements. 14554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Offset indicates the position within AI that is referenced by this 14564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// instruction. 14574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset, 14584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 1459145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E;) { 1460145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner Use &TheUse = UI.getUse(); 1461145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner Instruction *User = cast<Instruction>(*UI++); 14623cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 14634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 14644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteBitCast(BC, AI, Offset, NewElts); 1465145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner continue; 1466145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } 1467145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1468145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 14694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteGEP(GEPI, AI, Offset, NewElts); 1470145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner continue; 1471145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } 1472145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1473145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) { 14744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength()); 14754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t MemSize = Length->getZExtValue(); 14764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Offset == 0 && 14774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) 14784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteMemIntrinUserOfAlloca(MI, I, AI, NewElts); 14794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise the intrinsic can only touch a single element and the 14804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // address operand will be updated, so nothing else needs to be done. 1481145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner continue; 1482145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } 1483145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1484145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 14854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *LIType = LI->getType(); 1486192228edb1c08ca11da2df959072bcaa99eacd63Chris Lattner 1487704d1347c5009f674408fae6f78343b415891274Bob Wilson if (isCompatibleAggregate(LIType, AI->getAllocatedType())) { 14884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Replace: 14894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %res = load { i32, i32 }* %alloc 14904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with: 14914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %load.0 = load i32* %alloc.0 14924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0 14934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %load.1 = load i32* %alloc.1 14944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1 14954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (Also works for arrays instead of structs) 14964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Insert = UndefValue::get(LIType); 14974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 14984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Load = new LoadInst(NewElts[i], "load", LI); 14994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI); 15004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(Insert); 15024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(LI); 15034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (LIType->isIntegerTy() && 15044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(LIType) == 15054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(AI->getAllocatedType())) { 15064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a load of the entire alloca to an integer, rewrite it. 15074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteLoadUserOfWholeAlloca(LI, AI, NewElts); 15084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1509145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner continue; 1510145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } 1511145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1512145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 15134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Val = SI->getOperand(0); 15144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *SIType = Val->getType(); 1515704d1347c5009f674408fae6f78343b415891274Bob Wilson if (isCompatibleAggregate(SIType, AI->getAllocatedType())) { 15164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Replace: 15174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store { i32, i32 } %val, { i32, i32 }* %alloc 15184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // with: 15194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %val.0 = extractvalue { i32, i32 } %val, 0 15204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store i32 %val.0, i32* %alloc.0 15214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // %val.1 = extractvalue { i32, i32 } %val, 1 15224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // store i32 %val.1, i32* %alloc.1 15234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // (Also works for arrays instead of structs) 15244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 15254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI); 15264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Extract, NewElts[i], SI); 15274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(SI); 15294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (SIType->isIntegerTy() && 15304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(SIType) == 15314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TD->getTypeAllocSize(AI->getAllocatedType())) { 15324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a store of the entire alloca from an integer, rewrite it. 15334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteStoreUserOfWholeAlloca(SI, AI, NewElts); 153439a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 1535145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner continue; 1536145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner } 1537145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1538145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (isa<SelectInst>(User) || isa<PHINode>(User)) { 1539145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // If we have a PHI user of the alloca itself (as opposed to a GEP or 1540145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // bitcast) we have to rewrite it. GEP and bitcast uses will be RAUW'd to 1541145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // the new pointer. 1542145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner if (!isa<AllocaInst>(I)) continue; 1543145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1544145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner assert(Offset == 0 && NewElts[0] && 1545145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner "Direct alloca use should have a zero offset"); 1546145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 1547145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // If we have a use of the alloca, we know the derived uses will be 1548145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // utilizing just the first element of the scalarized result. Insert a 1549145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner // bitcast of the first alloca before the user as required. 1550145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner AllocaInst *NewAI = NewElts[0]; 1551145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner BitCastInst *BCI = new BitCastInst(NewAI, AI->getType(), "", NewAI); 1552145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner NewAI->moveBefore(BCI); 1553145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner TheUse = BCI; 1554145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner continue; 155539a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 15564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 15574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 15583cb3650a278e37aa6378127c51e407d2823139b4Duncan Sands 15594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteBitCast - Update a bitcast reference to the alloca being replaced 15604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// and recursively continue updating all of its uses. 15614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset, 15624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 15634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(BC, AI, Offset, NewElts); 15644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (BC->getOperand(0) != AI) 15654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 156639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner 15674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The bitcast references the original alloca. Replace its uses with 15684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // references to the first new element alloca. 15694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Val = NewElts[0]; 15704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val->getType() != BC->getDestTy()) { 15714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = new BitCastInst(Val, BC->getDestTy(), "", BC); 15724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val->takeName(BC); 157339a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner } 15744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner BC->replaceAllUsesWith(Val); 15754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(BC); 157639a1c04323a5993d6b2993e615ec44c16e19aeeaChris Lattner} 1577372dda8881c7a32a6f5ce0f76a713e3a9ef46ea1Chris Lattner 15784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// FindElementAndOffset - Return the index of the element containing Offset 15794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// within the specified type, which must be either a struct or an array. 15804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Sets T to the type of the element and Offset to the offset within that 15814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// element. IdxTy is set to the type of the index result to be used in a 15824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// GEP instruction. 15834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattneruint64_t SROA::FindElementAndOffset(const Type *&T, uint64_t &Offset, 15844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *&IdxTy) { 15854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Idx = 0; 15864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *ST = dyn_cast<StructType>(T)) { 15874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(ST); 15884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Idx = Layout->getElementContainingOffset(Offset); 15894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = ST->getContainedType(Idx); 15904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Layout->getElementOffset(Idx); 15914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IdxTy = Type::getInt32Ty(T->getContext()); 15924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Idx; 1593f5990edc877c4e63503c589928a00ec6ec751830Chris Lattner } 15944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *AT = cast<ArrayType>(T); 15954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = AT->getElementType(); 15964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltSize = TD->getTypeAllocSize(T); 15974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Idx = Offset / EltSize; 15984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset -= Idx * EltSize; 15994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner IdxTy = Type::getInt64Ty(T->getContext()); 16004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return Idx; 16015e062a1eda2c4adffd428a35e737a431fc37f4e0Chris Lattner} 1602a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 16034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteGEP - Check if this GEP instruction moves the pointer across 16044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// elements of the alloca that are being split apart, and if so, rewrite 16054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// the GEP to be relative to the new element. 16064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset, 16074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 16084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t OldOffset = Offset; 16094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end()); 16104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), 16114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner &Indices[0], Indices.size()); 16124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner RewriteForScalarRepl(GEPI, AI, Offset, NewElts); 16144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *T = AI->getAllocatedType(); 16164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *IdxTy; 16174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t OldIdx = FindElementAndOffset(T, OldOffset, IdxTy); 16184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (GEPI->getOperand(0) == AI) 16194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OldIdx = ~0ULL; // Force the GEP to be rewritten. 16204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner T = AI->getAllocatedType(); 16224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltOffset = Offset; 16234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Idx = FindElementAndOffset(T, EltOffset, IdxTy); 16244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this GEP does not move the pointer across elements of the alloca 16264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // being split, then it does not needs to be rewritten. 16274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Idx == OldIdx) 1628c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner return; 1629c4472072641f702dbd99ae12b7da089e75c44a99Chris Lattner 16304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *i32Ty = Type::getInt32Ty(AI->getContext()); 16314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Value*, 8> NewArgs; 16324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.push_back(Constant::getNullValue(i32Ty)); 16334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner while (EltOffset != 0) { 16344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltIdx = FindElementAndOffset(T, EltOffset, IdxTy); 16354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.push_back(ConstantInt::get(IdxTy, EltIdx)); 16362e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 16374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Instruction *Val = NewElts[Idx]; 16384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (NewArgs.size() > 1) { 16394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = GetElementPtrInst::CreateInBounds(Val, NewArgs.begin(), 16404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner NewArgs.end(), "", GEPI); 16414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val->takeName(GEPI); 16424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 16434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Val->getType() != GEPI->getType()) 16444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Val = new BitCastInst(Val, GEPI->getType(), Val->getName(), GEPI); 16454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner GEPI->replaceAllUsesWith(Val); 16464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(GEPI); 1647a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 1648a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner 16494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI. 16504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// Rewrite it to copy or set the elements of the scalarized memory. 16514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst, 16524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner AllocaInst *AI, 16534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 16544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy/memmove, construct the other pointer as the 16554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // appropriate type. The "Other" pointer is the pointer that goes to memory 16564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // that doesn't have anything to do with the alloca that we are promoting. For 16574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // memset, this Value* stays null. 16584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *OtherPtr = 0; 16594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned MemAlignment = MI->getAlignment(); 16604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { // memmove/memcopy 16614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Inst == MTI->getRawDest()) 16624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr = MTI->getRawSource(); 16634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else { 16644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(Inst == MTI->getRawSource()); 16654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr = MTI->getRawDest(); 1666a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 16674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 16683ce5e887aef457701da95f1c6ccbd58ec3d32fe4Chris Lattner 16694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If there is an other pointer, we want to convert it to the same pointer 16704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // type as AI has, so we can GEP through it safely. 16714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr) { 16720238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner unsigned AddrSpace = 16730238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner cast<PointerType>(OtherPtr->getType())->getAddressSpace(); 16744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 16754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Remove bitcasts and all-zero GEPs from OtherPtr. This is an 16764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // optimization, but it's also required to detect the corner case where 16774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // both pointer operands are referencing the same memory, and where 16784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // OtherPtr may be a bitcast or GEP that currently being rewritten. (This 16794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // function is only called for mem intrinsics that access the whole 16804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // aggregate, so non-zero GEPs are not an issue here.) 16810238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner OtherPtr = OtherPtr->stripPointerCasts(); 16826974302e3ff20746268721959efed807c7711bfcBob Wilson 16834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Copying the alloca to itself is a no-op: just delete it. 16844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr == AI || OtherPtr == NewElts[0]) { 16854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // This code will run twice for a no-op memcpy -- once for each operand. 16864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Put only one reference to MI on the DeadInsts list. 16874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (SmallVector<Value*, 32>::const_iterator I = DeadInsts.begin(), 16884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner E = DeadInsts.end(); I != E; ++I) 16894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (*I == MI) return; 16904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(MI); 16914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return; 1692c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner } 16936974302e3ff20746268721959efed807c7711bfcBob Wilson 16944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the pointer is not the right type, insert a bitcast to the right 16954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // type. 16960238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner const Type *NewTy = 16970238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner PointerType::get(AI->getType()->getElementType(), AddrSpace); 16986974302e3ff20746268721959efed807c7711bfcBob Wilson 16990238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner if (OtherPtr->getType() != NewTy) 17000238f8c430050d23ef861169bb4c4f930af0ef97Chris Lattner OtherPtr = new BitCastInst(OtherPtr, NewTy, OtherPtr->getName(), MI); 1701a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 17026974302e3ff20746268721959efed807c7711bfcBob Wilson 17034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Process each element of the aggregate. 17044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner bool SROADest = MI->getRawDest() == Inst; 17056974302e3ff20746268721959efed807c7711bfcBob Wilson 17064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *Zero = Constant::getNullValue(Type::getInt32Ty(MI->getContext())); 17074b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 17084cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 17094cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If this is a memcpy/memmove, emit a GEP of the other element address. 17104cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *OtherElt = 0; 17114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned OtherEltAlign = MemAlignment; 17126974302e3ff20746268721959efed807c7711bfcBob Wilson 17134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (OtherPtr) { 17144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Idx[2] = { Zero, 17154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ConstantInt::get(Type::getInt32Ty(MI->getContext()), i) }; 17164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherElt = GetElementPtrInst::CreateInBounds(OtherPtr, Idx, Idx + 2, 17174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherPtr->getName()+"."+Twine(i), 17184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner MI); 17194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t EltOffset; 17204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType()); 1721d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner const Type *OtherTy = OtherPtrTy->getElementType(); 1722d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner if (const StructType *ST = dyn_cast<StructType>(OtherTy)) { 17234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltOffset = TD->getStructLayout(ST)->getElementOffset(i); 17244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 1725d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner const Type *EltTy = cast<SequentialType>(OtherTy)->getElementType(); 17264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner EltOffset = TD->getTypeAllocSize(EltTy)*i; 17274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17286974302e3ff20746268721959efed807c7711bfcBob Wilson 17294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // The alignment of the other pointer is the guaranteed alignment of the 17304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // element, which is affected by both the known alignment of the whole 17314cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // mem intrinsic and the alignment of the element. If the alignment of 17324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the memcpy (f.e.) is 32 but the element is at a 4-byte offset, then the 17334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // known alignment is just 4 bytes. 17344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset); 17359bc67da0a9982f2f7597d1d46cf18f079e4f8f98Chris Lattner } 17366974302e3ff20746268721959efed807c7711bfcBob Wilson 17374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltPtr = NewElts[i]; 17384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType(); 17396974302e3ff20746268721959efed807c7711bfcBob Wilson 17404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If we got down to a scalar, insert a load or store as appropriate. 17414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltTy->isSingleValueType()) { 17424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (isa<MemTransferInst>(MI)) { 17434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SROADest) { 17444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // From Other to Alloca. 17454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI); 17464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Elt, EltPtr, MI); 17474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 17484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // From Alloca to Other. 17494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *Elt = new LoadInst(EltPtr, "tmp", MI); 17504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI); 17514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 175333e24adc3bc3d046aa05cf903fb74da1610b57cbChris Lattner } 17544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(isa<MemSetInst>(MI)); 17556974302e3ff20746268721959efed807c7711bfcBob Wilson 17564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the stored element is zero (common case), just store a null 17574cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // constant. 17584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant *StoreVal; 17596f14c8c7c1ec97797a04631abad6885bfaabcc6dGabor Greif if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getArgOperand(1))) { 17604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (CI->isZero()) { 17614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = Constant::getNullValue(EltTy); // 0.0, null, 0, <0,0> 17624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 17634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If EltTy is a vector type, get the element type. 17644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ValTy = EltTy->getScalarType(); 1765c570487d45f7426dc5f75c0309122d6f9330ecf7Chris Lattner 17664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Construct an integer with the right value. 17674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD->getTypeSizeInBits(ValTy); 17684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt OneVal(EltSize, CI->getZExtValue()); 17694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner APInt TotalVal(OneVal); 17704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Set each byte. 17714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0; 8*i < EltSize; ++i) { 17724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TotalVal = TotalVal.shl(8); 17734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner TotalVal |= OneVal; 17744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17756974302e3ff20746268721959efed807c7711bfcBob Wilson 17764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Convert the integer value to the appropriate type. 1777d55c1c16598eba6111fb3a5b6e5dbc6469a562f7Chris Lattner StoreVal = ConstantInt::get(CI->getContext(), TotalVal); 17784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ValTy->isPointerTy()) 17794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy); 17804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else if (ValTy->isFloatingPointTy()) 17814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy); 17824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner assert(StoreVal->getType() == ValTy && "Type mismatch!"); 17836974302e3ff20746268721959efed807c7711bfcBob Wilson 17844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If the requested value was a vector constant, create it. 17854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltTy != ValTy) { 17864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned NumElts = cast<VectorType>(ValTy)->getNumElements(); 17874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<Constant*, 16> Elts(NumElts, StoreVal); 17884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner StoreVal = ConstantVector::get(&Elts[0], NumElts); 17894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17904cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(StoreVal, EltPtr, MI); 17924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner continue; 17934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, if we're storing a byte variable, use a memset call for 17954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // this element. 17964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 17976974302e3ff20746268721959efed807c7711bfcBob Wilson 17984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner unsigned EltSize = TD->getTypeAllocSize(EltTy); 17996974302e3ff20746268721959efed807c7711bfcBob Wilson 180061db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner IRBuilder<> Builder(MI); 18016974302e3ff20746268721959efed807c7711bfcBob Wilson 18024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Finally, insert the meminst for this element. 180361db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner if (isa<MemSetInst>(MI)) { 180461db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Builder.CreateMemSet(EltPtr, MI->getArgOperand(1), EltSize, 180561db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner MI->isVolatile()); 18064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 180761db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner assert(isa<MemTransferInst>(MI)); 180861db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Value *Dst = SROADest ? EltPtr : OtherElt; // Dest ptr 180961db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Value *Src = SROADest ? OtherElt : EltPtr; // Src ptr 18106974302e3ff20746268721959efed807c7711bfcBob Wilson 181161db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner if (isa<MemCpyInst>(MI)) 181261db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Builder.CreateMemCpy(Dst, Src, EltSize, OtherEltAlign,MI->isVolatile()); 181361db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner else 181461db1f56d0b717d67557bbb2a9d83af1449458cbChris Lattner Builder.CreateMemMove(Dst, Src, EltSize,OtherEltAlign,MI->isVolatile()); 18154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1816a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner } 18174cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(MI); 1818a188894d67a3cc2516b25aae9b3cbdbff4b0babeChris Lattner} 181979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 18204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteStoreUserOfWholeAlloca - We found a store of an integer that 18214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// overwrites the entire allocation. Extract out the pieces of the stored 18224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// integer and store them individually. 18234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI, 18244cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts){ 18254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Extract each element out of the integer according to its structure offset 18264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // and store the element value to the individual alloca. 18274cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcVal = SI->getOperand(0); 18284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaEltTy = AI->getAllocatedType(); 18294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 18306974302e3ff20746268721959efed807c7711bfcBob Wilson 183170728532799d751b8e0e97719dcb3344a2fc97deChris Lattner IRBuilder<> Builder(SI); 183270728532799d751b8e0e97719dcb3344a2fc97deChris Lattner 18334cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle tail padding by extending the operand 18344cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits) 183570728532799d751b8e0e97719dcb3344a2fc97deChris Lattner SrcVal = Builder.CreateZExt(SrcVal, 183670728532799d751b8e0e97719dcb3344a2fc97deChris Lattner IntegerType::get(SI->getContext(), AllocaSizeBits)); 18374b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 18384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << '\n' << *SI 18394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner << '\n'); 18404b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 18414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // There are two forms here: AI could be an array or struct. Both cases 18424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // have different ways to compute the element offset. 18434cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 18444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = TD->getStructLayout(EltSTy); 18456974302e3ff20746268721959efed807c7711bfcBob Wilson 18464cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 18474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Get the number of bits to shift SrcVal to get the value. 18484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *FieldTy = EltSTy->getElementType(i); 18494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift = Layout->getElementOffsetInBits(i); 18506974302e3ff20746268721959efed807c7711bfcBob Wilson 18514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 18524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-Shift-TD->getTypeAllocSizeInBits(FieldTy); 18536974302e3ff20746268721959efed807c7711bfcBob Wilson 18544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltVal = SrcVal; 18554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 18564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 185770728532799d751b8e0e97719dcb3344a2fc97deChris Lattner EltVal = Builder.CreateLShr(EltVal, ShiftVal, "sroa.store.elt"); 18584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 18596974302e3ff20746268721959efed807c7711bfcBob Wilson 18604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncate down to an integer of the right size. 18614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 18626974302e3ff20746268721959efed807c7711bfcBob Wilson 18634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 18644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits == 0) continue; 18656974302e3ff20746268721959efed807c7711bfcBob Wilson 18664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits != AllocaSizeBits) 186770728532799d751b8e0e97719dcb3344a2fc97deChris Lattner EltVal = Builder.CreateTrunc(EltVal, 186870728532799d751b8e0e97719dcb3344a2fc97deChris Lattner IntegerType::get(SI->getContext(), FieldSizeBits)); 18694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *DestField = NewElts[i]; 18704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltVal->getType() == FieldTy) { 18714cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing to an integer field of this size, just do it. 18724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (FieldTy->isFloatingPointTy() || FieldTy->isVectorTy()) { 18734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Bitcast to the right element type (for fp/vector values). 187470728532799d751b8e0e97719dcb3344a2fc97deChris Lattner EltVal = Builder.CreateBitCast(EltVal, FieldTy); 18754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 18764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 187770728532799d751b8e0e97719dcb3344a2fc97deChris Lattner DestField = Builder.CreateBitCast(DestField, 187870728532799d751b8e0e97719dcb3344a2fc97deChris Lattner PointerType::getUnqual(EltVal->getType())); 18794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 18804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(EltVal, DestField, SI); 18814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 18826974302e3ff20746268721959efed807c7711bfcBob Wilson 18839d34c4d678cfc836a59a114b7b2cf91e9dd5eac4Chris Lattner } else { 18844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const ArrayType *ATy = cast<ArrayType>(AllocaEltTy); 18854cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ArrayEltTy = ATy->getElementType(); 18864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ElementOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 18874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy); 18884b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 18894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift; 18906974302e3ff20746268721959efed807c7711bfcBob Wilson 18914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 18924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-ElementOffset; 18936974302e3ff20746268721959efed807c7711bfcBob Wilson else 18944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = 0; 18956974302e3ff20746268721959efed807c7711bfcBob Wilson 18964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 18974cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 18984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ElementSizeBits == 0) continue; 18996974302e3ff20746268721959efed807c7711bfcBob Wilson 19004cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *EltVal = SrcVal; 19014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 19024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift); 190370728532799d751b8e0e97719dcb3344a2fc97deChris Lattner EltVal = Builder.CreateLShr(EltVal, ShiftVal, "sroa.store.elt"); 19044cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 19056974302e3ff20746268721959efed807c7711bfcBob Wilson 19064cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Truncate down to an integer of the right size. 19074cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (ElementSizeBits != AllocaSizeBits) 190870728532799d751b8e0e97719dcb3344a2fc97deChris Lattner EltVal = Builder.CreateTrunc(EltVal, 190970728532799d751b8e0e97719dcb3344a2fc97deChris Lattner IntegerType::get(SI->getContext(), 191070728532799d751b8e0e97719dcb3344a2fc97deChris Lattner ElementSizeBits)); 19114cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *DestField = NewElts[i]; 19124cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (EltVal->getType() == ArrayEltTy) { 19134cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Storing to an integer field of this size, just do it. 19144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else if (ArrayEltTy->isFloatingPointTy() || 19154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ArrayEltTy->isVectorTy()) { 19164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Bitcast to the right element type (for fp/vector values). 191770728532799d751b8e0e97719dcb3344a2fc97deChris Lattner EltVal = Builder.CreateBitCast(EltVal, ArrayEltTy); 19184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 19194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Otherwise, bitcast the dest pointer (for aggregates). 192070728532799d751b8e0e97719dcb3344a2fc97deChris Lattner DestField = Builder.CreateBitCast(DestField, 192170728532799d751b8e0e97719dcb3344a2fc97deChris Lattner PointerType::getUnqual(EltVal->getType())); 19224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 19234cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner new StoreInst(EltVal, DestField, SI); 19246974302e3ff20746268721959efed807c7711bfcBob Wilson 19254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 19264cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift -= ElementOffset; 19276974302e3ff20746268721959efed807c7711bfcBob Wilson else 19284cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift += ElementOffset; 19294cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 1930800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 19316974302e3ff20746268721959efed807c7711bfcBob Wilson 19324cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(SI); 1933800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 1934800de31776356910eb877e71df9f32b0a6215324Chris Lattner 19354cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// RewriteLoadUserOfWholeAlloca - We found a load of the entire allocation to 19364cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// an integer. Load the individual pieces to form the aggregate value. 19374cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnervoid SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI, 19384cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SmallVector<AllocaInst*, 32> &NewElts) { 19394cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Extract each element out of the NewElts according to its structure offset 19404cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // and form the result value. 19414cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *AllocaEltTy = AI->getAllocatedType(); 19424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy); 19436974302e3ff20746268721959efed807c7711bfcBob Wilson 19444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << '\n' << *LI 19454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner << '\n'); 19466974302e3ff20746268721959efed807c7711bfcBob Wilson 19474cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // There are two forms here: AI could be an array or struct. Both cases 19484cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // have different ways to compute the element offset. 19494cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const StructLayout *Layout = 0; 19504cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t ArrayEltBitOffset = 0; 19514cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) { 19524cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Layout = TD->getStructLayout(EltSTy); 19534cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } else { 19544cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType(); 19554cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ArrayEltBitOffset = TD->getTypeAllocSizeInBits(ArrayEltTy); 19566974302e3ff20746268721959efed807c7711bfcBob Wilson } 19576974302e3ff20746268721959efed807c7711bfcBob Wilson 19586974302e3ff20746268721959efed807c7711bfcBob Wilson Value *ResultVal = 19594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Constant::getNullValue(IntegerType::get(LI->getContext(), AllocaSizeBits)); 19606974302e3ff20746268721959efed807c7711bfcBob Wilson 19614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner for (unsigned i = 0, e = NewElts.size(); i != e; ++i) { 19624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Load the value from the alloca. If the NewElt is an aggregate, cast 19634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the pointer to an integer of the same size before doing the load. 19644cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *SrcField = NewElts[i]; 19654cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner const Type *FieldTy = 19664cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner cast<PointerType>(SrcField->getType())->getElementType(); 19674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy); 19686974302e3ff20746268721959efed807c7711bfcBob Wilson 19694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Ignore zero sized fields like {}, they obviously contain no data. 19704cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (FieldSizeBits == 0) continue; 19716974302e3ff20746268721959efed807c7711bfcBob Wilson 19726974302e3ff20746268721959efed807c7711bfcBob Wilson const IntegerType *FieldIntTy = IntegerType::get(LI->getContext(), 19734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner FieldSizeBits); 19744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (!FieldTy->isIntegerTy() && !FieldTy->isFloatingPointTy() && 19754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner !FieldTy->isVectorTy()) 19764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new BitCastInst(SrcField, 19774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PointerType::getUnqual(FieldIntTy), 19784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner "", LI); 19794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new LoadInst(SrcField, "sroa.load.elt", LI); 198029e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 19814cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // If SrcField is a fp or vector of the right size but that isn't an 19824cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // integer type, bitcast to an integer so we can shift it. 19834cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcField->getType() != FieldIntTy) 19844cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI); 198529e641761e81bd000bdc4ccfae479c6dda18e402Chris Lattner 19864cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Zero extend the field to be the same size as the final alloca so that 19874cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // we can shift and insert it. 19884cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (SrcField->getType() != ResultVal->getType()) 19894cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI); 19906974302e3ff20746268721959efed807c7711bfcBob Wilson 19914cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Determine the number of bits to shift SrcField. 19924cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner uint64_t Shift; 19934cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Layout) // Struct case. 19944cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = Layout->getElementOffsetInBits(i); 19954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner else // Array case. 19964cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = i*ArrayEltBitOffset; 19976974302e3ff20746268721959efed807c7711bfcBob Wilson 19984cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->isBigEndian()) 19994cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth(); 20006974302e3ff20746268721959efed807c7711bfcBob Wilson 20014cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Shift) { 20024cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift); 20034cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI); 20049b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 20054cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 20061495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner // Don't create an 'or x, 0' on the first iteration. 20071495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner if (!isa<Constant>(ResultVal) || 20081495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner !cast<Constant>(ResultVal)->isNullValue()) 20091495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI); 20101495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner else 20111495247f517c0ac3aeeb9e6c7c0205dd7849d332Chris Lattner ResultVal = SrcField; 20129b872db775797dea4b391a9347cfbd2ca9c558e2Chris Lattner } 20134b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 20144cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Handle tail padding by truncating the result 20154cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits) 20164cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI); 20174b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 20184cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner LI->replaceAllUsesWith(ResultVal); 20194cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DeadInsts.push_back(LI); 20204cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 20214cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 20224cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// HasPadding - Return true if the specified type has any structure or 2023694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson/// alignment padding in between the elements that would be split apart 2024694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson/// by SROA; return false otherwise. 20254cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerstatic bool HasPadding(const Type *Ty, const TargetData &TD) { 2026694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 2027694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson Ty = ATy->getElementType(); 2028694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson return TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty); 2029694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson } 20304cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 2031694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson // SROA currently handles only Arrays and Structs. 2032694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson const StructType *STy = cast<StructType>(Ty); 2033694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson const StructLayout *SL = TD.getStructLayout(STy); 2034694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson unsigned PrevFieldBitOffset = 0; 2035694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 2036694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson unsigned FieldBitOffset = SL->getElementOffsetInBits(i); 2037694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson 2038694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson // Check to see if there is any padding between this element and the 2039694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson // previous one. 2040694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson if (i) { 2041694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson unsigned PrevFieldEnd = 20424cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1)); 2043694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson if (PrevFieldEnd < FieldBitOffset) 20444cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 20454cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner } 2046694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson PrevFieldBitOffset = FieldBitOffset; 20472e0d5f84325303fa95997cd66485811bd0a6ef70Chris Lattner } 2048694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson // Check for tail padding. 2049694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson if (unsigned EltCount = STy->getNumElements()) { 2050694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson unsigned PrevFieldEnd = PrevFieldBitOffset + 2051694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson TD.getTypeSizeInBits(STy->getElementType(EltCount-1)); 2052694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson if (PrevFieldEnd < SL->getSizeInBits()) 2053694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson return true; 2054694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson } 2055694a10e7d8410f24639971224ce0e282c8cd04cbBob Wilson return false; 20564cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner} 20574b3dfbd220835cbba519162712c9cb6afaa44059Duncan Sands 20584cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of 20594cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// an aggregate can be broken down into elements. Return 0 if not, 3 if safe, 20604cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner/// or 1 if safe after canonicalization has been performed. 20614cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattnerbool SROA::isSafeAllocaToScalarRepl(AllocaInst *AI) { 20624cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Loop over the use list of the alloca. We can only transform it if all of 20634cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // the users are safe to transform. 20646c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner AllocaInfo Info(AI); 20656974302e3ff20746268721959efed807c7711bfcBob Wilson 20666c95d24927b11fb76bc3e76ebe6a8198d74fc178Chris Lattner isSafeForScalarRepl(AI, 0, Info); 20674cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isUnsafe) { 20684cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner DEBUG(dbgs() << "Cannot transform: " << *AI << '\n'); 20694cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 2070800de31776356910eb877e71df9f32b0a6215324Chris Lattner } 20716974302e3ff20746268721959efed807c7711bfcBob Wilson 20724cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // Okay, we know all the users are promotable. If the aggregate is a memcpy 20734cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // source and destination, we have to be careful. In particular, the memcpy 20744cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // could be moving around elements that live in structure padding of the LLVM 20754cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // types, but may actually be used. In these cases, we refuse to promote the 20764cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner // struct. 20774cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner if (Info.isMemCpySrc && Info.isMemCpyDst && 20784cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner HasPadding(AI->getAllocatedType(), *TD)) 20794cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return false; 20804cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner 2081396a0567cf959d86a8a1ad185e54d84f5dacbacfChris Lattner // If the alloca never has an access to just *part* of it, but is accessed 2082396a0567cf959d86a8a1ad185e54d84f5dacbacfChris Lattner // via loads and stores, then we should use ConvertToScalarInfo to promote 20837e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner // the alloca instead of promoting each piece at a time and inserting fission 20847e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner // and fusion code. 20857e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner if (!Info.hasSubelementAccess && Info.hasALoadOrStore) { 20867e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner // If the struct/array just has one element, use basic SRoA. 20877e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) { 20887e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner if (ST->getNumElements() > 1) return false; 20897e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner } else { 20907e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner if (cast<ArrayType>(AI->getAllocatedType())->getNumElements() > 1) 20917e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner return false; 20927e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner } 20937e9b427c879ae32b72fd24aeaf011e87e5692fd7Chris Lattner } 2094145c532e68acdf70d40bab5bc2034f692848b8dcChris Lattner 20954cc576bc5ea27951f3bb15ccefbe483293bf8eafChris Lattner return true; 2096800de31776356910eb877e71df9f32b0a6215324Chris Lattner} 2097800de31776356910eb877e71df9f32b0a6215324Chris Lattner 2098800de31776356910eb877e71df9f32b0a6215324Chris Lattner 209979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 210079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// PointsToConstantGlobal - Return true if V (possibly indirectly) points to 210179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// some part of a constant global variable. This intentionally only accepts 210279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// constant expressions because we don't can't rewrite arbitrary instructions. 210379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattnerstatic bool PointsToConstantGlobal(Value *V) { 210479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 210579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return GV->isConstant(); 210679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 21076974302e3ff20746268721959efed807c7711bfcBob Wilson if (CE->getOpcode() == Instruction::BitCast || 210879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner CE->getOpcode() == Instruction::GetElementPtr) 210979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return PointsToConstantGlobal(CE->getOperand(0)); 211079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 211179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 211279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 211379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) 211479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// pointer to an alloca. Ignore any reads of the pointer, return false if we 211579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// see any stores or other unknown uses. If we see pointer arithmetic, keep 211679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// track of whether it moves the pointer (with isOffset) but otherwise traverse 211779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to 2118081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky/// the alloca, and if the source pointer is a pointer to a constant global, we 211979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// can optimize this. 212031d80103d56c026403d7fb6c50833664ff63ddcbChris Lattnerstatic bool isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy, 212179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner bool isOffset) { 212279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) { 21238a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif User *U = cast<Instruction>(*UI); 21248a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif 21252e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 21266e733d34ca487ab7ff8a6def018a933620393869Chris Lattner // Ignore non-volatile loads, they are always ok. 21272e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (LI->isVolatile()) return false; 21282e61849f45144f2f05d57b00947df7e101610694Chris Lattner continue; 21292e61849f45144f2f05d57b00947df7e101610694Chris Lattner } 21306974302e3ff20746268721959efed807c7711bfcBob Wilson 21318a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { 213279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If uses of the bitcast are ok, we are ok. 213379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset)) 213479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 213579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 213679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 21378a8a4350db3e66a517dc179ba38439c66bb726a8Gabor Greif if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 213879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the GEP has all zero indices, it doesn't offset the pointer. If it 213979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // doesn't, it does. 214079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy, 214179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner isOffset || !GEP->hasAllZeroIndices())) 214279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 214379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner continue; 214479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 21456974302e3ff20746268721959efed807c7711bfcBob Wilson 21466248065194778c866164b0c10f09f0f0d91b91acChris Lattner if (CallSite CS = U) { 21476248065194778c866164b0c10f09f0f0d91b91acChris Lattner // If this is a readonly/readnone call site, then we know it is just a 21486248065194778c866164b0c10f09f0f0d91b91acChris Lattner // load and we can ignore it. 2149a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner if (CS.onlyReadsMemory()) 2150a9be1df6d7a9b5a07253d83a634ae5876e7e5550Chris Lattner continue; 2151081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky 2152081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky // If this is the function being called then we treat it like a load and 2153081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky // ignore it. 2154081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky if (CS.isCallee(UI)) 2155081f80078dccf02c1f9c61378ff88bbf1b4afb5eNick Lewycky continue; 21566974302e3ff20746268721959efed807c7711bfcBob Wilson 21576248065194778c866164b0c10f09f0f0d91b91acChris Lattner // If this is being passed as a byval argument, the caller is making a 21586248065194778c866164b0c10f09f0f0d91b91acChris Lattner // copy, so it is only a read of the alloca. 21596248065194778c866164b0c10f09f0f0d91b91acChris Lattner unsigned ArgNo = CS.getArgumentNo(UI); 21606248065194778c866164b0c10f09f0f0d91b91acChris Lattner if (CS.paramHasAttr(ArgNo+1, Attribute::ByVal)) 21616248065194778c866164b0c10f09f0f0d91b91acChris Lattner continue; 21626248065194778c866164b0c10f09f0f0d91b91acChris Lattner } 21636974302e3ff20746268721959efed807c7711bfcBob Wilson 216479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If this is isn't our memcpy/memmove, reject it as something we can't 216579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // handle. 216631d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner MemTransferInst *MI = dyn_cast<MemTransferInst>(U); 216731d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner if (MI == 0) 216879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 21696974302e3ff20746268721959efed807c7711bfcBob Wilson 21702e61849f45144f2f05d57b00947df7e101610694Chris Lattner // If the transfer is using the alloca as a source of the transfer, then 21712e29ebd9e8efefe3ff926aa99cf2e5323665998eChris Lattner // ignore it since it is a load (unless the transfer is volatile). 21722e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (UI.getOperandNo() == 1) { 21732e61849f45144f2f05d57b00947df7e101610694Chris Lattner if (MI->isVolatile()) return false; 21742e61849f45144f2f05d57b00947df7e101610694Chris Lattner continue; 21752e61849f45144f2f05d57b00947df7e101610694Chris Lattner } 217679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 217779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If we already have seen a copy, reject the second one. 217879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (TheCopy) return false; 21796974302e3ff20746268721959efed807c7711bfcBob Wilson 218079b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the pointer has been offset from the start of the alloca, we can't 218179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // safely handle this. 218279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (isOffset) return false; 218379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 218479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the memintrinsic isn't using the alloca as the dest, reject it. 2185a6aac4c5bc22bb10c7adb11eee3f82c703af7002Gabor Greif if (UI.getOperandNo() != 0) return false; 21866974302e3ff20746268721959efed807c7711bfcBob Wilson 218779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // If the source of the memcpy/move is not a constant global, reject it. 218831d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner if (!PointsToConstantGlobal(MI->getSource())) 218979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return false; 21906974302e3ff20746268721959efed807c7711bfcBob Wilson 219179b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner // Otherwise, the transform is safe. Remember the copy instruction. 219279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner TheCopy = MI; 219379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner } 219479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return true; 219579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 219679b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner 219779b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only 219879b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// modified by a copy from a constant global. If we can prove this, we can 219979b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner/// replace any uses of the alloca with uses of the global directly. 220031d80103d56c026403d7fb6c50833664ff63ddcbChris LattnerMemTransferInst *SROA::isOnlyCopiedFromConstantGlobal(AllocaInst *AI) { 220131d80103d56c026403d7fb6c50833664ff63ddcbChris Lattner MemTransferInst *TheCopy = 0; 220279b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false)) 220379b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return TheCopy; 220479b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner return 0; 220579b3bd395dc3303cde65e18e0524ed2f70268c99Chris Lattner} 2206