lib/Transforms/IPO/GlobalOpt.cpp

   1 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass transforms simple global variables that never have their address
  11 // taken.  If obviously true, it marks read/write globals as constant, deletes
  12 // variables only stored to, etc.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "globalopt"
  17 #include "llvm/Transforms/IPO.h"
  18 #include "llvm/CallingConv.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Instructions.h"
  22 #include "llvm/IntrinsicInst.h"
  23 #include "llvm/Module.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/Analysis/ConstantFolding.h"
  26 #include "llvm/Analysis/MemoryBuiltins.h"
  27 #include "llvm/Target/TargetData.h"
  28 #include "llvm/Support/CallSite.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/ErrorHandling.h"
  31 #include "llvm/Support/GetElementPtrTypeIterator.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/ADT/DenseMap.h"
  35 #include "llvm/ADT/SmallPtrSet.h"
  36 #include "llvm/ADT/SmallVector.h"
  37 #include "llvm/ADT/Statistic.h"
  38 #include "llvm/ADT/STLExtras.h"
  39 #include <algorithm>
  40 using namespace llvm;
  41
  42 STATISTIC(NumMarked    , "Number of globals marked constant");
  43 STATISTIC(NumSRA       , "Number of aggregate globals broken into scalars");
  44 STATISTIC(NumHeapSRA   , "Number of heap objects SRA'd");
  45 STATISTIC(NumSubstitute,"Number of globals with initializers stored into them");
  46 STATISTIC(NumDeleted   , "Number of globals deleted");
  47 STATISTIC(NumFnDeleted , "Number of functions deleted");
  48 STATISTIC(NumGlobUses  , "Number of global uses devirtualized");
  49 STATISTIC(NumLocalized , "Number of globals localized");
  50 STATISTIC(NumShrunkToBool  , "Number of global vars shrunk to booleans");
  51 STATISTIC(NumFastCallFns   , "Number of functions converted to fastcc");
  52 STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated");
  53 STATISTIC(NumNestRemoved   , "Number of nest attributes removed");
  54 STATISTIC(NumAliasesResolved, "Number of global aliases resolved");
  55 STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated");
  56
  57 namespace {
  58   struct GlobalOpt : public ModulePass {
  59     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  60     }
  61     static char ID; // Pass identification, replacement for typeid
  62     GlobalOpt() : ModulePass(&ID) {}
  63
  64     bool runOnModule(Module &M);
  65
  66   private:
  67     GlobalVariable *FindGlobalCtors(Module &M);
  68     bool OptimizeFunctions(Module &M);
  69     bool OptimizeGlobalVars(Module &M);
  70     bool OptimizeGlobalAliases(Module &M);
  71     bool OptimizeGlobalCtorsList(GlobalVariable *&GCL);
  72     bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI);
  73   };
  74 }
  75
  76 char GlobalOpt::ID = 0;
  77 static RegisterPass<GlobalOpt> X("globalopt", "Global Variable Optimizer");
  78
  79 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
  80
  81 namespace {
  82
  83 /// GlobalStatus - As we analyze each global, keep track of some information
  84 /// about it.  If we find out that the address of the global is taken, none of
  85 /// this info will be accurate.
  86 struct GlobalStatus {
  87   /// isLoaded - True if the global is ever loaded.  If the global isn't ever
  88   /// loaded it can be deleted.
  89   bool isLoaded;
  90
  91   /// StoredType - Keep track of what stores to the global look like.
  92   ///
  93   enum StoredType {
  94     /// NotStored - There is no store to this global.  It can thus be marked
  95     /// constant.
  96     NotStored,
  97
  98     /// isInitializerStored - This global is stored to, but the only thing
  99     /// stored is the constant it was initialized with.  This is only tracked
 100     /// for scalar globals.
 101     isInitializerStored,
 102
 103     /// isStoredOnce - This global is stored to, but only its initializer and
 104     /// one other value is ever stored to it.  If this global isStoredOnce, we
 105     /// track the value stored to it in StoredOnceValue below.  This is only
 106     /// tracked for scalar globals.
 107     isStoredOnce,
 108
 109     /// isStored - This global is stored to by multiple values or something else
 110     /// that we cannot track.
 111     isStored
 112   } StoredType;
 113
 114   /// StoredOnceValue - If only one value (besides the initializer constant) is
 115   /// ever stored to this global, keep track of what value it is.
 116   Value *StoredOnceValue;
 117
 118   /// AccessingFunction/HasMultipleAccessingFunctions - These start out
 119   /// null/false.  When the first accessing function is noticed, it is recorded.
 120   /// When a second different accessing function is noticed,
 121   /// HasMultipleAccessingFunctions is set to true.
 122   Function *AccessingFunction;
 123   bool HasMultipleAccessingFunctions;
 124
 125   /// HasNonInstructionUser - Set to true if this global has a user that is not
 126   /// an instruction (e.g. a constant expr or GV initializer).
 127   bool HasNonInstructionUser;
 128
 129   /// HasPHIUser - Set to true if this global has a user that is a PHI node.
 130   bool HasPHIUser;
 131
 132   GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0),
 133                    AccessingFunction(0), HasMultipleAccessingFunctions(false),
 134                    HasNonInstructionUser(false), HasPHIUser(false) {}
 135 };
 136
 137 }
 138
 139 // SafeToDestroyConstant - It is safe to destroy a constant iff it is only used
 140 // by constants itself.  Note that constants cannot be cyclic, so this test is
 141 // pretty easy to implement recursively.
 142 //
 143 static bool SafeToDestroyConstant(Constant *C) {
 144   if (isa<GlobalValue>(C)) return false;
 145
 146   for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI)
 147     if (Constant *CU = dyn_cast<Constant>(*UI)) {
 148       if (!SafeToDestroyConstant(CU)) return false;
 149     } else
 150       return false;
 151   return true;
 152 }
 153
 154
 155 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus
 156 /// structure.  If the global has its address taken, return true to indicate we
 157 /// can't do anything with it.
 158 ///
 159 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
 160                           SmallPtrSet<PHINode*, 16> &PHIUsers) {
 161   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 162     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
 163       GS.HasNonInstructionUser = true;
 164
 165       if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
 166
 167     } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
 168       if (!GS.HasMultipleAccessingFunctions) {
 169         Function *F = I->getParent()->getParent();
 170         if (GS.AccessingFunction == 0)
 171           GS.AccessingFunction = F;
 172         else if (GS.AccessingFunction != F)
 173           GS.HasMultipleAccessingFunctions = true;
 174       }
 175       if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 176         GS.isLoaded = true;
 177         if (LI->isVolatile()) return true;  // Don't hack on volatile loads.
 178       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 179         // Don't allow a store OF the address, only stores TO the address.
 180         if (SI->getOperand(0) == V) return true;
 181
 182         if (SI->isVolatile()) return true;  // Don't hack on volatile stores.
 183
 184         // If this is a direct store to the global (i.e., the global is a scalar
 185         // value, not an aggregate), keep more specific information about
 186         // stores.
 187         if (GS.StoredType != GlobalStatus::isStored) {
 188           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
 189             Value *StoredVal = SI->getOperand(0);
 190             if (StoredVal == GV->getInitializer()) {
 191               if (GS.StoredType < GlobalStatus::isInitializerStored)
 192                 GS.StoredType = GlobalStatus::isInitializerStored;
 193             } else if (isa<LoadInst>(StoredVal) &&
 194                        cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
 195               // G = G
 196               if (GS.StoredType < GlobalStatus::isInitializerStored)
 197                 GS.StoredType = GlobalStatus::isInitializerStored;
 198             } else if (GS.StoredType < GlobalStatus::isStoredOnce) {
 199               GS.StoredType = GlobalStatus::isStoredOnce;
 200               GS.StoredOnceValue = StoredVal;
 201             } else if (GS.StoredType == GlobalStatus::isStoredOnce &&
 202                        GS.StoredOnceValue == StoredVal) {
 203               // noop.
 204             } else {
 205               GS.StoredType = GlobalStatus::isStored;
 206             }
 207           } else {
 208             GS.StoredType = GlobalStatus::isStored;
 209           }
 210         }
 211       } else if (isa<GetElementPtrInst>(I)) {
 212         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 213       } else if (isa<SelectInst>(I)) {
 214         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 215       } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
 216         // PHI nodes we can check just like select or GEP instructions, but we
 217         // have to be careful about infinite recursion.
 218         if (PHIUsers.insert(PN))  // Not already visited.
 219           if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 220         GS.HasPHIUser = true;
 221       } else if (isa<CmpInst>(I)) {
 222       } else if (isa<MemTransferInst>(I)) {
 223         if (I->getOperand(1) == V)
 224           GS.StoredType = GlobalStatus::isStored;
 225         if (I->getOperand(2) == V)
 226           GS.isLoaded = true;
 227       } else if (isa<MemSetInst>(I)) {
 228         assert(I->getOperand(1) == V && "Memset only takes one pointer!");
 229         GS.StoredType = GlobalStatus::isStored;
 230       } else {
 231         return true;  // Any other non-load instruction might take address!
 232       }
 233     } else if (Constant *C = dyn_cast<Constant>(*UI)) {
 234       GS.HasNonInstructionUser = true;
 235       // We might have a dead and dangling constant hanging off of here.
 236       if (!SafeToDestroyConstant(C))
 237         return true;
 238     } else {
 239       GS.HasNonInstructionUser = true;
 240       // Otherwise must be some other user.
 241       return true;
 242     }
 243
 244   return false;
 245 }
 246
 247 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) {
 248   ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
 249   if (!CI) return 0;
 250   unsigned IdxV = CI->getZExtValue();
 251
 252   if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) {
 253     if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV);
 254   } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) {
 255     if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV);
 256   } else if (ConstantVector *CP = dyn_cast<ConstantVector>(Agg)) {
 257     if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV);
 258   } else if (isa<ConstantAggregateZero>(Agg)) {
 259     if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
 260       if (IdxV < STy->getNumElements())
 261         return Constant::getNullValue(STy->getElementType(IdxV));
 262     } else if (const SequentialType *STy =
 263                dyn_cast<SequentialType>(Agg->getType())) {
 264       return Constant::getNullValue(STy->getElementType());
 265     }
 266   } else if (isa<UndefValue>(Agg)) {
 267     if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
 268       if (IdxV < STy->getNumElements())
 269         return UndefValue::get(STy->getElementType(IdxV));
 270     } else if (const SequentialType *STy =
 271                dyn_cast<SequentialType>(Agg->getType())) {
 272       return UndefValue::get(STy->getElementType());
 273     }
 274   }
 275   return 0;
 276 }
 277
 278
 279 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
 280 /// users of the global, cleaning up the obvious ones.  This is largely just a
 281 /// quick scan over the use list to clean up the easy and obvious cruft.  This
 282 /// returns true if it made a change.
 283 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) {
 284   bool Changed = false;
 285   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) {
 286     User *U = *UI++;
 287
 288     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
 289       if (Init) {
 290         // Replace the load with the initializer.
 291         LI->replaceAllUsesWith(Init);
 292         LI->eraseFromParent();
 293         Changed = true;
 294       }
 295     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 296       // Store must be unreachable or storing Init into the global.
 297       SI->eraseFromParent();
 298       Changed = true;
 299     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 300       if (CE->getOpcode() == Instruction::GetElementPtr) {
 301         Constant *SubInit = 0;
 302         if (Init)
 303           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
 304         Changed |= CleanupConstantGlobalUsers(CE, SubInit);
 305       } else if (CE->getOpcode() == Instruction::BitCast &&
 306                  CE->getType()->isPointerTy()) {
 307         // Pointer cast, delete any stores and memsets to the global.
 308         Changed |= CleanupConstantGlobalUsers(CE, 0);
 309       }
 310
 311       if (CE->use_empty()) {
 312         CE->destroyConstant();
 313         Changed = true;
 314       }
 315     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
 316       // Do not transform "gepinst (gep constexpr (GV))" here, because forming
 317       // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
 318       // and will invalidate our notion of what Init is.
 319       Constant *SubInit = 0;
 320       if (!isa<ConstantExpr>(GEP->getOperand(0))) {
 321         ConstantExpr *CE =
 322           dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP));
 323         if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
 324           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
 325       }
 326       Changed |= CleanupConstantGlobalUsers(GEP, SubInit);
 327
 328       if (GEP->use_empty()) {
 329         GEP->eraseFromParent();
 330         Changed = true;
 331       }
 332     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
 333       if (MI->getRawDest() == V) {
 334         MI->eraseFromParent();
 335         Changed = true;
 336       }
 337
 338     } else if (Constant *C = dyn_cast<Constant>(U)) {
 339       // If we have a chain of dead constantexprs or other things dangling from
 340       // us, and if they are all dead, nuke them without remorse.
 341       if (SafeToDestroyConstant(C)) {
 342         C->destroyConstant();
 343         // This could have invalidated UI, start over from scratch.
 344         CleanupConstantGlobalUsers(V, Init);
 345         return true;
 346       }
 347     }
 348   }
 349   return Changed;
 350 }
 351
 352 /// isSafeSROAElementUse - Return true if the specified instruction is a safe
 353 /// user of a derived expression from a global that we want to SROA.
 354 static bool isSafeSROAElementUse(Value *V) {
 355   // We might have a dead and dangling constant hanging off of here.
 356   if (Constant *C = dyn_cast<Constant>(V))
 357     return SafeToDestroyConstant(C);
 358
 359   Instruction *I = dyn_cast<Instruction>(V);
 360   if (!I) return false;
 361
 362   // Loads are ok.
 363   if (isa<LoadInst>(I)) return true;
 364
 365   // Stores *to* the pointer are ok.
 366   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 367     return SI->getOperand(0) != V;
 368
 369   // Otherwise, it must be a GEP.
 370   GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I);
 371   if (GEPI == 0) return false;
 372
 373   if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) ||
 374       !cast<Constant>(GEPI->getOperand(1))->isNullValue())
 375     return false;
 376
 377   for (Value::use_iterator I = GEPI->use_begin(), E = GEPI->use_end();
 378        I != E; ++I)
 379     if (!isSafeSROAElementUse(*I))
 380       return false;
 381   return true;
 382 }
 383
 384
 385 /// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value.
 386 /// Look at it and its uses and decide whether it is safe to SROA this global.
 387 ///
 388 static bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) {
 389   // The user of the global must be a GEP Inst or a ConstantExpr GEP.
 390   if (!isa<GetElementPtrInst>(U) &&
 391       (!isa<ConstantExpr>(U) ||
 392        cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr))
 393     return false;
 394
 395   // Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
 396   // don't like < 3 operand CE's, and we don't like non-constant integer
 397   // indices.  This enforces that all uses are 'gep GV, 0, C, ...' for some
 398   // value of C.
 399   if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) ||
 400       !cast<Constant>(U->getOperand(1))->isNullValue() ||
 401       !isa<ConstantInt>(U->getOperand(2)))
 402     return false;
 403
 404   gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U);
 405   ++GEPI;  // Skip over the pointer index.
 406
 407   // If this is a use of an array allocation, do a bit more checking for sanity.
 408   if (const ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) {
 409     uint64_t NumElements = AT->getNumElements();
 410     ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2));
 411
 412     // Check to make sure that index falls within the array.  If not,
 413     // something funny is going on, so we won't do the optimization.
 414     //
 415     if (Idx->getZExtValue() >= NumElements)
 416       return false;
 417
 418     // We cannot scalar repl this level of the array unless any array
 419     // sub-indices are in-range constants.  In particular, consider:
 420     // A[0][i].  We cannot know that the user isn't doing invalid things like
 421     // allowing i to index an out-of-range subscript that accesses A[1].
 422     //
 423     // Scalar replacing *just* the outer index of the array is probably not
 424     // going to be a win anyway, so just give up.
 425     for (++GEPI; // Skip array index.
 426          GEPI != E;
 427          ++GEPI) {
 428       uint64_t NumElements;
 429       if (const ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI))
 430         NumElements = SubArrayTy->getNumElements();
 431       else if (const VectorType *SubVectorTy = dyn_cast<VectorType>(*GEPI))
 432         NumElements = SubVectorTy->getNumElements();
 433       else {
 434         assert((*GEPI)->isStructTy() &&
 435                "Indexed GEP type is not array, vector, or struct!");
 436         continue;
 437       }
 438
 439       ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
 440       if (!IdxVal || IdxVal->getZExtValue() >= NumElements)
 441         return false;
 442     }
 443   }
 444
 445   for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I)
 446     if (!isSafeSROAElementUse(*I))
 447       return false;
 448   return true;
 449 }
 450
 451 /// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it
 452 /// is safe for us to perform this transformation.
 453 ///
 454 static bool GlobalUsersSafeToSRA(GlobalValue *GV) {
 455   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end();
 456        UI != E; ++UI) {
 457     if (!IsUserOfGlobalSafeForSRA(*UI, GV))
 458       return false;
 459   }
 460   return true;
 461 }
 462
 463
 464 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
 465 /// variable.  This opens the door for other optimizations by exposing the
 466 /// behavior of the program in a more fine-grained way.  We have determined that
 467 /// this transformation is safe already.  We return the first global variable we
 468 /// insert so that the caller can reprocess it.
 469 static GlobalVariable *SRAGlobal(GlobalVariable *GV, const TargetData &TD) {
 470   // Make sure this global only has simple uses that we can SRA.
 471   if (!GlobalUsersSafeToSRA(GV))
 472     return 0;
 473
 474   assert(GV->hasLocalLinkage() && !GV->isConstant());
 475   Constant *Init = GV->getInitializer();
 476   const Type *Ty = Init->getType();
 477
 478   std::vector<GlobalVariable*> NewGlobals;
 479   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
 480
 481   // Get the alignment of the global, either explicit or target-specific.
 482   unsigned StartAlignment = GV->getAlignment();
 483   if (StartAlignment == 0)
 484     StartAlignment = TD.getABITypeAlignment(GV->getType());
 485
 486   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 487     NewGlobals.reserve(STy->getNumElements());
 488     const StructLayout &Layout = *TD.getStructLayout(STy);
 489     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
 490       Constant *In = getAggregateConstantElement(Init,
 491                     ConstantInt::get(Type::getInt32Ty(STy->getContext()), i));
 492       assert(In && "Couldn't get element of initializer?");
 493       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
 494                                                GlobalVariable::InternalLinkage,
 495                                                In, GV->getName()+"."+Twine(i),
 496                                                GV->isThreadLocal(),
 497                                               GV->getType()->getAddressSpace());
 498       Globals.insert(GV, NGV);
 499       NewGlobals.push_back(NGV);
 500
 501       // Calculate the known alignment of the field.  If the original aggregate
 502       // had 256 byte alignment for example, something might depend on that:
 503       // propagate info to each field.
 504       uint64_t FieldOffset = Layout.getElementOffset(i);
 505       unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset);
 506       if (NewAlign > TD.getABITypeAlignment(STy->getElementType(i)))
 507         NGV->setAlignment(NewAlign);
 508     }
 509   } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
 510     unsigned NumElements = 0;
 511     if (const ArrayType *ATy = dyn_cast<ArrayType>(STy))
 512       NumElements = ATy->getNumElements();
 513     else
 514       NumElements = cast<VectorType>(STy)->getNumElements();
 515
 516     if (NumElements > 16 && GV->hasNUsesOrMore(16))
 517       return 0; // It's not worth it.
 518     NewGlobals.reserve(NumElements);
 519
 520     uint64_t EltSize = TD.getTypeAllocSize(STy->getElementType());
 521     unsigned EltAlign = TD.getABITypeAlignment(STy->getElementType());
 522     for (unsigned i = 0, e = NumElements; i != e; ++i) {
 523       Constant *In = getAggregateConstantElement(Init,
 524                     ConstantInt::get(Type::getInt32Ty(Init->getContext()), i));
 525       assert(In && "Couldn't get element of initializer?");
 526
 527       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
 528                                                GlobalVariable::InternalLinkage,
 529                                                In, GV->getName()+"."+Twine(i),
 530                                                GV->isThreadLocal(),
 531                                               GV->getType()->getAddressSpace());
 532       Globals.insert(GV, NGV);
 533       NewGlobals.push_back(NGV);
 534
 535       // Calculate the known alignment of the field.  If the original aggregate
 536       // had 256 byte alignment for example, something might depend on that:
 537       // propagate info to each field.
 538       unsigned NewAlign = (unsigned)MinAlign(StartAlignment, EltSize*i);
 539       if (NewAlign > EltAlign)
 540         NGV->setAlignment(NewAlign);
 541     }
 542   }
 543
 544   if (NewGlobals.empty())
 545     return 0;
 546
 547   DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV);
 548
 549   Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext()));
 550
 551   // Loop over all of the uses of the global, replacing the constantexpr geps,
 552   // with smaller constantexpr geps or direct references.
 553   while (!GV->use_empty()) {
 554     User *GEP = GV->use_back();
 555     assert(((isa<ConstantExpr>(GEP) &&
 556              cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||
 557             isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!");
 558
 559     // Ignore the 1th operand, which has to be zero or else the program is quite
 560     // broken (undefined).  Get the 2nd operand, which is the structure or array
 561     // index.
 562     unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
 563     if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
 564
 565     Value *NewPtr = NewGlobals[Val];
 566
 567     // Form a shorter GEP if needed.
 568     if (GEP->getNumOperands() > 3) {
 569       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
 570         SmallVector<Constant*, 8> Idxs;
 571         Idxs.push_back(NullInt);
 572         for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
 573           Idxs.push_back(CE->getOperand(i));
 574         NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr),
 575                                                 &Idxs[0], Idxs.size());
 576       } else {
 577         GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
 578         SmallVector<Value*, 8> Idxs;
 579         Idxs.push_back(NullInt);
 580         for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
 581           Idxs.push_back(GEPI->getOperand(i));
 582         NewPtr = GetElementPtrInst::Create(NewPtr, Idxs.begin(), Idxs.end(),
 583                                            GEPI->getName()+"."+Twine(Val),GEPI);
 584       }
 585     }
 586     GEP->replaceAllUsesWith(NewPtr);
 587
 588     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
 589       GEPI->eraseFromParent();
 590     else
 591       cast<ConstantExpr>(GEP)->destroyConstant();
 592   }
 593
 594   // Delete the old global, now that it is dead.
 595   Globals.erase(GV);
 596   ++NumSRA;
 597
 598   // Loop over the new globals array deleting any globals that are obviously
 599   // dead.  This can arise due to scalarization of a structure or an array that
 600   // has elements that are dead.
 601   unsigned FirstGlobal = 0;
 602   for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i)
 603     if (NewGlobals[i]->use_empty()) {
 604       Globals.erase(NewGlobals[i]);
 605       if (FirstGlobal == i) ++FirstGlobal;
 606     }
 607
 608   return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0;
 609 }
 610
 611 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified
 612 /// value will trap if the value is dynamically null.  PHIs keeps track of any
 613 /// phi nodes we've seen to avoid reprocessing them.
 614 static bool AllUsesOfValueWillTrapIfNull(Value *V,
 615                                          SmallPtrSet<PHINode*, 8> &PHIs) {
 616   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 617     if (isa<LoadInst>(*UI)) {
 618       // Will trap.
 619     } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
 620       if (SI->getOperand(0) == V) {
 621         //cerr << "NONTRAPPING USE: " << **UI;
 622         return false;  // Storing the value.
 623       }
 624     } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
 625       if (CI->getOperand(0) != V) {
 626         //cerr << "NONTRAPPING USE: " << **UI;
 627         return false;  // Not calling the ptr
 628       }
 629     } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) {
 630       if (II->getOperand(0) != V) {
 631         //cerr << "NONTRAPPING USE: " << **UI;
 632         return false;  // Not calling the ptr
 633       }
 634     } else if (BitCastInst *CI = dyn_cast<BitCastInst>(*UI)) {
 635       if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false;
 636     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) {
 637       if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
 638     } else if (PHINode *PN = dyn_cast<PHINode>(*UI)) {
 639       // If we've already seen this phi node, ignore it, it has already been
 640       // checked.
 641       if (PHIs.insert(PN) && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
 642         return false;
 643     } else if (isa<ICmpInst>(*UI) &&
 644                isa<ConstantPointerNull>(UI->getOperand(1))) {
 645       // Ignore icmp X, null
 646     } else {
 647       //cerr << "NONTRAPPING USE: " << **UI;
 648       return false;
 649     }
 650   return true;
 651 }
 652
 653 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads
 654 /// from GV will trap if the loaded value is null.  Note that this also permits
 655 /// comparisons of the loaded value against null, as a special case.
 656 static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) {
 657   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI!=E; ++UI)
 658     if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
 659       SmallPtrSet<PHINode*, 8> PHIs;
 660       if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
 661         return false;
 662     } else if (isa<StoreInst>(*UI)) {
 663       // Ignore stores to the global.
 664     } else {
 665       // We don't know or understand this user, bail out.
 666       //cerr << "UNKNOWN USER OF GLOBAL!: " << **UI;
 667       return false;
 668     }
 669
 670   return true;
 671 }
 672
 673 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
 674   bool Changed = false;
 675   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) {
 676     Instruction *I = cast<Instruction>(*UI++);
 677     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 678       LI->setOperand(0, NewV);
 679       Changed = true;
 680     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 681       if (SI->getOperand(1) == V) {
 682         SI->setOperand(1, NewV);
 683         Changed = true;
 684       }
 685     } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
 686       if (I->getOperand(0) == V) {
 687         // Calling through the pointer!  Turn into a direct call, but be careful
 688         // that the pointer is not also being passed as an argument.
 689         I->setOperand(0, NewV);
 690         Changed = true;
 691         bool PassedAsArg = false;
 692         for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
 693           if (I->getOperand(i) == V) {
 694             PassedAsArg = true;
 695             I->setOperand(i, NewV);
 696           }
 697
 698         if (PassedAsArg) {
 699           // Being passed as an argument also.  Be careful to not invalidate UI!
 700           UI = V->use_begin();
 701         }
 702       }
 703     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
 704       Changed |= OptimizeAwayTrappingUsesOfValue(CI,
 705                                 ConstantExpr::getCast(CI->getOpcode(),
 706                                                       NewV, CI->getType()));
 707       if (CI->use_empty()) {
 708         Changed = true;
 709         CI->eraseFromParent();
 710       }
 711     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
 712       // Should handle GEP here.
 713       SmallVector<Constant*, 8> Idxs;
 714       Idxs.reserve(GEPI->getNumOperands()-1);
 715       for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end();
 716            i != e; ++i)
 717         if (Constant *C = dyn_cast<Constant>(*i))
 718           Idxs.push_back(C);
 719         else
 720           break;
 721       if (Idxs.size() == GEPI->getNumOperands()-1)
 722         Changed |= OptimizeAwayTrappingUsesOfValue(GEPI,
 723                           ConstantExpr::getGetElementPtr(NewV, &Idxs[0],
 724                                                         Idxs.size()));
 725       if (GEPI->use_empty()) {
 726         Changed = true;
 727         GEPI->eraseFromParent();
 728       }
 729     }
 730   }
 731
 732   return Changed;
 733 }
 734
 735
 736 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null
 737 /// value stored into it.  If there are uses of the loaded value that would trap
 738 /// if the loaded value is dynamically null, then we know that they cannot be
 739 /// reachable with a null optimize away the load.
 740 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) {
 741   bool Changed = false;
 742
 743   // Keep track of whether we are able to remove all the uses of the global
 744   // other than the store that defines it.
 745   bool AllNonStoreUsesGone = true;
 746
 747   // Replace all uses of loads with uses of uses of the stored value.
 748   for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); GUI != E;){
 749     User *GlobalUser = *GUI++;
 750     if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
 751       Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
 752       // If we were able to delete all uses of the loads
 753       if (LI->use_empty()) {
 754         LI->eraseFromParent();
 755         Changed = true;
 756       } else {
 757         AllNonStoreUsesGone = false;
 758       }
 759     } else if (isa<StoreInst>(GlobalUser)) {
 760       // Ignore the store that stores "LV" to the global.
 761       assert(GlobalUser->getOperand(1) == GV &&
 762              "Must be storing *to* the global");
 763     } else {
 764       AllNonStoreUsesGone = false;
 765
 766       // If we get here we could have other crazy uses that are transitively
 767       // loaded.
 768       assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) ||
 769               isa<ConstantExpr>(GlobalUser)) && "Only expect load and stores!");
 770     }
 771   }
 772
 773   if (Changed) {
 774     DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV);
 775     ++NumGlobUses;
 776   }
 777
 778   // If we nuked all of the loads, then none of the stores are needed either,
 779   // nor is the global.
 780   if (AllNonStoreUsesGone) {
 781     DEBUG(dbgs() << "  *** GLOBAL NOW DEAD!\n");
 782     CleanupConstantGlobalUsers(GV, 0);
 783     if (GV->use_empty()) {
 784       GV->eraseFromParent();
 785       ++NumDeleted;
 786     }
 787     Changed = true;
 788   }
 789   return Changed;
 790 }
 791
 792 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the
 793 /// instructions that are foldable.
 794 static void ConstantPropUsersOf(Value *V) {
 795   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; )
 796     if (Instruction *I = dyn_cast<Instruction>(*UI++))
 797       if (Constant *NewC = ConstantFoldInstruction(I)) {
 798         I->replaceAllUsesWith(NewC);
 799
 800         // Advance UI to the next non-I use to avoid invalidating it!
 801         // Instructions could multiply use V.
 802         while (UI != E && *UI == I)
 803           ++UI;
 804         I->eraseFromParent();
 805       }
 806 }
 807
 808 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global
 809 /// variable, and transforms the program as if it always contained the result of
 810 /// the specified malloc.  Because it is always the result of the specified
 811 /// malloc, there is no reason to actually DO the malloc.  Instead, turn the
 812 /// malloc into a global, and any loads of GV as uses of the new global.
 813 static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV,
 814                                                      CallInst *CI,
 815                                                      const Type *AllocTy,
 816                                                      ConstantInt *NElements,
 817                                                      TargetData* TD) {
 818   DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << "  CALL = " << *CI << '\n');
 819
 820   const Type *GlobalType;
 821   if (NElements->getZExtValue() == 1)
 822     GlobalType = AllocTy;
 823   else
 824     // If we have an array allocation, the global variable is of an array.
 825     GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue());
 826
 827   // Create the new global variable.  The contents of the malloc'd memory is
 828   // undefined, so initialize with an undef value.
 829   const Type *MAT = getMallocAllocatedType(CI);
 830   GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(),
 831                                              MAT, false,
 832                                              GlobalValue::InternalLinkage,
 833                                              UndefValue::get(MAT),
 834                                              GV->getName()+".body",
 835                                              GV,
 836                                              GV->isThreadLocal());
 837
 838   // If there are bitcast users of the malloc (which is typical, usually we have
 839   // a malloc + bitcast) then replace them with uses of the new global.  Update
 840   // other users to use the global as well.
 841   BitCastInst *TheBC = 0;
 842   while (!CI->use_empty()) {
 843     Instruction *User = cast<Instruction>(CI->use_back());
 844     if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
 845       if (BCI->getType() == NewGV->getType()) {
 846         BCI->replaceAllUsesWith(NewGV);
 847         BCI->eraseFromParent();
 848       } else {
 849         BCI->setOperand(0, NewGV);
 850       }
 851     } else {
 852       if (TheBC == 0)
 853         TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI);
 854       User->replaceUsesOfWith(CI, TheBC);
 855     }
 856   }
 857
 858   // Update Anything else that used the malloc or its bitcast now uses the global directly.
 859   CI->replaceAllUsesWith(new BitCastInst(NewGV, CI->getType(), "newgv", CI));
 860
 861   Constant *RepValue = NewGV;
 862   if (NewGV->getType() != GV->getType()->getElementType())
 863     RepValue = ConstantExpr::getBitCast(RepValue,
 864                                         GV->getType()->getElementType());
 865
 866   // If there is a comparison against null, we will insert a global bool to
 867   // keep track of whether the global was initialized yet or not.
 868   GlobalVariable *InitBool =
 869     new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
 870                        GlobalValue::InternalLinkage,
 871                        ConstantInt::getFalse(GV->getContext()),
 872                        GV->getName()+".init", GV->isThreadLocal());
 873   bool InitBoolUsed = false;
 874
 875   // Loop over all uses of GV, processing them in turn.
 876   while (!GV->use_empty()) {
 877     if (StoreInst *SI = dyn_cast<StoreInst>(GV->use_back())) {
 878       // The global is initialized when the store to it occurs.
 879       new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, SI);
 880       SI->eraseFromParent();
 881       continue;
 882     }
 883
 884     LoadInst *LI = cast<LoadInst>(GV->use_back());
 885     while (!LI->use_empty()) {
 886       Use &LoadUse = LI->use_begin().getUse();
 887       if (!isa<ICmpInst>(LoadUse.getUser())) {
 888         LoadUse = RepValue;
 889         continue;
 890       }
 891
 892       ICmpInst *ICI = cast<ICmpInst>(LoadUse.getUser());
 893       // Replace the cmp X, 0 with a use of the bool value.
 894       Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", ICI);
 895       InitBoolUsed = true;
 896       switch (ICI->getPredicate()) {
 897       default: llvm_unreachable("Unknown ICmp Predicate!");
 898       case ICmpInst::ICMP_ULT:
 899       case ICmpInst::ICMP_SLT:   // X < null -> always false
 900         LV = ConstantInt::getFalse(GV->getContext());
 901         break;
 902       case ICmpInst::ICMP_ULE:
 903       case ICmpInst::ICMP_SLE:
 904       case ICmpInst::ICMP_EQ:
 905         LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
 906         break;
 907       case ICmpInst::ICMP_NE:
 908       case ICmpInst::ICMP_UGE:
 909       case ICmpInst::ICMP_SGE:
 910       case ICmpInst::ICMP_UGT:
 911       case ICmpInst::ICMP_SGT:
 912         break;  // no change.
 913       }
 914       ICI->replaceAllUsesWith(LV);
 915       ICI->eraseFromParent();
 916     }
 917     LI->eraseFromParent();
 918   }
 919
 920   // If the initialization boolean was used, insert it, otherwise delete it.
 921   if (!InitBoolUsed) {
 922     while (!InitBool->use_empty())  // Delete initializations
 923       cast<StoreInst>(InitBool->use_back())->eraseFromParent();
 924     delete InitBool;
 925   } else
 926     GV->getParent()->getGlobalList().insert(GV, InitBool);
 927
 928   // Now the GV is dead, nuke it and the malloc..
 929   GV->eraseFromParent();
 930   CI->eraseFromParent();
 931
 932   // To further other optimizations, loop over all users of NewGV and try to
 933   // constant prop them.  This will promote GEP instructions with constant
 934   // indices into GEP constant-exprs, which will allow global-opt to hack on it.
 935   ConstantPropUsersOf(NewGV);
 936   if (RepValue != NewGV)
 937     ConstantPropUsersOf(RepValue);
 938
 939   return NewGV;
 940 }
 941
 942 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking
 943 /// to make sure that there are no complex uses of V.  We permit simple things
 944 /// like dereferencing the pointer, but not storing through the address, unless
 945 /// it is to the specified global.
 946 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Instruction *V,
 947                                                       GlobalVariable *GV,
 948                                               SmallPtrSet<PHINode*, 8> &PHIs) {
 949   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
 950     Instruction *Inst = cast<Instruction>(*UI);
 951
 952     if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) {
 953       continue; // Fine, ignore.
 954     }
 955
 956     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 957       if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
 958         return false;  // Storing the pointer itself... bad.
 959       continue; // Otherwise, storing through it, or storing into GV... fine.
 960     }
 961
 962     if (isa<GetElementPtrInst>(Inst)) {
 963       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs))
 964         return false;
 965       continue;
 966     }
 967
 968     if (PHINode *PN = dyn_cast<PHINode>(Inst)) {
 969       // PHIs are ok if all uses are ok.  Don't infinitely recurse through PHI
 970       // cycles.
 971       if (PHIs.insert(PN))
 972         if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs))
 973           return false;
 974       continue;
 975     }
 976
 977     if (BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) {
 978       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs))
 979         return false;
 980       continue;
 981     }
 982
 983     return false;
 984   }
 985   return true;
 986 }
 987
 988 /// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV
 989 /// somewhere.  Transform all uses of the allocation into loads from the
 990 /// global and uses of the resultant pointer.  Further, delete the store into
 991 /// GV.  This assumes that these value pass the
 992 /// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate.
 993 static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc,
 994                                           GlobalVariable *GV) {
 995   while (!Alloc->use_empty()) {
 996     Instruction *U = cast<Instruction>(*Alloc->use_begin());
 997     Instruction *InsertPt = U;
 998     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 999       // If this is the store of the allocation into the global, remove it.
1000       if (SI->getOperand(1) == GV) {
1001         SI->eraseFromParent();
1002         continue;
1003       }
1004     } else if (PHINode *PN = dyn_cast<PHINode>(U)) {
1005       // Insert the load in the corresponding predecessor, not right before the
1006       // PHI.
1007       InsertPt = PN->getIncomingBlock(Alloc->use_begin())->getTerminator();
1008     } else if (isa<BitCastInst>(U)) {
1009       // Must be bitcast between the malloc and store to initialize the global.
1010       ReplaceUsesOfMallocWithGlobal(U, GV);
1011       U->eraseFromParent();
1012       continue;
1013     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
1014       // If this is a "GEP bitcast" and the user is a store to the global, then
1015       // just process it as a bitcast.
1016       if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse())
1017         if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->use_back()))
1018           if (SI->getOperand(1) == GV) {
1019             // Must be bitcast GEP between the malloc and store to initialize
1020             // the global.
1021             ReplaceUsesOfMallocWithGlobal(GEPI, GV);
1022             GEPI->eraseFromParent();
1023             continue;
1024           }
1025     }
1026
1027     // Insert a load from the global, and use it instead of the malloc.
1028     Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt);
1029     U->replaceUsesOfWith(Alloc, NL);
1030   }
1031 }
1032
1033 /// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi
1034 /// of a load) are simple enough to perform heap SRA on.  This permits GEP's
1035 /// that index through the array and struct field, icmps of null, and PHIs.
1036 static bool LoadUsesSimpleEnoughForHeapSRA(Value *V,
1037                               SmallPtrSet<PHINode*, 32> &LoadUsingPHIs,
1038                               SmallPtrSet<PHINode*, 32> &LoadUsingPHIsPerLoad) {
1039   // We permit two users of the load: setcc comparing against the null
1040   // pointer, and a getelementptr of a specific form.
1041   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
1042     Instruction *User = cast<Instruction>(*UI);
1043
1044     // Comparison against null is ok.
1045     if (ICmpInst *ICI = dyn_cast<ICmpInst>(User)) {
1046       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
1047         return false;
1048       continue;
1049     }
1050
1051     // getelementptr is also ok, but only a simple form.
1052     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
1053       // Must index into the array and into the struct.
1054       if (GEPI->getNumOperands() < 3)
1055         return false;
1056
1057       // Otherwise the GEP is ok.
1058       continue;
1059     }
1060
1061     if (PHINode *PN = dyn_cast<PHINode>(User)) {
1062       if (!LoadUsingPHIsPerLoad.insert(PN))
1063         // This means some phi nodes are dependent on each other.
1064         // Avoid infinite looping!
1065         return false;
1066       if (!LoadUsingPHIs.insert(PN))
1067         // If we have already analyzed this PHI, then it is safe.
1068         continue;
1069
1070       // Make sure all uses of the PHI are simple enough to transform.
1071       if (!LoadUsesSimpleEnoughForHeapSRA(PN,
1072                                           LoadUsingPHIs, LoadUsingPHIsPerLoad))
1073         return false;
1074
1075       continue;
1076     }
1077
1078     // Otherwise we don't know what this is, not ok.
1079     return false;
1080   }
1081
1082   return true;
1083 }
1084
1085
1086 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from
1087 /// GV are simple enough to perform HeapSRA, return true.
1088 static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV,
1089                                                     Instruction *StoredVal) {
1090   SmallPtrSet<PHINode*, 32> LoadUsingPHIs;
1091   SmallPtrSet<PHINode*, 32> LoadUsingPHIsPerLoad;
1092   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;
1093        ++UI)
1094     if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
1095       if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs,
1096                                           LoadUsingPHIsPerLoad))
1097         return false;
1098       LoadUsingPHIsPerLoad.clear();
1099     }
1100
1101   // If we reach here, we know that all uses of the loads and transitive uses
1102   // (through PHI nodes) are simple enough to transform.  However, we don't know
1103   // that all inputs the to the PHI nodes are in the same equivalence sets.
1104   // Check to verify that all operands of the PHIs are either PHIS that can be
1105   // transformed, loads from GV, or MI itself.
1106   for (SmallPtrSet<PHINode*, 32>::iterator I = LoadUsingPHIs.begin(),
1107        E = LoadUsingPHIs.end(); I != E; ++I) {
1108     PHINode *PN = *I;
1109     for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) {
1110       Value *InVal = PN->getIncomingValue(op);
1111
1112       // PHI of the stored value itself is ok.
1113       if (InVal == StoredVal) continue;
1114
1115       if (PHINode *InPN = dyn_cast<PHINode>(InVal)) {
1116         // One of the PHIs in our set is (optimistically) ok.
1117         if (LoadUsingPHIs.count(InPN))
1118           continue;
1119         return false;
1120       }
1121
1122       // Load from GV is ok.
1123       if (LoadInst *LI = dyn_cast<LoadInst>(InVal))
1124         if (LI->getOperand(0) == GV)
1125           continue;
1126
1127       // UNDEF? NULL?
1128
1129       // Anything else is rejected.
1130       return false;
1131     }
1132   }
1133
1134   return true;
1135 }
1136
1137 static Value *GetHeapSROAValue(Value *V, unsigned FieldNo,
1138                DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1139                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1140   std::vector<Value*> &FieldVals = InsertedScalarizedValues[V];
1141
1142   if (FieldNo >= FieldVals.size())
1143     FieldVals.resize(FieldNo+1);
1144
1145   // If we already have this value, just reuse the previously scalarized
1146   // version.
1147   if (Value *FieldVal = FieldVals[FieldNo])
1148     return FieldVal;
1149
1150   // Depending on what instruction this is, we have several cases.
1151   Value *Result;
1152   if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
1153     // This is a scalarized version of the load from the global.  Just create
1154     // a new Load of the scalarized global.
1155     Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo,
1156                                            InsertedScalarizedValues,
1157                                            PHIsToRewrite),
1158                           LI->getName()+".f"+Twine(FieldNo), LI);
1159   } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
1160     // PN's type is pointer to struct.  Make a new PHI of pointer to struct
1161     // field.
1162     const StructType *ST =
1163       cast<StructType>(cast<PointerType>(PN->getType())->getElementType());
1164
1165     Result =
1166      PHINode::Create(PointerType::getUnqual(ST->getElementType(FieldNo)),
1167                      PN->getName()+".f"+Twine(FieldNo), PN);
1168     PHIsToRewrite.push_back(std::make_pair(PN, FieldNo));
1169   } else {
1170     llvm_unreachable("Unknown usable value");
1171     Result = 0;
1172   }
1173
1174   return FieldVals[FieldNo] = Result;
1175 }
1176
1177 /// RewriteHeapSROALoadUser - Given a load instruction and a value derived from
1178 /// the load, rewrite the derived value to use the HeapSRoA'd load.
1179 static void RewriteHeapSROALoadUser(Instruction *LoadUser,
1180              DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1181                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1182   // If this is a comparison against null, handle it.
1183   if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) {
1184     assert(isa<ConstantPointerNull>(SCI->getOperand(1)));
1185     // If we have a setcc of the loaded pointer, we can use a setcc of any
1186     // field.
1187     Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0,
1188                                    InsertedScalarizedValues, PHIsToRewrite);
1189
1190     Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr,
1191                               Constant::getNullValue(NPtr->getType()),
1192                               SCI->getName());
1193     SCI->replaceAllUsesWith(New);
1194     SCI->eraseFromParent();
1195     return;
1196   }
1197
1198   // Handle 'getelementptr Ptr, Idx, i32 FieldNo ...'
1199   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) {
1200     assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2))
1201            && "Unexpected GEPI!");
1202
1203     // Load the pointer for this field.
1204     unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue();
1205     Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo,
1206                                      InsertedScalarizedValues, PHIsToRewrite);
1207
1208     // Create the new GEP idx vector.
1209     SmallVector<Value*, 8> GEPIdx;
1210     GEPIdx.push_back(GEPI->getOperand(1));
1211     GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end());
1212
1213     Value *NGEPI = GetElementPtrInst::Create(NewPtr,
1214                                              GEPIdx.begin(), GEPIdx.end(),
1215                                              GEPI->getName(), GEPI);
1216     GEPI->replaceAllUsesWith(NGEPI);
1217     GEPI->eraseFromParent();
1218     return;
1219   }
1220
1221   // Recursively transform the users of PHI nodes.  This will lazily create the
1222   // PHIs that are needed for individual elements.  Keep track of what PHIs we
1223   // see in InsertedScalarizedValues so that we don't get infinite loops (very
1224   // antisocial).  If the PHI is already in InsertedScalarizedValues, it has
1225   // already been seen first by another load, so its uses have already been
1226   // processed.
1227   PHINode *PN = cast<PHINode>(LoadUser);
1228   bool Inserted;
1229   DenseMap<Value*, std::vector<Value*> >::iterator InsertPos;
1230   tie(InsertPos, Inserted) =
1231     InsertedScalarizedValues.insert(std::make_pair(PN, std::vector<Value*>()));
1232   if (!Inserted) return;
1233
1234   // If this is the first time we've seen this PHI, recursively process all
1235   // users.
1236   for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; ) {
1237     Instruction *User = cast<Instruction>(*UI++);
1238     RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
1239   }
1240 }
1241
1242 /// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global.  Ptr
1243 /// is a value loaded from the global.  Eliminate all uses of Ptr, making them
1244 /// use FieldGlobals instead.  All uses of loaded values satisfy
1245 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA.
1246 static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load,
1247                DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1248                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1249   for (Value::use_iterator UI = Load->use_begin(), E = Load->use_end();
1250        UI != E; ) {
1251     Instruction *User = cast<Instruction>(*UI++);
1252     RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
1253   }
1254
1255   if (Load->use_empty()) {
1256     Load->eraseFromParent();
1257     InsertedScalarizedValues.erase(Load);
1258   }
1259 }
1260
1261 /// PerformHeapAllocSRoA - CI is an allocation of an array of structures.  Break
1262 /// it up into multiple allocations of arrays of the fields.
1263 static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI,
1264                                             Value* NElems, TargetData *TD) {
1265   DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV << "  MALLOC = " << *CI << '\n');
1266   const Type* MAT = getMallocAllocatedType(CI);
1267   const StructType *STy = cast<StructType>(MAT);
1268
1269   // There is guaranteed to be at least one use of the malloc (storing
1270   // it into GV).  If there are other uses, change them to be uses of
1271   // the global to simplify later code.  This also deletes the store
1272   // into GV.
1273   ReplaceUsesOfMallocWithGlobal(CI, GV);
1274
1275   // Okay, at this point, there are no users of the malloc.  Insert N
1276   // new mallocs at the same place as CI, and N globals.
1277   std::vector<Value*> FieldGlobals;
1278   std::vector<Value*> FieldMallocs;
1279
1280   for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){
1281     const Type *FieldTy = STy->getElementType(FieldNo);
1282     const PointerType *PFieldTy = PointerType::getUnqual(FieldTy);
1283
1284     GlobalVariable *NGV =
1285       new GlobalVariable(*GV->getParent(),
1286                          PFieldTy, false, GlobalValue::InternalLinkage,
1287                          Constant::getNullValue(PFieldTy),
1288                          GV->getName() + ".f" + Twine(FieldNo), GV,
1289                          GV->isThreadLocal());
1290     FieldGlobals.push_back(NGV);
1291
1292     unsigned TypeSize = TD->getTypeAllocSize(FieldTy);
1293     if (const StructType *ST = dyn_cast<StructType>(FieldTy))
1294       TypeSize = TD->getStructLayout(ST)->getSizeInBytes();
1295     const Type *IntPtrTy = TD->getIntPtrType(CI->getContext());
1296     Value *NMI = CallInst::CreateMalloc(CI, IntPtrTy, FieldTy,
1297                                         ConstantInt::get(IntPtrTy, TypeSize),
1298                                         NElems,
1299                                         CI->getName() + ".f" + Twine(FieldNo));
1300     CallInst *NCI = dyn_cast<BitCastInst>(NMI) ?
1301                     extractMallocCallFromBitCast(NMI) : cast<CallInst>(NMI);
1302     FieldMallocs.push_back(NCI);
1303     new StoreInst(NMI, NGV, CI);
1304   }
1305
1306   // The tricky aspect of this transformation is handling the case when malloc
1307   // fails.  In the original code, malloc failing would set the result pointer
1308   // of malloc to null.  In this case, some mallocs could succeed and others
1309   // could fail.  As such, we emit code that looks like this:
1310   //    F0 = malloc(field0)
1311   //    F1 = malloc(field1)
1312   //    F2 = malloc(field2)
1313   //    if (F0 == 0 || F1 == 0 || F2 == 0) {
1314   //      if (F0) { free(F0); F0 = 0; }
1315   //      if (F1) { free(F1); F1 = 0; }
1316   //      if (F2) { free(F2); F2 = 0; }
1317   //    }
1318   // The malloc can also fail if its argument is too large.
1319   Constant *ConstantZero = ConstantInt::get(CI->getOperand(1)->getType(), 0);
1320   Value *RunningOr = new ICmpInst(CI, ICmpInst::ICMP_SLT, CI->getOperand(1),
1321                                   ConstantZero, "isneg");
1322   for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) {
1323     Value *Cond = new ICmpInst(CI, ICmpInst::ICMP_EQ, FieldMallocs[i],
1324                              Constant::getNullValue(FieldMallocs[i]->getType()),
1325                                "isnull");
1326     RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI);
1327   }
1328
1329   // Split the basic block at the old malloc.
1330   BasicBlock *OrigBB = CI->getParent();
1331   BasicBlock *ContBB = OrigBB->splitBasicBlock(CI, "malloc_cont");
1332
1333   // Create the block to check the first condition.  Put all these blocks at the
1334   // end of the function as they are unlikely to be executed.
1335   BasicBlock *NullPtrBlock = BasicBlock::Create(OrigBB->getContext(),
1336                                                 "malloc_ret_null",
1337                                                 OrigBB->getParent());
1338
1339   // Remove the uncond branch from OrigBB to ContBB, turning it into a cond
1340   // branch on RunningOr.
1341   OrigBB->getTerminator()->eraseFromParent();
1342   BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB);
1343
1344   // Within the NullPtrBlock, we need to emit a comparison and branch for each
1345   // pointer, because some may be null while others are not.
1346   for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1347     Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock);
1348     Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal,
1349                               Constant::getNullValue(GVVal->getType()),
1350                               "tmp");
1351     BasicBlock *FreeBlock = BasicBlock::Create(Cmp->getContext(), "free_it",
1352                                                OrigBB->getParent());
1353     BasicBlock *NextBlock = BasicBlock::Create(Cmp->getContext(), "next",
1354                                                OrigBB->getParent());
1355     Instruction *BI = BranchInst::Create(FreeBlock, NextBlock,
1356                                          Cmp, NullPtrBlock);
1357
1358     // Fill in FreeBlock.
1359     CallInst::CreateFree(GVVal, BI);
1360     new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i],
1361                   FreeBlock);
1362     BranchInst::Create(NextBlock, FreeBlock);
1363
1364     NullPtrBlock = NextBlock;
1365   }
1366
1367   BranchInst::Create(ContBB, NullPtrBlock);
1368
1369   // CI is no longer needed, remove it.
1370   CI->eraseFromParent();
1371
1372   /// InsertedScalarizedLoads - As we process loads, if we can't immediately
1373   /// update all uses of the load, keep track of what scalarized loads are
1374   /// inserted for a given load.
1375   DenseMap<Value*, std::vector<Value*> > InsertedScalarizedValues;
1376   InsertedScalarizedValues[GV] = FieldGlobals;
1377
1378   std::vector<std::pair<PHINode*, unsigned> > PHIsToRewrite;
1379
1380   // Okay, the malloc site is completely handled.  All of the uses of GV are now
1381   // loads, and all uses of those loads are simple.  Rewrite them to use loads
1382   // of the per-field globals instead.
1383   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;) {
1384     Instruction *User = cast<Instruction>(*UI++);
1385
1386     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
1387       RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite);
1388       continue;
1389     }
1390
1391     // Must be a store of null.
1392     StoreInst *SI = cast<StoreInst>(User);
1393     assert(isa<ConstantPointerNull>(SI->getOperand(0)) &&
1394            "Unexpected heap-sra user!");
1395
1396     // Insert a store of null into each global.
1397     for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1398       const PointerType *PT = cast<PointerType>(FieldGlobals[i]->getType());
1399       Constant *Null = Constant::getNullValue(PT->getElementType());
1400       new StoreInst(Null, FieldGlobals[i], SI);
1401     }
1402     // Erase the original store.
1403     SI->eraseFromParent();
1404   }
1405
1406   // While we have PHIs that are interesting to rewrite, do it.
1407   while (!PHIsToRewrite.empty()) {
1408     PHINode *PN = PHIsToRewrite.back().first;
1409     unsigned FieldNo = PHIsToRewrite.back().second;
1410     PHIsToRewrite.pop_back();
1411     PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]);
1412     assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi");
1413
1414     // Add all the incoming values.  This can materialize more phis.
1415     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1416       Value *InVal = PN->getIncomingValue(i);
1417       InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues,
1418                                PHIsToRewrite);
1419       FieldPN->addIncoming(InVal, PN->getIncomingBlock(i));
1420     }
1421   }
1422
1423   // Drop all inter-phi links and any loads that made it this far.
1424   for (DenseMap<Value*, std::vector<Value*> >::iterator
1425        I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
1426        I != E; ++I) {
1427     if (PHINode *PN = dyn_cast<PHINode>(I->first))
1428       PN->dropAllReferences();
1429     else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
1430       LI->dropAllReferences();
1431   }
1432
1433   // Delete all the phis and loads now that inter-references are dead.
1434   for (DenseMap<Value*, std::vector<Value*> >::iterator
1435        I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
1436        I != E; ++I) {
1437     if (PHINode *PN = dyn_cast<PHINode>(I->first))
1438       PN->eraseFromParent();
1439     else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
1440       LI->eraseFromParent();
1441   }
1442
1443   // The old global is now dead, remove it.
1444   GV->eraseFromParent();
1445
1446   ++NumHeapSRA;
1447   return cast<GlobalVariable>(FieldGlobals[0]);
1448 }
1449
1450 /// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a
1451 /// pointer global variable with a single value stored it that is a malloc or
1452 /// cast of malloc.
1453 static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV,
1454                                                CallInst *CI,
1455                                                const Type *AllocTy,
1456                                                Module::global_iterator &GVI,
1457                                                TargetData *TD) {
1458   // If this is a malloc of an abstract type, don't touch it.
1459   if (!AllocTy->isSized())
1460     return false;
1461
1462   // We can't optimize this global unless all uses of it are *known* to be
1463   // of the malloc value, not of the null initializer value (consider a use
1464   // that compares the global's value against zero to see if the malloc has
1465   // been reached).  To do this, we check to see if all uses of the global
1466   // would trap if the global were null: this proves that they must all
1467   // happen after the malloc.
1468   if (!AllUsesOfLoadedValueWillTrapIfNull(GV))
1469     return false;
1470
1471   // We can't optimize this if the malloc itself is used in a complex way,
1472   // for example, being stored into multiple globals.  This allows the
1473   // malloc to be stored into the specified global, loaded setcc'd, and
1474   // GEP'd.  These are all things we could transform to using the global
1475   // for.
1476   {
1477     SmallPtrSet<PHINode*, 8> PHIs;
1478     if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV, PHIs))
1479       return false;
1480   }
1481
1482   // If we have a global that is only initialized with a fixed size malloc,
1483   // transform the program to use global memory instead of malloc'd memory.
1484   // This eliminates dynamic allocation, avoids an indirection accessing the
1485   // data, and exposes the resultant global to further GlobalOpt.
1486   // We cannot optimize the malloc if we cannot determine malloc array size.
1487   if (Value *NElems = getMallocArraySize(CI, TD, true)) {
1488     if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems))
1489       // Restrict this transformation to only working on small allocations
1490       // (2048 bytes currently), as we don't want to introduce a 16M global or
1491       // something.
1492       if (TD &&
1493           NElements->getZExtValue() * TD->getTypeAllocSize(AllocTy) < 2048) {
1494         GVI = OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, TD);
1495         return true;
1496       }
1497
1498     // If the allocation is an array of structures, consider transforming this
1499     // into multiple malloc'd arrays, one for each field.  This is basically
1500     // SRoA for malloc'd memory.
1501
1502     // If this is an allocation of a fixed size array of structs, analyze as a
1503     // variable size array.  malloc [100 x struct],1 -> malloc struct, 100
1504     if (NElems == ConstantInt::get(CI->getOperand(1)->getType(), 1))
1505       if (const ArrayType *AT = dyn_cast<ArrayType>(AllocTy))
1506         AllocTy = AT->getElementType();
1507
1508     if (const StructType *AllocSTy = dyn_cast<StructType>(AllocTy)) {
1509       // This the structure has an unreasonable number of fields, leave it
1510       // alone.
1511       if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 &&
1512           AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV, CI)) {
1513
1514         // If this is a fixed size array, transform the Malloc to be an alloc of
1515         // structs.  malloc [100 x struct],1 -> malloc struct, 100
1516         if (const ArrayType *AT =
1517                               dyn_cast<ArrayType>(getMallocAllocatedType(CI))) {
1518           const Type *IntPtrTy = TD->getIntPtrType(CI->getContext());
1519           unsigned TypeSize = TD->getStructLayout(AllocSTy)->getSizeInBytes();
1520           Value *AllocSize = ConstantInt::get(IntPtrTy, TypeSize);
1521           Value *NumElements = ConstantInt::get(IntPtrTy, AT->getNumElements());
1522           Instruction *Malloc = CallInst::CreateMalloc(CI, IntPtrTy, AllocSTy,
1523                                                        AllocSize, NumElements,
1524                                                        CI->getName());
1525           Instruction *Cast = new BitCastInst(Malloc, CI->getType(), "tmp", CI);
1526           CI->replaceAllUsesWith(Cast);
1527           CI->eraseFromParent();
1528           CI = dyn_cast<BitCastInst>(Malloc) ?
1529                extractMallocCallFromBitCast(Malloc) : cast<CallInst>(Malloc);
1530         }
1531
1532         GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, TD, true),TD);
1533         return true;
1534       }
1535     }
1536   }
1537
1538   return false;
1539 }
1540
1541 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge
1542 // that only one value (besides its initializer) is ever stored to the global.
1543 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
1544                                      Module::global_iterator &GVI,
1545                                      TargetData *TD) {
1546   // Ignore no-op GEPs and bitcasts.
1547   StoredOnceVal = StoredOnceVal->stripPointerCasts();
1548
1549   // If we are dealing with a pointer global that is initialized to null and
1550   // only has one (non-null) value stored into it, then we can optimize any
1551   // users of the loaded value (often calls and loads) that would trap if the
1552   // value was null.
1553   if (GV->getInitializer()->getType()->isPointerTy() &&
1554       GV->getInitializer()->isNullValue()) {
1555     if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
1556       if (GV->getInitializer()->getType() != SOVC->getType())
1557         SOVC =
1558          ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
1559
1560       // Optimize away any trapping uses of the loaded value.
1561       if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC))
1562         return true;
1563     } else if (CallInst *CI = extractMallocCall(StoredOnceVal)) {
1564       const Type* MallocType = getMallocAllocatedType(CI);
1565       if (MallocType && TryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType,
1566                                                            GVI, TD))
1567         return true;
1568     }
1569   }
1570
1571   return false;
1572 }
1573
1574 /// TryToShrinkGlobalToBoolean - At this point, we have learned that the only
1575 /// two values ever stored into GV are its initializer and OtherVal.  See if we
1576 /// can shrink the global into a boolean and select between the two values
1577 /// whenever it is used.  This exposes the values to other scalar optimizations.
1578 static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
1579   const Type *GVElType = GV->getType()->getElementType();
1580
1581   // If GVElType is already i1, it is already shrunk.  If the type of the GV is
1582   // an FP value, pointer or vector, don't do this optimization because a select
1583   // between them is very expensive and unlikely to lead to later
1584   // simplification.  In these cases, we typically end up with "cond ? v1 : v2"
1585   // where v1 and v2 both require constant pool loads, a big loss.
1586   if (GVElType == Type::getInt1Ty(GV->getContext()) ||
1587       GVElType->isFloatingPointTy() ||
1588       GVElType->isPointerTy() || GVElType->isVectorTy())
1589     return false;
1590
1591   // Walk the use list of the global seeing if all the uses are load or store.
1592   // If there is anything else, bail out.
1593   for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I)
1594     if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
1595       return false;
1596
1597   DEBUG(dbgs() << "   *** SHRINKING TO BOOL: " << *GV);
1598
1599   // Create the new global, initializing it to false.
1600   GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(GV->getContext()),
1601                                              false,
1602                                              GlobalValue::InternalLinkage,
1603                                         ConstantInt::getFalse(GV->getContext()),
1604                                              GV->getName()+".b",
1605                                              GV->isThreadLocal());
1606   GV->getParent()->getGlobalList().insert(GV, NewGV);
1607
1608   Constant *InitVal = GV->getInitializer();
1609   assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) &&
1610          "No reason to shrink to bool!");
1611
1612   // If initialized to zero and storing one into the global, we can use a cast
1613   // instead of a select to synthesize the desired value.
1614   bool IsOneZero = false;
1615   if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal))
1616     IsOneZero = InitVal->isNullValue() && CI->isOne();
1617
1618   while (!GV->use_empty()) {
1619     Instruction *UI = cast<Instruction>(GV->use_back());
1620     if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
1621       // Change the store into a boolean store.
1622       bool StoringOther = SI->getOperand(0) == OtherVal;
1623       // Only do this if we weren't storing a loaded value.
1624       Value *StoreVal;
1625       if (StoringOther || SI->getOperand(0) == InitVal)
1626         StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()),
1627                                     StoringOther);
1628       else {
1629         // Otherwise, we are storing a previously loaded copy.  To do this,
1630         // change the copy from copying the original value to just copying the
1631         // bool.
1632         Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
1633
1634         // If we're already replaced the input, StoredVal will be a cast or
1635         // select instruction.  If not, it will be a load of the original
1636         // global.
1637         if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
1638           assert(LI->getOperand(0) == GV && "Not a copy!");
1639           // Insert a new load, to preserve the saved value.
1640           StoreVal = new LoadInst(NewGV, LI->getName()+".b", LI);
1641         } else {
1642           assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&
1643                  "This is not a form that we understand!");
1644           StoreVal = StoredVal->getOperand(0);
1645           assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!");
1646         }
1647       }
1648       new StoreInst(StoreVal, NewGV, SI);
1649     } else {
1650       // Change the load into a load of bool then a select.
1651       LoadInst *LI = cast<LoadInst>(UI);
1652       LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", LI);
1653       Value *NSI;
1654       if (IsOneZero)
1655         NSI = new ZExtInst(NLI, LI->getType(), "", LI);
1656       else
1657         NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
1658       NSI->takeName(LI);
1659       LI->replaceAllUsesWith(NSI);
1660     }
1661     UI->eraseFromParent();
1662   }
1663
1664   GV->eraseFromParent();
1665   return true;
1666 }
1667
1668
1669 /// ProcessInternalGlobal - Analyze the specified global variable and optimize
1670 /// it if possible.  If we make a change, return true.
1671 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
1672                                       Module::global_iterator &GVI) {
1673   SmallPtrSet<PHINode*, 16> PHIUsers;
1674   GlobalStatus GS;
1675   GV->removeDeadConstantUsers();
1676
1677   if (GV->use_empty()) {
1678     DEBUG(dbgs() << "GLOBAL DEAD: " << *GV);
1679     GV->eraseFromParent();
1680     ++NumDeleted;
1681     return true;
1682   }
1683
1684   if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
1685 #if 0
1686     DEBUG(dbgs() << "Global: " << *GV);
1687     DEBUG(dbgs() << "  isLoaded = " << GS.isLoaded << "\n");
1688     DEBUG(dbgs() << "  StoredType = ");
1689     switch (GS.StoredType) {
1690     case GlobalStatus::NotStored: DEBUG(dbgs() << "NEVER STORED\n"); break;
1691     case GlobalStatus::isInitializerStored: DEBUG(dbgs() << "INIT STORED\n");
1692                                             break;
1693     case GlobalStatus::isStoredOnce: DEBUG(dbgs() << "STORED ONCE\n"); break;
1694     case GlobalStatus::isStored: DEBUG(dbgs() << "stored\n"); break;
1695     }
1696     if (GS.StoredType == GlobalStatus::isStoredOnce && GS.StoredOnceValue)
1697       DEBUG(dbgs() << "  StoredOnceValue = " << *GS.StoredOnceValue << "\n");
1698     if (GS.AccessingFunction && !GS.HasMultipleAccessingFunctions)
1699       DEBUG(dbgs() << "  AccessingFunction = " << GS.AccessingFunction->getName()
1700                   << "\n");
1701     DEBUG(dbgs() << "  HasMultipleAccessingFunctions =  "
1702                  << GS.HasMultipleAccessingFunctions << "\n");
1703     DEBUG(dbgs() << "  HasNonInstructionUser = "
1704                  << GS.HasNonInstructionUser<<"\n");
1705     DEBUG(dbgs() << "\n");
1706 #endif
1707
1708     // If this is a first class global and has only one accessing function
1709     // and this function is main (which we know is not recursive we can make
1710     // this global a local variable) we replace the global with a local alloca
1711     // in this function.
1712     //
1713     // NOTE: It doesn't make sense to promote non single-value types since we
1714     // are just replacing static memory to stack memory.
1715     //
1716     // If the global is in different address space, don't bring it to stack.
1717     if (!GS.HasMultipleAccessingFunctions &&
1718         GS.AccessingFunction && !GS.HasNonInstructionUser &&
1719         GV->getType()->getElementType()->isSingleValueType() &&
1720         GS.AccessingFunction->getName() == "main" &&
1721         GS.AccessingFunction->hasExternalLinkage() &&
1722         GV->getType()->getAddressSpace() == 0) {
1723       DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV);
1724       Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin();
1725       const Type* ElemTy = GV->getType()->getElementType();
1726       // FIXME: Pass Global's alignment when globals have alignment
1727       AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), FirstI);
1728       if (!isa<UndefValue>(GV->getInitializer()))
1729         new StoreInst(GV->getInitializer(), Alloca, FirstI);
1730
1731       GV->replaceAllUsesWith(Alloca);
1732       GV->eraseFromParent();
1733       ++NumLocalized;
1734       return true;
1735     }
1736
1737     // If the global is never loaded (but may be stored to), it is dead.
1738     // Delete it now.
1739     if (!GS.isLoaded) {
1740       DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV);
1741
1742       // Delete any stores we can find to the global.  We may not be able to
1743       // make it completely dead though.
1744       bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer());
1745
1746       // If the global is dead now, delete it.
1747       if (GV->use_empty()) {
1748         GV->eraseFromParent();
1749         ++NumDeleted;
1750         Changed = true;
1751       }
1752       return Changed;
1753
1754     } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
1755       DEBUG(dbgs() << "MARKING CONSTANT: " << *GV);
1756       GV->setConstant(true);
1757
1758       // Clean up any obviously simplifiable users now.
1759       CleanupConstantGlobalUsers(GV, GV->getInitializer());
1760
1761       // If the global is dead now, just nuke it.
1762       if (GV->use_empty()) {
1763         DEBUG(dbgs() << "   *** Marking constant allowed us to simplify "
1764                      << "all users and delete global!\n");
1765         GV->eraseFromParent();
1766         ++NumDeleted;
1767       }
1768
1769       ++NumMarked;
1770       return true;
1771     } else if (!GV->getInitializer()->getType()->isSingleValueType()) {
1772       if (TargetData *TD = getAnalysisIfAvailable<TargetData>())
1773         if (GlobalVariable *FirstNewGV = SRAGlobal(GV, *TD)) {
1774           GVI = FirstNewGV;  // Don't skip the newly produced globals!
1775           return true;
1776         }
1777     } else if (GS.StoredType == GlobalStatus::isStoredOnce) {
1778       // If the initial value for the global was an undef value, and if only
1779       // one other value was stored into it, we can just change the
1780       // initializer to be the stored value, then delete all stores to the
1781       // global.  This allows us to mark it constant.
1782       if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
1783         if (isa<UndefValue>(GV->getInitializer())) {
1784           // Change the initial value here.
1785           GV->setInitializer(SOVConstant);
1786
1787           // Clean up any obviously simplifiable users now.
1788           CleanupConstantGlobalUsers(GV, GV->getInitializer());
1789
1790           if (GV->use_empty()) {
1791             DEBUG(dbgs() << "   *** Substituting initializer allowed us to "
1792                          << "simplify all users and delete global!\n");
1793             GV->eraseFromParent();
1794             ++NumDeleted;
1795           } else {
1796             GVI = GV;
1797           }
1798           ++NumSubstitute;
1799           return true;
1800         }
1801
1802       // Try to optimize globals based on the knowledge that only one value
1803       // (besides its initializer) is ever stored to the global.
1804       if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GVI,
1805                                    getAnalysisIfAvailable<TargetData>()))
1806         return true;
1807
1808       // Otherwise, if the global was not a boolean, we can shrink it to be a
1809       // boolean.
1810       if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
1811         if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
1812           ++NumShrunkToBool;
1813           return true;
1814         }
1815     }
1816   }
1817   return false;
1818 }
1819
1820 /// ChangeCalleesToFastCall - Walk all of the direct calls of the specified
1821 /// function, changing them to FastCC.
1822 static void ChangeCalleesToFastCall(Function *F) {
1823   for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){
1824     CallSite User(cast<Instruction>(*UI));
1825     User.setCallingConv(CallingConv::Fast);
1826   }
1827 }
1828
1829 static AttrListPtr StripNest(const AttrListPtr &Attrs) {
1830   for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) {
1831     if ((Attrs.getSlot(i).Attrs & Attribute::Nest) == 0)
1832       continue;
1833
1834     // There can be only one.
1835     return Attrs.removeAttr(Attrs.getSlot(i).Index, Attribute::Nest);
1836   }
1837
1838   return Attrs;
1839 }
1840
1841 static void RemoveNestAttribute(Function *F) {
1842   F->setAttributes(StripNest(F->getAttributes()));
1843   for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){
1844     CallSite User(cast<Instruction>(*UI));
1845     User.setAttributes(StripNest(User.getAttributes()));
1846   }
1847 }
1848
1849 bool GlobalOpt::OptimizeFunctions(Module &M) {
1850   bool Changed = false;
1851   // Optimize functions.
1852   for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
1853     Function *F = FI++;
1854     // Functions without names cannot be referenced outside this module.
1855     if (!F->hasName() && !F->isDeclaration())
1856       F->setLinkage(GlobalValue::InternalLinkage);
1857     F->removeDeadConstantUsers();
1858     if (F->use_empty() && (F->hasLocalLinkage() || F->hasLinkOnceLinkage())) {
1859       F->eraseFromParent();
1860       Changed = true;
1861       ++NumFnDeleted;
1862     } else if (F->hasLocalLinkage()) {
1863       if (F->getCallingConv() == CallingConv::C && !F->isVarArg() &&
1864           !F->hasAddressTaken()) {
1865         // If this function has C calling conventions, is not a varargs
1866         // function, and is only called directly, promote it to use the Fast
1867         // calling convention.
1868         F->setCallingConv(CallingConv::Fast);
1869         ChangeCalleesToFastCall(F);
1870         ++NumFastCallFns;
1871         Changed = true;
1872       }
1873
1874       if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) &&
1875           !F->hasAddressTaken()) {
1876         // The function is not used by a trampoline intrinsic, so it is safe
1877         // to remove the 'nest' attribute.
1878         RemoveNestAttribute(F);
1879         ++NumNestRemoved;
1880         Changed = true;
1881       }
1882     }
1883   }
1884   return Changed;
1885 }
1886
1887 bool GlobalOpt::OptimizeGlobalVars(Module &M) {
1888   bool Changed = false;
1889   for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
1890        GVI != E; ) {
1891     GlobalVariable *GV = GVI++;
1892     // Global variables without names cannot be referenced outside this module.
1893     if (!GV->hasName() && !GV->isDeclaration())
1894       GV->setLinkage(GlobalValue::InternalLinkage);
1895     // Simplify the initializer.
1896     if (GV->hasInitializer())
1897       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GV->getInitializer())) {
1898         TargetData *TD = getAnalysisIfAvailable<TargetData>();
1899         Constant *New = ConstantFoldConstantExpression(CE, TD);
1900         if (New && New != CE)
1901           GV->setInitializer(New);
1902       }
1903     // Do more involved optimizations if the global is internal.
1904     if (!GV->isConstant() && GV->hasLocalLinkage() &&
1905         GV->hasInitializer())
1906       Changed |= ProcessInternalGlobal(GV, GVI);
1907   }
1908   return Changed;
1909 }
1910
1911 /// FindGlobalCtors - Find the llvm.globalctors list, verifying that all
1912 /// initializers have an init priority of 65535.
1913 GlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) {
1914   for (Module::global_iterator I = M.global_begin(), E = M.global_end();
1915        I != E; ++I)
1916     if (I->getName() == "llvm.global_ctors") {
1917       // Found it, verify it's an array of { int, void()* }.
1918       const ArrayType *ATy =dyn_cast<ArrayType>(I->getType()->getElementType());
1919       if (!ATy) return 0;
1920       const StructType *STy = dyn_cast<StructType>(ATy->getElementType());
1921       if (!STy || STy->getNumElements() != 2 ||
1922           !STy->getElementType(0)->isIntegerTy(32)) return 0;
1923       const PointerType *PFTy = dyn_cast<PointerType>(STy->getElementType(1));
1924       if (!PFTy) return 0;
1925       const FunctionType *FTy = dyn_cast<FunctionType>(PFTy->getElementType());
1926       if (!FTy || !FTy->getReturnType()->isVoidTy() ||
1927           FTy->isVarArg() || FTy->getNumParams() != 0)
1928         return 0;
1929
1930       // Verify that the initializer is simple enough for us to handle.
1931       if (!I->hasDefinitiveInitializer()) return 0;
1932       ConstantArray *CA = dyn_cast<ConstantArray>(I->getInitializer());
1933       if (!CA) return 0;
1934       for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i)
1935         if (ConstantStruct *CS = dyn_cast<ConstantStruct>(*i)) {
1936           if (isa<ConstantPointerNull>(CS->getOperand(1)))
1937             continue;
1938
1939           // Must have a function or null ptr.
1940           if (!isa<Function>(CS->getOperand(1)))
1941             return 0;
1942
1943           // Init priority must be standard.
1944           ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0));
1945           if (!CI || CI->getZExtValue() != 65535)
1946             return 0;
1947         } else {
1948           return 0;
1949         }
1950
1951       return I;
1952     }
1953   return 0;
1954 }
1955
1956 /// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand,
1957 /// return a list of the functions and null terminator as a vector.
1958 static std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) {
1959   ConstantArray *CA = cast<ConstantArray>(GV->getInitializer());
1960   std::vector<Function*> Result;
1961   Result.reserve(CA->getNumOperands());
1962   for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) {
1963     ConstantStruct *CS = cast<ConstantStruct>(*i);
1964     Result.push_back(dyn_cast<Function>(CS->getOperand(1)));
1965   }
1966   return Result;
1967 }
1968
1969 /// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the
1970 /// specified array, returning the new global to use.
1971 static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL,
1972                                           const std::vector<Function*> &Ctors) {
1973   // If we made a change, reassemble the initializer list.
1974   std::vector<Constant*> CSVals;
1975   CSVals.push_back(ConstantInt::get(Type::getInt32Ty(GCL->getContext()),65535));
1976   CSVals.push_back(0);
1977
1978   // Create the new init list.
1979   std::vector<Constant*> CAList;
1980   for (unsigned i = 0, e = Ctors.size(); i != e; ++i) {
1981     if (Ctors[i]) {
1982       CSVals[1] = Ctors[i];
1983     } else {
1984       const Type *FTy = FunctionType::get(Type::getVoidTy(GCL->getContext()),
1985                                           false);
1986       const PointerType *PFTy = PointerType::getUnqual(FTy);
1987       CSVals[1] = Constant::getNullValue(PFTy);
1988       CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()),
1989                                    2147483647);
1990     }
1991     CAList.push_back(ConstantStruct::get(GCL->getContext(), CSVals, false));
1992   }
1993
1994   // Create the array initializer.
1995   const Type *StructTy =
1996       cast<ArrayType>(GCL->getType()->getElementType())->getElementType();
1997   Constant *CA = ConstantArray::get(ArrayType::get(StructTy,
1998                                                    CAList.size()), CAList);
1999
2000   // If we didn't change the number of elements, don't create a new GV.
2001   if (CA->getType() == GCL->getInitializer()->getType()) {
2002     GCL->setInitializer(CA);
2003     return GCL;
2004   }
2005
2006   // Create the new global and insert it next to the existing list.
2007   GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(),
2008                                            GCL->getLinkage(), CA, "",
2009                                            GCL->isThreadLocal());
2010   GCL->getParent()->getGlobalList().insert(GCL, NGV);
2011   NGV->takeName(GCL);
2012
2013   // Nuke the old list, replacing any uses with the new one.
2014   if (!GCL->use_empty()) {
2015     Constant *V = NGV;
2016     if (V->getType() != GCL->getType())
2017       V = ConstantExpr::getBitCast(V, GCL->getType());
2018     GCL->replaceAllUsesWith(V);
2019   }
2020   GCL->eraseFromParent();
2021
2022   if (Ctors.size())
2023     return NGV;
2024   else
2025     return 0;
2026 }
2027
2028
2029 static Constant *getVal(DenseMap<Value*, Constant*> &ComputedValues,
2030                         Value *V) {
2031   if (Constant *CV = dyn_cast<Constant>(V)) return CV;
2032   Constant *R = ComputedValues[V];
2033   assert(R && "Reference to an uncomputed value!");
2034   return R;
2035 }
2036
2037 /// isSimpleEnoughPointerToCommit - Return true if this constant is simple
2038 /// enough for us to understand.  In particular, if it is a cast of something,
2039 /// we punt.  We basically just support direct accesses to globals and GEP's of
2040 /// globals.  This should be kept up to date with CommitValueTo.
2041 static bool isSimpleEnoughPointerToCommit(Constant *C) {
2042   // Conservatively, avoid aggregate types. This is because we don't
2043   // want to worry about them partially overlapping other stores.
2044   if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
2045     return false;
2046
2047   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
2048     // Do not allow weak/linkonce/dllimport/dllexport linkage or
2049     // external globals.
2050     return GV->hasDefinitiveInitializer();
2051
2052   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
2053     // Handle a constantexpr gep.
2054     if (CE->getOpcode() == Instruction::GetElementPtr &&
2055         isa<GlobalVariable>(CE->getOperand(0)) &&
2056         cast<GEPOperator>(CE)->isInBounds()) {
2057       GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2058       // Do not allow weak/linkonce/dllimport/dllexport linkage or
2059       // external globals.
2060       if (!GV->hasDefinitiveInitializer())
2061         return false;
2062
2063       // The first index must be zero.
2064       ConstantInt *CI = dyn_cast<ConstantInt>(*next(CE->op_begin()));
2065       if (!CI || !CI->isZero()) return false;
2066
2067       // The remaining indices must be compile-time known integers within the
2068       // notional bounds of the corresponding static array types.
2069       if (!CE->isGEPWithNoNotionalOverIndexing())
2070         return false;
2071
2072       return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
2073     }
2074   return false;
2075 }
2076
2077 /// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global
2078 /// initializer.  This returns 'Init' modified to reflect 'Val' stored into it.
2079 /// At this point, the GEP operands of Addr [0, OpNo) have been stepped into.
2080 static Constant *EvaluateStoreInto(Constant *Init, Constant *Val,
2081                                    ConstantExpr *Addr, unsigned OpNo) {
2082   // Base case of the recursion.
2083   if (OpNo == Addr->getNumOperands()) {
2084     assert(Val->getType() == Init->getType() && "Type mismatch!");
2085     return Val;
2086   }
2087
2088   std::vector<Constant*> Elts;
2089   if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
2090
2091     // Break up the constant into its elements.
2092     if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
2093       for (User::op_iterator i = CS->op_begin(), e = CS->op_end(); i != e; ++i)
2094         Elts.push_back(cast<Constant>(*i));
2095     } else if (isa<ConstantAggregateZero>(Init)) {
2096       for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2097         Elts.push_back(Constant::getNullValue(STy->getElementType(i)));
2098     } else if (isa<UndefValue>(Init)) {
2099       for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2100         Elts.push_back(UndefValue::get(STy->getElementType(i)));
2101     } else {
2102       llvm_unreachable("This code is out of sync with "
2103              " ConstantFoldLoadThroughGEPConstantExpr");
2104     }
2105
2106     // Replace the element that we are supposed to.
2107     ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
2108     unsigned Idx = CU->getZExtValue();
2109     assert(Idx < STy->getNumElements() && "Struct index out of range!");
2110     Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);
2111
2112     // Return the modified struct.
2113     return ConstantStruct::get(Init->getContext(), &Elts[0], Elts.size(),
2114                                STy->isPacked());
2115   } else {
2116     ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
2117     const SequentialType *InitTy = cast<SequentialType>(Init->getType());
2118
2119     uint64_t NumElts;
2120     if (const ArrayType *ATy = dyn_cast<ArrayType>(InitTy))
2121       NumElts = ATy->getNumElements();
2122     else
2123       NumElts = cast<VectorType>(InitTy)->getNumElements();
2124
2125
2126     // Break up the array into elements.
2127     if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
2128       for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i)
2129         Elts.push_back(cast<Constant>(*i));
2130     } else if (ConstantVector *CV = dyn_cast<ConstantVector>(Init)) {
2131       for (User::op_iterator i = CV->op_begin(), e = CV->op_end(); i != e; ++i)
2132         Elts.push_back(cast<Constant>(*i));
2133     } else if (isa<ConstantAggregateZero>(Init)) {
2134       Elts.assign(NumElts, Constant::getNullValue(InitTy->getElementType()));
2135     } else {
2136       assert(isa<UndefValue>(Init) && "This code is out of sync with "
2137              " ConstantFoldLoadThroughGEPConstantExpr");
2138       Elts.assign(NumElts, UndefValue::get(InitTy->getElementType()));
2139     }
2140
2141     assert(CI->getZExtValue() < NumElts);
2142     Elts[CI->getZExtValue()] =
2143       EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);
2144
2145     if (Init->getType()->isArrayTy())
2146       return ConstantArray::get(cast<ArrayType>(InitTy), Elts);
2147     else
2148       return ConstantVector::get(&Elts[0], Elts.size());
2149   }
2150 }
2151
2152 /// CommitValueTo - We have decided that Addr (which satisfies the predicate
2153 /// isSimpleEnoughPointerToCommit) should get Val as its value.  Make it happen.
2154 static void CommitValueTo(Constant *Val, Constant *Addr) {
2155   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
2156     assert(GV->hasInitializer());
2157     GV->setInitializer(Val);
2158     return;
2159   }
2160
2161   ConstantExpr *CE = cast<ConstantExpr>(Addr);
2162   GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2163   GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
2164 }
2165
2166 /// ComputeLoadResult - Return the value that would be computed by a load from
2167 /// P after the stores reflected by 'memory' have been performed.  If we can't
2168 /// decide, return null.
2169 static Constant *ComputeLoadResult(Constant *P,
2170                                 const DenseMap<Constant*, Constant*> &Memory) {
2171   // If this memory location has been recently stored, use the stored value: it
2172   // is the most up-to-date.
2173   DenseMap<Constant*, Constant*>::const_iterator I = Memory.find(P);
2174   if (I != Memory.end()) return I->second;
2175
2176   // Access it.
2177   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
2178     if (GV->hasDefinitiveInitializer())
2179       return GV->getInitializer();
2180     return 0;
2181   }
2182
2183   // Handle a constantexpr getelementptr.
2184   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P))
2185     if (CE->getOpcode() == Instruction::GetElementPtr &&
2186         isa<GlobalVariable>(CE->getOperand(0))) {
2187       GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2188       if (GV->hasDefinitiveInitializer())
2189         return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
2190     }
2191
2192   return 0;  // don't know how to evaluate.
2193 }
2194
2195 /// EvaluateFunction - Evaluate a call to function F, returning true if
2196 /// successful, false if we can't evaluate it.  ActualArgs contains the formal
2197 /// arguments for the function.
2198 static bool EvaluateFunction(Function *F, Constant *&RetVal,
2199                              const SmallVectorImpl<Constant*> &ActualArgs,
2200                              std::vector<Function*> &CallStack,
2201                              DenseMap<Constant*, Constant*> &MutatedMemory,
2202                              std::vector<GlobalVariable*> &AllocaTmps) {
2203   // Check to see if this function is already executing (recursion).  If so,
2204   // bail out.  TODO: we might want to accept limited recursion.
2205   if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end())
2206     return false;
2207
2208   CallStack.push_back(F);
2209
2210   /// Values - As we compute SSA register values, we store their contents here.
2211   DenseMap<Value*, Constant*> Values;
2212
2213   // Initialize arguments to the incoming values specified.
2214   unsigned ArgNo = 0;
2215   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
2216        ++AI, ++ArgNo)
2217     Values[AI] = ActualArgs[ArgNo];
2218
2219   /// ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
2220   /// we can only evaluate any one basic block at most once.  This set keeps
2221   /// track of what we have executed so we can detect recursive cases etc.
2222   SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
2223
2224   // CurInst - The current instruction we're evaluating.
2225   BasicBlock::iterator CurInst = F->begin()->begin();
2226
2227   // This is the main evaluation loop.
2228   while (1) {
2229     Constant *InstResult = 0;
2230
2231     if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
2232       if (SI->isVolatile()) return false;  // no volatile accesses.
2233       Constant *Ptr = getVal(Values, SI->getOperand(1));
2234       if (!isSimpleEnoughPointerToCommit(Ptr))
2235         // If this is too complex for us to commit, reject it.
2236         return false;
2237       Constant *Val = getVal(Values, SI->getOperand(0));
2238       MutatedMemory[Ptr] = Val;
2239     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
2240       InstResult = ConstantExpr::get(BO->getOpcode(),
2241                                      getVal(Values, BO->getOperand(0)),
2242                                      getVal(Values, BO->getOperand(1)));
2243     } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
2244       InstResult = ConstantExpr::getCompare(CI->getPredicate(),
2245                                             getVal(Values, CI->getOperand(0)),
2246                                             getVal(Values, CI->getOperand(1)));
2247     } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
2248       InstResult = ConstantExpr::getCast(CI->getOpcode(),
2249                                          getVal(Values, CI->getOperand(0)),
2250                                          CI->getType());
2251     } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
2252       InstResult =
2253             ConstantExpr::getSelect(getVal(Values, SI->getOperand(0)),
2254                                            getVal(Values, SI->getOperand(1)),
2255                                            getVal(Values, SI->getOperand(2)));
2256     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
2257       Constant *P = getVal(Values, GEP->getOperand(0));
2258       SmallVector<Constant*, 8> GEPOps;
2259       for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
2260            i != e; ++i)
2261         GEPOps.push_back(getVal(Values, *i));
2262       InstResult = cast<GEPOperator>(GEP)->isInBounds() ?
2263           ConstantExpr::getInBoundsGetElementPtr(P, &GEPOps[0], GEPOps.size()) :
2264           ConstantExpr::getGetElementPtr(P, &GEPOps[0], GEPOps.size());
2265     } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
2266       if (LI->isVolatile()) return false;  // no volatile accesses.
2267       InstResult = ComputeLoadResult(getVal(Values, LI->getOperand(0)),
2268                                      MutatedMemory);
2269       if (InstResult == 0) return false; // Could not evaluate load.
2270     } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
2271       if (AI->isArrayAllocation()) return false;  // Cannot handle array allocs.
2272       const Type *Ty = AI->getType()->getElementType();
2273       AllocaTmps.push_back(new GlobalVariable(Ty, false,
2274                                               GlobalValue::InternalLinkage,
2275                                               UndefValue::get(Ty),
2276                                               AI->getName()));
2277       InstResult = AllocaTmps.back();
2278     } else if (CallInst *CI = dyn_cast<CallInst>(CurInst)) {
2279
2280       // Debug info can safely be ignored here.
2281       if (isa<DbgInfoIntrinsic>(CI)) {
2282         ++CurInst;
2283         continue;
2284       }
2285
2286       // Cannot handle inline asm.
2287       if (isa<InlineAsm>(CI->getOperand(0))) return false;
2288
2289       // Resolve function pointers.
2290       Function *Callee = dyn_cast<Function>(getVal(Values, CI->getOperand(0)));
2291       if (!Callee) return false;  // Cannot resolve.
2292
2293       SmallVector<Constant*, 8> Formals;
2294       for (User::op_iterator i = CI->op_begin() + 1, e = CI->op_end();
2295            i != e; ++i)
2296         Formals.push_back(getVal(Values, *i));
2297
2298       if (Callee->isDeclaration()) {
2299         // If this is a function we can constant fold, do it.
2300         if (Constant *C = ConstantFoldCall(Callee, Formals.data(),
2301                                            Formals.size())) {
2302           InstResult = C;
2303         } else {
2304           return false;
2305         }
2306       } else {
2307         if (Callee->getFunctionType()->isVarArg())
2308           return false;
2309
2310         Constant *RetVal;
2311         // Execute the call, if successful, use the return value.
2312         if (!EvaluateFunction(Callee, RetVal, Formals, CallStack,
2313                               MutatedMemory, AllocaTmps))
2314           return false;
2315         InstResult = RetVal;
2316       }
2317     } else if (isa<TerminatorInst>(CurInst)) {
2318       BasicBlock *NewBB = 0;
2319       if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
2320         if (BI->isUnconditional()) {
2321           NewBB = BI->getSuccessor(0);
2322         } else {
2323           ConstantInt *Cond =
2324             dyn_cast<ConstantInt>(getVal(Values, BI->getCondition()));
2325           if (!Cond) return false;  // Cannot determine.
2326
2327           NewBB = BI->getSuccessor(!Cond->getZExtValue());
2328         }
2329       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
2330         ConstantInt *Val =
2331           dyn_cast<ConstantInt>(getVal(Values, SI->getCondition()));
2332         if (!Val) return false;  // Cannot determine.
2333         NewBB = SI->getSuccessor(SI->findCaseValue(Val));
2334       } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
2335         Value *Val = getVal(Values, IBI->getAddress())->stripPointerCasts();
2336         if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
2337           NewBB = BA->getBasicBlock();
2338         else
2339           return false;  // Cannot determine.
2340       } else if (ReturnInst *RI = dyn_cast<ReturnInst>(CurInst)) {
2341         if (RI->getNumOperands())
2342           RetVal = getVal(Values, RI->getOperand(0));
2343
2344         CallStack.pop_back();  // return from fn.
2345         return true;  // We succeeded at evaluating this ctor!
2346       } else {
2347         // invoke, unwind, unreachable.
2348         return false;  // Cannot handle this terminator.
2349       }
2350
2351       // Okay, we succeeded in evaluating this control flow.  See if we have
2352       // executed the new block before.  If so, we have a looping function,
2353       // which we cannot evaluate in reasonable time.
2354       if (!ExecutedBlocks.insert(NewBB))
2355         return false;  // looped!
2356
2357       // Okay, we have never been in this block before.  Check to see if there
2358       // are any PHI nodes.  If so, evaluate them with information about where
2359       // we came from.
2360       BasicBlock *OldBB = CurInst->getParent();
2361       CurInst = NewBB->begin();
2362       PHINode *PN;
2363       for (; (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
2364         Values[PN] = getVal(Values, PN->getIncomingValueForBlock(OldBB));
2365
2366       // Do NOT increment CurInst.  We know that the terminator had no value.
2367       continue;
2368     } else {
2369       // Did not know how to evaluate this!
2370       return false;
2371     }
2372
2373     if (!CurInst->use_empty())
2374       Values[CurInst] = InstResult;
2375
2376     // Advance program counter.
2377     ++CurInst;
2378   }
2379 }
2380
2381 /// EvaluateStaticConstructor - Evaluate static constructors in the function, if
2382 /// we can.  Return true if we can, false otherwise.
2383 static bool EvaluateStaticConstructor(Function *F) {
2384   /// MutatedMemory - For each store we execute, we update this map.  Loads
2385   /// check this to get the most up-to-date value.  If evaluation is successful,
2386   /// this state is committed to the process.
2387   DenseMap<Constant*, Constant*> MutatedMemory;
2388
2389   /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable
2390   /// to represent its body.  This vector is needed so we can delete the
2391   /// temporary globals when we are done.
2392   std::vector<GlobalVariable*> AllocaTmps;
2393
2394   /// CallStack - This is used to detect recursion.  In pathological situations
2395   /// we could hit exponential behavior, but at least there is nothing
2396   /// unbounded.
2397   std::vector<Function*> CallStack;
2398
2399   // Call the function.
2400   Constant *RetValDummy;
2401   bool EvalSuccess = EvaluateFunction(F, RetValDummy,
2402                                       SmallVector<Constant*, 0>(), CallStack,
2403                                       MutatedMemory, AllocaTmps);
2404   if (EvalSuccess) {
2405     // We succeeded at evaluation: commit the result.
2406     DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
2407           << F->getName() << "' to " << MutatedMemory.size()
2408           << " stores.\n");
2409     for (DenseMap<Constant*, Constant*>::iterator I = MutatedMemory.begin(),
2410          E = MutatedMemory.end(); I != E; ++I)
2411       CommitValueTo(I->second, I->first);
2412   }
2413
2414   // At this point, we are done interpreting.  If we created any 'alloca'
2415   // temporaries, release them now.
2416   while (!AllocaTmps.empty()) {
2417     GlobalVariable *Tmp = AllocaTmps.back();
2418     AllocaTmps.pop_back();
2419
2420     // If there are still users of the alloca, the program is doing something
2421     // silly, e.g. storing the address of the alloca somewhere and using it
2422     // later.  Since this is undefined, we'll just make it be null.
2423     if (!Tmp->use_empty())
2424       Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
2425     delete Tmp;
2426   }
2427
2428   return EvalSuccess;
2429 }
2430
2431
2432
2433 /// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible.
2434 /// Return true if anything changed.
2435 bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) {
2436   std::vector<Function*> Ctors = ParseGlobalCtors(GCL);
2437   bool MadeChange = false;
2438   if (Ctors.empty()) return false;
2439
2440   // Loop over global ctors, optimizing them when we can.
2441   for (unsigned i = 0; i != Ctors.size(); ++i) {
2442     Function *F = Ctors[i];
2443     // Found a null terminator in the middle of the list, prune off the rest of
2444     // the list.
2445     if (F == 0) {
2446       if (i != Ctors.size()-1) {
2447         Ctors.resize(i+1);
2448         MadeChange = true;
2449       }
2450       break;
2451     }
2452
2453     // We cannot simplify external ctor functions.
2454     if (F->empty()) continue;
2455
2456     // If we can evaluate the ctor at compile time, do.
2457     if (EvaluateStaticConstructor(F)) {
2458       Ctors.erase(Ctors.begin()+i);
2459       MadeChange = true;
2460       --i;
2461       ++NumCtorsEvaluated;
2462       continue;
2463     }
2464   }
2465
2466   if (!MadeChange) return false;
2467
2468   GCL = InstallGlobalCtors(GCL, Ctors);
2469   return true;
2470 }
2471
2472 bool GlobalOpt::OptimizeGlobalAliases(Module &M) {
2473   bool Changed = false;
2474
2475   for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
2476        I != E;) {
2477     Module::alias_iterator J = I++;
2478     // Aliases without names cannot be referenced outside this module.
2479     if (!J->hasName() && !J->isDeclaration())
2480       J->setLinkage(GlobalValue::InternalLinkage);
2481     // If the aliasee may change at link time, nothing can be done - bail out.
2482     if (J->mayBeOverridden())
2483       continue;
2484
2485     Constant *Aliasee = J->getAliasee();
2486     GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
2487     Target->removeDeadConstantUsers();
2488     bool hasOneUse = Target->hasOneUse() && Aliasee->hasOneUse();
2489
2490     // Make all users of the alias use the aliasee instead.
2491     if (!J->use_empty()) {
2492       J->replaceAllUsesWith(Aliasee);
2493       ++NumAliasesResolved;
2494       Changed = true;
2495     }
2496
2497     // If the alias is externally visible, we may still be able to simplify it.
2498     if (!J->hasLocalLinkage()) {
2499       // If the aliasee has internal linkage, give it the name and linkage
2500       // of the alias, and delete the alias.  This turns:
2501       //   define internal ... @f(...)
2502       //   @a = alias ... @f
2503       // into:
2504       //   define ... @a(...)
2505       if (!Target->hasLocalLinkage())
2506         continue;
2507
2508       // Do not perform the transform if multiple aliases potentially target the
2509       // aliasee.  This check also ensures that it is safe to replace the section
2510       // and other attributes of the aliasee with those of the alias.
2511       if (!hasOneUse)
2512         continue;
2513
2514       // Give the aliasee the name, linkage and other attributes of the alias.
2515       Target->takeName(J);
2516       Target->setLinkage(J->getLinkage());
2517       Target->GlobalValue::copyAttributesFrom(J);
2518     }
2519
2520     // Delete the alias.
2521     M.getAliasList().erase(J);
2522     ++NumAliasesRemoved;
2523     Changed = true;
2524   }
2525
2526   return Changed;
2527 }
2528
2529 bool GlobalOpt::runOnModule(Module &M) {
2530   bool Changed = false;
2531
2532   // Try to find the llvm.globalctors list.
2533   GlobalVariable *GlobalCtors = FindGlobalCtors(M);
2534
2535   bool LocalChange = true;
2536   while (LocalChange) {
2537     LocalChange = false;
2538
2539     // Delete functions that are trivially dead, ccc -> fastcc
2540     LocalChange |= OptimizeFunctions(M);
2541
2542     // Optimize global_ctors list.
2543     if (GlobalCtors)
2544       LocalChange |= OptimizeGlobalCtorsList(GlobalCtors);
2545
2546     // Optimize non-address-taken globals.
2547     LocalChange |= OptimizeGlobalVars(M);
2548
2549     // Resolve aliases, when possible.
2550     LocalChange |= OptimizeGlobalAliases(M);
2551     Changed |= LocalChange;
2552   }
2553
2554   // TODO: Move all global ctors functions to the end of the module for code
2555   // layout.
2556
2557   return Changed;
2558 }