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