lib/Transforms/Scalar/ScalarReplAggregates.cpp

   1 //===- ScalarReplAggregates.cpp - Scalar Replacement of Aggregates --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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     bool runOnFunction(Function &F);
  51
  52     bool performScalarRepl(Function &F);
  53     bool performPromotion(Function &F);
  54
  55     // getAnalysisUsage - This pass does not require any passes, but we know it
  56     // will not alter the CFG, so say so.
  57     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  58       AU.addRequired<ETForest>();
  59       AU.addRequired<DominanceFrontier>();
  60       AU.addRequired<TargetData>();
  61       AU.setPreservesCFG();
  62     }
  63
  64   private:
  65     int isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI);
  66     int isSafeUseOfAllocation(Instruction *User, AllocationInst *AI);
  67     bool isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI);
  68     bool isSafeUseOfBitCastedAllocation(BitCastInst *User, AllocationInst *AI);
  69     int isSafeAllocaToScalarRepl(AllocationInst *AI);
  70     void DoScalarReplacement(AllocationInst *AI,
  71                              std::vector<AllocationInst*> &WorkList);
  72     void CanonicalizeAllocaUsers(AllocationInst *AI);
  73     AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocationInst *Base);
  74
  75     void RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI,
  76                                     SmallVector<AllocaInst*, 32> &NewElts);
  77
  78     const Type *CanConvertToScalar(Value *V, bool &IsNotTrivial);
  79     void ConvertToScalar(AllocationInst *AI, const Type *Ty);
  80     void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset);
  81     static Instruction *isOnlyCopiedFromConstantGlobal(AllocationInst *AI);
  82   };
  83
  84   RegisterPass<SROA> X("scalarrepl", "Scalar Replacement of Aggregates");
  85 }
  86
  87 // Public interface to the ScalarReplAggregates pass
  88 FunctionPass *llvm::createScalarReplAggregatesPass() { return new SROA(); }
  89
  90
  91 bool SROA::runOnFunction(Function &F) {
  92   bool Changed = performPromotion(F);
  93   while (1) {
  94     bool LocalChange = performScalarRepl(F);
  95     if (!LocalChange) break;   // No need to repromote if no scalarrepl
  96     Changed = true;
  97     LocalChange = performPromotion(F);
  98     if (!LocalChange) break;   // No need to re-scalarrepl if no promotion
  99   }
 100
 101   return Changed;
 102 }
 103
 104
 105 bool SROA::performPromotion(Function &F) {
 106   std::vector<AllocaInst*> Allocas;
 107   ETForest         &ET = getAnalysis<ETForest>();
 108   DominanceFrontier &DF = getAnalysis<DominanceFrontier>();
 109
 110   BasicBlock &BB = F.getEntryBlock();  // Get the entry node for the function
 111
 112   bool Changed = false;
 113
 114   while (1) {
 115     Allocas.clear();
 116
 117     // Find allocas that are safe to promote, by looking at all instructions in
 118     // the entry node
 119     for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
 120       if (AllocaInst *AI = dyn_cast<AllocaInst>(I))       // Is it an alloca?
 121         if (isAllocaPromotable(AI))
 122           Allocas.push_back(AI);
 123
 124     if (Allocas.empty()) break;
 125
 126     PromoteMemToReg(Allocas, ET, DF);
 127     NumPromoted += Allocas.size();
 128     Changed = true;
 129   }
 130
 131   return Changed;
 132 }
 133
 134 // performScalarRepl - This algorithm is a simple worklist driven algorithm,
 135 // which runs on all of the malloc/alloca instructions in the function, removing
 136 // them if they are only used by getelementptr instructions.
 137 //
 138 bool SROA::performScalarRepl(Function &F) {
 139   std::vector<AllocationInst*> WorkList;
 140
 141   // Scan the entry basic block, adding any alloca's and mallocs to the worklist
 142   BasicBlock &BB = F.getEntryBlock();
 143   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
 144     if (AllocationInst *A = dyn_cast<AllocationInst>(I))
 145       WorkList.push_back(A);
 146
 147   // Process the worklist
 148   bool Changed = false;
 149   while (!WorkList.empty()) {
 150     AllocationInst *AI = WorkList.back();
 151     WorkList.pop_back();
 152
 153     // Handle dead allocas trivially.  These can be formed by SROA'ing arrays
 154     // with unused elements.
 155     if (AI->use_empty()) {
 156       AI->eraseFromParent();
 157       continue;
 158     }
 159
 160     // If we can turn this aggregate value (potentially with casts) into a
 161     // simple scalar value that can be mem2reg'd into a register value.
 162     bool IsNotTrivial = false;
 163     if (const Type *ActualType = CanConvertToScalar(AI, IsNotTrivial))
 164       if (IsNotTrivial && ActualType != Type::VoidTy) {
 165         ConvertToScalar(AI, ActualType);
 166         Changed = true;
 167         continue;
 168       }
 169
 170     // Check to see if we can perform the core SROA transformation.  We cannot
 171     // transform the allocation instruction if it is an array allocation
 172     // (allocations OF arrays are ok though), and an allocation of a scalar
 173     // value cannot be decomposed at all.
 174     if (!AI->isArrayAllocation() &&
 175         (isa<StructType>(AI->getAllocatedType()) ||
 176          isa<ArrayType>(AI->getAllocatedType()))) {
 177       // Check that all of the users of the allocation are capable of being
 178       // transformed.
 179       switch (isSafeAllocaToScalarRepl(AI)) {
 180       default: assert(0 && "Unexpected value!");
 181       case 0:  // Not safe to scalar replace.
 182         break;
 183       case 1:  // Safe, but requires cleanup/canonicalizations first
 184         CanonicalizeAllocaUsers(AI);
 185         // FALL THROUGH.
 186       case 3:  // Safe to scalar replace.
 187         DoScalarReplacement(AI, WorkList);
 188         Changed = true;
 189         continue;
 190       }
 191     }
 192
 193     // Check to see if this allocation is only modified by a memcpy/memmove from
 194     // a constant global.  If this is the case, we can change all users to use
 195     // the constant global instead.  This is commonly produced by the CFE by
 196     // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A'
 197     // is only subsequently read.
 198     if (Instruction *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) {
 199       DOUT << "Found alloca equal to global: " << *AI;
 200       DOUT << "  memcpy = " << *TheCopy;
 201       Constant *TheSrc = cast<Constant>(TheCopy->getOperand(2));
 202       AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType()));
 203       TheCopy->eraseFromParent();  // Don't mutate the global.
 204       AI->eraseFromParent();
 205       ++NumGlobals;
 206       Changed = true;
 207       continue;
 208     }
 209
 210     // Otherwise, couldn't process this.
 211   }
 212
 213   return Changed;
 214 }
 215
 216 /// DoScalarReplacement - This alloca satisfied the isSafeAllocaToScalarRepl
 217 /// predicate, do SROA now.
 218 void SROA::DoScalarReplacement(AllocationInst *AI,
 219                                std::vector<AllocationInst*> &WorkList) {
 220   DOUT << "Found inst to SROA: " << *AI;
 221   SmallVector<AllocaInst*, 32> ElementAllocas;
 222   if (const StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) {
 223     ElementAllocas.reserve(ST->getNumContainedTypes());
 224     for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) {
 225       AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0,
 226                                       AI->getAlignment(),
 227                                       AI->getName() + "." + utostr(i), AI);
 228       ElementAllocas.push_back(NA);
 229       WorkList.push_back(NA);  // Add to worklist for recursive processing
 230     }
 231   } else {
 232     const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
 233     ElementAllocas.reserve(AT->getNumElements());
 234     const Type *ElTy = AT->getElementType();
 235     for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
 236       AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(),
 237                                       AI->getName() + "." + utostr(i), AI);
 238       ElementAllocas.push_back(NA);
 239       WorkList.push_back(NA);  // Add to worklist for recursive processing
 240     }
 241   }
 242
 243   // Now that we have created the alloca instructions that we want to use,
 244   // expand the getelementptr instructions to use them.
 245   //
 246   while (!AI->use_empty()) {
 247     Instruction *User = cast<Instruction>(AI->use_back());
 248     if (BitCastInst *BCInst = dyn_cast<BitCastInst>(User)) {
 249       RewriteBitCastUserOfAlloca(BCInst, AI, ElementAllocas);
 250       BCInst->eraseFromParent();
 251       continue;
 252     }
 253
 254     GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User);
 255     // We now know that the GEP is of the form: GEP <ptr>, 0, <cst>
 256     unsigned Idx =
 257        (unsigned)cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue();
 258
 259     assert(Idx < ElementAllocas.size() && "Index out of range?");
 260     AllocaInst *AllocaToUse = ElementAllocas[Idx];
 261
 262     Value *RepValue;
 263     if (GEPI->getNumOperands() == 3) {
 264       // Do not insert a new getelementptr instruction with zero indices, only
 265       // to have it optimized out later.
 266       RepValue = AllocaToUse;
 267     } else {
 268       // We are indexing deeply into the structure, so we still need a
 269       // getelement ptr instruction to finish the indexing.  This may be
 270       // expanded itself once the worklist is rerun.
 271       //
 272       SmallVector<Value*, 8> NewArgs;
 273       NewArgs.push_back(Constant::getNullValue(Type::Int32Ty));
 274       NewArgs.append(GEPI->op_begin()+3, GEPI->op_end());
 275       RepValue = new GetElementPtrInst(AllocaToUse, &NewArgs[0],
 276                                        NewArgs.size(), "", GEPI);
 277       RepValue->takeName(GEPI);
 278     }
 279
 280     // If this GEP is to the start of the aggregate, check for memcpys.
 281     if (Idx == 0) {
 282       bool IsStartOfAggregateGEP = true;
 283       for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i) {
 284         if (!isa<ConstantInt>(GEPI->getOperand(i))) {
 285           IsStartOfAggregateGEP = false;
 286           break;
 287         }
 288         if (!cast<ConstantInt>(GEPI->getOperand(i))->isZero()) {
 289           IsStartOfAggregateGEP = false;
 290           break;
 291         }
 292       }
 293
 294       if (IsStartOfAggregateGEP)
 295         RewriteBitCastUserOfAlloca(GEPI, AI, ElementAllocas);
 296     }
 297
 298
 299     // Move all of the users over to the new GEP.
 300     GEPI->replaceAllUsesWith(RepValue);
 301     // Delete the old GEP
 302     GEPI->eraseFromParent();
 303   }
 304
 305   // Finally, delete the Alloca instruction
 306   AI->eraseFromParent();
 307   NumReplaced++;
 308 }
 309
 310
 311 /// isSafeElementUse - Check to see if this use is an allowed use for a
 312 /// getelementptr instruction of an array aggregate allocation.  isFirstElt
 313 /// indicates whether Ptr is known to the start of the aggregate.
 314 ///
 315 int SROA::isSafeElementUse(Value *Ptr, bool isFirstElt, AllocationInst *AI) {
 316   for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end();
 317        I != E; ++I) {
 318     Instruction *User = cast<Instruction>(*I);
 319     switch (User->getOpcode()) {
 320     case Instruction::Load:  break;
 321     case Instruction::Store:
 322       // Store is ok if storing INTO the pointer, not storing the pointer
 323       if (User->getOperand(0) == Ptr) return 0;
 324       break;
 325     case Instruction::GetElementPtr: {
 326       GetElementPtrInst *GEP = cast<GetElementPtrInst>(User);
 327       bool AreAllZeroIndices = isFirstElt;
 328       if (GEP->getNumOperands() > 1) {
 329         if (!isa<ConstantInt>(GEP->getOperand(1)) ||
 330             !cast<ConstantInt>(GEP->getOperand(1))->isZero())
 331           return 0;  // Using pointer arithmetic to navigate the array.
 332
 333         if (AreAllZeroIndices) {
 334           for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) {
 335             if (!isa<ConstantInt>(GEP->getOperand(i)) ||
 336                 !cast<ConstantInt>(GEP->getOperand(i))->isZero()) {
 337               AreAllZeroIndices = false;
 338               break;
 339             }
 340           }
 341         }
 342       }
 343       if (!isSafeElementUse(GEP, AreAllZeroIndices, AI)) return 0;
 344       break;
 345     }
 346     case Instruction::BitCast:
 347       if (isFirstElt &&
 348           isSafeUseOfBitCastedAllocation(cast<BitCastInst>(User), AI))
 349         break;
 350       DOUT << "  Transformation preventing inst: " << *User;
 351       return 0;
 352     case Instruction::Call:
 353       if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) {
 354         if (isFirstElt && isSafeMemIntrinsicOnAllocation(MI, AI))
 355           break;
 356       }
 357       DOUT << "  Transformation preventing inst: " << *User;
 358       return 0;
 359     default:
 360       DOUT << "  Transformation preventing inst: " << *User;
 361       return 0;
 362     }
 363   }
 364   return 3;  // All users look ok :)
 365 }
 366
 367 /// AllUsersAreLoads - Return true if all users of this value are loads.
 368 static bool AllUsersAreLoads(Value *Ptr) {
 369   for (Value::use_iterator I = Ptr->use_begin(), E = Ptr->use_end();
 370        I != E; ++I)
 371     if (cast<Instruction>(*I)->getOpcode() != Instruction::Load)
 372       return false;
 373   return true;
 374 }
 375
 376 /// isSafeUseOfAllocation - Check to see if this user is an allowed use for an
 377 /// aggregate allocation.
 378 ///
 379 int SROA::isSafeUseOfAllocation(Instruction *User, AllocationInst *AI) {
 380   if (BitCastInst *C = dyn_cast<BitCastInst>(User))
 381     return isSafeUseOfBitCastedAllocation(C, AI) ? 3 : 0;
 382   if (!isa<GetElementPtrInst>(User)) return 0;
 383
 384   GetElementPtrInst *GEPI = cast<GetElementPtrInst>(User);
 385   gep_type_iterator I = gep_type_begin(GEPI), E = gep_type_end(GEPI);
 386
 387   // The GEP is not safe to transform if not of the form "GEP <ptr>, 0, <cst>".
 388   if (I == E ||
 389       I.getOperand() != Constant::getNullValue(I.getOperand()->getType()))
 390     return 0;
 391
 392   ++I;
 393   if (I == E) return 0;  // ran out of GEP indices??
 394
 395   bool IsAllZeroIndices = true;
 396
 397   // If this is a use of an array allocation, do a bit more checking for sanity.
 398   if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) {
 399     uint64_t NumElements = AT->getNumElements();
 400
 401     if (ConstantInt *Idx = dyn_cast<ConstantInt>(I.getOperand())) {
 402       IsAllZeroIndices &= Idx->isZero();
 403
 404       // Check to make sure that index falls within the array.  If not,
 405       // something funny is going on, so we won't do the optimization.
 406       //
 407       if (Idx->getZExtValue() >= NumElements)
 408         return 0;
 409
 410       // We cannot scalar repl this level of the array unless any array
 411       // sub-indices are in-range constants.  In particular, consider:
 412       // A[0][i].  We cannot know that the user isn't doing invalid things like
 413       // allowing i to index an out-of-range subscript that accesses A[1].
 414       //
 415       // Scalar replacing *just* the outer index of the array is probably not
 416       // going to be a win anyway, so just give up.
 417       for (++I; I != E && (isa<ArrayType>(*I) || isa<VectorType>(*I)); ++I) {
 418         uint64_t NumElements;
 419         if (const ArrayType *SubArrayTy = dyn_cast<ArrayType>(*I))
 420           NumElements = SubArrayTy->getNumElements();
 421         else
 422           NumElements = cast<VectorType>(*I)->getNumElements();
 423
 424         ConstantInt *IdxVal = dyn_cast<ConstantInt>(I.getOperand());
 425         if (!IdxVal) return 0;
 426         if (IdxVal->getZExtValue() >= NumElements)
 427           return 0;
 428         IsAllZeroIndices &= IdxVal->isZero();
 429       }
 430
 431     } else {
 432       IsAllZeroIndices = 0;
 433
 434       // If this is an array index and the index is not constant, we cannot
 435       // promote... that is unless the array has exactly one or two elements in
 436       // it, in which case we CAN promote it, but we have to canonicalize this
 437       // out if this is the only problem.
 438       if ((NumElements == 1 || NumElements == 2) &&
 439           AllUsersAreLoads(GEPI))
 440         return 1;  // Canonicalization required!
 441       return 0;
 442     }
 443   }
 444
 445   // If there are any non-simple uses of this getelementptr, make sure to reject
 446   // them.
 447   return isSafeElementUse(GEPI, IsAllZeroIndices, AI);
 448 }
 449
 450 /// isSafeMemIntrinsicOnAllocation - Return true if the specified memory
 451 /// intrinsic can be promoted by SROA.  At this point, we know that the operand
 452 /// of the memintrinsic is a pointer to the beginning of the allocation.
 453 bool SROA::isSafeMemIntrinsicOnAllocation(MemIntrinsic *MI, AllocationInst *AI){
 454   // If not constant length, give up.
 455   ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
 456   if (!Length) return false;
 457
 458   // If not the whole aggregate, give up.
 459   const TargetData &TD = getAnalysis<TargetData>();
 460   if (Length->getZExtValue() != TD.getTypeSize(AI->getType()->getElementType()))
 461     return false;
 462
 463   // We only know about memcpy/memset/memmove.
 464   if (!isa<MemCpyInst>(MI) && !isa<MemSetInst>(MI) && !isa<MemMoveInst>(MI))
 465     return false;
 466   // Otherwise, we can transform it.
 467   return true;
 468 }
 469
 470 /// isSafeUseOfBitCastedAllocation - Return true if all users of this bitcast
 471 /// are
 472 bool SROA::isSafeUseOfBitCastedAllocation(BitCastInst *BC, AllocationInst *AI) {
 473   for (Value::use_iterator UI = BC->use_begin(), E = BC->use_end();
 474        UI != E; ++UI) {
 475     if (BitCastInst *BCU = dyn_cast<BitCastInst>(UI)) {
 476       if (!isSafeUseOfBitCastedAllocation(BCU, AI))
 477         return false;
 478     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(UI)) {
 479       if (!isSafeMemIntrinsicOnAllocation(MI, AI))
 480         return false;
 481     } else {
 482       return false;
 483     }
 484   }
 485   return true;
 486 }
 487
 488 /// RewriteBitCastUserOfAlloca - BCInst (transitively) bitcasts AI, or indexes
 489 /// to its first element.  Transform users of the cast to use the new values
 490 /// instead.
 491 void SROA::RewriteBitCastUserOfAlloca(Instruction *BCInst, AllocationInst *AI,
 492                                       SmallVector<AllocaInst*, 32> &NewElts) {
 493   Constant *Zero = Constant::getNullValue(Type::Int32Ty);
 494   const TargetData &TD = getAnalysis<TargetData>();
 495
 496   Value::use_iterator UI = BCInst->use_begin(), UE = BCInst->use_end();
 497   while (UI != UE) {
 498     if (BitCastInst *BCU = dyn_cast<BitCastInst>(*UI)) {
 499       RewriteBitCastUserOfAlloca(BCU, AI, NewElts);
 500       ++UI;
 501       BCU->eraseFromParent();
 502       continue;
 503     }
 504
 505     // Otherwise, must be memcpy/memmove/memset of the entire aggregate.  Split
 506     // into one per element.
 507     MemIntrinsic *MI = dyn_cast<MemIntrinsic>(*UI);
 508
 509     // If it's not a mem intrinsic, it must be some other user of a gep of the
 510     // first pointer.  Just leave these alone.
 511     if (!MI) {
 512       ++UI;
 513       continue;
 514     }
 515
 516     // If this is a memcpy/memmove, construct the other pointer as the
 517     // appropriate type.
 518     Value *OtherPtr = 0;
 519     if (MemCpyInst *MCI = dyn_cast<MemCpyInst>(MI)) {
 520       if (BCInst == MCI->getRawDest())
 521         OtherPtr = MCI->getRawSource();
 522       else {
 523         assert(BCInst == MCI->getRawSource());
 524         OtherPtr = MCI->getRawDest();
 525       }
 526     } else if (MemMoveInst *MMI = dyn_cast<MemMoveInst>(MI)) {
 527       if (BCInst == MMI->getRawDest())
 528         OtherPtr = MMI->getRawSource();
 529       else {
 530         assert(BCInst == MMI->getRawSource());
 531         OtherPtr = MMI->getRawDest();
 532       }
 533     }
 534
 535     // If there is an other pointer, we want to convert it to the same pointer
 536     // type as AI has, so we can GEP through it.
 537     if (OtherPtr) {
 538       // It is likely that OtherPtr is a bitcast, if so, remove it.
 539       if (BitCastInst *BC = dyn_cast<BitCastInst>(OtherPtr))
 540         OtherPtr = BC->getOperand(0);
 541       if (ConstantExpr *BCE = dyn_cast<ConstantExpr>(OtherPtr))
 542         if (BCE->getOpcode() == Instruction::BitCast)
 543           OtherPtr = BCE->getOperand(0);
 544
 545       // If the pointer is not the right type, insert a bitcast to the right
 546       // type.
 547       if (OtherPtr->getType() != AI->getType())
 548         OtherPtr = new BitCastInst(OtherPtr, AI->getType(), OtherPtr->getName(),
 549                                    MI);
 550     }
 551
 552     // Process each element of the aggregate.
 553     Value *TheFn = MI->getOperand(0);
 554     const Type *BytePtrTy = MI->getRawDest()->getType();
 555     bool SROADest = MI->getRawDest() == BCInst;
 556
 557     for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
 558       // If this is a memcpy/memmove, emit a GEP of the other element address.
 559       Value *OtherElt = 0;
 560       if (OtherPtr) {
 561         OtherElt = new GetElementPtrInst(OtherPtr, Zero,
 562                                          ConstantInt::get(Type::Int32Ty, i),
 563                                          OtherPtr->getNameStr()+"."+utostr(i),
 564                                          MI);
 565       }
 566
 567       Value *EltPtr = NewElts[i];
 568       const Type *EltTy =cast<PointerType>(EltPtr->getType())->getElementType();
 569
 570       // If we got down to a scalar, insert a load or store as appropriate.
 571       if (EltTy->isFirstClassType()) {
 572         if (isa<MemCpyInst>(MI) || isa<MemMoveInst>(MI)) {
 573           Value *Elt = new LoadInst(SROADest ? OtherElt : EltPtr, "tmp",
 574                                     MI);
 575           new StoreInst(Elt, SROADest ? EltPtr : OtherElt, MI);
 576           continue;
 577         } else {
 578           assert(isa<MemSetInst>(MI));
 579
 580           // If the stored element is zero (common case), just store a null
 581           // constant.
 582           Constant *StoreVal;
 583           if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getOperand(2))) {
 584             if (CI->isZero()) {
 585               StoreVal = Constant::getNullValue(EltTy);  // 0.0, null, 0, <0,0>
 586             } else {
 587               // If EltTy is a packed type, get the element type.
 588               const Type *ValTy = EltTy;
 589               if (const VectorType *VTy = dyn_cast<VectorType>(ValTy))
 590                 ValTy = VTy->getElementType();
 591
 592               // Construct an integer with the right value.
 593               unsigned EltSize = TD.getTypeSize(ValTy);
 594               APInt OneVal(EltSize*8, CI->getZExtValue());
 595               APInt TotalVal(OneVal);
 596               // Set each byte.
 597               for (unsigned i = 0; i != EltSize-1; ++i) {
 598                 TotalVal = TotalVal.shl(8);
 599                 TotalVal |= OneVal;
 600               }
 601
 602               // Convert the integer value to the appropriate type.
 603               StoreVal = ConstantInt::get(TotalVal);
 604               if (isa<PointerType>(ValTy))
 605                 StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy);
 606               else if (ValTy->isFloatingPoint())
 607                 StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy);
 608               assert(StoreVal->getType() == ValTy && "Type mismatch!");
 609
 610               // If the requested value was a vector constant, create it.
 611               if (EltTy != ValTy) {
 612                 unsigned NumElts = cast<VectorType>(ValTy)->getNumElements();
 613                 SmallVector<Constant*, 16> Elts(NumElts, StoreVal);
 614                 StoreVal = ConstantVector::get(&Elts[0], NumElts);
 615               }
 616             }
 617             new StoreInst(StoreVal, EltPtr, MI);
 618             continue;
 619           }
 620           // Otherwise, if we're storing a byte variable, use a memset call for
 621           // this element.
 622         }
 623       }
 624
 625       // Cast the element pointer to BytePtrTy.
 626       if (EltPtr->getType() != BytePtrTy)
 627         EltPtr = new BitCastInst(EltPtr, BytePtrTy, EltPtr->getNameStr(), MI);
 628
 629       // Cast the other pointer (if we have one) to BytePtrTy.
 630       if (OtherElt && OtherElt->getType() != BytePtrTy)
 631         OtherElt = new BitCastInst(OtherElt, BytePtrTy,OtherElt->getNameStr(),
 632                                    MI);
 633
 634       unsigned EltSize = TD.getTypeSize(EltTy);
 635
 636       // Finally, insert the meminst for this element.
 637       if (isa<MemCpyInst>(MI) || isa<MemMoveInst>(MI)) {
 638         Value *Ops[] = {
 639           SROADest ? EltPtr : OtherElt,  // Dest ptr
 640           SROADest ? OtherElt : EltPtr,  // Src ptr
 641           ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size
 642           Zero  // Align
 643         };
 644         new CallInst(TheFn, Ops, 4, "", MI);
 645       } else {
 646         assert(isa<MemSetInst>(MI));
 647         Value *Ops[] = {
 648           EltPtr, MI->getOperand(2),  // Dest, Value,
 649           ConstantInt::get(MI->getOperand(3)->getType(), EltSize), // Size
 650           Zero  // Align
 651         };
 652         new CallInst(TheFn, Ops, 4, "", MI);
 653       }
 654     }
 655
 656     // Finally, MI is now dead, as we've modified its actions to occur on all of
 657     // the elements of the aggregate.
 658     ++UI;
 659     MI->eraseFromParent();
 660   }
 661 }
 662
 663
 664 /// isSafeStructAllocaToScalarRepl - Check to see if the specified allocation of
 665 /// an aggregate can be broken down into elements.  Return 0 if not, 3 if safe,
 666 /// or 1 if safe after canonicalization has been performed.
 667 ///
 668 int SROA::isSafeAllocaToScalarRepl(AllocationInst *AI) {
 669   // Loop over the use list of the alloca.  We can only transform it if all of
 670   // the users are safe to transform.
 671   //
 672   int isSafe = 3;
 673   for (Value::use_iterator I = AI->use_begin(), E = AI->use_end();
 674        I != E; ++I) {
 675     isSafe &= isSafeUseOfAllocation(cast<Instruction>(*I), AI);
 676     if (isSafe == 0) {
 677       DOUT << "Cannot transform: " << *AI << "  due to user: " << **I;
 678       return 0;
 679     }
 680   }
 681   // If we require cleanup, isSafe is now 1, otherwise it is 3.
 682   return isSafe;
 683 }
 684
 685 /// CanonicalizeAllocaUsers - If SROA reported that it can promote the specified
 686 /// allocation, but only if cleaned up, perform the cleanups required.
 687 void SROA::CanonicalizeAllocaUsers(AllocationInst *AI) {
 688   // At this point, we know that the end result will be SROA'd and promoted, so
 689   // we can insert ugly code if required so long as sroa+mem2reg will clean it
 690   // up.
 691   for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
 692        UI != E; ) {
 693     GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI++);
 694     if (!GEPI) continue;
 695     gep_type_iterator I = gep_type_begin(GEPI);
 696     ++I;
 697
 698     if (const ArrayType *AT = dyn_cast<ArrayType>(*I)) {
 699       uint64_t NumElements = AT->getNumElements();
 700
 701       if (!isa<ConstantInt>(I.getOperand())) {
 702         if (NumElements == 1) {
 703           GEPI->setOperand(2, Constant::getNullValue(Type::Int32Ty));
 704         } else {
 705           assert(NumElements == 2 && "Unhandled case!");
 706           // All users of the GEP must be loads.  At each use of the GEP, insert
 707           // two loads of the appropriate indexed GEP and select between them.
 708           Value *IsOne = new ICmpInst(ICmpInst::ICMP_NE, I.getOperand(),
 709                               Constant::getNullValue(I.getOperand()->getType()),
 710              "isone", GEPI);
 711           // Insert the new GEP instructions, which are properly indexed.
 712           SmallVector<Value*, 8> Indices(GEPI->op_begin()+1, GEPI->op_end());
 713           Indices[1] = Constant::getNullValue(Type::Int32Ty);
 714           Value *ZeroIdx = new GetElementPtrInst(GEPI->getOperand(0),
 715                                                  &Indices[0], Indices.size(),
 716                                                  GEPI->getName()+".0", GEPI);
 717           Indices[1] = ConstantInt::get(Type::Int32Ty, 1);
 718           Value *OneIdx = new GetElementPtrInst(GEPI->getOperand(0),
 719                                                 &Indices[0], Indices.size(),
 720                                                 GEPI->getName()+".1", GEPI);
 721           // Replace all loads of the variable index GEP with loads from both
 722           // indexes and a select.
 723           while (!GEPI->use_empty()) {
 724             LoadInst *LI = cast<LoadInst>(GEPI->use_back());
 725             Value *Zero = new LoadInst(ZeroIdx, LI->getName()+".0", LI);
 726             Value *One  = new LoadInst(OneIdx , LI->getName()+".1", LI);
 727             Value *R = new SelectInst(IsOne, One, Zero, LI->getName(), LI);
 728             LI->replaceAllUsesWith(R);
 729             LI->eraseFromParent();
 730           }
 731           GEPI->eraseFromParent();
 732         }
 733       }
 734     }
 735   }
 736 }
 737
 738 /// MergeInType - Add the 'In' type to the accumulated type so far.  If the
 739 /// types are incompatible, return true, otherwise update Accum and return
 740 /// false.
 741 ///
 742 /// There are three cases we handle here:
 743 ///   1) An effectively-integer union, where the pieces are stored into as
 744 ///      smaller integers (common with byte swap and other idioms).
 745 ///   2) A union of vector types of the same size and potentially its elements.
 746 ///      Here we turn element accesses into insert/extract element operations.
 747 ///   3) A union of scalar types, such as int/float or int/pointer.  Here we
 748 ///      merge together into integers, allowing the xform to work with #1 as
 749 ///      well.
 750 static bool MergeInType(const Type *In, const Type *&Accum,
 751                         const TargetData &TD) {
 752   // If this is our first type, just use it.
 753   const VectorType *PTy;
 754   if (Accum == Type::VoidTy || In == Accum) {
 755     Accum = In;
 756   } else if (In == Type::VoidTy) {
 757     // Noop.
 758   } else if (In->isInteger() && Accum->isInteger()) {   // integer union.
 759     // Otherwise pick whichever type is larger.
 760     if (cast<IntegerType>(In)->getBitWidth() >
 761         cast<IntegerType>(Accum)->getBitWidth())
 762       Accum = In;
 763   } else if (isa<PointerType>(In) && isa<PointerType>(Accum)) {
 764     // Pointer unions just stay as one of the pointers.
 765   } else if (isa<VectorType>(In) || isa<VectorType>(Accum)) {
 766     if ((PTy = dyn_cast<VectorType>(Accum)) &&
 767         PTy->getElementType() == In) {
 768       // Accum is a vector, and we are accessing an element: ok.
 769     } else if ((PTy = dyn_cast<VectorType>(In)) &&
 770                PTy->getElementType() == Accum) {
 771       // In is a vector, and accum is an element: ok, remember In.
 772       Accum = In;
 773     } else if ((PTy = dyn_cast<VectorType>(In)) && isa<VectorType>(Accum) &&
 774                PTy->getBitWidth() == cast<VectorType>(Accum)->getBitWidth()) {
 775       // Two vectors of the same size: keep Accum.
 776     } else {
 777       // Cannot insert an short into a <4 x int> or handle
 778       // <2 x int> -> <4 x int>
 779       return true;
 780     }
 781   } else {
 782     // Pointer/FP/Integer unions merge together as integers.
 783     switch (Accum->getTypeID()) {
 784     case Type::PointerTyID: Accum = TD.getIntPtrType(); break;
 785     case Type::FloatTyID:   Accum = Type::Int32Ty; break;
 786     case Type::DoubleTyID:  Accum = Type::Int64Ty; break;
 787     default:
 788       assert(Accum->isInteger() && "Unknown FP type!");
 789       break;
 790     }
 791
 792     switch (In->getTypeID()) {
 793     case Type::PointerTyID: In = TD.getIntPtrType(); break;
 794     case Type::FloatTyID:   In = Type::Int32Ty; break;
 795     case Type::DoubleTyID:  In = Type::Int64Ty; break;
 796     default:
 797       assert(In->isInteger() && "Unknown FP type!");
 798       break;
 799     }
 800     return MergeInType(In, Accum, TD);
 801   }
 802   return false;
 803 }
 804
 805 /// getUIntAtLeastAsBitAs - Return an unsigned integer type that is at least
 806 /// as big as the specified type.  If there is no suitable type, this returns
 807 /// null.
 808 const Type *getUIntAtLeastAsBitAs(unsigned NumBits) {
 809   if (NumBits > 64) return 0;
 810   if (NumBits > 32) return Type::Int64Ty;
 811   if (NumBits > 16) return Type::Int32Ty;
 812   if (NumBits > 8) return Type::Int16Ty;
 813   return Type::Int8Ty;
 814 }
 815
 816 /// CanConvertToScalar - V is a pointer.  If we can convert the pointee to a
 817 /// single scalar integer type, return that type.  Further, if the use is not
 818 /// a completely trivial use that mem2reg could promote, set IsNotTrivial.  If
 819 /// there are no uses of this pointer, return Type::VoidTy to differentiate from
 820 /// failure.
 821 ///
 822 const Type *SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial) {
 823   const Type *UsedType = Type::VoidTy; // No uses, no forced type.
 824   const TargetData &TD = getAnalysis<TargetData>();
 825   const PointerType *PTy = cast<PointerType>(V->getType());
 826
 827   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
 828     Instruction *User = cast<Instruction>(*UI);
 829
 830     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
 831       if (MergeInType(LI->getType(), UsedType, TD))
 832         return 0;
 833
 834     } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
 835       // Storing the pointer, not into the value?
 836       if (SI->getOperand(0) == V) return 0;
 837
 838       // NOTE: We could handle storing of FP imms into integers here!
 839
 840       if (MergeInType(SI->getOperand(0)->getType(), UsedType, TD))
 841         return 0;
 842     } else if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) {
 843       IsNotTrivial = true;
 844       const Type *SubTy = CanConvertToScalar(CI, IsNotTrivial);
 845       if (!SubTy || MergeInType(SubTy, UsedType, TD)) return 0;
 846     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
 847       // Check to see if this is stepping over an element: GEP Ptr, int C
 848       if (GEP->getNumOperands() == 2 && isa<ConstantInt>(GEP->getOperand(1))) {
 849         unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getZExtValue();
 850         unsigned ElSize = TD.getTypeSize(PTy->getElementType());
 851         unsigned BitOffset = Idx*ElSize*8;
 852         if (BitOffset > 64 || !isPowerOf2_32(ElSize)) return 0;
 853
 854         IsNotTrivial = true;
 855         const Type *SubElt = CanConvertToScalar(GEP, IsNotTrivial);
 856         if (SubElt == 0) return 0;
 857         if (SubElt != Type::VoidTy && SubElt->isInteger()) {
 858           const Type *NewTy =
 859             getUIntAtLeastAsBitAs(TD.getTypeSize(SubElt)*8+BitOffset);
 860           if (NewTy == 0 || MergeInType(NewTy, UsedType, TD)) return 0;
 861           continue;
 862         }
 863       } else if (GEP->getNumOperands() == 3 &&
 864                  isa<ConstantInt>(GEP->getOperand(1)) &&
 865                  isa<ConstantInt>(GEP->getOperand(2)) &&
 866                  cast<ConstantInt>(GEP->getOperand(1))->isZero()) {
 867         // We are stepping into an element, e.g. a structure or an array:
 868         // GEP Ptr, int 0, uint C
 869         const Type *AggTy = PTy->getElementType();
 870         unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
 871
 872         if (const ArrayType *ATy = dyn_cast<ArrayType>(AggTy)) {
 873           if (Idx >= ATy->getNumElements()) return 0;  // Out of range.
 874         } else if (const VectorType *VectorTy = dyn_cast<VectorType>(AggTy)) {
 875           // Getting an element of the packed vector.
 876           if (Idx >= VectorTy->getNumElements()) return 0;  // Out of range.
 877
 878           // Merge in the vector type.
 879           if (MergeInType(VectorTy, UsedType, TD)) return 0;
 880
 881           const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial);
 882           if (SubTy == 0) return 0;
 883
 884           if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType, TD))
 885             return 0;
 886
 887           // We'll need to change this to an insert/extract element operation.
 888           IsNotTrivial = true;
 889           continue;    // Everything looks ok
 890
 891         } else if (isa<StructType>(AggTy)) {
 892           // Structs are always ok.
 893         } else {
 894           return 0;
 895         }
 896         const Type *NTy = getUIntAtLeastAsBitAs(TD.getTypeSize(AggTy)*8);
 897         if (NTy == 0 || MergeInType(NTy, UsedType, TD)) return 0;
 898         const Type *SubTy = CanConvertToScalar(GEP, IsNotTrivial);
 899         if (SubTy == 0) return 0;
 900         if (SubTy != Type::VoidTy && MergeInType(SubTy, UsedType, TD))
 901           return 0;
 902         continue;    // Everything looks ok
 903       }
 904       return 0;
 905     } else {
 906       // Cannot handle this!
 907       return 0;
 908     }
 909   }
 910
 911   return UsedType;
 912 }
 913
 914 /// ConvertToScalar - The specified alloca passes the CanConvertToScalar
 915 /// predicate and is non-trivial.  Convert it to something that can be trivially
 916 /// promoted into a register by mem2reg.
 917 void SROA::ConvertToScalar(AllocationInst *AI, const Type *ActualTy) {
 918   DOUT << "CONVERT TO SCALAR: " << *AI << "  TYPE = "
 919        << *ActualTy << "\n";
 920   ++NumConverted;
 921
 922   BasicBlock *EntryBlock = AI->getParent();
 923   assert(EntryBlock == &EntryBlock->getParent()->getEntryBlock() &&
 924          "Not in the entry block!");
 925   EntryBlock->getInstList().remove(AI);  // Take the alloca out of the program.
 926
 927   // Create and insert the alloca.
 928   AllocaInst *NewAI = new AllocaInst(ActualTy, 0, AI->getName(),
 929                                      EntryBlock->begin());
 930   ConvertUsesToScalar(AI, NewAI, 0);
 931   delete AI;
 932 }
 933
 934
 935 /// ConvertUsesToScalar - Convert all of the users of Ptr to use the new alloca
 936 /// directly.  This happens when we are converting an "integer union" to a
 937 /// single integer scalar, or when we are converting a "vector union" to a
 938 /// vector with insert/extractelement instructions.
 939 ///
 940 /// Offset is an offset from the original alloca, in bits that need to be
 941 /// shifted to the right.  By the end of this, there should be no uses of Ptr.
 942 void SROA::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, unsigned Offset) {
 943   const TargetData &TD = getAnalysis<TargetData>();
 944   while (!Ptr->use_empty()) {
 945     Instruction *User = cast<Instruction>(Ptr->use_back());
 946
 947     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
 948       // The load is a bit extract from NewAI shifted right by Offset bits.
 949       Value *NV = new LoadInst(NewAI, LI->getName(), LI);
 950       if (NV->getType() == LI->getType()) {
 951         // We win, no conversion needed.
 952       } else if (const VectorType *PTy = dyn_cast<VectorType>(NV->getType())) {
 953         // If the result alloca is a vector type, this is either an element
 954         // access or a bitcast to another vector type.
 955         if (isa<VectorType>(LI->getType())) {
 956           NV = new BitCastInst(NV, LI->getType(), LI->getName(), LI);
 957         } else {
 958           // Must be an element access.
 959           unsigned Elt = Offset/(TD.getTypeSize(PTy->getElementType())*8);
 960           NV = new ExtractElementInst(
 961                          NV, ConstantInt::get(Type::Int32Ty, Elt), "tmp", LI);
 962         }
 963       } else if (isa<PointerType>(NV->getType())) {
 964         assert(isa<PointerType>(LI->getType()));
 965         // Must be ptr->ptr cast.  Anything else would result in NV being
 966         // an integer.
 967         NV = new BitCastInst(NV, LI->getType(), LI->getName(), LI);
 968       } else {
 969         const IntegerType *NTy = cast<IntegerType>(NV->getType());
 970         unsigned LIBitWidth = TD.getTypeSizeInBits(LI->getType());
 971
 972         // If this is a big-endian system and the load is narrower than the
 973         // full alloca type, we need to do a shift to get the right bits.
 974         int ShAmt = 0;
 975         if (TD.isBigEndian()) {
 976           ShAmt = NTy->getBitWidth()-LIBitWidth-Offset;
 977         } else {
 978           ShAmt = Offset;
 979         }
 980
 981         // Note: we support negative bitwidths (with shl) which are not defined.
 982         // We do this to support (f.e.) loads off the end of a structure where
 983         // only some bits are used.
 984         if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth())
 985           NV = BinaryOperator::createLShr(NV,
 986                                           ConstantInt::get(NV->getType(),ShAmt),
 987                                           LI->getName(), LI);
 988         else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth())
 989           NV = BinaryOperator::createShl(NV,
 990                                          ConstantInt::get(NV->getType(),-ShAmt),
 991                                          LI->getName(), LI);
 992
 993         // Finally, unconditionally truncate the integer to the right width.
 994         if (LIBitWidth < NTy->getBitWidth())
 995           NV = new TruncInst(NV, IntegerType::get(LIBitWidth),
 996                              LI->getName(), LI);
 997
 998         // If the result is an integer, this is a trunc or bitcast.
 999         if (isa<IntegerType>(LI->getType())) {
1000           assert(NV->getType() == LI->getType() && "Truncate wasn't enough?");
1001         } else if (LI->getType()->isFloatingPoint()) {
1002           // Just do a bitcast, we know the sizes match up.
1003           NV = new BitCastInst(NV, LI->getType(), LI->getName(), LI);
1004         } else {
1005           // Otherwise must be a pointer.
1006           NV = new IntToPtrInst(NV, LI->getType(), LI->getName(), LI);
1007         }
1008       }
1009       LI->replaceAllUsesWith(NV);
1010       LI->eraseFromParent();
1011     } else if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
1012       assert(SI->getOperand(0) != Ptr && "Consistency error!");
1013
1014       // Convert the stored type to the actual type, shift it left to insert
1015       // then 'or' into place.
1016       Value *SV = SI->getOperand(0);
1017       const Type *AllocaType = NewAI->getType()->getElementType();
1018       if (SV->getType() == AllocaType) {
1019         // All is well.
1020       } else if (const VectorType *PTy = dyn_cast<VectorType>(AllocaType)) {
1021         Value *Old = new LoadInst(NewAI, NewAI->getName()+".in", SI);
1022
1023         // If the result alloca is a vector type, this is either an element
1024         // access or a bitcast to another vector type.
1025         if (isa<VectorType>(SV->getType())) {
1026           SV = new BitCastInst(SV, AllocaType, SV->getName(), SI);
1027         } else {
1028           // Must be an element insertion.
1029           unsigned Elt = Offset/(TD.getTypeSize(PTy->getElementType())*8);
1030           SV = new InsertElementInst(Old, SV,
1031                                      ConstantInt::get(Type::Int32Ty, Elt),
1032                                      "tmp", SI);
1033         }
1034       } else if (isa<PointerType>(AllocaType)) {
1035         // If the alloca type is a pointer, then all the elements must be
1036         // pointers.
1037         if (SV->getType() != AllocaType)
1038           SV = new BitCastInst(SV, AllocaType, SV->getName(), SI);
1039       } else {
1040         Value *Old = new LoadInst(NewAI, NewAI->getName()+".in", SI);
1041
1042         // If SV is a float, convert it to the appropriate integer type.
1043         // If it is a pointer, do the same, and also handle ptr->ptr casts
1044         // here.
1045         unsigned SrcWidth = TD.getTypeSizeInBits(SV->getType());
1046         unsigned DestWidth = AllocaType->getPrimitiveSizeInBits();
1047         if (SV->getType()->isFloatingPoint())
1048           SV = new BitCastInst(SV, IntegerType::get(SrcWidth),
1049                                SV->getName(), SI);
1050         else if (isa<PointerType>(SV->getType()))
1051           SV = new PtrToIntInst(SV, TD.getIntPtrType(), SV->getName(), SI);
1052
1053         // Always zero extend the value if needed.
1054         if (SV->getType() != AllocaType)
1055           SV = new ZExtInst(SV, AllocaType, SV->getName(), SI);
1056
1057         // If this is a big-endian system and the store is narrower than the
1058         // full alloca type, we need to do a shift to get the right bits.
1059         int ShAmt = 0;
1060         if (TD.isBigEndian()) {
1061           ShAmt = DestWidth-SrcWidth-Offset;
1062         } else {
1063           ShAmt = Offset;
1064         }
1065
1066         // Note: we support negative bitwidths (with shr) which are not defined.
1067         // We do this to support (f.e.) stores off the end of a structure where
1068         // only some bits in the structure are set.
1069         APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth));
1070         if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) {
1071           SV = BinaryOperator::createShl(SV,
1072                                          ConstantInt::get(SV->getType(), ShAmt),
1073                                          SV->getName(), SI);
1074           Mask <<= ShAmt;
1075         } else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) {
1076           SV = BinaryOperator::createLShr(SV,
1077                                          ConstantInt::get(SV->getType(),-ShAmt),
1078                                           SV->getName(), SI);
1079           Mask = Mask.lshr(ShAmt);
1080         }
1081
1082         // Mask out the bits we are about to insert from the old value, and or
1083         // in the new bits.
1084         if (SrcWidth != DestWidth) {
1085           assert(DestWidth > SrcWidth);
1086           Old = BinaryOperator::createAnd(Old, ConstantInt::get(~Mask),
1087                                           Old->getName()+".mask", SI);
1088           SV = BinaryOperator::createOr(Old, SV, SV->getName()+".ins", SI);
1089         }
1090       }
1091       new StoreInst(SV, NewAI, SI);
1092       SI->eraseFromParent();
1093
1094     } else if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) {
1095        ConvertUsesToScalar(CI, NewAI, Offset);
1096       CI->eraseFromParent();
1097     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
1098       const PointerType *AggPtrTy =
1099         cast<PointerType>(GEP->getOperand(0)->getType());
1100       const TargetData &TD = getAnalysis<TargetData>();
1101       unsigned AggSizeInBits = TD.getTypeSize(AggPtrTy->getElementType())*8;
1102
1103       // Check to see if this is stepping over an element: GEP Ptr, int C
1104       unsigned NewOffset = Offset;
1105       if (GEP->getNumOperands() == 2) {
1106         unsigned Idx = cast<ConstantInt>(GEP->getOperand(1))->getZExtValue();
1107         unsigned BitOffset = Idx*AggSizeInBits;
1108
1109         NewOffset += BitOffset;
1110       } else if (GEP->getNumOperands() == 3) {
1111         // We know that operand #2 is zero.
1112         unsigned Idx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
1113         const Type *AggTy = AggPtrTy->getElementType();
1114         if (const SequentialType *SeqTy = dyn_cast<SequentialType>(AggTy)) {
1115           unsigned ElSizeBits = TD.getTypeSize(SeqTy->getElementType())*8;
1116
1117           NewOffset += ElSizeBits*Idx;
1118         } else if (const StructType *STy = dyn_cast<StructType>(AggTy)) {
1119           unsigned EltBitOffset =
1120             TD.getStructLayout(STy)->getElementOffset(Idx)*8;
1121
1122           NewOffset += EltBitOffset;
1123         } else {
1124           assert(0 && "Unsupported operation!");
1125           abort();
1126         }
1127       } else {
1128         assert(0 && "Unsupported operation!");
1129         abort();
1130       }
1131       ConvertUsesToScalar(GEP, NewAI, NewOffset);
1132       GEP->eraseFromParent();
1133     } else {
1134       assert(0 && "Unsupported operation!");
1135       abort();
1136     }
1137   }
1138 }
1139
1140
1141 /// PointsToConstantGlobal - Return true if V (possibly indirectly) points to
1142 /// some part of a constant global variable.  This intentionally only accepts
1143 /// constant expressions because we don't can't rewrite arbitrary instructions.
1144 static bool PointsToConstantGlobal(Value *V) {
1145   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
1146     return GV->isConstant();
1147   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
1148     if (CE->getOpcode() == Instruction::BitCast ||
1149         CE->getOpcode() == Instruction::GetElementPtr)
1150       return PointsToConstantGlobal(CE->getOperand(0));
1151   return false;
1152 }
1153
1154 /// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived)
1155 /// pointer to an alloca.  Ignore any reads of the pointer, return false if we
1156 /// see any stores or other unknown uses.  If we see pointer arithmetic, keep
1157 /// track of whether it moves the pointer (with isOffset) but otherwise traverse
1158 /// the uses.  If we see a memcpy/memmove that targets an unoffseted pointer to
1159 /// the alloca, and if the source pointer is a pointer to a constant  global, we
1160 /// can optimize this.
1161 static bool isOnlyCopiedFromConstantGlobal(Value *V, Instruction *&TheCopy,
1162                                            bool isOffset) {
1163   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
1164     if (isa<LoadInst>(*UI)) {
1165       // Ignore loads, they are always ok.
1166       continue;
1167     }
1168     if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) {
1169       // If uses of the bitcast are ok, we are ok.
1170       if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset))
1171         return false;
1172       continue;
1173     }
1174     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
1175       // If the GEP has all zero indices, it doesn't offset the pointer.  If it
1176       // doesn't, it does.
1177       if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy,
1178                                          isOffset || !GEP->hasAllZeroIndices()))
1179         return false;
1180       continue;
1181     }
1182
1183     // If this is isn't our memcpy/memmove, reject it as something we can't
1184     // handle.
1185     if (!isa<MemCpyInst>(*UI) && !isa<MemMoveInst>(*UI))
1186       return false;
1187
1188     // If we already have seen a copy, reject the second one.
1189     if (TheCopy) return false;
1190
1191     // If the pointer has been offset from the start of the alloca, we can't
1192     // safely handle this.
1193     if (isOffset) return false;
1194
1195     // If the memintrinsic isn't using the alloca as the dest, reject it.
1196     if (UI.getOperandNo() != 1) return false;
1197
1198     MemIntrinsic *MI = cast<MemIntrinsic>(*UI);
1199
1200     // If the source of the memcpy/move is not a constant global, reject it.
1201     if (!PointsToConstantGlobal(MI->getOperand(2)))
1202       return false;
1203
1204     // Otherwise, the transform is safe.  Remember the copy instruction.
1205     TheCopy = MI;
1206   }
1207   return true;
1208 }
1209
1210 /// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only
1211 /// modified by a copy from a constant global.  If we can prove this, we can
1212 /// replace any uses of the alloca with uses of the global directly.
1213 Instruction *SROA::isOnlyCopiedFromConstantGlobal(AllocationInst *AI) {
1214   Instruction *TheCopy = 0;
1215   if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false))
1216     return TheCopy;
1217   return 0;
1218 }