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