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