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