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