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