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/Pass.h"
  31 #include "llvm/Analysis/Dominators.h"
  32 #include "llvm/Target/TargetData.h"
  33 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/GetElementPtrTypeIterator.h"
  36 #include "llvm/Support/MathExtras.h"
  37 #include "llvm/Support/Compiler.h"
  38 #include "llvm/ADT/SmallVector.h"
  39 #include "llvm/ADT/Statistic.h"
  40 #include "llvm/ADT/StringExtras.h"
  41 using namespace llvm;
  42
  43 STATISTIC(NumReplaced,  "Number of allocas broken up");
  44 STATISTIC(NumPromoted,  "Number of allocas promoted");
  45 STATISTIC(NumConverted, "Number of aggregates converted to scalar");
  46 STATISTIC(NumGlobals,   "Number of allocas copied from constant global");
  47
  48 namespace {
  49   struct VISIBILITY_HIDDEN SROA : public FunctionPass {
  50     static char ID; // Pass identification, replacement for typeid
  51     explicit SROA(signed T = -1) : FunctionPass(&ID) {
  52       if (T == -1)
  53         SRThreshold = 128;
  54       else
  55         SRThreshold = T;
  56     }
  57
  58     bool runOnFunction(Function &F);
  59
  60     bool performScalarRepl(Function &F);
  61     bool performPromotion(Function &F);
  62
  63     // getAnalysisUsage - This pass does not require any passes, but we know it
  64     // will not alter the CFG, so say so.
  65     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  66       AU.addRequired<DominatorTree>();
  67       AU.addRequired<DominanceFrontier>();
  68       AU.addRequired<TargetData>();
  69       AU.setPreservesCFG();
  70     }
  71
  72   private:
  73     TargetData *TD;
  74
  75     /// AllocaInfo - When analyzing uses of an alloca instruction, this captures
  76     /// information about the uses.  All these fields are initialized to false
  77     /// and set to true when something is learned.
  78     struct AllocaInfo {
  79       /// isUnsafe - This is set to true if the alloca cannot be SROA'd.
  80       bool isUnsafe : 1;
  81
  82       /// needsCanon - This is set to true if there is some use of the alloca
  83       /// that requires canonicalization.
  84       bool needsCanon : 1;
  85
  86       /// isMemCpySrc - This is true if this aggregate is memcpy'd from.
  87       bool isMemCpySrc : 1;
  88
  89       /// isMemCpyDst - This is true if this aggregate is memcpy'd into.
  90       bool isMemCpyDst : 1;
  91
  92       AllocaInfo()
  93         : isUnsafe(false), needsCanon(false),
  94           isMemCpySrc(false), isMemCpyDst(false) {}
  95     };
  96
  97     unsigned SRThreshold;
  98
  99     void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; }
 100
 101     int isSafeAllocaToScalarRepl(AllocationInst *AI);
 102
 103     void isSafeUseOfAllocation(Instruction *User, AllocationInst *AI,
 104                                AllocaInfo &Info);
 105     void isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI,
 106                          AllocaInfo &Info);
 107     void isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI,
 108                                         unsigned OpNo, AllocaInfo &Info);
 109     void isSafeUseOfBitCastedAllocation(BitCastInst *User, AllocationInst *AI,
 110                                         AllocaInfo &Info);
 111
 112     void DoScalarReplacement(AllocationInst *AI,
 113                              std::vector<AllocationInst*> &WorkList);
 114     void CanonicalizeAllocaUsers(AllocationInst *AI);
 115     AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base);
 116
 117     void RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI,
 118                                     SmallVector<AllocaInst*, 32> &NewElts);
 119
 120     void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *BCInst,
 121                                       AllocationInst *AI,
 122                                       SmallVector<AllocaInst*, 32> &NewElts);
 123     void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocationInst *AI,
 124                                        SmallVector<AllocaInst*, 32> &NewElts);
 125
 126     const Type *CanConvertToScalar(Value *V, bool &IsNotTrivial);
 127     void ConvertToScalar(AllocationInst *AI, const Type *Ty);
 128     void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset);
 129     Value *ConvertUsesOfLoadToScalar(LoadInst *LI, AllocaInst *NewAI,
 130                                      unsigned Offset);
 131     Value *ConvertUsesOfStoreToScalar(StoreInst *SI, AllocaInst *NewAI,
 132                                       unsigned Offset);
 133     static Instruction *isOnlyCopiedFromConstantGlobal(AllocationInst *AI);
 134   };
 135 }
 136
 137 char SROA::ID = 0;
 138 static RegisterPass<SROA> X("scalarrepl", "Scalar Replacement of Aggregates");
 139
 140 // Public interface to the ScalarReplAggregates pass
 141 FunctionPass *llvm::createScalarReplAggregatesPass(signed int Threshold) {
 142   return new SROA(Threshold);
 143 }
 144
 145
 146 bool SROA::runOnFunction(Function &F) {
 147   TD = &getAnalysis<TargetData>();
 148
 149   bool Changed = performPromotion(F);
 150   while (1) {
 151     bool LocalChange = performScalarRepl(F);
 152     if (!LocalChange) break;   // No need to repromote if no scalarrepl
 153     Changed = true;
 154     LocalChange = performPromotion(F);
 155     if (!LocalChange) break;   // No need to re-scalarrepl if no promotion
 156   }
 157
 158   return Changed;
 159 }
 160
 161
 162 bool SROA::performPromotion(Function &F) {
 163   std::vector<AllocaInst*> Allocas;
 164   DominatorTree         &DT = getAnalysis<DominatorTree>();
 165   DominanceFrontier &DF = getAnalysis<DominanceFrontier>();
 166
 167   BasicBlock &BB = F.getEntryBlock();  // Get the entry node for the function
 168
 169   bool Changed = false;
 170
 171   while (1) {
 172     Allocas.clear();
 173
 174     // Find allocas that are safe to promote, by looking at all instructions in
 175     // the entry node
 176     for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
 177       if (AllocaInst *AI = dyn_cast<AllocaInst>(I))       // Is it an alloca?
 178         if (isAllocaPromotable(AI))
 179           Allocas.push_back(AI);
 180
 181     if (Allocas.empty()) break;
 182
 183     PromoteMemToReg(Allocas, DT, DF);
 184     NumPromoted += Allocas.size();
 185     Changed = true;
 186   }
 187
 188   return Changed;
 189 }
 190
 191 /// getNumSAElements - Return the number of elements in the specific struct or
 192 /// array.
 193 static uint64_t getNumSAElements(const Type *T) {
 194   if (const StructType *ST = dyn_cast<StructType>(T))
 195     return ST->getNumElements();
 196   return cast<ArrayType>(T)->getNumElements();
 197 }
 198
 199 // performScalarRepl - This algorithm is a simple worklist driven algorithm,
 200 // which runs on all of the malloc/alloca instructions in the function, removing
 201 // them if they are only used by getelementptr instructions.
 202 //
 203 bool SROA::performScalarRepl(Function &F) {
 204   std::vector<AllocationInst*> WorkList;
 205
 206   // Scan the entry basic block, adding any alloca's and mallocs to the worklist
 207   BasicBlock &BB = F.getEntryBlock();
 208   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
 209     if (AllocationInst *A = dyn_cast<AllocationInst>(I))
 210       WorkList.push_back(A);
 211
 212   // Process the worklist
 213   bool Changed = false;
 214   while (!WorkList.empty()) {
 215     AllocationInst *AI = WorkList.back();
 216     WorkList.pop_back();
 217
 218     // Handle dead allocas trivially.  These can be formed by SROA'ing arrays
 219     // with unused elements.
 220     if (AI->use_empty()) {
 221       AI->eraseFromParent();
 222       continue;
 223     }
 224
 225     // If we can turn this aggregate value (potentially with casts) into a
 226     // simple scalar value that can be mem2reg'd into a register value.
 227     bool IsNotTrivial = false;
 228     if (const Type *ActualType = CanConvertToScalar(AI, IsNotTrivial))
 229       if (IsNotTrivial && ActualType != Type::VoidTy) {
 230         ConvertToScalar(AI, ActualType);
 231         Changed = true;
 232         continue;
 233       }
 234
 235     // Check to see if we can perform the core SROA transformation.  We cannot
 236     // transform the allocation instruction if it is an array allocation
 237     // (allocations OF arrays are ok though), and an allocation of a scalar
 238     // value cannot be decomposed at all.
 239     if (!AI->isArrayAllocation() &&
 240         (isa<StructType>(AI->getAllocatedType()) ||
 241          isa<ArrayType>(AI->getAllocatedType())) &&
 242         AI->getAllocatedType()->isSized() &&
 243         // Do not promote any struct whose size is larger than "128" bytes.
 244         TD->getABITypeSize(AI->getAllocatedType()) < SRThreshold &&
 245         // Do not promote any struct into more than "32" separate vars.
 246         getNumSAElements(AI->getAllocatedType()) < SRThreshold/4) {
 247       // Check that all of the users of the allocation are capable of being
 248       // transformed.
 249       switch (isSafeAllocaToScalarRepl(AI)) {
 250       default: assert(0 && "Unexpected value!");
 251       case 0:  // Not safe to scalar replace.
 252         break;
 253       case 1:  // Safe, but requires cleanup/canonicalizations first
 254         CanonicalizeAllocaUsers(AI);
 255         // FALL THROUGH.
 256       case 3:  // Safe to scalar replace.
 257         DoScalarReplacement(AI, WorkList);
 258         Changed = true;
 259         continue;
 260       }
 261     }
 262
 263     // Check to see if this allocation is only modified by a memcpy/memmove from
 264     // a constant global.  If this is the case, we can change all users to use
 265     // the constant global instead.  This is commonly produced by the CFE by
 266     // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A'
 267     // is only subsequently read.
 268     if (Instruction *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) {
 269       DOUT << "Found alloca equal to global: " << *AI;
 270       DOUT << "  memcpy = " << *TheCopy;
 271       Constant *TheSrc = cast<Constant>(TheCopy->getOperand(2));
 272       AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType()));
 273       TheCopy->eraseFromParent();  // Don't mutate the global.
 274       AI->eraseFromParent();
 275       ++NumGlobals;
 276       Changed = true;
 277       continue;
 278     }
 279
 280     // Otherwise, couldn't process this.
 281   }
 282
 283   return Changed;
 284 }
 285
 286 /// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl
 287 /// predicate, do SROA now.
 288 void SROA::DoScalarReplacement(AllocationInst *AI,
 289                                std::vector<AllocationInst*> &WorkList) {
 290   DOUT << "Found inst to SROA: " << *AI;
 291   SmallVector<AllocaInst*, 32> ElementAllocas;
 292   if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) {
 293     ElementAllocas.reserve(ST->getNumContainedTypes());
 294     for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) {
 295       AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0,
 296                                       AI->getAlignment(),
 297                                       AI->getName() + "." + utostr(i), AI);
 298       ElementAllocas.push_back(NA);
 299       WorkList.push_back(NA);  // Add to worklist for recursive processing
 300     }
 301   } else {
 302     const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
 303     ElementAllocas.reserve(AT->getNumElements());
 304     const Type *ElTy = AT->getElementType();
 305     for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
 306       AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(),
 307                                       AI->getName() + "." + utostr(i), AI);
 308       ElementAllocas.push_back(NA);
 309       WorkList.push_back(NA);  // Add to worklist for recursive processing
 310     }
 311   }
 312
 313   // Now that we have created the alloca instructions that we want to use,
 314   // expand the getelementptr instructions to use them.
 315   //
 316   while (!AI->use_empty()) {
 317     Instruction *User = cast<Instruction>(AI->use_back());
 318     if (BitCastInst *BCInst = dyn_cast<BitCastInst>(User)) {
 319       RewriteBitCastUserOfAlloca(BCInst, AI, ElementAllocas);
 320       BCInst->eraseFromParent();
 321       continue;
 322     }
 323
 324     // Replace:
 325     //   %res = load { i32, i32 }* %alloc
 326     // with:
 327     //   %load.0 = load i32* %alloc.0
 328     //   %insert.0 insertvalue { i32, i32 } zeroinitializer, i32 %load.0, 0
 329     //   %load.1 = load i32* %alloc.1
 330     //   %insert = insertvalue { i32, i32 } %insert.0, i32 %load.1, 1
 331     // (Also works for arrays instead of structs)
 332     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
 333       Value *Insert = UndefValue::get(LI->getType());
 334       for (unsigned i = 0, e = ElementAllocas.size(); i != e; ++i) {
 335         Value *Load = new LoadInst(ElementAllocas[i], "load", LI);
 336         Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI);
 337       }
 338       LI->replaceAllUsesWith(Insert);
 339       LI->eraseFromParent();
 340       continue;
 341     }
 342
 343     // Replace:
 344     //   store { i32, i32 } %val, { i32, i32 }* %alloc
 345     // with:
 346     //   %val.0 = extractvalue { i32, i32 } %val, 0
 347     //   store i32 %val.0, i32* %alloc.0
 348     //   %val.1 = extractvalue { i32, i32 } %val, 1
 349     //   store i32 %val.1, i32* %alloc.1
 350     // (Also works for arrays instead of structs)
 351     if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
 352       Value *Val = SI->getOperand(0);
 353       for (unsigned i = 0, e = ElementAllocas.size(); i != e; ++i) {
 354         Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI);
 355         new StoreInst(Extract, ElementAllocas[i], SI);
 356       }
 357       SI->eraseFromParent();
 358       continue;
 359     }
 360
 361     GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User);
 362     // We now know that the GEP is of the form: GEP <ptr>, 0, <cst>
 363     unsigned Idx =
 364        (unsigned)cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue();
 365
 366     assert(Idx < ElementAllocas.size() && "Index out of range?");
 367     AllocaInst *AllocaToUse = ElementAllocas[Idx];
 368
 369     Value *RepValue;
 370     if (GEPI->getNumOperands() == 3) {
 371       // Do not insert a new getelementptr instruction with zero indices, only
 372       // to have it optimized out later.
 373       RepValue = AllocaToUse;
 374     } else {
 375       // We are indexing deeply into the structure, so we still need a
 376       // getelement ptr instruction to finish the indexing.  This may be
 377       // expanded itself once the worklist is rerun.
 378       //
 379       SmallVector<Value*, 8> NewArgs;
 380       NewArgs.push_back(Constant::getNullValue(Type::Int32Ty));
 381       NewArgs.append(GEPI->op_begin()+3, GEPI->op_end());
 382       RepValue = GetElementPtrInst::Create(AllocaToUse, NewArgs.begin(),
 383                                            NewArgs.end(), "", GEPI);
 384       RepValue->takeName(GEPI);
 385     }
 386
 387     // If this GEP is to the start of the aggregate, check for memcpys.
 388     if (Idx == 0 && GEPI->hasAllZeroIndices())
 389       RewriteBitCastUserOfAlloca(GEPI, AI, ElementAllocas);
 390
 391     // Move all of the users over to the new GEP.
 392     GEPI->replaceAllUsesWith(RepValue);
 393     // Delete the old GEP
 394     GEPI->eraseFromParent();
 395   }
 396
 397   // Finally, delete the Alloca instruction
 398   AI->eraseFromParent();
 399   NumReplaced++;
 400 }
 401
 402
 403 /// isSafeElementUse - Check to see if this use is an allowed use for a
 404 /// getelementptr instruction of an array aggregate allocation.  isFirstElt
 405 /// indicates whether Ptr is known to the start of the aggregate.
 406 ///
 407 void SROA::isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI,
 408                             AllocaInfo &Info) {
 409   for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end();
 410        I != E; ++I) {
 411     Instruction *User = cast<Instruction>(*I);
 412     switch (User->getOpcode()) {
 413     case Instruction::Load:  break;
 414     case Instruction::Store:
 415       // Store is ok if storing INTO the pointer, not storing the pointer
 416       if (User->getOperand(0) == Ptr) return MarkUnsafe(Info);
 417       break;
 418     case Instruction::GetElementPtr: {
 419       GetElementPtrInst *GEP = cast<GetElementPtrInst>(User);
 420       bool AreAllZeroIndices = isFirstElt;
 421       if (GEP->getNumOperands() > 1) {
 422         if (!isa<ConstantInt>(GEP->getOperand(1)) ||
 423             !cast<ConstantInt>(GEP->getOperand(1))->isZero())
 424           // Using pointer arithmetic to navigate the array.
 425           return MarkUnsafe(Info);
 426
 427         if (AreAllZeroIndices)
 428           AreAllZeroIndices = GEP->hasAllZeroIndices();
 429       }
 430       isSafeElementUse(GEP, AreAllZeroIndices, AI, Info);
 431       if (Info.isUnsafe) return;
 432       break;
 433     }
 434     case Instruction::BitCast:
 435       if (isFirstElt) {
 436         isSafeUseOfBitCastedAllocation(cast<BitCastInst>(User), AI, Info);
 437         if (Info.isUnsafe) return;
 438         break;
 439       }
 440       DOUT << "  Transformation preventing inst: " << *User;
 441       return MarkUnsafe(Info);
 442     case Instruction::Call:
 443       if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) {
 444         if (isFirstElt) {
 445           isSafeMemIntrinsicOnAllocation(MI, AI, I.getOperandNo(), Info);
 446           if (Info.isUnsafe) return;
 447           break;
 448         }
 449       }
 450       DOUT << "  Transformation preventing inst: " << *User;
 451       return MarkUnsafe(Info);
 452     default:
 453       DOUT << "  Transformation preventing inst: " << *User;
 454       return MarkUnsafe(Info);
 455     }
 456   }
 457   return;  // All users look ok :)
 458 }
 459
 460 /// AllUsersAreLoads - Return true if all users of this value are loads.
 461 static bool AllUsersAreLoads(Value *Ptr) {
 462   for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end();
 463        I != E; ++I)
 464     if (cast<Instruction>(*I)->getOpcode() != Instruction::Load)
 465       return false;
 466   return true;
 467 }
 468
 469 /// isSafeUseOfAllocation - Check to see if this user is an allowed use for an
 470 /// aggregate allocation.
 471 ///
 472 void SROA::isSafeUseOfAllocation(Instruction *User, AllocationInst *AI,
 473                                  AllocaInfo &Info) {
 474   if (BitCastInst *C = dyn_cast<BitCastInst>(User))
 475     return isSafeUseOfBitCastedAllocation(C, AI, Info);
 476
 477   if (isa<LoadInst>(User))
 478     return; // Loads (returning a first class aggregrate) are always rewritable
 479
 480   if (isa<StoreInst>(User) && User->getOperand(0) != AI)
 481     return; // Store is ok if storing INTO the pointer, not storing the pointer
 482
 483   GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User);
 484   if (GEPI == 0)
 485     return MarkUnsafe(Info);
 486
 487   gep_type_iterator I = gep_type_begin(GEPI), E = gep_type_end(GEPI);
 488
 489   // The GEP is not safe to transform if not of the form "GEP <ptr>, 0, <cst>".
 490   if (I == E ||
 491       I.getOperand() != Constant::getNullValue(I.getOperand()->getType())) {
 492     return MarkUnsafe(Info);
 493   }
 494
 495   ++I;
 496   if (I == E) return MarkUnsafe(Info);  // ran out of GEP indices??
 497
 498   bool IsAllZeroIndices = true;
 499
 500   // If the first index is a non-constant index into an array, see if we can
 501   // handle it as a special case.
 502   if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) {
 503     if (!isa<ConstantInt>(I.getOperand())) {
 504       IsAllZeroIndices = 0;
 505       uint64_t NumElements = AT->getNumElements();
 506
 507       // If this is an array index and the index is not constant, we cannot
 508       // promote... that is unless the array has exactly one or two elements in
 509       // it, in which case we CAN promote it, but we have to canonicalize this
 510       // out if this is the only problem.
 511       if ((NumElements == 1 || NumElements == 2) &&
 512           AllUsersAreLoads(GEPI)) {
 513         Info.needsCanon = true;
 514         return;  // Canonicalization required!
 515       }
 516       return MarkUnsafe(Info);
 517     }
 518   }
 519
 520   // Walk through the GEP type indices, checking the types that this indexes
 521   // into.
 522   for (; I != E; ++I) {
 523     // Ignore struct elements, no extra checking needed for these.
 524     if (isa<StructType>(*I))
 525       continue;
 526
 527     ConstantInt *IdxVal = dyn_cast<ConstantInt>(I.getOperand());
 528     if (!IdxVal) return MarkUnsafe(Info);
 529
 530     // Are all indices still zero?
 531     IsAllZeroIndices &= IdxVal->isZero();
 532
 533     if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) {
 534       // This GEP indexes an array.  Verify that this is an in-range constant
 535       // integer. Specifically, consider A[0][i]. We cannot know that the user
 536       // isn't doing invalid things like allowing i to index an out-of-range
 537       // subscript that accesses A[1].  Because of this, we have to reject SROA
 538       // of any accesses into structs where any of the components are variables.
 539       if (IdxVal->getZExtValue() >= AT->getNumElements())
 540         return MarkUnsafe(Info);
 541     } else if (const VectorType *VT = dyn_cast<VectorType>(*I)) {
 542       if (IdxVal->getZExtValue() >= VT->getNumElements())
 543         return MarkUnsafe(Info);
 544     }
 545   }
 546
 547   // If there are any non-simple uses of this getelementptr, make sure to reject
 548   // them.
 549   return isSafeElementUse(GEPI, IsAllZeroIndices, AI, Info);
 550 }
 551
 552 /// isSafeMemIntrinsicOnAllocation - Return true if the specified memory
 553 /// intrinsic can be promoted by SROA.  At this point, we know that the operand
 554 /// of the memintrinsic is a pointer to the beginning of the allocation.
 555 void SROA::isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI,
 556                                           unsigned OpNo, AllocaInfo &Info) {
 557   // If not constant length, give up.
 558   ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
 559   if (!Length) return MarkUnsafe(Info);
 560
 561   // If not the whole aggregate, give up.
 562   if (Length->getZExtValue() !=
 563       TD->getABITypeSize(AI->getType()->getElementType()))
 564     return MarkUnsafe(Info);
 565
 566   // We only know about memcpy/memset/memmove.
 567   if (!isa<MemCpyInst>(MI) && !isa<MemSetInst>(MI) && !isa<MemMoveInst>(MI))
 568     return MarkUnsafe(Info);
 569
 570   // Otherwise, we can transform it.  Determine whether this is a memcpy/set
 571   // into or out of the aggregate.
 572   if (OpNo == 1)
 573     Info.isMemCpyDst = true;
 574   else {
 575     assert(OpNo == 2);
 576     Info.isMemCpySrc = true;
 577   }
 578 }
 579
 580 /// isSafeUseOfBitCastedAllocation - Return true if all users of this bitcast
 581 /// are
 582 void SROA::isSafeUseOfBitCastedAllocation(BitCastInst *BC, AllocationInst *AI,
 583                                           AllocaInfo &Info) {
 584   for (Value::use_iterator UI = BC->use_begin(), E = BC->use_end();
 585        UI != E; ++UI) {
 586     if (BitCastInst *BCU = dyn_cast<BitCastInst>(UI)) {
 587       isSafeUseOfBitCastedAllocation(BCU, AI, Info);
 588     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(UI)) {
 589       isSafeMemIntrinsicOnAllocation(MI, AI, UI.getOperandNo(), Info);
 590     } else if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
 591       // If storing the entire alloca in one chunk through a bitcasted pointer
 592       // to integer, we can transform it.  This happens (for example) when you
 593       // cast a {i32,i32}* to i64* and store through it.  This is similar to the
 594       // memcpy case and occurs in various "byval" cases and emulated memcpys.
 595       if (isa<IntegerType>(SI->getOperand(0)->getType()) &&
 596           TD->getABITypeSize(SI->getOperand(0)->getType()) ==
 597           TD->getABITypeSize(AI->getType()->getElementType())) {
 598         Info.isMemCpyDst = true;
 599         continue;
 600       }
 601       return MarkUnsafe(Info);
 602     } else {
 603       return MarkUnsafe(Info);
 604     }
 605     if (Info.isUnsafe) return;
 606   }
 607 }
 608
 609 /// RewriteBitCastUserOfAlloca - BCInst (transitively) bitcasts AI, or indexes
 610 /// to its first element.  Transform users of the cast to use the new values
 611 /// instead.
 612 void SROA::RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI,
 613                                       SmallVector<AllocaInst*, 32> &NewElts) {
 614   Value::use_iterator UI = BCInst->use_begin(), UE = BCInst->use_end();
 615   while (UI != UE) {
 616     Instruction *User = cast<Instruction>(*UI++);
 617     if (BitCastInst *BCU = dyn_cast<BitCastInst>(User)) {
 618       RewriteBitCastUserOfAlloca(BCU, AI, NewElts);
 619       if (BCU->use_empty()) BCU->eraseFromParent();
 620       continue;
 621     }
 622
 623     if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) {
 624       // This must be memcpy/memmove/memset of the entire aggregate.
 625       // Split into one per element.
 626       RewriteMemIntrinUserOfAlloca(MI, BCInst, AI, NewElts);
 627       continue;
 628     }
 629
 630     if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
 631       // This must be a store of the entire alloca from an integer.
 632       RewriteStoreUserOfWholeAlloca(SI, AI, NewElts);
 633       continue;
 634     }
 635
 636     // Otherwise it must be some other user of a gep of the first pointer.  Just
 637     // leave these alone.
 638     continue;
 639   }
 640 }
 641
 642 /// RewriteMemIntrinUserOfAlloca - MI is a memcpy/memset/memmove from or to AI.
 643 /// Rewrite it to copy or set the elements of the scalarized memory.
 644 void SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *BCInst,
 645                                         AllocationInst *AI,
 646                                         SmallVector<AllocaInst*, 32> &NewElts) {
 647
 648   // If this is a memcpy/memmove, construct the other pointer as the
 649   // appropriate type.
 650   Value *OtherPtr = 0;
 651   if (MemCpyInst *MCI = dyn_cast<MemCpyInst>(MI)) {
 652     if (BCInst == MCI->getRawDest())
 653       OtherPtr = MCI->getRawSource();
 654     else {
 655       assert(BCInst == MCI->getRawSource());
 656       OtherPtr = MCI->getRawDest();
 657     }
 658   } else if (MemMoveInst *MMI = dyn_cast<MemMoveInst>(MI)) {
 659     if (BCInst == MMI->getRawDest())
 660       OtherPtr = MMI->getRawSource();
 661     else {
 662       assert(BCInst == MMI->getRawSource());
 663       OtherPtr = MMI->getRawDest();
 664     }
 665   }
 666
 667   // If there is an other pointer, we want to convert it to the same pointer
 668   // type as AI has, so we can GEP through it safely.
 669   if (OtherPtr) {
 670     // It is likely that OtherPtr is a bitcast, if so, remove it.
 671     if (BitCastInst *BC = dyn_cast<BitCastInst>(OtherPtr))
 672       OtherPtr = BC->getOperand(0);
 673     // All zero GEPs are effectively bitcasts.
 674     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(OtherPtr))
 675       if (GEP->hasAllZeroIndices())
 676         OtherPtr = GEP->getOperand(0);
 677
 678     if (ConstantExpr *BCE = dyn_cast<ConstantExpr>(OtherPtr))
 679       if (BCE->getOpcode() == Instruction::BitCast)
 680         OtherPtr = BCE->getOperand(0);
 681
 682     // If the pointer is not the right type, insert a bitcast to the right
 683     // type.
 684     if (OtherPtr->getType() != AI->getType())
 685       OtherPtr = new BitCastInst(OtherPtr, AI->getType(), OtherPtr->getName(),
 686                                  MI);
 687   }
 688
 689   // Process each element of the aggregate.
 690   Value *TheFn = MI->getOperand(0);
 691   const Type *BytePtrTy = MI->getRawDest()->getType();
 692   bool SROADest = MI->getRawDest() == BCInst;
 693
 694   Constant *Zero = Constant::getNullValue(Type::Int32Ty);
 695
 696   for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
 697     // If this is a memcpy/memmove, emit a GEP of the other element address.
 698     Value *OtherElt = 0;
 699     if (OtherPtr) {
 700       Value *Idx[2] = { Zero, ConstantInt::get(Type::Int32Ty, i) };
 701       OtherElt = GetElementPtrInst::Create(OtherPtr, Idx, Idx + 2,
 702                                            OtherPtr->getNameStr()+"."+utostr(i),
 703                                            MI);
 704     }
 705
 706     Value *EltPtr = NewElts[i];
 707     const Type *EltTy =cast<PointerType>(EltPtr->getType())->getElementType();
 708
 709     // If we got down to a scalar, insert a load or store as appropriate.
 710     if (EltTy->isSingleValueType()) {
 711       if (isa<MemCpyInst>(MI) || isa<MemMoveInst>(MI)) {
 712         Value *Elt = new LoadInst(SROADest ? OtherElt : EltPtr, "tmp",
 713                                   MI);
 714         new StoreInst(Elt, SROADest ? EltPtr : OtherElt, MI);
 715         continue;
 716       }
 717       assert(isa<MemSetInst>(MI));
 718
 719       // If the stored element is zero (common case), just store a null
 720       // constant.
 721       Constant *StoreVal;
 722       if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getOperand(2))) {
 723         if (CI->isZero()) {
 724           StoreVal = Constant::getNullValue(EltTy);  // 0.0, null, 0, <0,0>
 725         } else {
 726           // If EltTy is a vector type, get the element type.
 727           const Type *ValTy = EltTy;
 728           if (const VectorType *VTy = dyn_cast<VectorType>(ValTy))
 729             ValTy = VTy->getElementType();
 730
 731           // Construct an integer with the right value.
 732           unsigned EltSize = TD->getTypeSizeInBits(ValTy);
 733           APInt OneVal(EltSize, CI->getZExtValue());
 734           APInt TotalVal(OneVal);
 735           // Set each byte.
 736           for (unsigned i = 0; 8*i < EltSize; ++i) {
 737             TotalVal = TotalVal.shl(8);
 738             TotalVal |= OneVal;
 739           }
 740
 741           // Convert the integer value to the appropriate type.
 742           StoreVal = ConstantInt::get(TotalVal);
 743           if (isa<PointerType>(ValTy))
 744             StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy);
 745           else if (ValTy->isFloatingPoint())
 746             StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy);
 747           assert(StoreVal->getType() == ValTy && "Type mismatch!");
 748
 749           // If the requested value was a vector constant, create it.
 750           if (EltTy != ValTy) {
 751             unsigned NumElts = cast<VectorType>(ValTy)->getNumElements();
 752             SmallVector<Constant*, 16> Elts(NumElts, StoreVal);
 753             StoreVal = ConstantVector::get(&Elts[0], NumElts);
 754           }
 755         }
 756         new StoreInst(StoreVal, EltPtr, MI);
 757         continue;
 758       }
 759       // Otherwise, if we're storing a byte variable, use a memset call for
 760       // this element.
 761     }
 762
 763     // Cast the element pointer to BytePtrTy.
 764     if (EltPtr->getType() != BytePtrTy)
 765       EltPtr = new BitCastInst(EltPtr, BytePtrTy, EltPtr->getNameStr(), MI);
 766
 767     // Cast the other pointer (if we have one) to BytePtrTy.
 768     if (OtherElt && OtherElt->getType() != BytePtrTy)
 769       OtherElt = new BitCastInst(OtherElt, BytePtrTy,OtherElt->getNameStr(),
 770                                  MI);
 771
 772     unsigned EltSize = TD->getABITypeSize(EltTy);
 773
 774     // Finally, insert the meminst for this element.
 775     if (isa<MemCpyInst>(MI) || isa<MemMoveInst>(MI)) {
 776       Value *Ops[] = {
 777         SROADest ? EltPtr : OtherElt,  // Dest ptr
 778         SROADest ? OtherElt : EltPtr,  // Src ptr
 779         ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size
 780         Zero  // Align
 781       };
 782       CallInst::Create(TheFn, Ops, Ops + 4, "", MI);
 783     } else {
 784       assert(isa<MemSetInst>(MI));
 785       Value *Ops[] = {
 786         EltPtr, MI->getOperand(2),  // Dest, Value,
 787         ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size
 788         Zero  // Align
 789       };
 790       CallInst::Create(TheFn, Ops, Ops + 4, "", MI);
 791     }
 792   }
 793   MI->eraseFromParent();
 794 }
 795
 796 /// RewriteStoreUserOfWholeAlloca - We found an store of an integer that
 797 /// overwrites the entire allocation.  Extract out the pieces of the stored
 798 /// integer and store them individually.
 799 void SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI,
 800                                          AllocationInst *AI,
 801                                          SmallVector<AllocaInst*, 32> &NewElts){
 802   // Extract each element out of the integer according to its structure offset
 803   // and store the element value to the individual alloca.
 804   Value *SrcVal = SI->getOperand(0);
 805   const Type *AllocaEltTy = AI->getType()->getElementType();
 806   uint64_t AllocaSizeBits = TD->getABITypeSizeInBits(AllocaEltTy);
 807
 808   // If this isn't a store of an integer to the whole alloca, it may be a store
 809   // to the first element.  Just ignore the store in this case and normal SROA
 810   // will handle it.
 811   if (!isa<IntegerType>(SrcVal->getType()) ||
 812       TD->getABITypeSizeInBits(SrcVal->getType()) != AllocaSizeBits)
 813     return;
 814
 815   DOUT << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << *SI;
 816
 817   // There are two forms here: AI could be an array or struct.  Both cases
 818   // have different ways to compute the element offset.
 819   if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) {
 820     const StructLayout *Layout = TD->getStructLayout(EltSTy);
 821
 822     for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
 823       // Get the number of bits to shift SrcVal to get the value.
 824       const Type *FieldTy = EltSTy->getElementType(i);
 825       uint64_t Shift = Layout->getElementOffsetInBits(i);
 826
 827       if (TD->isBigEndian())
 828         Shift = AllocaSizeBits-Shift-TD->getABITypeSizeInBits(FieldTy);
 829
 830       Value *EltVal = SrcVal;
 831       if (Shift) {
 832         Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift);
 833         EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal,
 834                                             "sroa.store.elt", SI);
 835       }
 836
 837       // Truncate down to an integer of the right size.
 838       uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy);
 839       if (FieldSizeBits != AllocaSizeBits)
 840         EltVal = new TruncInst(EltVal, IntegerType::get(FieldSizeBits), "", SI);
 841       Value *DestField = NewElts[i];
 842       if (EltVal->getType() == FieldTy) {
 843         // Storing to an integer field of this size, just do it.
 844       } else if (FieldTy->isFloatingPoint() || isa<VectorType>(FieldTy)) {
 845         // Bitcast to the right element type (for fp/vector values).
 846         EltVal = new BitCastInst(EltVal, FieldTy, "", SI);
 847       } else {
 848         // Otherwise, bitcast the dest pointer (for aggregates).
 849         DestField = new BitCastInst(DestField,
 850                                     PointerType::getUnqual(EltVal->getType()),
 851                                     "", SI);
 852       }
 853       new StoreInst(EltVal, DestField, SI);
 854     }
 855
 856   } else {
 857     const ArrayType *ATy = cast<ArrayType>(AllocaEltTy);
 858     const Type *ArrayEltTy = ATy->getElementType();
 859     uint64_t ElementOffset = TD->getABITypeSizeInBits(ArrayEltTy);
 860     uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy);
 861
 862     uint64_t Shift;
 863
 864     if (TD->isBigEndian())
 865       Shift = AllocaSizeBits-ElementOffset;
 866     else
 867       Shift = 0;
 868
 869     for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
 870
 871       Value *EltVal = SrcVal;
 872       if (Shift) {
 873         Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift);
 874         EltVal = BinaryOperator::CreateLShr(EltVal, ShiftVal,
 875                                             "sroa.store.elt", SI);
 876       }
 877
 878       // Truncate down to an integer of the right size.
 879       if (ElementSizeBits != AllocaSizeBits)
 880         EltVal = new TruncInst(EltVal, IntegerType::get(ElementSizeBits),"",SI);
 881       Value *DestField = NewElts[i];
 882       if (EltVal->getType() == ArrayEltTy) {
 883         // Storing to an integer field of this size, just do it.
 884       } else if (ArrayEltTy->isFloatingPoint() || isa<VectorType>(ArrayEltTy)) {
 885         // Bitcast to the right element type (for fp/vector values).
 886         EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI);
 887       } else {
 888         // Otherwise, bitcast the dest pointer (for aggregates).
 889         DestField = new BitCastInst(DestField,
 890                                     PointerType::getUnqual(EltVal->getType()),
 891                                     "", SI);
 892       }
 893       new StoreInst(EltVal, DestField, SI);
 894
 895       if (TD->isBigEndian())
 896         Shift -= ElementOffset;
 897       else
 898         Shift += ElementOffset;
 899     }
 900   }
 901
 902   SI->eraseFromParent();
 903 }
 904
 905
 906 /// HasPadding - Return true if the specified type has any structure or
 907 /// alignment padding, false otherwise.
 908 static bool HasPadding(const Type *Ty, const TargetData &TD) {
 909   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 910     const StructLayout *SL = TD.getStructLayout(STy);
 911     unsigned PrevFieldBitOffset = 0;
 912     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
 913       unsigned FieldBitOffset = SL->getElementOffsetInBits(i);
 914
 915       // Padding in sub-elements?
 916       if (HasPadding(STy->getElementType(i), TD))
 917         return true;
 918
 919       // Check to see if there is any padding between this element and the
 920       // previous one.
 921       if (i) {
 922         unsigned PrevFieldEnd =
 923         PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1));
 924         if (PrevFieldEnd < FieldBitOffset)
 925           return true;
 926       }
 927
 928       PrevFieldBitOffset = FieldBitOffset;
 929     }
 930
 931     //  Check for tail padding.
 932     if (unsigned EltCount = STy->getNumElements()) {
 933       unsigned PrevFieldEnd = PrevFieldBitOffset +
 934                    TD.getTypeSizeInBits(STy->getElementType(EltCount-1));
 935       if (PrevFieldEnd < SL->getSizeInBits())
 936         return true;
 937     }
 938
 939   } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
 940     return HasPadding(ATy->getElementType(), TD);
 941   } else if (const VectorType *VTy = dyn_cast<VectorType>(Ty)) {
 942     return HasPadding(VTy->getElementType(), TD);
 943   }
 944   return TD.getTypeSizeInBits(Ty) != TD.getABITypeSizeInBits(Ty);
 945 }
 946
 947 /// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of
 948 /// an aggregate can be broken down into elements.  Return 0 if not, 3 if safe,
 949 /// or 1 if safe after canonicalization has been performed.
 950 ///
 951 int SROA::isSafeAllocaToScalarRepl(AllocationInst *AI) {
 952   // Loop over the use list of the alloca.  We can only transform it if all of
 953   // the users are safe to transform.
 954   AllocaInfo Info;
 955
 956   for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
 957        I != E; ++I) {
 958     isSafeUseOfAllocation(cast<Instruction>(*I), AI, Info);
 959     if (Info.isUnsafe) {
 960       DOUT << "Cannot transform: " << *AI << "  due to user: " << **I;
 961       return 0;
 962     }
 963   }
 964
 965   // Okay, we know all the users are promotable.  If the aggregate is a memcpy
 966   // source and destination, we have to be careful.  In particular, the memcpy
 967   // could be moving around elements that live in structure padding of the LLVM
 968   // types, but may actually be used.  In these cases, we refuse to promote the
 969   // struct.
 970   if (Info.isMemCpySrc && Info.isMemCpyDst &&
 971       HasPadding(AI->getType()->getElementType(), *TD))
 972     return 0;
 973
 974   // If we require cleanup, return 1, otherwise return 3.
 975   return Info.needsCanon ? 1 : 3;
 976 }
 977
 978 /// CanonicalizeAllocaUsers - If SROA reported that it can promote the specified
 979 /// allocation, but only if cleaned up, perform the cleanups required.
 980 void SROA::CanonicalizeAllocaUsers(AllocationInst *AI) {
 981   // At this point, we know that the end result will be SROA'd and promoted, so
 982   // we can insert ugly code if required so long as sroa+mem2reg will clean it
 983   // up.
 984   for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
 985        UI != E; ) {
 986     GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI++);
 987     if (!GEPI) continue;
 988     gep_type_iterator I = gep_type_begin(GEPI);
 989     ++I;
 990
 991     if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) {
 992       uint64_t NumElements = AT->getNumElements();
 993
 994       if (!isa<ConstantInt>(I.getOperand())) {
 995         if (NumElements == 1) {
 996           GEPI->setOperand(2, Constant::getNullValue(Type::Int32Ty));
 997         } else {
 998           assert(NumElements == 2 && "Unhandled case!");
 999           // All users of the GEP must be loads.  At each use of the GEP, insert
1000           // two loads of the appropriate indexed GEP and select between them.
1001           Value *IsOne = new ICmpInst(ICmpInst::ICMP_NE, I.getOperand(),
1002                               Constant::getNullValue(I.getOperand()->getType()),
1003              "isone", GEPI);
1004           // Insert the new GEP instructions, which are properly indexed.
1005           SmallVector<Value*, 8> Indices(GEPI->op_begin()+1, GEPI->op_end());
1006           Indices[1] = Constant::getNullValue(Type::Int32Ty);
1007           Value *ZeroIdx = GetElementPtrInst::Create(GEPI->getOperand(0),
1008                                                      Indices.begin(),
1009                                                      Indices.end(),
1010                                                      GEPI->getName()+".0", GEPI);
1011           Indices[1] = ConstantInt::get(Type::Int32Ty, 1);
1012           Value *OneIdx = GetElementPtrInst::Create(GEPI->getOperand(0),
1013                                                     Indices.begin(),
1014                                                     Indices.end(),
1015                                                     GEPI->getName()+".1", GEPI);
1016           // Replace all loads of the variable index GEP with loads from both
1017           // indexes and a select.
1018           while (!GEPI->use_empty()) {
1019             LoadInst *LI = cast<LoadInst>(GEPI->use_back());
1020             Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI);
1021             Value *One  = new LoadInst(OneIdx , LI->getName()+".1", LI);
1022             Value *R = SelectInst::Create(IsOne, One, Zero, LI->getName(), LI);
1023             LI->replaceAllUsesWith(R);
1024             LI->eraseFromParent();
1025           }
1026           GEPI->eraseFromParent();
1027         }
1028       }
1029     }
1030   }
1031 }
1032
1033 /// MergeInType - Add the 'In' type to the accumulated type so far.  If the
1034 /// types are incompatible, return true, otherwise update Accum and return
1035 /// false.
1036 ///
1037 /// There are three cases we handle here:
1038 ///   1) An effectively-integer union, where the pieces are stored into as
1039 ///      smaller integers (common with byte swap and other idioms).
1040 ///   2) A union of vector types of the same size and potentially its elements.
1041 ///      Here we turn element accesses into insert/extract element operations.
1042 ///   3) A union of scalar types, such as int/float or int/pointer.  Here we
1043 ///      merge together into integers, allowing the xform to work with #1 as
1044 ///      well.
1045 static bool MergeInType(const Type *In, const Type *&Accum,
1046                         const TargetData &TD) {
1047   // If this is our first type, just use it.
1048   const VectorType *PTy;
1049   if (Accum == Type::VoidTy || In == Accum) {
1050     Accum = In;
1051   } else if (In == Type::VoidTy) {
1052     // Noop.
1053   } else if (In->isInteger() && Accum->isInteger()) {   // integer union.
1054     // Otherwise pick whichever type is larger.
1055     if (cast<IntegerType>(In)->getBitWidth() >
1056         cast<IntegerType>(Accum)->getBitWidth())
1057       Accum = In;
1058   } else if (isa<PointerType>(In) && isa<PointerType>(Accum)) {
1059     // Pointer unions just stay as one of the pointers.
1060   } else if (isa<VectorType>(In) || isa<VectorType>(Accum)) {
1061     if ((PTy = dyn_cast<VectorType>(Accum)) &&
1062         PTy->getElementType() == In) {
1063       // Accum is a vector, and we are accessing an element: ok.
1064     } else if ((PTy = dyn_cast<VectorType>(In)) &&
1065                PTy->getElementType() == Accum) {
1066       // In is a vector, and accum is an element: ok, remember In.
1067       Accum = In;
1068     } else if ((PTy = dyn_cast<VectorType>(In)) && isa<VectorType>(Accum) &&
1069                PTy->getBitWidth() == cast<VectorType>(Accum)->getBitWidth()) {
1070       // Two vectors of the same size: keep Accum.
1071     } else {
1072       // Cannot insert an short into a <4 x int> or handle
1073       // <2 x int> -> <4 x int>
1074       return true;
1075     }
1076   } else {
1077     // Pointer/FP/Integer unions merge together as integers.
1078     switch (Accum->getTypeID()) {
1079     case Type::PointerTyID: Accum = TD.getIntPtrType(); break;
1080     case Type::FloatTyID:   Accum = Type::Int32Ty; break;
1081     case Type::DoubleTyID:  Accum = Type::Int64Ty; break;
1082     case Type::X86_FP80TyID:  return true;
1083     case Type::FP128TyID: return true;
1084     case Type::PPC_FP128TyID: return true;
1085     default:
1086       assert(Accum->isInteger() && "Unknown FP type!");
1087       break;
1088     }
1089
1090     switch (In->getTypeID()) {
1091     case Type::PointerTyID: In = TD.getIntPtrType(); break;
1092     case Type::FloatTyID:   In = Type::Int32Ty; break;
1093     case Type::DoubleTyID:  In = Type::Int64Ty; break;
1094     case Type::X86_FP80TyID:  return true;
1095     case Type::FP128TyID: return true;
1096     case Type::PPC_FP128TyID: return true;
1097     default:
1098       assert(In->isInteger() && "Unknown FP type!");
1099       break;
1100     }
1101     return MergeInType(In, Accum, TD);
1102   }
1103   return false;
1104 }
1105
1106 /// getIntAtLeastAsBigAs - Return an integer type that is at least as big as the
1107 /// specified type.  If there is no suitable type, this returns null.
1108 const Type *getIntAtLeastAsBigAs(unsigned NumBits) {
1109   if (NumBits > 64) return 0;
1110   if (NumBits > 32) return Type::Int64Ty;
1111   if (NumBits > 16) return Type::Int32Ty;
1112   if (NumBits > 8) return Type::Int16Ty;
1113   return Type::Int8Ty;
1114 }
1115
1116 /// CanConvertToScalar - V is a pointer.  If we can convert the pointee to a
1117 /// single scalar integer type, return that type.  Further, if the use is not
1118 /// a completely trivial use that mem2reg could promote, set IsNotTrivial.  If
1119 /// there are no uses of this pointer, return Type::VoidTy to differentiate from
1120 /// failure.
1121 ///
1122 const Type *SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial) {
1123   const Type *UsedType = Type::VoidTy; // No uses, no forced type.
1124   const PointerType *PTy = cast<PointerType>(V->getType());
1125
1126   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
1127     Instruction *User = cast<Instruction>(*UI);
1128
1129     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
1130       // FIXME: Loads of a first class aggregrate value could be converted to a
1131       // series of loads and insertvalues
1132       if (!LI->getType()->isSingleValueType())
1133         return 0;
1134
1135       if (MergeInType(LI->getType(), UsedType, *TD))
1136         return 0;
1137       continue;
1138     }
1139
1140     if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
1141       // Storing the pointer, not into the value?
1142       if (SI->getOperand(0) == V) return 0;
1143
1144       // FIXME: Stores of a first class aggregrate value could be converted to a
1145       // series of extractvalues and stores
1146       if (!SI->getOperand(0)->getType()->isSingleValueType())
1147         return 0;
1148
1149       // NOTE: We could handle storing of FP imms into integers here!
1150
1151       if (MergeInType(SI->getOperand(0)->getType(), UsedType, *TD))
1152         return 0;
1153       continue;
1154     }
1155     if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) {
1156       IsNotTrivial = true;
1157       const Type *SubTy = CanConvertToScalar(CI, IsNotTrivial);
1158       if (!SubTy || MergeInType(SubTy, UsedType, *TD)) return 0;
1159       continue;
1160     }
1161
1162     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
1163       // Check to see if this is stepping over an element: GEP Ptr, int C
1164       if (GEP->getNumOperands() == 2 && isa<ConstantInt>(GEP->getOperand(1))) {
1165         unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getZExtValue();
1166         unsigned ElSize = TD->getABITypeSize(PTy->getElementType());
1167         unsigned BitOffset = Idx*ElSize*8;
1168         if (BitOffset > 64 || !isPowerOf2_32(ElSize)) return 0;
1169
1170         IsNotTrivial = true;
1171         const Type *SubElt = CanConvertToScalar(GEP, IsNotTrivial);
1172         if (SubElt == 0) return 0;
1173         if (SubElt != Type::VoidTy && SubElt->isInteger()) {
1174           const Type *NewTy =
1175             getIntAtLeastAsBigAs(TD->getABITypeSizeInBits(SubElt)+BitOffset);
1176           if (NewTy == 0 || MergeInType(NewTy, UsedType, *TD)) return 0;
1177           continue;
1178         }
1179         // Cannot handle this!
1180         return 0;
1181       }
1182
1183       if (GEP->getNumOperands() == 3 &&
1184           isa<ConstantInt>(GEP->getOperand(1)) &&
1185           isa<ConstantInt>(GEP->getOperand(2)) &&
1186           cast<ConstantInt>(GEP->getOperand(1))->isZero()) {
1187         // We are stepping into an element, e.g. a structure or an array:
1188         // GEP Ptr, i32 0, i32 Cst
1189         const Type *AggTy = PTy->getElementType();
1190         unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
1191
1192         if (const ArrayType *ATy = dyn_cast<ArrayType>(AggTy)) {
1193           if (Idx >= ATy->getNumElements()) return 0;  // Out of range.
1194         } else if (const VectorType *VectorTy = dyn_cast<VectorType>(AggTy)) {
1195           // Getting an element of the vector.
1196           if (Idx >= VectorTy->getNumElements()) return 0;  // Out of range.
1197
1198           // Merge in the vector type.
1199           if (MergeInType(VectorTy, UsedType, *TD)) return 0;
1200
1201           const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial);
1202           if (SubTy == 0) return 0;
1203
1204           if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType, *TD))
1205             return 0;
1206
1207           // We'll need to change this to an insert/extract element operation.
1208           IsNotTrivial = true;
1209           continue;    // Everything looks ok
1210
1211         } else if (isa<StructType>(AggTy)) {
1212           // Structs are always ok.
1213         } else {
1214           return 0;
1215         }
1216         const Type *NTy = getIntAtLeastAsBigAs(TD->getABITypeSizeInBits(AggTy));
1217         if (NTy == 0 || MergeInType(NTy, UsedType, *TD)) return 0;
1218         const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial);
1219         if (SubTy == 0) return 0;
1220         if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType, *TD))
1221           return 0;
1222         continue;    // Everything looks ok
1223       }
1224       return 0;
1225     }
1226
1227     // Cannot handle this!
1228     return 0;
1229   }
1230
1231   return UsedType;
1232 }
1233
1234 /// ConvertToScalar - The specified alloca passes the CanConvertToScalar
1235 /// predicate and is non-trivial.  Convert it to something that can be trivially
1236 /// promoted into a register by mem2reg.
1237 void SROA::ConvertToScalar(AllocationInst *AI, const Type *ActualTy) {
1238   DOUT << "CONVERT TO SCALAR: " << *AI << "  TYPE = "
1239        << *ActualTy << "\n";
1240   ++NumConverted;
1241
1242   BasicBlock *EntryBlock = AI->getParent();
1243   assert(EntryBlock == &EntryBlock->getParent()->getEntryBlock() &&
1244          "Not in the entry block!");
1245   EntryBlock->getInstList().remove(AI);  // Take the alloca out of the program.
1246
1247   // Create and insert the alloca.
1248   AllocaInst *NewAI = new AllocaInst(ActualTy, 0, AI->getName(),
1249                                      EntryBlock->begin());
1250   ConvertUsesToScalar(AI, NewAI, 0);
1251   delete AI;
1252 }
1253
1254
1255 /// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca
1256 /// directly.  This happens when we are converting an "integer union" to a
1257 /// single integer scalar, or when we are converting a "vector union" to a
1258 /// vector with insert/extractelement instructions.
1259 ///
1260 /// Offset is an offset from the original alloca, in bits that need to be
1261 /// shifted to the right.  By the end of this, there should be no uses of Ptr.
1262 void SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset) {
1263   while (!Ptr->use_empty()) {
1264     Instruction *User = cast<Instruction>(Ptr->use_back());
1265
1266     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
1267       Value *NV = ConvertUsesOfLoadToScalar(LI, NewAI, Offset);
1268       LI->replaceAllUsesWith(NV);
1269       LI->eraseFromParent();
1270       continue;
1271     }
1272
1273     if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
1274       assert(SI->getOperand(0) != Ptr && "Consistency error!");
1275
1276       Value *SV = ConvertUsesOfStoreToScalar(SI, NewAI, Offset);
1277       new StoreInst(SV, NewAI, SI);
1278       SI->eraseFromParent();
1279       continue;
1280     }
1281
1282     if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) {
1283       ConvertUsesToScalar(CI, NewAI, Offset);
1284       CI->eraseFromParent();
1285       continue;
1286     }
1287
1288     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
1289       const PointerType *AggPtrTy =
1290         cast<PointerType>(GEP->getOperand(0)->getType());
1291       unsigned AggSizeInBits =
1292         TD->getABITypeSizeInBits(AggPtrTy->getElementType());
1293
1294       // Check to see if this is stepping over an element: GEP Ptr, int C
1295       unsigned NewOffset = Offset;
1296       if (GEP->getNumOperands() == 2) {
1297         unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getZExtValue();
1298         unsigned BitOffset = Idx*AggSizeInBits;
1299
1300         NewOffset += BitOffset;
1301         ConvertUsesToScalar(GEP, NewAI, NewOffset);
1302         GEP->eraseFromParent();
1303         continue;
1304       }
1305
1306       assert(GEP->getNumOperands() == 3 && "Unsupported operation");
1307
1308       // We know that operand #2 is zero.
1309       unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
1310       const Type *AggTy = AggPtrTy->getElementType();
1311       if (const SequentialType *SeqTy = dyn_cast<SequentialType>(AggTy)) {
1312         unsigned ElSizeBits =
1313           TD->getABITypeSizeInBits(SeqTy->getElementType());
1314
1315         NewOffset += ElSizeBits*Idx;
1316       } else {
1317         const StructType *STy = cast<StructType>(AggTy);
1318         unsigned EltBitOffset =
1319           TD->getStructLayout(STy)->getElementOffsetInBits(Idx);
1320
1321         NewOffset += EltBitOffset;
1322       }
1323       ConvertUsesToScalar(GEP, NewAI, NewOffset);
1324       GEP->eraseFromParent();
1325       continue;
1326     }
1327
1328     assert(0 && "Unsupported operation!");
1329     abort();
1330   }
1331 }
1332
1333 /// ConvertUsesOfLoadToScalar - Convert all of the users the specified load to
1334 /// use the new alloca directly, returning the value that should replace the
1335 /// load.  This happens when we are converting an "integer union" to a
1336 /// single integer scalar, or when we are converting a "vector union" to a
1337 /// vector with insert/extractelement instructions.
1338 ///
1339 /// Offset is an offset from the original alloca, in bits that need to be
1340 /// shifted to the right.  By the end of this, there should be no uses of Ptr.
1341 Value *SROA::ConvertUsesOfLoadToScalar(LoadInst *LI, AllocaInst *NewAI,
1342                                        unsigned Offset) {
1343   // The load is a bit extract from NewAI shifted right by Offset bits.
1344   Value *NV = new LoadInst(NewAI, LI->getName(), LI);
1345
1346   if (NV->getType() == LI->getType() && Offset == 0) {
1347     // We win, no conversion needed.
1348     return NV;
1349   }
1350
1351   // If the result type of the 'union' is a pointer, then this must be ptr->ptr
1352   // cast.  Anything else would result in NV being an integer.
1353   if (isa<PointerType>(NV->getType())) {
1354     assert(isa<PointerType>(LI->getType()));
1355     return new BitCastInst(NV, LI->getType(), LI->getName(), LI);
1356   }
1357
1358   if (const VectorType *VTy = dyn_cast<VectorType>(NV->getType())) {
1359     // If the result alloca is a vector type, this is either an element
1360     // access or a bitcast to another vector type.
1361     if (isa<VectorType>(LI->getType()))
1362       return new BitCastInst(NV, LI->getType(), LI->getName(), LI);
1363
1364     // Otherwise it must be an element access.
1365     unsigned Elt = 0;
1366     if (Offset) {
1367       unsigned EltSize = TD->getABITypeSizeInBits(VTy->getElementType());
1368       Elt = Offset/EltSize;
1369       Offset -= EltSize*Elt;
1370     }
1371     NV = new ExtractElementInst(NV, ConstantInt::get(Type::Int32Ty, Elt),
1372                                 "tmp", LI);
1373
1374     // If we're done, return this element.
1375     if (NV->getType() == LI->getType() && Offset == 0)
1376       return NV;
1377   }
1378
1379   const IntegerType *NTy = cast<IntegerType>(NV->getType());
1380
1381   // If this is a big-endian system and the load is narrower than the
1382   // full alloca type, we need to do a shift to get the right bits.
1383   int ShAmt = 0;
1384   if (TD->isBigEndian()) {
1385     // On big-endian machines, the lowest bit is stored at the bit offset
1386     // from the pointer given by getTypeStoreSizeInBits.  This matters for
1387     // integers with a bitwidth that is not a multiple of 8.
1388     ShAmt = TD->getTypeStoreSizeInBits(NTy) -
1389             TD->getTypeStoreSizeInBits(LI->getType()) - Offset;
1390   } else {
1391     ShAmt = Offset;
1392   }
1393
1394   // Note: we support negative bitwidths (with shl) which are not defined.
1395   // We do this to support (f.e.) loads off the end of a structure where
1396   // only some bits are used.
1397   if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth())
1398     NV = BinaryOperator::CreateLShr(NV,
1399                                     ConstantInt::get(NV->getType(),ShAmt),
1400                                     LI->getName(), LI);
1401   else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth())
1402     NV = BinaryOperator::CreateShl(NV,
1403                                    ConstantInt::get(NV->getType(),-ShAmt),
1404                                    LI->getName(), LI);
1405
1406   // Finally, unconditionally truncate the integer to the right width.
1407   unsigned LIBitWidth = TD->getTypeSizeInBits(LI->getType());
1408   if (LIBitWidth < NTy->getBitWidth())
1409     NV = new TruncInst(NV, IntegerType::get(LIBitWidth),
1410                        LI->getName(), LI);
1411
1412   // If the result is an integer, this is a trunc or bitcast.
1413   if (isa<IntegerType>(LI->getType())) {
1414     // Should be done.
1415   } else if (LI->getType()->isFloatingPoint()) {
1416     // Just do a bitcast, we know the sizes match up.
1417     NV = new BitCastInst(NV, LI->getType(), LI->getName(), LI);
1418   } else {
1419     // Otherwise must be a pointer.
1420     NV = new IntToPtrInst(NV, LI->getType(), LI->getName(), LI);
1421   }
1422   assert(NV->getType() == LI->getType() && "Didn't convert right?");
1423   return NV;
1424 }
1425
1426
1427 /// ConvertUsesOfStoreToScalar - Convert the specified store to a load+store
1428 /// pair of the new alloca directly, returning the value that should be stored
1429 /// to the alloca.  This happens when we are converting an "integer union" to a
1430 /// single integer scalar, or when we are converting a "vector union" to a
1431 /// vector with insert/extractelement instructions.
1432 ///
1433 /// Offset is an offset from the original alloca, in bits that need to be
1434 /// shifted to the right.  By the end of this, there should be no uses of Ptr.
1435 Value *SROA::ConvertUsesOfStoreToScalar(StoreInst *SI, AllocaInst *NewAI,
1436                                         unsigned Offset) {
1437
1438   // Convert the stored type to the actual type, shift it left to insert
1439   // then 'or' into place.
1440   Value *SV = SI->getOperand(0);
1441   const Type *AllocaType = NewAI->getType()->getElementType();
1442   if (SV->getType() == AllocaType && Offset == 0) {
1443     // All is well.
1444   } else if (const VectorType *PTy = dyn_cast<VectorType>(AllocaType)) {
1445     Value *Old = new LoadInst(NewAI, NewAI->getName()+".in", SI);
1446
1447     // If the result alloca is a vector type, this is either an element
1448     // access or a bitcast to another vector type.
1449     if (isa<VectorType>(SV->getType())) {
1450       SV = new BitCastInst(SV, AllocaType, SV->getName(), SI);
1451     } else {
1452       // Must be an element insertion.
1453       unsigned Elt = Offset/TD->getABITypeSizeInBits(PTy->getElementType());
1454       SV = InsertElementInst::Create(Old, SV,
1455                                      ConstantInt::get(Type::Int32Ty, Elt),
1456                                      "tmp", SI);
1457     }
1458   } else if (isa<PointerType>(AllocaType)) {
1459     // If the alloca type is a pointer, then all the elements must be
1460     // pointers.
1461     if (SV->getType() != AllocaType)
1462       SV = new BitCastInst(SV, AllocaType, SV->getName(), SI);
1463   } else {
1464     Value *Old = new LoadInst(NewAI, NewAI->getName()+".in", SI);
1465
1466     // If SV is a float, convert it to the appropriate integer type.
1467     // If it is a pointer, do the same, and also handle ptr->ptr casts
1468     // here.
1469     unsigned SrcWidth = TD->getTypeSizeInBits(SV->getType());
1470     unsigned DestWidth = TD->getTypeSizeInBits(AllocaType);
1471     unsigned SrcStoreWidth = TD->getTypeStoreSizeInBits(SV->getType());
1472     unsigned DestStoreWidth = TD->getTypeStoreSizeInBits(AllocaType);
1473     if (SV->getType()->isFloatingPoint())
1474       SV = new BitCastInst(SV, IntegerType::get(SrcWidth),
1475                            SV->getName(), SI);
1476     else if (isa<PointerType>(SV->getType()))
1477       SV = new PtrToIntInst(SV, TD->getIntPtrType(), SV->getName(), SI);
1478
1479     // Always zero extend the value if needed.
1480     if (SV->getType() != AllocaType)
1481       SV = new ZExtInst(SV, AllocaType, SV->getName(), SI);
1482
1483     // If this is a big-endian system and the store is narrower than the
1484     // full alloca type, we need to do a shift to get the right bits.
1485     int ShAmt = 0;
1486     if (TD->isBigEndian()) {
1487       // On big-endian machines, the lowest bit is stored at the bit offset
1488       // from the pointer given by getTypeStoreSizeInBits.  This matters for
1489       // integers with a bitwidth that is not a multiple of 8.
1490       ShAmt = DestStoreWidth - SrcStoreWidth - Offset;
1491     } else {
1492       ShAmt = Offset;
1493     }
1494
1495     // Note: we support negative bitwidths (with shr) which are not defined.
1496     // We do this to support (f.e.) stores off the end of a structure where
1497     // only some bits in the structure are set.
1498     APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth));
1499     if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) {
1500       SV = BinaryOperator::CreateShl(SV,
1501                                      ConstantInt::get(SV->getType(), ShAmt),
1502                                      SV->getName(), SI);
1503       Mask <<= ShAmt;
1504     } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) {
1505       SV = BinaryOperator::CreateLShr(SV,
1506                                       ConstantInt::get(SV->getType(),-ShAmt),
1507                                       SV->getName(), SI);
1508       Mask = Mask.lshr(ShAmt);
1509     }
1510
1511     // Mask out the bits we are about to insert from the old value, and or
1512     // in the new bits.
1513     if (SrcWidth != DestWidth) {
1514       assert(DestWidth > SrcWidth);
1515       Old = BinaryOperator::CreateAnd(Old, ConstantInt::get(~Mask),
1516                                       Old->getName()+".mask", SI);
1517       SV = BinaryOperator::CreateOr(Old, SV, SV->getName()+".ins", SI);
1518     }
1519   }
1520   return SV;
1521 }
1522
1523
1524
1525 /// PointsToConstantGlobal - Return true if V (possibly indirectly) points to
1526 /// some part of a constant global variable.  This intentionally only accepts
1527 /// constant expressions because we don't can't rewrite arbitrary instructions.
1528 static bool PointsToConstantGlobal(Value *V) {
1529   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
1530     return GV->isConstant();
1531   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
1532     if (CE->getOpcode() == Instruction::BitCast ||
1533         CE->getOpcode() == Instruction::GetElementPtr)
1534       return PointsToConstantGlobal(CE->getOperand(0));
1535   return false;
1536 }
1537
1538 /// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived)
1539 /// pointer to an alloca.  Ignore any reads of the pointer, return false if we
1540 /// see any stores or other unknown uses.  If we see pointer arithmetic, keep
1541 /// track of whether it moves the pointer (with isOffset) but otherwise traverse
1542 /// the uses.  If we see a memcpy/memmove that targets an unoffseted pointer to
1543 /// the alloca, and if the source pointer is a pointer to a constant  global, we
1544 /// can optimize this.
1545 static bool isOnlyCopiedFromConstantGlobal(Value *V, Instruction *&TheCopy,
1546                                            bool isOffset) {
1547   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
1548     if (isa<LoadInst>(*UI)) {
1549       // Ignore loads, they are always ok.
1550       continue;
1551     }
1552     if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) {
1553       // If uses of the bitcast are ok, we are ok.
1554       if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset))
1555         return false;
1556       continue;
1557     }
1558     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
1559       // If the GEP has all zero indices, it doesn't offset the pointer.  If it
1560       // doesn't, it does.
1561       if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy,
1562                                          isOffset || !GEP->hasAllZeroIndices()))
1563         return false;
1564       continue;
1565     }
1566
1567     // If this is isn't our memcpy/memmove, reject it as something we can't
1568     // handle.
1569     if (!isa<MemCpyInst>(*UI) && !isa<MemMoveInst>(*UI))
1570       return false;
1571
1572     // If we already have seen a copy, reject the second one.
1573     if (TheCopy) return false;
1574
1575     // If the pointer has been offset from the start of the alloca, we can't
1576     // safely handle this.
1577     if (isOffset) return false;
1578
1579     // If the memintrinsic isn't using the alloca as the dest, reject it.
1580     if (UI.getOperandNo() != 1) return false;
1581
1582     MemIntrinsic *MI = cast<MemIntrinsic>(*UI);
1583
1584     // If the source of the memcpy/move is not a constant global, reject it.
1585     if (!PointsToConstantGlobal(MI->getOperand(2)))
1586       return false;
1587
1588     // Otherwise, the transform is safe.  Remember the copy instruction.
1589     TheCopy = MI;
1590   }
1591   return true;
1592 }
1593
1594 /// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only
1595 /// modified by a copy from a constant global.  If we can prove this, we can
1596 /// replace any uses of the alloca with uses of the global directly.
1597 Instruction *SROA::isOnlyCopiedFromConstantGlobal(AllocationInst *AI) {
1598   Instruction *TheCopy = 0;
1599   if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false))
1600     return TheCopy;
1601   return 0;
1602 }