lib/Transforms/Scalar/ScalarReplAggregates.cpp

   1 //===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This transformation implements the well known scalar replacement of
  11 // aggregates transformation.  This xform breaks up alloca instructions of
  12 // aggregate type (structure or array) into individual alloca instructions for
  13 // each member (if possible).  Then, if possible, it transforms the individual
  14 // alloca instructions into nice clean scalar SSA form.
  15 //
  16 // This combines a simple SRoA algorithm with the Mem2Reg algorithm because
  17 // often interact, especially for C++ programs.  As such, iterating between
  18 // SRoA, then Mem2Reg until we run out of things to promote works well.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #define DEBUG_TYPE "scalarrepl"
  23 #include "llvm/Transforms/Scalar.h"
  24 #include "llvm/Constants.h"
  25 #include "llvm/DerivedTypes.h"
  26 #include "llvm/Function.h"
  27 #include "llvm/GlobalVariable.h"
  28 #include "llvm/Instructions.h"
  29 #include "llvm/IntrinsicInst.h"
  30 #include "llvm/LLVMContext.h"
  31 #include "llvm/Module.h"
  32 #include "llvm/Pass.h"
  33 #include "llvm/Analysis/DominanceFrontier.h"
  34 #include "llvm/Analysis/ValueTracking.h"
  35 #include "llvm/Target/TargetData.h"
  36 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
  37 #include "llvm/Transforms/Utils/Local.h"
  38 #include "llvm/Transforms/Utils/SSAUpdater.h"
  39 #include "llvm/Support/CallSite.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/ErrorHandling.h"
  42 #include "llvm/Support/GetElementPtrTypeIterator.h"
  43 #include "llvm/Support/IRBuilder.h"
  44 #include "llvm/Support/MathExtras.h"
  45 #include "llvm/Support/raw_ostream.h"
  46 #include "llvm/ADT/SmallVector.h"
  47 #include "llvm/ADT/Statistic.h"
  48 using namespace llvm;
  49
  50 STATISTIC(NumReplaced,  "Number of allocas broken up");
  51 STATISTIC(NumPromoted,  "Number of allocas promoted");
  52 STATISTIC(NumConverted, "Number of aggregates converted to scalar");
  53 STATISTIC(NumGlobals,   "Number of allocas copied from constant global");
  54
  55 namespace {
  56   struct SROA : public FunctionPass {
  57     SROA(int T, bool hasDF, char &ID)
  58       : FunctionPass(ID), HasDomFrontiers(hasDF) {
  59       if (T == -1)
  60         SRThreshold = 128;
  61       else
  62         SRThreshold = T;
  63     }
  64
  65     bool runOnFunction(Function &F);
  66
  67     bool performScalarRepl(Function &F);
  68     bool performPromotion(Function &F);
  69
  70   private:
  71     bool HasDomFrontiers;
  72     TargetData *TD;
  73
  74     /// DeadInsts - Keep track of instructions we have made dead, so that
  75     /// we can remove them after we are done working.
  76     SmallVector<Value*, 32> DeadInsts;
  77
  78     /// AllocaInfo - When analyzing uses of an alloca instruction, this captures
  79     /// information about the uses.  All these fields are initialized to false
  80     /// and set to true when something is learned.
  81     struct AllocaInfo {
  82       /// isUnsafe - This is set to true if the alloca cannot be SROA'd.
  83       bool isUnsafe : 1;
  84
  85       /// isMemCpySrc - This is true if this aggregate is memcpy'd from.
  86       bool isMemCpySrc : 1;
  87
  88       /// isMemCpyDst - This is true if this aggregate is memcpy'd into.
  89       bool isMemCpyDst : 1;
  90
  91       AllocaInfo()
  92         : isUnsafe(false), isMemCpySrc(false), isMemCpyDst(false) {}
  93     };
  94
  95     unsigned SRThreshold;
  96
  97     void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; }
  98
  99     bool isSafeAllocaToScalarRepl(AllocaInst *AI);
 100
 101     void isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset,
 102                              AllocaInfo &Info);
 103     void isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t &Offset,
 104                    AllocaInfo &Info);
 105     void isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t MemSize,
 106                          const Type *MemOpType, bool isStore, AllocaInfo &Info);
 107     bool TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size);
 108     uint64_t FindElementAndOffset(const Type *&T, uint64_t &Offset,
 109                                   const Type *&IdxTy);
 110
 111     void DoScalarReplacement(AllocaInst *AI,
 112                              std::vector<AllocaInst*> &WorkList);
 113     void DeleteDeadInstructions();
 114
 115     void RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset,
 116                               SmallVector<AllocaInst*, 32> &NewElts);
 117     void RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset,
 118                         SmallVector<AllocaInst*, 32> &NewElts);
 119     void RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset,
 120                     SmallVector<AllocaInst*, 32> &NewElts);
 121     void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst,
 122                                       AllocaInst *AI,
 123                                       SmallVector<AllocaInst*, 32> &NewElts);
 124     void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI,
 125                                        SmallVector<AllocaInst*, 32> &NewElts);
 126     void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI,
 127                                       SmallVector<AllocaInst*, 32> &NewElts);
 128
 129     static MemTransferInst *isOnlyCopiedFromConstantGlobal(AllocaInst *AI);
 130   };
 131
 132   // SROA_DF - SROA that uses DominanceFrontier.
 133   struct SROA_DF : public SROA {
 134     static char ID;
 135   public:
 136     SROA_DF(int T = -1) : SROA(T, true, ID) {
 137       initializeSROA_DFPass(*PassRegistry::getPassRegistry());
 138     }
 139
 140     // getAnalysisUsage - This pass does not require any passes, but we know it
 141     // will not alter the CFG, so say so.
 142     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 143       AU.addRequired<DominatorTree>();
 144       AU.addRequired<DominanceFrontier>();
 145       AU.setPreservesCFG();
 146     }
 147   };
 148
 149   // SROA_SSAUp - SROA that uses SSAUpdater.
 150   struct SROA_SSAUp : public SROA {
 151     static char ID;
 152   public:
 153     SROA_SSAUp(int T = -1) : SROA(T, false, ID) {
 154       initializeSROA_SSAUpPass(*PassRegistry::getPassRegistry());
 155     }
 156
 157     // getAnalysisUsage - This pass does not require any passes, but we know it
 158     // will not alter the CFG, so say so.
 159     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 160       AU.setPreservesCFG();
 161     }
 162   };
 163
 164 }
 165
 166 char SROA_DF::ID = 0;
 167 char SROA_SSAUp::ID = 0;
 168
 169 INITIALIZE_PASS_BEGIN(SROA_DF, "scalarrepl",
 170                 "Scalar Replacement of Aggregates (DF)", false, false)
 171 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 172 INITIALIZE_PASS_DEPENDENCY(DominanceFrontier)
 173 INITIALIZE_PASS_END(SROA_DF, "scalarrepl",
 174                 "Scalar Replacement of Aggregates (DF)", false, false)
 175
 176 INITIALIZE_PASS_BEGIN(SROA_SSAUp, "scalarrepl-ssa",
 177                       "Scalar Replacement of Aggregates (SSAUp)", false, false)
 178 INITIALIZE_PASS_END(SROA_SSAUp, "scalarrepl-ssa",
 179                     "Scalar Replacement of Aggregates (SSAUp)", false, false)
 180
 181 // Public interface to the ScalarReplAggregates pass
 182 FunctionPass *llvm::createScalarReplAggregatesPass(int Threshold,
 183                                                    bool UseDomFrontier) {
 184   if (UseDomFrontier)
 185     return new SROA_DF(Threshold);
 186   return new SROA_SSAUp(Threshold);
 187 }
 188
 189
 190 //===----------------------------------------------------------------------===//
 191 // Convert To Scalar Optimization.
 192 //===----------------------------------------------------------------------===//
 193
 194 namespace {
 195 /// ConvertToScalarInfo - This class implements the "Convert To Scalar"
 196 /// optimization, which scans the uses of an alloca and determines if it can
 197 /// rewrite it in terms of a single new alloca that can be mem2reg'd.
 198 class ConvertToScalarInfo {
 199   /// AllocaSize - The size of the alloca being considered.
 200   unsigned AllocaSize;
 201   const TargetData &TD;
 202
 203   /// IsNotTrivial - This is set to true if there is some access to the object
 204   /// which means that mem2reg can't promote it.
 205   bool IsNotTrivial;
 206
 207   /// VectorTy - This tracks the type that we should promote the vector to if
 208   /// it is possible to turn it into a vector.  This starts out null, and if it
 209   /// isn't possible to turn into a vector type, it gets set to VoidTy.
 210   const Type *VectorTy;
 211
 212   /// HadAVector - True if there is at least one vector access to the alloca.
 213   /// We don't want to turn random arrays into vectors and use vector element
 214   /// insert/extract, but if there are element accesses to something that is
 215   /// also declared as a vector, we do want to promote to a vector.
 216   bool HadAVector;
 217
 218 public:
 219   explicit ConvertToScalarInfo(unsigned Size, const TargetData &td)
 220     : AllocaSize(Size), TD(td) {
 221     IsNotTrivial = false;
 222     VectorTy = 0;
 223     HadAVector = false;
 224   }
 225
 226   AllocaInst *TryConvert(AllocaInst *AI);
 227
 228 private:
 229   bool CanConvertToScalar(Value *V, uint64_t Offset);
 230   void MergeInType(const Type *In, uint64_t Offset);
 231   void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset);
 232
 233   Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType,
 234                                     uint64_t Offset, IRBuilder<> &Builder);
 235   Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal,
 236                                    uint64_t Offset, IRBuilder<> &Builder);
 237 };
 238 } // end anonymous namespace.
 239
 240
 241 /// IsVerbotenVectorType - Return true if this is a vector type ScalarRepl isn't
 242 /// allowed to form.  We do this to avoid MMX types, which is a complete hack,
 243 /// but is required until the backend is fixed.
 244 static bool IsVerbotenVectorType(const VectorType *VTy, const Instruction *I) {
 245   StringRef Triple(I->getParent()->getParent()->getParent()->getTargetTriple());
 246   if (!Triple.startswith("i386") &&
 247       !Triple.startswith("x86_64"))
 248     return false;
 249
 250   // Reject all the MMX vector types.
 251   switch (VTy->getNumElements()) {
 252   default: return false;
 253   case 1: return VTy->getElementType()->isIntegerTy(64);
 254   case 2: return VTy->getElementType()->isIntegerTy(32);
 255   case 4: return VTy->getElementType()->isIntegerTy(16);
 256   case 8: return VTy->getElementType()->isIntegerTy(8);
 257   }
 258 }
 259
 260
 261 /// TryConvert - Analyze the specified alloca, and if it is safe to do so,
 262 /// rewrite it to be a new alloca which is mem2reg'able.  This returns the new
 263 /// alloca if possible or null if not.
 264 AllocaInst *ConvertToScalarInfo::TryConvert(AllocaInst *AI) {
 265   // If we can't convert this scalar, or if mem2reg can trivially do it, bail
 266   // out.
 267   if (!CanConvertToScalar(AI, 0) || !IsNotTrivial)
 268     return 0;
 269
 270   // If we were able to find a vector type that can handle this with
 271   // insert/extract elements, and if there was at least one use that had
 272   // a vector type, promote this to a vector.  We don't want to promote
 273   // random stuff that doesn't use vectors (e.g. <9 x double>) because then
 274   // we just get a lot of insert/extracts.  If at least one vector is
 275   // involved, then we probably really do have a union of vector/array.
 276   const Type *NewTy;
 277   if (VectorTy && VectorTy->isVectorTy() && HadAVector &&
 278       !IsVerbotenVectorType(cast<VectorType>(VectorTy), AI)) {
 279     DEBUG(dbgs() << "CONVERT TO VECTOR: " << *AI << "\n  TYPE = "
 280           << *VectorTy << '\n');
 281     NewTy = VectorTy;  // Use the vector type.
 282   } else {
 283     DEBUG(dbgs() << "CONVERT TO SCALAR INTEGER: " << *AI << "\n");
 284     // Create and insert the integer alloca.
 285     NewTy = IntegerType::get(AI->getContext(), AllocaSize*8);
 286   }
 287   AllocaInst *NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin());
 288   ConvertUsesToScalar(AI, NewAI, 0);
 289   return NewAI;
 290 }
 291
 292 /// MergeInType - Add the 'In' type to the accumulated vector type (VectorTy)
 293 /// so far at the offset specified by Offset (which is specified in bytes).
 294 ///
 295 /// There are two cases we handle here:
 296 ///   1) A union of vector types of the same size and potentially its elements.
 297 ///      Here we turn element accesses into insert/extract element operations.
 298 ///      This promotes a <4 x float> with a store of float to the third element
 299 ///      into a <4 x float> that uses insert element.
 300 ///   2) A fully general blob of memory, which we turn into some (potentially
 301 ///      large) integer type with extract and insert operations where the loads
 302 ///      and stores would mutate the memory.  We mark this by setting VectorTy
 303 ///      to VoidTy.
 304 void ConvertToScalarInfo::MergeInType(const Type *In, uint64_t Offset) {
 305   // If we already decided to turn this into a blob of integer memory, there is
 306   // nothing to be done.
 307   if (VectorTy && VectorTy->isVoidTy())
 308     return;
 309
 310   // If this could be contributing to a vector, analyze it.
 311
 312   // If the In type is a vector that is the same size as the alloca, see if it
 313   // matches the existing VecTy.
 314   if (const VectorType *VInTy = dyn_cast<VectorType>(In)) {
 315     // Remember if we saw a vector type.
 316     HadAVector = true;
 317
 318     if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) {
 319       // If we're storing/loading a vector of the right size, allow it as a
 320       // vector.  If this the first vector we see, remember the type so that
 321       // we know the element size.  If this is a subsequent access, ignore it
 322       // even if it is a differing type but the same size.  Worst case we can
 323       // bitcast the resultant vectors.
 324       if (VectorTy == 0)
 325         VectorTy = VInTy;
 326       return;
 327     }
 328   } else if (In->isFloatTy() || In->isDoubleTy() ||
 329              (In->isIntegerTy() && In->getPrimitiveSizeInBits() >= 8 &&
 330               isPowerOf2_32(In->getPrimitiveSizeInBits()))) {
 331     // If we're accessing something that could be an element of a vector, see
 332     // if the implied vector agrees with what we already have and if Offset is
 333     // compatible with it.
 334     unsigned EltSize = In->getPrimitiveSizeInBits()/8;
 335     if (Offset % EltSize == 0 && AllocaSize % EltSize == 0 &&
 336         (VectorTy == 0 ||
 337          cast<VectorType>(VectorTy)->getElementType()
 338                ->getPrimitiveSizeInBits()/8 == EltSize)) {
 339       if (VectorTy == 0)
 340         VectorTy = VectorType::get(In, AllocaSize/EltSize);
 341       return;
 342     }
 343   }
 344
 345   // Otherwise, we have a case that we can't handle with an optimized vector
 346   // form.  We can still turn this into a large integer.
 347   VectorTy = Type::getVoidTy(In->getContext());
 348 }
 349
 350 /// CanConvertToScalar - V is a pointer.  If we can convert the pointee and all
 351 /// its accesses to a single vector type, return true and set VecTy to
 352 /// the new type.  If we could convert the alloca into a single promotable
 353 /// integer, return true but set VecTy to VoidTy.  Further, if the use is not a
 354 /// completely trivial use that mem2reg could promote, set IsNotTrivial.  Offset
 355 /// is the current offset from the base of the alloca being analyzed.
 356 ///
 357 /// If we see at least one access to the value that is as a vector type, set the
 358 /// SawVec flag.
 359 bool ConvertToScalarInfo::CanConvertToScalar(Value *V, uint64_t Offset) {
 360   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
 361     Instruction *User = cast<Instruction>(*UI);
 362
 363     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
 364       // Don't break volatile loads.
 365       if (LI->isVolatile())
 366         return false;
 367       // Don't touch MMX operations.
 368       if (LI->getType()->isX86_MMXTy())
 369         return false;
 370       MergeInType(LI->getType(), Offset);
 371       continue;
 372     }
 373
 374     if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
 375       // Storing the pointer, not into the value?
 376       if (SI->getOperand(0) == V || SI->isVolatile()) return false;
 377       // Don't touch MMX operations.
 378       if (SI->getOperand(0)->getType()->isX86_MMXTy())
 379         return false;
 380       MergeInType(SI->getOperand(0)->getType(), Offset);
 381       continue;
 382     }
 383
 384     if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
 385       IsNotTrivial = true;  // Can't be mem2reg'd.
 386       if (!CanConvertToScalar(BCI, Offset))
 387         return false;
 388       continue;
 389     }
 390
 391     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
 392       // If this is a GEP with a variable indices, we can't handle it.
 393       if (!GEP->hasAllConstantIndices())
 394         return false;
 395
 396       // Compute the offset that this GEP adds to the pointer.
 397       SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end());
 398       uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(),
 399                                                &Indices[0], Indices.size());
 400       // See if all uses can be converted.
 401       if (!CanConvertToScalar(GEP, Offset+GEPOffset))
 402         return false;
 403       IsNotTrivial = true;  // Can't be mem2reg'd.
 404       continue;
 405     }
 406
 407     // If this is a constant sized memset of a constant value (e.g. 0) we can
 408     // handle it.
 409     if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) {
 410       // Store of constant value and constant size.
 411       if (!isa<ConstantInt>(MSI->getValue()) ||
 412           !isa<ConstantInt>(MSI->getLength()))
 413         return false;
 414       IsNotTrivial = true;  // Can't be mem2reg'd.
 415       continue;
 416     }
 417
 418     // If this is a memcpy or memmove into or out of the whole allocation, we
 419     // can handle it like a load or store of the scalar type.
 420     if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) {
 421       ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength());
 422       if (Len == 0 || Len->getZExtValue() != AllocaSize || Offset != 0)
 423         return false;
 424
 425       IsNotTrivial = true;  // Can't be mem2reg'd.
 426       continue;
 427     }
 428
 429     // Otherwise, we cannot handle this!
 430     return false;
 431   }
 432
 433   return true;
 434 }
 435
 436 /// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca
 437 /// directly.  This happens when we are converting an "integer union" to a
 438 /// single integer scalar, or when we are converting a "vector union" to a
 439 /// vector with insert/extractelement instructions.
 440 ///
 441 /// Offset is an offset from the original alloca, in bits that need to be
 442 /// shifted to the right.  By the end of this, there should be no uses of Ptr.
 443 void ConvertToScalarInfo::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI,
 444                                               uint64_t Offset) {
 445   while (!Ptr->use_empty()) {
 446     Instruction *User = cast<Instruction>(Ptr->use_back());
 447
 448     if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) {
 449       ConvertUsesToScalar(CI, NewAI, Offset);
 450       CI->eraseFromParent();
 451       continue;
 452     }
 453
 454     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
 455       // Compute the offset that this GEP adds to the pointer.
 456       SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end());
 457       uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(),
 458                                                &Indices[0], Indices.size());
 459       ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8);
 460       GEP->eraseFromParent();
 461       continue;
 462     }
 463
 464     IRBuilder<> Builder(User);
 465
 466     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
 467       // The load is a bit extract from NewAI shifted right by Offset bits.
 468       Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp");
 469       Value *NewLoadVal
 470         = ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder);
 471       LI->replaceAllUsesWith(NewLoadVal);
 472       LI->eraseFromParent();
 473       continue;
 474     }
 475
 476     if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
 477       assert(SI->getOperand(0) != Ptr && "Consistency error!");
 478       Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in");
 479       Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset,
 480                                              Builder);
 481       Builder.CreateStore(New, NewAI);
 482       SI->eraseFromParent();
 483
 484       // If the load we just inserted is now dead, then the inserted store
 485       // overwrote the entire thing.
 486       if (Old->use_empty())
 487         Old->eraseFromParent();
 488       continue;
 489     }
 490
 491     // If this is a constant sized memset of a constant value (e.g. 0) we can
 492     // transform it into a store of the expanded constant value.
 493     if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) {
 494       assert(MSI->getRawDest() == Ptr && "Consistency error!");
 495       unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue();
 496       if (NumBytes != 0) {
 497         unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue();
 498
 499         // Compute the value replicated the right number of times.
 500         APInt APVal(NumBytes*8, Val);
 501
 502         // Splat the value if non-zero.
 503         if (Val)
 504           for (unsigned i = 1; i != NumBytes; ++i)
 505             APVal |= APVal << 8;
 506
 507         Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in");
 508         Value *New = ConvertScalar_InsertValue(
 509                                     ConstantInt::get(User->getContext(), APVal),
 510                                                Old, Offset, Builder);
 511         Builder.CreateStore(New, NewAI);
 512
 513         // If the load we just inserted is now dead, then the memset overwrote
 514         // the entire thing.
 515         if (Old->use_empty())
 516           Old->eraseFromParent();
 517       }
 518       MSI->eraseFromParent();
 519       continue;
 520     }
 521
 522     // If this is a memcpy or memmove into or out of the whole allocation, we
 523     // can handle it like a load or store of the scalar type.
 524     if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) {
 525       assert(Offset == 0 && "must be store to start of alloca");
 526
 527       // If the source and destination are both to the same alloca, then this is
 528       // a noop copy-to-self, just delete it.  Otherwise, emit a load and store
 529       // as appropriate.
 530       AllocaInst *OrigAI = cast<AllocaInst>(GetUnderlyingObject(Ptr, 0));
 531
 532       if (GetUnderlyingObject(MTI->getSource(), 0) != OrigAI) {
 533         // Dest must be OrigAI, change this to be a load from the original
 534         // pointer (bitcasted), then a store to our new alloca.
 535         assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?");
 536         Value *SrcPtr = MTI->getSource();
 537         const PointerType* SPTy = cast<PointerType>(SrcPtr->getType());
 538         const PointerType* AIPTy = cast<PointerType>(NewAI->getType());
 539         if (SPTy->getAddressSpace() != AIPTy->getAddressSpace()) {
 540           AIPTy = PointerType::get(AIPTy->getElementType(),
 541                                    SPTy->getAddressSpace());
 542         }
 543         SrcPtr = Builder.CreateBitCast(SrcPtr, AIPTy);
 544
 545         LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval");
 546         SrcVal->setAlignment(MTI->getAlignment());
 547         Builder.CreateStore(SrcVal, NewAI);
 548       } else if (GetUnderlyingObject(MTI->getDest(), 0) != OrigAI) {
 549         // Src must be OrigAI, change this to be a load from NewAI then a store
 550         // through the original dest pointer (bitcasted).
 551         assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?");
 552         LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval");
 553
 554         const PointerType* DPTy = cast<PointerType>(MTI->getDest()->getType());
 555         const PointerType* AIPTy = cast<PointerType>(NewAI->getType());
 556         if (DPTy->getAddressSpace() != AIPTy->getAddressSpace()) {
 557           AIPTy = PointerType::get(AIPTy->getElementType(),
 558                                    DPTy->getAddressSpace());
 559         }
 560         Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), AIPTy);
 561
 562         StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr);
 563         NewStore->setAlignment(MTI->getAlignment());
 564       } else {
 565         // Noop transfer. Src == Dst
 566       }
 567
 568       MTI->eraseFromParent();
 569       continue;
 570     }
 571
 572     llvm_unreachable("Unsupported operation!");
 573   }
 574 }
 575
 576 /// ConvertScalar_ExtractValue - Extract a value of type ToType from an integer
 577 /// or vector value FromVal, extracting the bits from the offset specified by
 578 /// Offset.  This returns the value, which is of type ToType.
 579 ///
 580 /// This happens when we are converting an "integer union" to a single
 581 /// integer scalar, or when we are converting a "vector union" to a vector with
 582 /// insert/extractelement instructions.
 583 ///
 584 /// Offset is an offset from the original alloca, in bits that need to be
 585 /// shifted to the right.
 586 Value *ConvertToScalarInfo::
 587 ConvertScalar_ExtractValue(Value *FromVal, const Type *ToType,
 588                            uint64_t Offset, IRBuilder<> &Builder) {
 589   // If the load is of the whole new alloca, no conversion is needed.
 590   if (FromVal->getType() == ToType && Offset == 0)
 591     return FromVal;
 592
 593   // If the result alloca is a vector type, this is either an element
 594   // access or a bitcast to another vector type of the same size.
 595   if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) {
 596     if (ToType->isVectorTy())
 597       return Builder.CreateBitCast(FromVal, ToType, "tmp");
 598
 599     // Otherwise it must be an element access.
 600     unsigned Elt = 0;
 601     if (Offset) {
 602       unsigned EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType());
 603       Elt = Offset/EltSize;
 604       assert(EltSize*Elt == Offset && "Invalid modulus in validity checking");
 605     }
 606     // Return the element extracted out of it.
 607     Value *V = Builder.CreateExtractElement(FromVal, ConstantInt::get(
 608                     Type::getInt32Ty(FromVal->getContext()), Elt), "tmp");
 609     if (V->getType() != ToType)
 610       V = Builder.CreateBitCast(V, ToType, "tmp");
 611     return V;
 612   }
 613
 614   // If ToType is a first class aggregate, extract out each of the pieces and
 615   // use insertvalue's to form the FCA.
 616   if (const StructType *ST = dyn_cast<StructType>(ToType)) {
 617     const StructLayout &Layout = *TD.getStructLayout(ST);
 618     Value *Res = UndefValue::get(ST);
 619     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
 620       Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i),
 621                                         Offset+Layout.getElementOffsetInBits(i),
 622                                               Builder);
 623       Res = Builder.CreateInsertValue(Res, Elt, i, "tmp");
 624     }
 625     return Res;
 626   }
 627
 628   if (const ArrayType *AT = dyn_cast<ArrayType>(ToType)) {
 629     uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType());
 630     Value *Res = UndefValue::get(AT);
 631     for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
 632       Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(),
 633                                               Offset+i*EltSize, Builder);
 634       Res = Builder.CreateInsertValue(Res, Elt, i, "tmp");
 635     }
 636     return Res;
 637   }
 638
 639   // Otherwise, this must be a union that was converted to an integer value.
 640   const IntegerType *NTy = cast<IntegerType>(FromVal->getType());
 641
 642   // If this is a big-endian system and the load is narrower than the
 643   // full alloca type, we need to do a shift to get the right bits.
 644   int ShAmt = 0;
 645   if (TD.isBigEndian()) {
 646     // On big-endian machines, the lowest bit is stored at the bit offset
 647     // from the pointer given by getTypeStoreSizeInBits.  This matters for
 648     // integers with a bitwidth that is not a multiple of 8.
 649     ShAmt = TD.getTypeStoreSizeInBits(NTy) -
 650             TD.getTypeStoreSizeInBits(ToType) - Offset;
 651   } else {
 652     ShAmt = Offset;
 653   }
 654
 655   // Note: we support negative bitwidths (with shl) which are not defined.
 656   // We do this to support (f.e.) loads off the end of a structure where
 657   // only some bits are used.
 658   if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth())
 659     FromVal = Builder.CreateLShr(FromVal,
 660                                  ConstantInt::get(FromVal->getType(),
 661                                                            ShAmt), "tmp");
 662   else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth())
 663     FromVal = Builder.CreateShl(FromVal,
 664                                 ConstantInt::get(FromVal->getType(),
 665                                                           -ShAmt), "tmp");
 666
 667   // Finally, unconditionally truncate the integer to the right width.
 668   unsigned LIBitWidth = TD.getTypeSizeInBits(ToType);
 669   if (LIBitWidth < NTy->getBitWidth())
 670     FromVal =
 671       Builder.CreateTrunc(FromVal, IntegerType::get(FromVal->getContext(),
 672                                                     LIBitWidth), "tmp");
 673   else if (LIBitWidth > NTy->getBitWidth())
 674     FromVal =
 675        Builder.CreateZExt(FromVal, IntegerType::get(FromVal->getContext(),
 676                                                     LIBitWidth), "tmp");
 677
 678   // If the result is an integer, this is a trunc or bitcast.
 679   if (ToType->isIntegerTy()) {
 680     // Should be done.
 681   } else if (ToType->isFloatingPointTy() || ToType->isVectorTy()) {
 682     // Just do a bitcast, we know the sizes match up.
 683     FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp");
 684   } else {
 685     // Otherwise must be a pointer.
 686     FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp");
 687   }
 688   assert(FromVal->getType() == ToType && "Didn't convert right?");
 689   return FromVal;
 690 }
 691
 692 /// ConvertScalar_InsertValue - Insert the value "SV" into the existing integer
 693 /// or vector value "Old" at the offset specified by Offset.
 694 ///
 695 /// This happens when we are converting an "integer union" to a
 696 /// single integer scalar, or when we are converting a "vector union" to a
 697 /// vector with insert/extractelement instructions.
 698 ///
 699 /// Offset is an offset from the original alloca, in bits that need to be
 700 /// shifted to the right.
 701 Value *ConvertToScalarInfo::
 702 ConvertScalar_InsertValue(Value *SV, Value *Old,
 703                           uint64_t Offset, IRBuilder<> &Builder) {
 704   // Convert the stored type to the actual type, shift it left to insert
 705   // then 'or' into place.
 706   const Type *AllocaType = Old->getType();
 707   LLVMContext &Context = Old->getContext();
 708
 709   if (const VectorType *VTy = dyn_cast<VectorType>(AllocaType)) {
 710     uint64_t VecSize = TD.getTypeAllocSizeInBits(VTy);
 711     uint64_t ValSize = TD.getTypeAllocSizeInBits(SV->getType());
 712
 713     // Changing the whole vector with memset or with an access of a different
 714     // vector type?
 715     if (ValSize == VecSize)
 716       return Builder.CreateBitCast(SV, AllocaType, "tmp");
 717
 718     uint64_t EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType());
 719
 720     // Must be an element insertion.
 721     unsigned Elt = Offset/EltSize;
 722
 723     if (SV->getType() != VTy->getElementType())
 724       SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp");
 725
 726     SV = Builder.CreateInsertElement(Old, SV,
 727                      ConstantInt::get(Type::getInt32Ty(SV->getContext()), Elt),
 728                                      "tmp");
 729     return SV;
 730   }
 731
 732   // If SV is a first-class aggregate value, insert each value recursively.
 733   if (const StructType *ST = dyn_cast<StructType>(SV->getType())) {
 734     const StructLayout &Layout = *TD.getStructLayout(ST);
 735     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
 736       Value *Elt = Builder.CreateExtractValue(SV, i, "tmp");
 737       Old = ConvertScalar_InsertValue(Elt, Old,
 738                                       Offset+Layout.getElementOffsetInBits(i),
 739                                       Builder);
 740     }
 741     return Old;
 742   }
 743
 744   if (const ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) {
 745     uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType());
 746     for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
 747       Value *Elt = Builder.CreateExtractValue(SV, i, "tmp");
 748       Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder);
 749     }
 750     return Old;
 751   }
 752
 753   // If SV is a float, convert it to the appropriate integer type.
 754   // If it is a pointer, do the same.
 755   unsigned SrcWidth = TD.getTypeSizeInBits(SV->getType());
 756   unsigned DestWidth = TD.getTypeSizeInBits(AllocaType);
 757   unsigned SrcStoreWidth = TD.getTypeStoreSizeInBits(SV->getType());
 758   unsigned DestStoreWidth = TD.getTypeStoreSizeInBits(AllocaType);
 759   if (SV->getType()->isFloatingPointTy() || SV->getType()->isVectorTy())
 760     SV = Builder.CreateBitCast(SV,
 761                             IntegerType::get(SV->getContext(),SrcWidth), "tmp");
 762   else if (SV->getType()->isPointerTy())
 763     SV = Builder.CreatePtrToInt(SV, TD.getIntPtrType(SV->getContext()), "tmp");
 764
 765   // Zero extend or truncate the value if needed.
 766   if (SV->getType() != AllocaType) {
 767     if (SV->getType()->getPrimitiveSizeInBits() <
 768              AllocaType->getPrimitiveSizeInBits())
 769       SV = Builder.CreateZExt(SV, AllocaType, "tmp");
 770     else {
 771       // Truncation may be needed if storing more than the alloca can hold
 772       // (undefined behavior).
 773       SV = Builder.CreateTrunc(SV, AllocaType, "tmp");
 774       SrcWidth = DestWidth;
 775       SrcStoreWidth = DestStoreWidth;
 776     }
 777   }
 778
 779   // If this is a big-endian system and the store is narrower than the
 780   // full alloca type, we need to do a shift to get the right bits.
 781   int ShAmt = 0;
 782   if (TD.isBigEndian()) {
 783     // On big-endian machines, the lowest bit is stored at the bit offset
 784     // from the pointer given by getTypeStoreSizeInBits.  This matters for
 785     // integers with a bitwidth that is not a multiple of 8.
 786     ShAmt = DestStoreWidth - SrcStoreWidth - Offset;
 787   } else {
 788     ShAmt = Offset;
 789   }
 790
 791   // Note: we support negative bitwidths (with shr) which are not defined.
 792   // We do this to support (f.e.) stores off the end of a structure where
 793   // only some bits in the structure are set.
 794   APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth));
 795   if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) {
 796     SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(),
 797                            ShAmt), "tmp");
 798     Mask <<= ShAmt;
 799   } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) {
 800     SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(),
 801                             -ShAmt), "tmp");
 802     Mask = Mask.lshr(-ShAmt);
 803   }
 804
 805   // Mask out the bits we are about to insert from the old value, and or
 806   // in the new bits.
 807   if (SrcWidth != DestWidth) {
 808     assert(DestWidth > SrcWidth);
 809     Old = Builder.CreateAnd(Old, ConstantInt::get(Context, ~Mask), "mask");
 810     SV = Builder.CreateOr(Old, SV, "ins");
 811   }
 812   return SV;
 813 }
 814
 815
 816 //===----------------------------------------------------------------------===//
 817 // SRoA Driver
 818 //===----------------------------------------------------------------------===//
 819
 820
 821 bool SROA::runOnFunction(Function &F) {
 822   TD = getAnalysisIfAvailable<TargetData>();
 823
 824   bool Changed = performPromotion(F);
 825
 826   // FIXME: ScalarRepl currently depends on TargetData more than it
 827   // theoretically needs to. It should be refactored in order to support
 828   // target-independent IR. Until this is done, just skip the actual
 829   // scalar-replacement portion of this pass.
 830   if (!TD) return Changed;
 831
 832   while (1) {
 833     bool LocalChange = performScalarRepl(F);
 834     if (!LocalChange) break;   // No need to repromote if no scalarrepl
 835     Changed = true;
 836     LocalChange = performPromotion(F);
 837     if (!LocalChange) break;   // No need to re-scalarrepl if no promotion
 838   }
 839
 840   return Changed;
 841 }
 842
 843 /// PromoteAlloca - Promote an alloca to registers, using SSAUpdater.
 844 static void PromoteAlloca(AllocaInst *AI, SSAUpdater &SSA) {
 845   SSA.Initialize(AI->getType()->getElementType(), AI->getName());
 846
 847   // First step: bucket up uses of the alloca by the block they occur in.
 848   // This is important because we have to handle multiple defs/uses in a block
 849   // ourselves: SSAUpdater is purely for cross-block references.
 850   // FIXME: Want a TinyVector<Instruction*> since there is often 0/1 element.
 851   DenseMap<BasicBlock*, std::vector<Instruction*> > UsesByBlock;
 852
 853   for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
 854        UI != E; ++UI) {
 855     Instruction *User = cast<Instruction>(*UI);
 856     UsesByBlock[User->getParent()].push_back(User);
 857   }
 858
 859   // Okay, now we can iterate over all the blocks in the function with uses,
 860   // processing them.  Keep track of which loads are loading a live-in value.
 861   // Walk the uses in the use-list order to be determinstic.
 862   SmallVector<LoadInst*, 32> LiveInLoads;
 863   DenseMap<Value*, Value*> ReplacedLoads;
 864
 865   for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
 866        UI != E; ++UI) {
 867     Instruction *User = cast<Instruction>(*UI);
 868     BasicBlock *BB = User->getParent();
 869     std::vector<Instruction*> &BlockUses = UsesByBlock[BB];
 870
 871     // If this block has already been processed, ignore this repeat use.
 872     if (BlockUses.empty()) continue;
 873
 874     // Okay, this is the first use in the block.  If this block just has a
 875     // single user in it, we can rewrite it trivially.
 876     if (BlockUses.size() == 1) {
 877       // If it is a store, it is a trivial def of the value in the block.
 878       if (StoreInst *SI = dyn_cast<StoreInst>(User))
 879         SSA.AddAvailableValue(BB, SI->getOperand(0));
 880       else
 881         // Otherwise it is a load, queue it to rewrite as a live-in load.
 882         LiveInLoads.push_back(cast<LoadInst>(User));
 883       BlockUses.clear();
 884       continue;
 885     }
 886
 887     // Otherwise, check to see if this block is all loads.
 888     bool HasStore = false;
 889     for (unsigned i = 0, e = BlockUses.size(); i != e; ++i) {
 890       if (isa<StoreInst>(BlockUses[i])) {
 891         HasStore = true;
 892         break;
 893       }
 894     }
 895
 896     // If so, we can queue them all as live in loads.  We don't have an
 897     // efficient way to tell which on is first in the block and don't want to
 898     // scan large blocks, so just add all loads as live ins.
 899     if (!HasStore) {
 900       for (unsigned i = 0, e = BlockUses.size(); i != e; ++i)
 901         LiveInLoads.push_back(cast<LoadInst>(BlockUses[i]));
 902       BlockUses.clear();
 903       continue;
 904     }
 905
 906     // Otherwise, we have mixed loads and stores (or just a bunch of stores).
 907     // Since SSAUpdater is purely for cross-block values, we need to determine
 908     // the order of these instructions in the block.  If the first use in the
 909     // block is a load, then it uses the live in value.  The last store defines
 910     // the live out value.  We handle this by doing a linear scan of the block.
 911     Value *StoredValue = 0;
 912     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) {
 913       if (LoadInst *L = dyn_cast<LoadInst>(II)) {
 914         // If this is a load from an unrelated pointer, ignore it.
 915         if (L->getOperand(0) != AI) continue;
 916
 917         // If we haven't seen a store yet, this is a live in use, otherwise
 918         // use the stored value.
 919         if (StoredValue) {
 920           L->replaceAllUsesWith(StoredValue);
 921           ReplacedLoads[L] = StoredValue;
 922         } else {
 923           LiveInLoads.push_back(L);
 924         }
 925         continue;
 926       }
 927
 928       if (StoreInst *S = dyn_cast<StoreInst>(II)) {
 929         // If this is a store to an unrelated pointer, ignore it.
 930         if (S->getPointerOperand() != AI) continue;
 931
 932         // Remember that this is the active value in the block.
 933         StoredValue = S->getOperand(0);
 934       }
 935     }
 936
 937     // The last stored value that happened is the live-out for the block.
 938     assert(StoredValue && "Already checked that there is a store in block");
 939     SSA.AddAvailableValue(BB, StoredValue);
 940     BlockUses.clear();
 941   }
 942
 943   // Okay, now we rewrite all loads that use live-in values in the loop,
 944   // inserting PHI nodes as necessary.
 945   for (unsigned i = 0, e = LiveInLoads.size(); i != e; ++i) {
 946     LoadInst *ALoad = LiveInLoads[i];
 947     Value *NewVal = SSA.GetValueInMiddleOfBlock(ALoad->getParent());
 948     ALoad->replaceAllUsesWith(NewVal);
 949     ReplacedLoads[ALoad] = NewVal;
 950   }
 951
 952   // Now that everything is rewritten, delete the old instructions from the
 953   // function.  They should all be dead now.
 954   for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E; ) {
 955     Instruction *User = cast<Instruction>(*UI++);
 956
 957     // If this is a load that still has uses, then the load must have been added
 958     // as a live value in the SSAUpdate data structure for a block (e.g. because
 959     // the loaded value was stored later).  In this case, we need to recursively
 960     // propagate the updates until we get to the real value.
 961     if (!User->use_empty()) {
 962       Value *NewVal = ReplacedLoads[User];
 963       assert(NewVal && "not a replaced load?");
 964
 965       // Propagate down to the ultimate replacee.  The intermediately loads
 966       // could theoretically already have been deleted, so we don't want to
 967       // dereference the Value*'s.
 968       DenseMap<Value*, Value*>::iterator RLI = ReplacedLoads.find(NewVal);
 969       while (RLI != ReplacedLoads.end()) {
 970         NewVal = RLI->second;
 971         RLI = ReplacedLoads.find(NewVal);
 972       }
 973
 974       User->replaceAllUsesWith(NewVal);
 975     }
 976
 977     User->eraseFromParent();
 978   }
 979 }
 980
 981
 982 bool SROA::performPromotion(Function &F) {
 983   std::vector<AllocaInst*> Allocas;
 984   DominatorTree *DT = 0;
 985   DominanceFrontier *DF = 0;
 986   if (HasDomFrontiers) {
 987     DT = &getAnalysis<DominatorTree>();
 988     DF = &getAnalysis<DominanceFrontier>();
 989   }
 990
 991   BasicBlock &BB = F.getEntryBlock();  // Get the entry node for the function
 992
 993   bool Changed = false;
 994
 995   while (1) {
 996     Allocas.clear();
 997
 998     // Find allocas that are safe to promote, by looking at all instructions in
 999     // the entry node
1000     for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
1001       if (AllocaInst *AI = dyn_cast<AllocaInst>(I))       // Is it an alloca?
1002         if (isAllocaPromotable(AI))
1003           Allocas.push_back(AI);
1004
1005     if (Allocas.empty()) break;
1006
1007     if (HasDomFrontiers)
1008       PromoteMemToReg(Allocas, *DT, *DF);
1009     else {
1010       SSAUpdater SSA;
1011       for (unsigned i = 0, e = Allocas.size(); i != e; ++i) {
1012         PromoteAlloca(Allocas[i], SSA);
1013         Allocas[i]->eraseFromParent();
1014       }
1015     }
1016     NumPromoted += Allocas.size();
1017     Changed = true;
1018   }
1019
1020   return Changed;
1021 }
1022
1023
1024 /// ShouldAttemptScalarRepl - Decide if an alloca is a good candidate for
1025 /// SROA.  It must be a struct or array type with a small number of elements.
1026 static bool ShouldAttemptScalarRepl(AllocaInst *AI) {
1027   const Type *T = AI->getAllocatedType();
1028   // Do not promote any struct into more than 32 separate vars.
1029   if (const StructType *ST = dyn_cast<StructType>(T))
1030     return ST->getNumElements() <= 32;
1031   // Arrays are much less likely to be safe for SROA; only consider
1032   // them if they are very small.
1033   if (const ArrayType *AT = dyn_cast<ArrayType>(T))
1034     return AT->getNumElements() <= 8;
1035   return false;
1036 }
1037
1038
1039 // performScalarRepl - This algorithm is a simple worklist driven algorithm,
1040 // which runs on all of the malloc/alloca instructions in the function, removing
1041 // them if they are only used by getelementptr instructions.
1042 //
1043 bool SROA::performScalarRepl(Function &F) {
1044   std::vector<AllocaInst*> WorkList;
1045
1046   // Scan the entry basic block, adding allocas to the worklist.
1047   BasicBlock &BB = F.getEntryBlock();
1048   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
1049     if (AllocaInst *A = dyn_cast<AllocaInst>(I))
1050       WorkList.push_back(A);
1051
1052   // Process the worklist
1053   bool Changed = false;
1054   while (!WorkList.empty()) {
1055     AllocaInst *AI = WorkList.back();
1056     WorkList.pop_back();
1057
1058     // Handle dead allocas trivially.  These can be formed by SROA'ing arrays
1059     // with unused elements.
1060     if (AI->use_empty()) {
1061       AI->eraseFromParent();
1062       Changed = true;
1063       continue;
1064     }
1065
1066     // If this alloca is impossible for us to promote, reject it early.
1067     if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized())
1068       continue;
1069
1070     // Check to see if this allocation is only modified by a memcpy/memmove from
1071     // a constant global.  If this is the case, we can change all users to use
1072     // the constant global instead.  This is commonly produced by the CFE by
1073     // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A'
1074     // is only subsequently read.
1075     if (MemTransferInst *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) {
1076       DEBUG(dbgs() << "Found alloca equal to global: " << *AI << '\n');
1077       DEBUG(dbgs() << "  memcpy = " << *TheCopy << '\n');
1078       Constant *TheSrc = cast<Constant>(TheCopy->getSource());
1079       AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType()));
1080       TheCopy->eraseFromParent();  // Don't mutate the global.
1081       AI->eraseFromParent();
1082       ++NumGlobals;
1083       Changed = true;
1084       continue;
1085     }
1086
1087     // Check to see if we can perform the core SROA transformation.  We cannot
1088     // transform the allocation instruction if it is an array allocation
1089     // (allocations OF arrays are ok though), and an allocation of a scalar
1090     // value cannot be decomposed at all.
1091     uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType());
1092
1093     // Do not promote [0 x %struct].
1094     if (AllocaSize == 0) continue;
1095
1096     // Do not promote any struct whose size is too big.
1097     if (AllocaSize > SRThreshold) continue;
1098
1099     // If the alloca looks like a good candidate for scalar replacement, and if
1100     // all its users can be transformed, then split up the aggregate into its
1101     // separate elements.
1102     if (ShouldAttemptScalarRepl(AI) && isSafeAllocaToScalarRepl(AI)) {
1103       DoScalarReplacement(AI, WorkList);
1104       Changed = true;
1105       continue;
1106     }
1107
1108     // If we can turn this aggregate value (potentially with casts) into a
1109     // simple scalar value that can be mem2reg'd into a register value.
1110     // IsNotTrivial tracks whether this is something that mem2reg could have
1111     // promoted itself.  If so, we don't want to transform it needlessly.  Note
1112     // that we can't just check based on the type: the alloca may be of an i32
1113     // but that has pointer arithmetic to set byte 3 of it or something.
1114     if (AllocaInst *NewAI =
1115           ConvertToScalarInfo((unsigned)AllocaSize, *TD).TryConvert(AI)) {
1116       NewAI->takeName(AI);
1117       AI->eraseFromParent();
1118       ++NumConverted;
1119       Changed = true;
1120       continue;
1121     }
1122
1123     // Otherwise, couldn't process this alloca.
1124   }
1125
1126   return Changed;
1127 }
1128
1129 /// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl
1130 /// predicate, do SROA now.
1131 void SROA::DoScalarReplacement(AllocaInst *AI,
1132                                std::vector<AllocaInst*> &WorkList) {
1133   DEBUG(dbgs() << "Found inst to SROA: " << *AI << '\n');
1134   SmallVector<AllocaInst*, 32> ElementAllocas;
1135   if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) {
1136     ElementAllocas.reserve(ST->getNumContainedTypes());
1137     for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) {
1138       AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0,
1139                                       AI->getAlignment(),
1140                                       AI->getName() + "." + Twine(i), AI);
1141       ElementAllocas.push_back(NA);
1142       WorkList.push_back(NA);  // Add to worklist for recursive processing
1143     }
1144   } else {
1145     const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
1146     ElementAllocas.reserve(AT->getNumElements());
1147     const Type *ElTy = AT->getElementType();
1148     for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
1149       AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(),
1150                                       AI->getName() + "." + Twine(i), AI);
1151       ElementAllocas.push_back(NA);
1152       WorkList.push_back(NA);  // Add to worklist for recursive processing
1153     }
1154   }
1155
1156   // Now that we have created the new alloca instructions, rewrite all the
1157   // uses of the old alloca.
1158   RewriteForScalarRepl(AI, AI, 0, ElementAllocas);
1159
1160   // Now erase any instructions that were made dead while rewriting the alloca.
1161   DeleteDeadInstructions();
1162   AI->eraseFromParent();
1163
1164   ++NumReplaced;
1165 }
1166
1167 /// DeleteDeadInstructions - Erase instructions on the DeadInstrs list,
1168 /// recursively including all their operands that become trivially dead.
1169 void SROA::DeleteDeadInstructions() {
1170   while (!DeadInsts.empty()) {
1171     Instruction *I = cast<Instruction>(DeadInsts.pop_back_val());
1172
1173     for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI)
1174       if (Instruction *U = dyn_cast<Instruction>(*OI)) {
1175         // Zero out the operand and see if it becomes trivially dead.
1176         // (But, don't add allocas to the dead instruction list -- they are
1177         // already on the worklist and will be deleted separately.)
1178         *OI = 0;
1179         if (isInstructionTriviallyDead(U) && !isa<AllocaInst>(U))
1180           DeadInsts.push_back(U);
1181       }
1182
1183     I->eraseFromParent();
1184   }
1185 }
1186
1187 /// isSafeForScalarRepl - Check if instruction I is a safe use with regard to
1188 /// performing scalar replacement of alloca AI.  The results are flagged in
1189 /// the Info parameter.  Offset indicates the position within AI that is
1190 /// referenced by this instruction.
1191 void SROA::isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset,
1192                                AllocaInfo &Info) {
1193   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) {
1194     Instruction *User = cast<Instruction>(*UI);
1195
1196     if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) {
1197       isSafeForScalarRepl(BC, AI, Offset, Info);
1198     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
1199       uint64_t GEPOffset = Offset;
1200       isSafeGEP(GEPI, AI, GEPOffset, Info);
1201       if (!Info.isUnsafe)
1202         isSafeForScalarRepl(GEPI, AI, GEPOffset, Info);
1203     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) {
1204       ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
1205       if (Length)
1206         isSafeMemAccess(AI, Offset, Length->getZExtValue(), 0,
1207                         UI.getOperandNo() == 0, Info);
1208       else
1209         MarkUnsafe(Info);
1210     } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
1211       if (!LI->isVolatile()) {
1212         const Type *LIType = LI->getType();
1213         isSafeMemAccess(AI, Offset, TD->getTypeAllocSize(LIType),
1214                         LIType, false, Info);
1215       } else
1216         MarkUnsafe(Info);
1217     } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
1218       // Store is ok if storing INTO the pointer, not storing the pointer
1219       if (!SI->isVolatile() && SI->getOperand(0) != I) {
1220         const Type *SIType = SI->getOperand(0)->getType();
1221         isSafeMemAccess(AI, Offset, TD->getTypeAllocSize(SIType),
1222                         SIType, true, Info);
1223       } else
1224         MarkUnsafe(Info);
1225     } else {
1226       DEBUG(errs() << "  Transformation preventing inst: " << *User << '\n');
1227       MarkUnsafe(Info);
1228     }
1229     if (Info.isUnsafe) return;
1230   }
1231 }
1232
1233 /// isSafeGEP - Check if a GEP instruction can be handled for scalar
1234 /// replacement.  It is safe when all the indices are constant, in-bounds
1235 /// references, and when the resulting offset corresponds to an element within
1236 /// the alloca type.  The results are flagged in the Info parameter.  Upon
1237 /// return, Offset is adjusted as specified by the GEP indices.
1238 void SROA::isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI,
1239                      uint64_t &Offset, AllocaInfo &Info) {
1240   gep_type_iterator GEPIt = gep_type_begin(GEPI), E = gep_type_end(GEPI);
1241   if (GEPIt == E)
1242     return;
1243
1244   // Walk through the GEP type indices, checking the types that this indexes
1245   // into.
1246   for (; GEPIt != E; ++GEPIt) {
1247     // Ignore struct elements, no extra checking needed for these.
1248     if ((*GEPIt)->isStructTy())
1249       continue;
1250
1251     ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPIt.getOperand());
1252     if (!IdxVal)
1253       return MarkUnsafe(Info);
1254   }
1255
1256   // Compute the offset due to this GEP and check if the alloca has a
1257   // component element at that offset.
1258   SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end());
1259   Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(),
1260                                  &Indices[0], Indices.size());
1261   if (!TypeHasComponent(AI->getAllocatedType(), Offset, 0))
1262     MarkUnsafe(Info);
1263 }
1264
1265 /// isHomogeneousAggregate - Check if type T is a struct or array containing
1266 /// elements of the same type (which is always true for arrays).  If so,
1267 /// return true with NumElts and EltTy set to the number of elements and the
1268 /// element type, respectively.
1269 static bool isHomogeneousAggregate(const Type *T, unsigned &NumElts,
1270                                    const Type *&EltTy) {
1271   if (const ArrayType *AT = dyn_cast<ArrayType>(T)) {
1272     NumElts = AT->getNumElements();
1273     EltTy = (NumElts == 0 ? 0 : AT->getElementType());
1274     return true;
1275   }
1276   if (const StructType *ST = dyn_cast<StructType>(T)) {
1277     NumElts = ST->getNumContainedTypes();
1278     EltTy = (NumElts == 0 ? 0 : ST->getContainedType(0));
1279     for (unsigned n = 1; n < NumElts; ++n) {
1280       if (ST->getContainedType(n) != EltTy)
1281         return false;
1282     }
1283     return true;
1284   }
1285   return false;
1286 }
1287
1288 /// isCompatibleAggregate - Check if T1 and T2 are either the same type or are
1289 /// "homogeneous" aggregates with the same element type and number of elements.
1290 static bool isCompatibleAggregate(const Type *T1, const Type *T2) {
1291   if (T1 == T2)
1292     return true;
1293
1294   unsigned NumElts1, NumElts2;
1295   const Type *EltTy1, *EltTy2;
1296   if (isHomogeneousAggregate(T1, NumElts1, EltTy1) &&
1297       isHomogeneousAggregate(T2, NumElts2, EltTy2) &&
1298       NumElts1 == NumElts2 &&
1299       EltTy1 == EltTy2)
1300     return true;
1301
1302   return false;
1303 }
1304
1305 /// isSafeMemAccess - Check if a load/store/memcpy operates on the entire AI
1306 /// alloca or has an offset and size that corresponds to a component element
1307 /// within it.  The offset checked here may have been formed from a GEP with a
1308 /// pointer bitcasted to a different type.
1309 void SROA::isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t MemSize,
1310                            const Type *MemOpType, bool isStore,
1311                            AllocaInfo &Info) {
1312   // Check if this is a load/store of the entire alloca.
1313   if (Offset == 0 && MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) {
1314     // This can be safe for MemIntrinsics (where MemOpType is 0) and integer
1315     // loads/stores (which are essentially the same as the MemIntrinsics with
1316     // regard to copying padding between elements).  But, if an alloca is
1317     // flagged as both a source and destination of such operations, we'll need
1318     // to check later for padding between elements.
1319     if (!MemOpType || MemOpType->isIntegerTy()) {
1320       if (isStore)
1321         Info.isMemCpyDst = true;
1322       else
1323         Info.isMemCpySrc = true;
1324       return;
1325     }
1326     // This is also safe for references using a type that is compatible with
1327     // the type of the alloca, so that loads/stores can be rewritten using
1328     // insertvalue/extractvalue.
1329     if (isCompatibleAggregate(MemOpType, AI->getAllocatedType()))
1330       return;
1331   }
1332   // Check if the offset/size correspond to a component within the alloca type.
1333   const Type *T = AI->getAllocatedType();
1334   if (TypeHasComponent(T, Offset, MemSize))
1335     return;
1336
1337   return MarkUnsafe(Info);
1338 }
1339
1340 /// TypeHasComponent - Return true if T has a component type with the
1341 /// specified offset and size.  If Size is zero, do not check the size.
1342 bool SROA::TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size) {
1343   const Type *EltTy;
1344   uint64_t EltSize;
1345   if (const StructType *ST = dyn_cast<StructType>(T)) {
1346     const StructLayout *Layout = TD->getStructLayout(ST);
1347     unsigned EltIdx = Layout->getElementContainingOffset(Offset);
1348     EltTy = ST->getContainedType(EltIdx);
1349     EltSize = TD->getTypeAllocSize(EltTy);
1350     Offset -= Layout->getElementOffset(EltIdx);
1351   } else if (const ArrayType *AT = dyn_cast<ArrayType>(T)) {
1352     EltTy = AT->getElementType();
1353     EltSize = TD->getTypeAllocSize(EltTy);
1354     if (Offset >= AT->getNumElements() * EltSize)
1355       return false;
1356     Offset %= EltSize;
1357   } else {
1358     return false;
1359   }
1360   if (Offset == 0 && (Size == 0 || EltSize == Size))
1361     return true;
1362   // Check if the component spans multiple elements.
1363   if (Offset + Size > EltSize)
1364     return false;
1365   return TypeHasComponent(EltTy, Offset, Size);
1366 }
1367
1368 /// RewriteForScalarRepl - Alloca AI is being split into NewElts, so rewrite
1369 /// the instruction I, which references it, to use the separate elements.
1370 /// Offset indicates the position within AI that is referenced by this
1371 /// instruction.
1372 void SROA::RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset,
1373                                 SmallVector<AllocaInst*, 32> &NewElts) {
1374   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) {
1375     Instruction *User = cast<Instruction>(*UI);
1376
1377     if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) {
1378       RewriteBitCast(BC, AI, Offset, NewElts);
1379     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
1380       RewriteGEP(GEPI, AI, Offset, NewElts);
1381     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) {
1382       ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
1383       uint64_t MemSize = Length->getZExtValue();
1384       if (Offset == 0 &&
1385           MemSize == TD->getTypeAllocSize(AI->getAllocatedType()))
1386         RewriteMemIntrinUserOfAlloca(MI, I, AI, NewElts);
1387       // Otherwise the intrinsic can only touch a single element and the
1388       // address operand will be updated, so nothing else needs to be done.
1389     } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
1390       const Type *LIType = LI->getType();
1391       if (isCompatibleAggregate(LIType, AI->getAllocatedType())) {
1392         // Replace:
1393         //   %res = load { i32, i32 }* %alloc
1394         // with:
1395         //   %load.0 = load i32* %alloc.0
1396         //   %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0
1397         //   %load.1 = load i32* %alloc.1
1398         //   %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1
1399         // (Also works for arrays instead of structs)
1400         Value *Insert = UndefValue::get(LIType);
1401         for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
1402           Value *Load = new LoadInst(NewElts[i], "load", LI);
1403           Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI);
1404         }
1405         LI->replaceAllUsesWith(Insert);
1406         DeadInsts.push_back(LI);
1407       } else if (LIType->isIntegerTy() &&
1408                  TD->getTypeAllocSize(LIType) ==
1409                  TD->getTypeAllocSize(AI->getAllocatedType())) {
1410         // If this is a load of the entire alloca to an integer, rewrite it.
1411         RewriteLoadUserOfWholeAlloca(LI, AI, NewElts);
1412       }
1413     } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
1414       Value *Val = SI->getOperand(0);
1415       const Type *SIType = Val->getType();
1416       if (isCompatibleAggregate(SIType, AI->getAllocatedType())) {
1417         // Replace:
1418         //   store { i32, i32 } %val, { i32, i32 }* %alloc
1419         // with:
1420         //   %val.0 = extractvalue { i32, i32 } %val, 0
1421         //   store i32 %val.0, i32* %alloc.0
1422         //   %val.1 = extractvalue { i32, i32 } %val, 1
1423         //   store i32 %val.1, i32* %alloc.1
1424         // (Also works for arrays instead of structs)
1425         for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
1426           Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI);
1427           new StoreInst(Extract, NewElts[i], SI);
1428         }
1429         DeadInsts.push_back(SI);
1430       } else if (SIType->isIntegerTy() &&
1431                  TD->getTypeAllocSize(SIType) ==
1432                  TD->getTypeAllocSize(AI->getAllocatedType())) {
1433         // If this is a store of the entire alloca from an integer, rewrite it.
1434         RewriteStoreUserOfWholeAlloca(SI, AI, NewElts);
1435       }
1436     }
1437   }
1438 }
1439
1440 /// RewriteBitCast - Update a bitcast reference to the alloca being replaced
1441 /// and recursively continue updating all of its uses.
1442 void SROA::RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset,
1443                           SmallVector<AllocaInst*, 32> &NewElts) {
1444   RewriteForScalarRepl(BC, AI, Offset, NewElts);
1445   if (BC->getOperand(0) != AI)
1446     return;
1447
1448   // The bitcast references the original alloca.  Replace its uses with
1449   // references to the first new element alloca.
1450   Instruction *Val = NewElts[0];
1451   if (Val->getType() != BC->getDestTy()) {
1452     Val = new BitCastInst(Val, BC->getDestTy(), "", BC);
1453     Val->takeName(BC);
1454   }
1455   BC->replaceAllUsesWith(Val);
1456   DeadInsts.push_back(BC);
1457 }
1458
1459 /// FindElementAndOffset - Return the index of the element containing Offset
1460 /// within the specified type, which must be either a struct or an array.
1461 /// Sets T to the type of the element and Offset to the offset within that
1462 /// element.  IdxTy is set to the type of the index result to be used in a
1463 /// GEP instruction.
1464 uint64_t SROA::FindElementAndOffset(const Type *&T, uint64_t &Offset,
1465                                     const Type *&IdxTy) {
1466   uint64_t Idx = 0;
1467   if (const StructType *ST = dyn_cast<StructType>(T)) {
1468     const StructLayout *Layout = TD->getStructLayout(ST);
1469     Idx = Layout->getElementContainingOffset(Offset);
1470     T = ST->getContainedType(Idx);
1471     Offset -= Layout->getElementOffset(Idx);
1472     IdxTy = Type::getInt32Ty(T->getContext());
1473     return Idx;
1474   }
1475   const ArrayType *AT = cast<ArrayType>(T);
1476   T = AT->getElementType();
1477   uint64_t EltSize = TD->getTypeAllocSize(T);
1478   Idx = Offset / EltSize;
1479   Offset -= Idx * EltSize;
1480   IdxTy = Type::getInt64Ty(T->getContext());
1481   return Idx;
1482 }
1483
1484 /// RewriteGEP - Check if this GEP instruction moves the pointer across
1485 /// elements of the alloca that are being split apart, and if so, rewrite
1486 /// the GEP to be relative to the new element.
1487 void SROA::RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset,
1488                       SmallVector<AllocaInst*, 32> &NewElts) {
1489   uint64_t OldOffset = Offset;
1490   SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end());
1491   Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(),
1492                                  &Indices[0], Indices.size());
1493
1494   RewriteForScalarRepl(GEPI, AI, Offset, NewElts);
1495
1496   const Type *T = AI->getAllocatedType();
1497   const Type *IdxTy;
1498   uint64_t OldIdx = FindElementAndOffset(T, OldOffset, IdxTy);
1499   if (GEPI->getOperand(0) == AI)
1500     OldIdx = ~0ULL; // Force the GEP to be rewritten.
1501
1502   T = AI->getAllocatedType();
1503   uint64_t EltOffset = Offset;
1504   uint64_t Idx = FindElementAndOffset(T, EltOffset, IdxTy);
1505
1506   // If this GEP does not move the pointer across elements of the alloca
1507   // being split, then it does not needs to be rewritten.
1508   if (Idx == OldIdx)
1509     return;
1510
1511   const Type *i32Ty = Type::getInt32Ty(AI->getContext());
1512   SmallVector<Value*, 8> NewArgs;
1513   NewArgs.push_back(Constant::getNullValue(i32Ty));
1514   while (EltOffset != 0) {
1515     uint64_t EltIdx = FindElementAndOffset(T, EltOffset, IdxTy);
1516     NewArgs.push_back(ConstantInt::get(IdxTy, EltIdx));
1517   }
1518   Instruction *Val = NewElts[Idx];
1519   if (NewArgs.size() > 1) {
1520     Val = GetElementPtrInst::CreateInBounds(Val, NewArgs.begin(),
1521                                             NewArgs.end(), "", GEPI);
1522     Val->takeName(GEPI);
1523   }
1524   if (Val->getType() != GEPI->getType())
1525     Val = new BitCastInst(Val, GEPI->getType(), Val->getName(), GEPI);
1526   GEPI->replaceAllUsesWith(Val);
1527   DeadInsts.push_back(GEPI);
1528 }
1529
1530 /// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI.
1531 /// Rewrite it to copy or set the elements of the scalarized memory.
1532 void SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst,
1533                                         AllocaInst *AI,
1534                                         SmallVector<AllocaInst*, 32> &NewElts) {
1535   // If this is a memcpy/memmove, construct the other pointer as the
1536   // appropriate type.  The "Other" pointer is the pointer that goes to memory
1537   // that doesn't have anything to do with the alloca that we are promoting. For
1538   // memset, this Value* stays null.
1539   Value *OtherPtr = 0;
1540   unsigned MemAlignment = MI->getAlignment();
1541   if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { // memmove/memcopy
1542     if (Inst == MTI->getRawDest())
1543       OtherPtr = MTI->getRawSource();
1544     else {
1545       assert(Inst == MTI->getRawSource());
1546       OtherPtr = MTI->getRawDest();
1547     }
1548   }
1549
1550   // If there is an other pointer, we want to convert it to the same pointer
1551   // type as AI has, so we can GEP through it safely.
1552   if (OtherPtr) {
1553     unsigned AddrSpace =
1554       cast<PointerType>(OtherPtr->getType())->getAddressSpace();
1555
1556     // Remove bitcasts and all-zero GEPs from OtherPtr.  This is an
1557     // optimization, but it's also required to detect the corner case where
1558     // both pointer operands are referencing the same memory, and where
1559     // OtherPtr may be a bitcast or GEP that currently being rewritten.  (This
1560     // function is only called for mem intrinsics that access the whole
1561     // aggregate, so non-zero GEPs are not an issue here.)
1562     OtherPtr = OtherPtr->stripPointerCasts();
1563
1564     // Copying the alloca to itself is a no-op: just delete it.
1565     if (OtherPtr == AI || OtherPtr == NewElts[0]) {
1566       // This code will run twice for a no-op memcpy -- once for each operand.
1567       // Put only one reference to MI on the DeadInsts list.
1568       for (SmallVector<Value*, 32>::const_iterator I = DeadInsts.begin(),
1569              E = DeadInsts.end(); I != E; ++I)
1570         if (*I == MI) return;
1571       DeadInsts.push_back(MI);
1572       return;
1573     }
1574
1575     // If the pointer is not the right type, insert a bitcast to the right
1576     // type.
1577     const Type *NewTy =
1578       PointerType::get(AI->getType()->getElementType(), AddrSpace);
1579
1580     if (OtherPtr->getType() != NewTy)
1581       OtherPtr = new BitCastInst(OtherPtr, NewTy, OtherPtr->getName(), MI);
1582   }
1583
1584   // Process each element of the aggregate.
1585   bool SROADest = MI->getRawDest() == Inst;
1586
1587   Constant *Zero = Constant::getNullValue(Type::getInt32Ty(MI->getContext()));
1588
1589   for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
1590     // If this is a memcpy/memmove, emit a GEP of the other element address.
1591     Value *OtherElt = 0;
1592     unsigned OtherEltAlign = MemAlignment;
1593
1594     if (OtherPtr) {
1595       Value *Idx[2] = { Zero,
1596                       ConstantInt::get(Type::getInt32Ty(MI->getContext()), i) };
1597       OtherElt = GetElementPtrInst::CreateInBounds(OtherPtr, Idx, Idx + 2,
1598                                               OtherPtr->getName()+"."+Twine(i),
1599                                                    MI);
1600       uint64_t EltOffset;
1601       const PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType());
1602       const Type *OtherTy = OtherPtrTy->getElementType();
1603       if (const StructType *ST = dyn_cast<StructType>(OtherTy)) {
1604         EltOffset = TD->getStructLayout(ST)->getElementOffset(i);
1605       } else {
1606         const Type *EltTy = cast<SequentialType>(OtherTy)->getElementType();
1607         EltOffset = TD->getTypeAllocSize(EltTy)*i;
1608       }
1609
1610       // The alignment of the other pointer is the guaranteed alignment of the
1611       // element, which is affected by both the known alignment of the whole
1612       // mem intrinsic and the alignment of the element.  If the alignment of
1613       // the memcpy (f.e.) is 32 but the element is at a 4-byte offset, then the
1614       // known alignment is just 4 bytes.
1615       OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset);
1616     }
1617
1618     Value *EltPtr = NewElts[i];
1619     const Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType();
1620
1621     // If we got down to a scalar, insert a load or store as appropriate.
1622     if (EltTy->isSingleValueType()) {
1623       if (isa<MemTransferInst>(MI)) {
1624         if (SROADest) {
1625           // From Other to Alloca.
1626           Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI);
1627           new StoreInst(Elt, EltPtr, MI);
1628         } else {
1629           // From Alloca to Other.
1630           Value *Elt = new LoadInst(EltPtr, "tmp", MI);
1631           new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI);
1632         }
1633         continue;
1634       }
1635       assert(isa<MemSetInst>(MI));
1636
1637       // If the stored element is zero (common case), just store a null
1638       // constant.
1639       Constant *StoreVal;
1640       if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getArgOperand(1))) {
1641         if (CI->isZero()) {
1642           StoreVal = Constant::getNullValue(EltTy);  // 0.0, null, 0, <0,0>
1643         } else {
1644           // If EltTy is a vector type, get the element type.
1645           const Type *ValTy = EltTy->getScalarType();
1646
1647           // Construct an integer with the right value.
1648           unsigned EltSize = TD->getTypeSizeInBits(ValTy);
1649           APInt OneVal(EltSize, CI->getZExtValue());
1650           APInt TotalVal(OneVal);
1651           // Set each byte.
1652           for (unsigned i = 0; 8*i < EltSize; ++i) {
1653             TotalVal = TotalVal.shl(8);
1654             TotalVal |= OneVal;
1655           }
1656
1657           // Convert the integer value to the appropriate type.
1658           StoreVal = ConstantInt::get(CI->getContext(), TotalVal);
1659           if (ValTy->isPointerTy())
1660             StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy);
1661           else if (ValTy->isFloatingPointTy())
1662             StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy);
1663           assert(StoreVal->getType() == ValTy && "Type mismatch!");
1664
1665           // If the requested value was a vector constant, create it.
1666           if (EltTy != ValTy) {
1667             unsigned NumElts = cast<VectorType>(ValTy)->getNumElements();
1668             SmallVector<Constant*, 16> Elts(NumElts, StoreVal);
1669             StoreVal = ConstantVector::get(&Elts[0], NumElts);
1670           }
1671         }
1672         new StoreInst(StoreVal, EltPtr, MI);
1673         continue;
1674       }
1675       // Otherwise, if we're storing a byte variable, use a memset call for
1676       // this element.
1677     }
1678
1679     unsigned EltSize = TD->getTypeAllocSize(EltTy);
1680
1681     IRBuilder<> Builder(MI);
1682
1683     // Finally, insert the meminst for this element.
1684     if (isa<MemSetInst>(MI)) {
1685       Builder.CreateMemSet(EltPtr, MI->getArgOperand(1), EltSize,
1686                            MI->isVolatile());
1687     } else {
1688       assert(isa<MemTransferInst>(MI));
1689       Value *Dst = SROADest ? EltPtr : OtherElt;  // Dest ptr
1690       Value *Src = SROADest ? OtherElt : EltPtr;  // Src ptr
1691
1692       if (isa<MemCpyInst>(MI))
1693         Builder.CreateMemCpy(Dst, Src, EltSize, OtherEltAlign,MI->isVolatile());
1694       else
1695         Builder.CreateMemMove(Dst, Src, EltSize,OtherEltAlign,MI->isVolatile());
1696     }
1697   }
1698   DeadInsts.push_back(MI);
1699 }
1700
1701 /// RewriteStoreUserOfWholeAlloca - We found a store of an integer that
1702 /// overwrites the entire allocation.  Extract out the pieces of the stored
1703 /// integer and store them individually.
1704 void SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI,
1705                                          SmallVector<AllocaInst*, 32> &NewElts){
1706   // Extract each element out of the integer according to its structure offset
1707   // and store the element value to the individual alloca.
1708   Value *SrcVal = SI->getOperand(0);
1709   const Type *AllocaEltTy = AI->getAllocatedType();
1710   uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy);
1711
1712   // Handle tail padding by extending the operand
1713   if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits)
1714     SrcVal = new ZExtInst(SrcVal,
1715                           IntegerType::get(SI->getContext(), AllocaSizeBits),
1716                           "", SI);
1717
1718   DEBUG(dbgs() << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << '\n' << *SI
1719                << '\n');
1720
1721   // There are two forms here: AI could be an array or struct.  Both cases
1722   // have different ways to compute the element offset.
1723   if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) {
1724     const StructLayout *Layout = TD->getStructLayout(EltSTy);
1725
1726     for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
1727       // Get the number of bits to shift SrcVal to get the value.
1728       const Type *FieldTy = EltSTy->getElementType(i);
1729       uint64_t Shift = Layout->getElementOffsetInBits(i);
1730
1731       if (TD->isBigEndian())
1732         Shift = AllocaSizeBits-Shift-TD->getTypeAllocSizeInBits(FieldTy);
1733
1734       Value *EltVal = SrcVal;
1735       if (Shift) {
1736         Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift);
1737         EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal,
1738                                             "sroa.store.elt", SI);
1739       }
1740
1741       // Truncate down to an integer of the right size.
1742       uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy);
1743
1744       // Ignore zero sized fields like {}, they obviously contain no data.
1745       if (FieldSizeBits == 0) continue;
1746
1747       if (FieldSizeBits != AllocaSizeBits)
1748         EltVal = new TruncInst(EltVal,
1749                              IntegerType::get(SI->getContext(), FieldSizeBits),
1750                               "", SI);
1751       Value *DestField = NewElts[i];
1752       if (EltVal->getType() == FieldTy) {
1753         // Storing to an integer field of this size, just do it.
1754       } else if (FieldTy->isFloatingPointTy() || FieldTy->isVectorTy()) {
1755         // Bitcast to the right element type (for fp/vector values).
1756         EltVal = new BitCastInst(EltVal, FieldTy, "", SI);
1757       } else {
1758         // Otherwise, bitcast the dest pointer (for aggregates).
1759         DestField = new BitCastInst(DestField,
1760                               PointerType::getUnqual(EltVal->getType()),
1761                                     "", SI);
1762       }
1763       new StoreInst(EltVal, DestField, SI);
1764     }
1765
1766   } else {
1767     const ArrayType *ATy = cast<ArrayType>(AllocaEltTy);
1768     const Type *ArrayEltTy = ATy->getElementType();
1769     uint64_t ElementOffset = TD->getTypeAllocSizeInBits(ArrayEltTy);
1770     uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy);
1771
1772     uint64_t Shift;
1773
1774     if (TD->isBigEndian())
1775       Shift = AllocaSizeBits-ElementOffset;
1776     else
1777       Shift = 0;
1778
1779     for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
1780       // Ignore zero sized fields like {}, they obviously contain no data.
1781       if (ElementSizeBits == 0) continue;
1782
1783       Value *EltVal = SrcVal;
1784       if (Shift) {
1785         Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift);
1786         EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal,
1787                                             "sroa.store.elt", SI);
1788       }
1789
1790       // Truncate down to an integer of the right size.
1791       if (ElementSizeBits != AllocaSizeBits)
1792         EltVal = new TruncInst(EltVal,
1793                                IntegerType::get(SI->getContext(),
1794                                                 ElementSizeBits), "", SI);
1795       Value *DestField = NewElts[i];
1796       if (EltVal->getType() == ArrayEltTy) {
1797         // Storing to an integer field of this size, just do it.
1798       } else if (ArrayEltTy->isFloatingPointTy() ||
1799                  ArrayEltTy->isVectorTy()) {
1800         // Bitcast to the right element type (for fp/vector values).
1801         EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI);
1802       } else {
1803         // Otherwise, bitcast the dest pointer (for aggregates).
1804         DestField = new BitCastInst(DestField,
1805                               PointerType::getUnqual(EltVal->getType()),
1806                                     "", SI);
1807       }
1808       new StoreInst(EltVal, DestField, SI);
1809
1810       if (TD->isBigEndian())
1811         Shift -= ElementOffset;
1812       else
1813         Shift += ElementOffset;
1814     }
1815   }
1816
1817   DeadInsts.push_back(SI);
1818 }
1819
1820 /// RewriteLoadUserOfWholeAlloca - We found a load of the entire allocation to
1821 /// an integer.  Load the individual pieces to form the aggregate value.
1822 void SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI,
1823                                         SmallVector<AllocaInst*, 32> &NewElts) {
1824   // Extract each element out of the NewElts according to its structure offset
1825   // and form the result value.
1826   const Type *AllocaEltTy = AI->getAllocatedType();
1827   uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy);
1828
1829   DEBUG(dbgs() << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << '\n' << *LI
1830                << '\n');
1831
1832   // There are two forms here: AI could be an array or struct.  Both cases
1833   // have different ways to compute the element offset.
1834   const StructLayout *Layout = 0;
1835   uint64_t ArrayEltBitOffset = 0;
1836   if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) {
1837     Layout = TD->getStructLayout(EltSTy);
1838   } else {
1839     const Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType();
1840     ArrayEltBitOffset = TD->getTypeAllocSizeInBits(ArrayEltTy);
1841   }
1842
1843   Value *ResultVal =
1844     Constant::getNullValue(IntegerType::get(LI->getContext(), AllocaSizeBits));
1845
1846   for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
1847     // Load the value from the alloca.  If the NewElt is an aggregate, cast
1848     // the pointer to an integer of the same size before doing the load.
1849     Value *SrcField = NewElts[i];
1850     const Type *FieldTy =
1851       cast<PointerType>(SrcField->getType())->getElementType();
1852     uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy);
1853
1854     // Ignore zero sized fields like {}, they obviously contain no data.
1855     if (FieldSizeBits == 0) continue;
1856
1857     const IntegerType *FieldIntTy = IntegerType::get(LI->getContext(),
1858                                                      FieldSizeBits);
1859     if (!FieldTy->isIntegerTy() && !FieldTy->isFloatingPointTy() &&
1860         !FieldTy->isVectorTy())
1861       SrcField = new BitCastInst(SrcField,
1862                                  PointerType::getUnqual(FieldIntTy),
1863                                  "", LI);
1864     SrcField = new LoadInst(SrcField, "sroa.load.elt", LI);
1865
1866     // If SrcField is a fp or vector of the right size but that isn't an
1867     // integer type, bitcast to an integer so we can shift it.
1868     if (SrcField->getType() != FieldIntTy)
1869       SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI);
1870
1871     // Zero extend the field to be the same size as the final alloca so that
1872     // we can shift and insert it.
1873     if (SrcField->getType() != ResultVal->getType())
1874       SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI);
1875
1876     // Determine the number of bits to shift SrcField.
1877     uint64_t Shift;
1878     if (Layout) // Struct case.
1879       Shift = Layout->getElementOffsetInBits(i);
1880     else  // Array case.
1881       Shift = i*ArrayEltBitOffset;
1882
1883     if (TD->isBigEndian())
1884       Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth();
1885
1886     if (Shift) {
1887       Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift);
1888       SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI);
1889     }
1890
1891     // Don't create an 'or x, 0' on the first iteration.
1892     if (!isa<Constant>(ResultVal) ||
1893         !cast<Constant>(ResultVal)->isNullValue())
1894       ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI);
1895     else
1896       ResultVal = SrcField;
1897   }
1898
1899   // Handle tail padding by truncating the result
1900   if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits)
1901     ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI);
1902
1903   LI->replaceAllUsesWith(ResultVal);
1904   DeadInsts.push_back(LI);
1905 }
1906
1907 /// HasPadding - Return true if the specified type has any structure or
1908 /// alignment padding in between the elements that would be split apart
1909 /// by SROA; return false otherwise.
1910 static bool HasPadding(const Type *Ty, const TargetData &TD) {
1911   if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
1912     Ty = ATy->getElementType();
1913     return TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty);
1914   }
1915
1916   // SROA currently handles only Arrays and Structs.
1917   const StructType *STy = cast<StructType>(Ty);
1918   const StructLayout *SL = TD.getStructLayout(STy);
1919   unsigned PrevFieldBitOffset = 0;
1920   for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1921     unsigned FieldBitOffset = SL->getElementOffsetInBits(i);
1922
1923     // Check to see if there is any padding between this element and the
1924     // previous one.
1925     if (i) {
1926       unsigned PrevFieldEnd =
1927         PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1));
1928       if (PrevFieldEnd < FieldBitOffset)
1929         return true;
1930     }
1931     PrevFieldBitOffset = FieldBitOffset;
1932   }
1933   // Check for tail padding.
1934   if (unsigned EltCount = STy->getNumElements()) {
1935     unsigned PrevFieldEnd = PrevFieldBitOffset +
1936       TD.getTypeSizeInBits(STy->getElementType(EltCount-1));
1937     if (PrevFieldEnd < SL->getSizeInBits())
1938       return true;
1939   }
1940   return false;
1941 }
1942
1943 /// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of
1944 /// an aggregate can be broken down into elements.  Return 0 if not, 3 if safe,
1945 /// or 1 if safe after canonicalization has been performed.
1946 bool SROA::isSafeAllocaToScalarRepl(AllocaInst *AI) {
1947   // Loop over the use list of the alloca.  We can only transform it if all of
1948   // the users are safe to transform.
1949   AllocaInfo Info;
1950
1951   isSafeForScalarRepl(AI, AI, 0, Info);
1952   if (Info.isUnsafe) {
1953     DEBUG(dbgs() << "Cannot transform: " << *AI << '\n');
1954     return false;
1955   }
1956
1957   // Okay, we know all the users are promotable.  If the aggregate is a memcpy
1958   // source and destination, we have to be careful.  In particular, the memcpy
1959   // could be moving around elements that live in structure padding of the LLVM
1960   // types, but may actually be used.  In these cases, we refuse to promote the
1961   // struct.
1962   if (Info.isMemCpySrc && Info.isMemCpyDst &&
1963       HasPadding(AI->getAllocatedType(), *TD))
1964     return false;
1965
1966   return true;
1967 }
1968
1969
1970
1971 /// PointsToConstantGlobal - Return true if V (possibly indirectly) points to
1972 /// some part of a constant global variable.  This intentionally only accepts
1973 /// constant expressions because we don't can't rewrite arbitrary instructions.
1974 static bool PointsToConstantGlobal(Value *V) {
1975   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
1976     return GV->isConstant();
1977   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
1978     if (CE->getOpcode() == Instruction::BitCast ||
1979         CE->getOpcode() == Instruction::GetElementPtr)
1980       return PointsToConstantGlobal(CE->getOperand(0));
1981   return false;
1982 }
1983
1984 /// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived)
1985 /// pointer to an alloca.  Ignore any reads of the pointer, return false if we
1986 /// see any stores or other unknown uses.  If we see pointer arithmetic, keep
1987 /// track of whether it moves the pointer (with isOffset) but otherwise traverse
1988 /// the uses.  If we see a memcpy/memmove that targets an unoffseted pointer to
1989 /// the alloca, and if the source pointer is a pointer to a constant global, we
1990 /// can optimize this.
1991 static bool isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy,
1992                                            bool isOffset) {
1993   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
1994     User *U = cast<Instruction>(*UI);
1995
1996     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
1997       // Ignore non-volatile loads, they are always ok.
1998       if (LI->isVolatile()) return false;
1999       continue;
2000     }
2001
2002     if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
2003       // If uses of the bitcast are ok, we are ok.
2004       if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset))
2005         return false;
2006       continue;
2007     }
2008     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
2009       // If the GEP has all zero indices, it doesn't offset the pointer.  If it
2010       // doesn't, it does.
2011       if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy,
2012                                          isOffset || !GEP->hasAllZeroIndices()))
2013         return false;
2014       continue;
2015     }
2016
2017     if (CallSite CS = U) {
2018       // If this is a readonly/readnone call site, then we know it is just a
2019       // load and we can ignore it.
2020       if (CS.onlyReadsMemory())
2021         continue;
2022
2023       // If this is the function being called then we treat it like a load and
2024       // ignore it.
2025       if (CS.isCallee(UI))
2026         continue;
2027
2028       // If this is being passed as a byval argument, the caller is making a
2029       // copy, so it is only a read of the alloca.
2030       unsigned ArgNo = CS.getArgumentNo(UI);
2031       if (CS.paramHasAttr(ArgNo+1, Attribute::ByVal))
2032         continue;
2033     }
2034
2035     // If this is isn't our memcpy/memmove, reject it as something we can't
2036     // handle.
2037     MemTransferInst *MI = dyn_cast<MemTransferInst>(U);
2038     if (MI == 0)
2039       return false;
2040
2041     // If the transfer is using the alloca as a source of the transfer, then
2042     // ignore it since it is a load (unless the transfer is volatile).
2043     if (UI.getOperandNo() == 1) {
2044       if (MI->isVolatile()) return false;
2045       continue;
2046     }
2047
2048     // If we already have seen a copy, reject the second one.
2049     if (TheCopy) return false;
2050
2051     // If the pointer has been offset from the start of the alloca, we can't
2052     // safely handle this.
2053     if (isOffset) return false;
2054
2055     // If the memintrinsic isn't using the alloca as the dest, reject it.
2056     if (UI.getOperandNo() != 0) return false;
2057
2058     // If the source of the memcpy/move is not a constant global, reject it.
2059     if (!PointsToConstantGlobal(MI->getSource()))
2060       return false;
2061
2062     // Otherwise, the transform is safe.  Remember the copy instruction.
2063     TheCopy = MI;
2064   }
2065   return true;
2066 }
2067
2068 /// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only
2069 /// modified by a copy from a constant global.  If we can prove this, we can
2070 /// replace any uses of the alloca with uses of the global directly.
2071 MemTransferInst *SROA::isOnlyCopiedFromConstantGlobal(AllocaInst *AI) {
2072   MemTransferInst *TheCopy = 0;
2073   if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false))
2074     return TheCopy;
2075   return 0;
2076 }