lib/Transforms/IPO/GlobalOpt.cpp

   1 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This 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/Constants.h"
  19 #include "llvm/DerivedTypes.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Module.h"
  22 #include "llvm/Pass.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/ADT/StringExtras.h"
  26 #include <set>
  27 #include <algorithm>
  28 using namespace llvm;
  29
  30 namespace {
  31   Statistic<> NumMarked   ("globalopt", "Number of globals marked constant");
  32   Statistic<> NumSRA      ("globalopt", "Number of aggregate globals broken "
  33                            "into scalars");
  34   Statistic<> NumDeleted  ("globalopt", "Number of globals deleted");
  35   Statistic<> NumFnDeleted("globalopt", "Number of functions deleted");
  36   Statistic<> NumGlobUses ("globalopt", "Number of global uses devirtualized");
  37
  38   struct GlobalOpt : public ModulePass {
  39     bool runOnModule(Module &M);
  40   };
  41
  42   RegisterOpt<GlobalOpt> X("globalopt", "Global Variable Optimizer");
  43 }
  44
  45 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
  46
  47 /// GlobalStatus - As we analyze each global, keep track of some information
  48 /// about it.  If we find out that the address of the global is taken, none of
  49 /// this info will be accurate.
  50 struct GlobalStatus {
  51   /// isLoaded - True if the global is ever loaded.  If the global isn't ever
  52   /// loaded it can be deleted.
  53   bool isLoaded;
  54
  55   /// StoredType - Keep track of what stores to the global look like.
  56   ///
  57   enum StoredType {
  58     /// NotStored - There is no store to this global.  It can thus be marked
  59     /// constant.
  60     NotStored,
  61
  62     /// isInitializerStored - This global is stored to, but the only thing
  63     /// stored is the constant it was initialized with.  This is only tracked
  64     /// for scalar globals.
  65     isInitializerStored,
  66
  67     /// isStoredOnce - This global is stored to, but only its initializer and
  68     /// one other value is ever stored to it.  If this global isStoredOnce, we
  69     /// track the value stored to it in StoredOnceValue below.  This is only
  70     /// tracked for scalar globals.
  71     isStoredOnce,
  72
  73     /// isStored - This global is stored to by multiple values or something else
  74     /// that we cannot track.
  75     isStored
  76   } StoredType;
  77
  78   /// StoredOnceValue - If only one value (besides the initializer constant) is
  79   /// ever stored to this global, keep track of what value it is.
  80   Value *StoredOnceValue;
  81
  82   /// isNotSuitableForSRA - Keep track of whether any SRA preventing users of
  83   /// the global exist.  Such users include GEP instruction with variable
  84   /// indexes, and non-gep/load/store users like constant expr casts.
  85   bool isNotSuitableForSRA;
  86
  87   GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0),
  88                    isNotSuitableForSRA(false) {}
  89 };
  90
  91
  92
  93 /// ConstantIsDead - Return true if the specified constant is (transitively)
  94 /// dead.  The constant may be used by other constants (e.g. constant arrays and
  95 /// constant exprs) as long as they are dead, but it cannot be used by anything
  96 /// else.
  97 static bool ConstantIsDead(Constant *C) {
  98   if (isa<GlobalValue>(C)) return false;
  99
 100   for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI)
 101     if (Constant *CU = dyn_cast<Constant>(*UI)) {
 102       if (!ConstantIsDead(CU)) return false;
 103     } else
 104       return false;
 105   return true;
 106 }
 107
 108
 109 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus
 110 /// structure.  If the global has its address taken, return true to indicate we
 111 /// can't do anything with it.
 112 ///
 113 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
 114                           std::set<PHINode*> &PHIUsers) {
 115   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 116     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
 117       if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
 118       if (CE->getOpcode() != Instruction::GetElementPtr)
 119         GS.isNotSuitableForSRA = true;
 120       else if (!GS.isNotSuitableForSRA) {
 121         // Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
 122         // don't like < 3 operand CE's, and we don't like non-constant integer
 123         // indices.
 124         if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue())
 125           GS.isNotSuitableForSRA = true;
 126         else {
 127           for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
 128             if (!isa<ConstantInt>(CE->getOperand(i))) {
 129               GS.isNotSuitableForSRA = true;
 130               break;
 131             }
 132         }
 133       }
 134
 135     } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
 136       if (isa<LoadInst>(I)) {
 137         GS.isLoaded = true;
 138       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 139         // Don't allow a store OF the address, only stores TO the address.
 140         if (SI->getOperand(0) == V) return true;
 141
 142         // If this is a direct store to the global (i.e., the global is a scalar
 143         // value, not an aggregate), keep more specific information about
 144         // stores.
 145         if (GS.StoredType != GlobalStatus::isStored)
 146           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
 147             if (SI->getOperand(0) == GV->getInitializer()) {
 148               if (GS.StoredType < GlobalStatus::isInitializerStored)
 149                 GS.StoredType = GlobalStatus::isInitializerStored;
 150             } else if (GS.StoredType < GlobalStatus::isStoredOnce) {
 151               GS.StoredType = GlobalStatus::isStoredOnce;
 152               GS.StoredOnceValue = SI->getOperand(0);
 153             } else if (GS.StoredType == GlobalStatus::isStoredOnce &&
 154                        GS.StoredOnceValue == SI->getOperand(0)) {
 155               // noop.
 156             } else {
 157               GS.StoredType = GlobalStatus::isStored;
 158             }
 159           } else {
 160             GS.StoredType = GlobalStatus::isStored;
 161           }
 162       } else if (I->getOpcode() == Instruction::GetElementPtr) {
 163         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 164         // Theoretically we could SRA globals with GEP insts if all indexes are
 165         // constants.  In practice, these GEPs would already be constant exprs
 166         // if that was the case though.
 167         GS.isNotSuitableForSRA = true;
 168       } else if (I->getOpcode() == Instruction::Select) {
 169         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 170         GS.isNotSuitableForSRA = true;
 171       } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
 172         // PHI nodes we can check just like select or GEP instructions, but we
 173         // have to be careful about infinite recursion.
 174         if (PHIUsers.insert(PN).second)  // Not already visited.
 175           if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 176         GS.isNotSuitableForSRA = true;
 177       } else if (isa<SetCondInst>(I)) {
 178         GS.isNotSuitableForSRA = true;
 179       } else {
 180         return true;  // Any other non-load instruction might take address!
 181       }
 182     } else if (Constant *C = dyn_cast<Constant>(*UI)) {
 183       // We might have a dead and dangling constant hanging off of here.
 184       if (!ConstantIsDead(C))
 185         return true;
 186     } else {
 187       // Otherwise must be a global or some other user.
 188       return true;
 189     }
 190
 191   return false;
 192 }
 193
 194 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) {
 195   ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
 196   if (!CI) return 0;
 197   uint64_t IdxV = CI->getRawValue();
 198
 199   if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) {
 200     if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV);
 201   } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) {
 202     if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV);
 203   } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Agg)) {
 204     if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV);
 205   } else if (ConstantAggregateZero *CAZ =
 206              dyn_cast<ConstantAggregateZero>(Agg)) {
 207     if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
 208       if (IdxV < STy->getNumElements())
 209         return Constant::getNullValue(STy->getElementType(IdxV));
 210     } else if (const SequentialType *STy =
 211                dyn_cast<SequentialType>(Agg->getType())) {
 212       return Constant::getNullValue(STy->getElementType());
 213     }
 214   }
 215   return 0;
 216 }
 217
 218 static Constant *TraverseGEPInitializer(User *GEP, Constant *Init) {
 219   if (GEP->getNumOperands() == 1 ||
 220       !isa<Constant>(GEP->getOperand(1)) ||
 221       !cast<Constant>(GEP->getOperand(1))->isNullValue())
 222     return 0;
 223
 224   for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) {
 225     ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
 226     if (!Idx) return 0;
 227     Init = getAggregateConstantElement(Init, Idx);
 228     if (Init == 0) return 0;
 229   }
 230   return Init;
 231 }
 232
 233 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
 234 /// users of the global, cleaning up the obvious ones.  This is largely just a
 235 /// quick scan over the use list to clean up the easy and obvious cruft.  This
 236 /// returns true if it made a change.
 237 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) {
 238   bool Changed = false;
 239   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) {
 240     User *U = *UI++;
 241
 242     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
 243       // Replace the load with the initializer.
 244       LI->replaceAllUsesWith(Init);
 245       LI->getParent()->getInstList().erase(LI);
 246       Changed = true;
 247     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 248       // Store must be unreachable or storing Init into the global.
 249       SI->getParent()->getInstList().erase(SI);
 250       Changed = true;
 251     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 252       if (CE->getOpcode() == Instruction::GetElementPtr) {
 253         if (Constant *SubInit = TraverseGEPInitializer(CE, Init))
 254           Changed |= CleanupConstantGlobalUsers(CE, SubInit);
 255         if (CE->use_empty()) {
 256           CE->destroyConstant();
 257           Changed = true;
 258         }
 259       }
 260     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
 261       if (Constant *SubInit = TraverseGEPInitializer(GEP, Init))
 262         Changed |= CleanupConstantGlobalUsers(GEP, SubInit);
 263       else {
 264         // If this GEP has variable indexes, we should still be able to delete
 265         // any stores through it.
 266         for (Value::use_iterator GUI = GEP->use_begin(), E = GEP->use_end();
 267              GUI != E;)
 268           if (StoreInst *SI = dyn_cast<StoreInst>(*GUI++)) {
 269             SI->getParent()->getInstList().erase(SI);
 270             Changed = true;
 271           }
 272       }
 273
 274       if (GEP->use_empty()) {
 275         GEP->getParent()->getInstList().erase(GEP);
 276         Changed = true;
 277       }
 278     } else if (Constant *C = dyn_cast<Constant>(U)) {
 279       // If we have a chain of dead constantexprs or other things dangling from
 280       // us, and if they are all dead, nuke them without remorse.
 281       if (ConstantIsDead(C)) {
 282         C->destroyConstant();
 283         // This could have incalidated UI, start over from scratch.x
 284         CleanupConstantGlobalUsers(V, Init);
 285         return true;
 286       }
 287     }
 288   }
 289   return Changed;
 290 }
 291
 292 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
 293 /// variable.  This opens the door for other optimizations by exposing the
 294 /// behavior of the program in a more fine-grained way.  We have determined that
 295 /// this transformation is safe already.  We return the first global variable we
 296 /// insert so that the caller can reprocess it.
 297 static GlobalVariable *SRAGlobal(GlobalVariable *GV) {
 298   assert(GV->hasInternalLinkage() && !GV->isConstant());
 299   Constant *Init = GV->getInitializer();
 300   const Type *Ty = Init->getType();
 301
 302   std::vector<GlobalVariable*> NewGlobals;
 303   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
 304
 305   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 306     NewGlobals.reserve(STy->getNumElements());
 307     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
 308       Constant *In = getAggregateConstantElement(Init,
 309                                             ConstantUInt::get(Type::UIntTy, i));
 310       assert(In && "Couldn't get element of initializer?");
 311       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
 312                                                GlobalVariable::InternalLinkage,
 313                                                In, GV->getName()+"."+utostr(i));
 314       Globals.insert(GV, NGV);
 315       NewGlobals.push_back(NGV);
 316     }
 317   } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
 318     unsigned NumElements = 0;
 319     if (const ArrayType *ATy = dyn_cast<ArrayType>(STy))
 320       NumElements = ATy->getNumElements();
 321     else if (const PackedType *PTy = dyn_cast<PackedType>(STy))
 322       NumElements = PTy->getNumElements();
 323     else
 324       assert(0 && "Unknown aggregate sequential type!");
 325
 326     if (NumElements > 16) return 0; // It's not worth it.
 327     NewGlobals.reserve(NumElements);
 328     for (unsigned i = 0, e = NumElements; i != e; ++i) {
 329       Constant *In = getAggregateConstantElement(Init,
 330                                             ConstantUInt::get(Type::UIntTy, i));
 331       assert(In && "Couldn't get element of initializer?");
 332
 333       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
 334                                                GlobalVariable::InternalLinkage,
 335                                                In, GV->getName()+"."+utostr(i));
 336       Globals.insert(GV, NGV);
 337       NewGlobals.push_back(NGV);
 338     }
 339   }
 340
 341   if (NewGlobals.empty())
 342     return 0;
 343
 344   Constant *NullInt = Constant::getNullValue(Type::IntTy);
 345
 346   // Loop over all of the uses of the global, replacing the constantexpr geps,
 347   // with smaller constantexpr geps or direct references.
 348   while (!GV->use_empty()) {
 349     ConstantExpr *CE = cast<ConstantExpr>(GV->use_back());
 350     assert(CE->getOpcode() == Instruction::GetElementPtr &&
 351            "NonGEP CE's are not SRAable!");
 352     // Ignore the 1th operand, which has to be zero or else the program is quite
 353     // broken (undefined).  Get the 2nd operand, which is the structure or array
 354     // index.
 355     unsigned Val = cast<ConstantInt>(CE->getOperand(2))->getRawValue();
 356     if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
 357
 358     Constant *NewPtr = NewGlobals[Val];
 359
 360     // Form a shorter GEP if needed.
 361     if (CE->getNumOperands() > 3) {
 362       std::vector<Constant*> Idxs;
 363       Idxs.push_back(NullInt);
 364       for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
 365         Idxs.push_back(CE->getOperand(i));
 366       NewPtr = ConstantExpr::getGetElementPtr(NewPtr, Idxs);
 367     }
 368     CE->replaceAllUsesWith(NewPtr);
 369     CE->destroyConstant();
 370   }
 371
 372   // Delete the old global, now that it is dead.
 373   Globals.erase(GV);
 374   ++NumSRA;
 375   return NewGlobals[0];
 376 }
 377
 378 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified
 379 /// value will trap if the value is dynamically null.
 380 static bool AllUsesOfValueWillTrapIfNull(Value *V) {
 381   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 382     if (isa<LoadInst>(*UI)) {
 383       // Will trap.
 384     } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
 385       if (SI->getOperand(0) == V) {
 386         //std::cerr << "NONTRAPPING USE: " << **UI;
 387         return false;  // Storing the value.
 388       }
 389     } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
 390       if (CI->getOperand(0) != V) {
 391         //std::cerr << "NONTRAPPING USE: " << **UI;
 392         return false;  // Not calling the ptr
 393       }
 394     } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) {
 395       if (II->getOperand(0) != V) {
 396         //std::cerr << "NONTRAPPING USE: " << **UI;
 397         return false;  // Not calling the ptr
 398       }
 399     } else if (CastInst *CI = dyn_cast<CastInst>(*UI)) {
 400       if (!AllUsesOfValueWillTrapIfNull(CI)) return false;
 401     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) {
 402       if (!AllUsesOfValueWillTrapIfNull(GEPI)) return false;
 403     } else {
 404       //std::cerr << "NONTRAPPING USE: " << **UI;
 405       return false;
 406     }
 407   return true;
 408 }
 409
 410 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads
 411 /// from GV will trap if the loaded value is null.
 412 static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) {
 413   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI!=E; ++UI)
 414     if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
 415       if (!AllUsesOfValueWillTrapIfNull(LI))
 416         return false;
 417     } else if (isa<StoreInst>(*UI)) {
 418       // Ignore stores to the global.
 419     } else {
 420       // We don't know or understand this user, bail out.
 421       //std::cerr << "UNKNOWN USER OF GLOBAL!: " << **UI;
 422       return false;
 423     }
 424
 425   return true;
 426 }
 427
 428 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
 429   bool Changed = false;
 430   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) {
 431     Instruction *I = cast<Instruction>(*UI++);
 432     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 433       LI->setOperand(0, NewV);
 434       Changed = true;
 435     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 436       if (SI->getOperand(1) == V) {
 437         SI->setOperand(1, NewV);
 438         Changed = true;
 439       }
 440     } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
 441       if (I->getOperand(0) == V) {
 442         // Calling through the pointer!  Turn into a direct call, but be careful
 443         // that the pointer is not also being passed as an argument.
 444         I->setOperand(0, NewV);
 445         Changed = true;
 446         bool PassedAsArg = false;
 447         for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
 448           if (I->getOperand(i) == V) {
 449             PassedAsArg = true;
 450             I->setOperand(i, NewV);
 451           }
 452
 453         if (PassedAsArg) {
 454           // Being passed as an argument also.  Be careful to not invalidate UI!
 455           UI = V->use_begin();
 456         }
 457       }
 458     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
 459       Changed |= OptimizeAwayTrappingUsesOfValue(CI,
 460                                     ConstantExpr::getCast(NewV, CI->getType()));
 461       if (CI->use_empty()) {
 462         Changed = true;
 463         CI->getParent()->getInstList().erase(CI);
 464       }
 465     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
 466       // Should handle GEP here.
 467       std::vector<Constant*> Indices;
 468       Indices.reserve(GEPI->getNumOperands()-1);
 469       for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i)
 470         if (Constant *C = dyn_cast<Constant>(GEPI->getOperand(i)))
 471           Indices.push_back(C);
 472         else
 473           break;
 474       if (Indices.size() == GEPI->getNumOperands()-1)
 475         Changed |= OptimizeAwayTrappingUsesOfValue(GEPI,
 476                                 ConstantExpr::getGetElementPtr(NewV, Indices));
 477       if (GEPI->use_empty()) {
 478         Changed = true;
 479         GEPI->getParent()->getInstList().erase(GEPI);
 480       }
 481     }
 482   }
 483
 484   return Changed;
 485 }
 486
 487
 488 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null
 489 /// value stored into it.  If there are uses of the loaded value that would trap
 490 /// if the loaded value is dynamically null, then we know that they cannot be
 491 /// reachable with a null optimize away the load.
 492 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) {
 493   std::vector<LoadInst*> Loads;
 494   bool Changed = false;
 495
 496   // Replace all uses of loads with uses of uses of the stored value.
 497   for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end();
 498        GUI != E; ++GUI)
 499     if (LoadInst *LI = dyn_cast<LoadInst>(*GUI)) {
 500       Loads.push_back(LI);
 501       Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
 502     } else {
 503       assert(isa<StoreInst>(*GUI) && "Only expect load and stores!");
 504     }
 505
 506   if (Changed) {
 507     DEBUG(std::cerr << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV);
 508     ++NumGlobUses;
 509   }
 510
 511   // Delete all of the loads we can, keeping track of whether we nuked them all!
 512   bool AllLoadsGone = true;
 513   while (!Loads.empty()) {
 514     LoadInst *L = Loads.back();
 515     if (L->use_empty()) {
 516       L->getParent()->getInstList().erase(L);
 517       Changed = true;
 518     } else {
 519       AllLoadsGone = false;
 520     }
 521     Loads.pop_back();
 522   }
 523
 524   // If we nuked all of the loads, then none of the stores are needed either,
 525   // nor is the global.
 526   if (AllLoadsGone) {
 527     DEBUG(std::cerr << "  *** GLOBAL NOW DEAD!\n");
 528     CleanupConstantGlobalUsers(GV, 0);
 529     if (GV->use_empty()) {
 530       GV->getParent()->getGlobalList().erase(GV);
 531       ++NumDeleted;
 532     }
 533     Changed = true;
 534   }
 535   return Changed;
 536 }
 537
 538
 539 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge
 540 // that only one value (besides its initializer) is ever stored to the global.
 541 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal) {
 542   if (CastInst *CI = dyn_cast<CastInst>(StoredOnceVal))
 543     StoredOnceVal = CI->getOperand(0);
 544   else if (GetElementPtrInst *GEPI =dyn_cast<GetElementPtrInst>(StoredOnceVal)){
 545     // "getelementptr Ptr, 0, 0, 0" is really just a cast.
 546     bool IsJustACast = true;
 547     for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i)
 548       if (!isa<Constant>(GEPI->getOperand(i)) ||
 549           !cast<Constant>(GEPI->getOperand(i))->isNullValue()) {
 550         IsJustACast = false;
 551         break;
 552       }
 553     if (IsJustACast)
 554       StoredOnceVal = GEPI->getOperand(0);
 555   }
 556
 557   // If we are dealing with a pointer global that is initialized to null and
 558   // only has one (non-null) value stored into it, then we can optimize any
 559   // users of the loaded value (often calls and loads) that would trap if the
 560   // value was null.
 561   if (isa<PointerType>(GV->getInitializer()->getType()) &&
 562       GV->getInitializer()->isNullValue()) {
 563     if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
 564       if (GV->getInitializer()->getType() != SOVC->getType())
 565         SOVC = ConstantExpr::getCast(SOVC, GV->getInitializer()->getType());
 566
 567       // Optimize away any trapping uses of the loaded value.
 568       if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC))
 569         return true;
 570     }
 571     //if (isa<MallocInst>(StoredOnceValue))
 572   }
 573   return false;
 574 }
 575
 576 /// ProcessInternalGlobal - Analyze the specified global variable and optimize
 577 /// it if possible.  If we make a change, return true.
 578 static bool ProcessInternalGlobal(GlobalVariable *GV, Module::giterator &GVI) {
 579   std::set<PHINode*> PHIUsers;
 580   GlobalStatus GS;
 581   PHIUsers.clear();
 582   GV->removeDeadConstantUsers();
 583
 584   if (GV->use_empty()) {
 585     DEBUG(std::cerr << "GLOBAL DEAD: " << *GV);
 586     GV->getParent()->getGlobalList().erase(GV);
 587     ++NumDeleted;
 588     return true;
 589   }
 590
 591   if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
 592     // If the global is never loaded (but may be stored to), it is dead.
 593     // Delete it now.
 594     if (!GS.isLoaded) {
 595       DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV);
 596
 597       // Delete any stores we can find to the global.  We may not be able to
 598       // make it completely dead though.
 599       bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer());
 600
 601       // If the global is dead now, delete it.
 602       if (GV->use_empty()) {
 603         GV->getParent()->getGlobalList().erase(GV);
 604         ++NumDeleted;
 605         Changed = true;
 606       }
 607       return Changed;
 608
 609     } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
 610       DEBUG(std::cerr << "MARKING CONSTANT: " << *GV);
 611       GV->setConstant(true);
 612
 613       // Clean up any obviously simplifiable users now.
 614       CleanupConstantGlobalUsers(GV, GV->getInitializer());
 615
 616       // If the global is dead now, just nuke it.
 617       if (GV->use_empty()) {
 618         DEBUG(std::cerr << "   *** Marking constant allowed us to simplify "
 619               "all users and delete global!\n");
 620         GV->getParent()->getGlobalList().erase(GV);
 621         ++NumDeleted;
 622       }
 623
 624       ++NumMarked;
 625       return true;
 626     } else if (!GS.isNotSuitableForSRA &&
 627                !GV->getInitializer()->getType()->isFirstClassType()) {
 628       DEBUG(std::cerr << "PERFORMING GLOBAL SRA ON: " << *GV);
 629       if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) {
 630         GVI = FirstNewGV;  // Don't skip the newly produced globals!
 631         return true;
 632       }
 633     } else if (GS.StoredType == GlobalStatus::isStoredOnce) {
 634       // Try to optimize globals based on the knowledge that only one value
 635       // (besides its initializer) is ever stored to the global.
 636       if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue))
 637         return true;
 638     }
 639   }
 640   return false;
 641 }
 642
 643
 644 bool GlobalOpt::runOnModule(Module &M) {
 645   bool Changed = false;
 646
 647   // As a prepass, delete functions that are trivially dead.
 648   bool LocalChange = true;
 649   while (LocalChange) {
 650     LocalChange = false;
 651     for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
 652       Function *F = FI++;
 653       F->removeDeadConstantUsers();
 654       if (F->use_empty() && (F->hasInternalLinkage() || F->hasWeakLinkage())) {
 655         M.getFunctionList().erase(F);
 656         LocalChange = true;
 657         ++NumFnDeleted;
 658       }
 659     }
 660     Changed |= LocalChange;
 661   }
 662
 663   LocalChange = true;
 664   while (LocalChange) {
 665     LocalChange = false;
 666     for (Module::giterator GVI = M.gbegin(), E = M.gend(); GVI != E;) {
 667       GlobalVariable *GV = GVI++;
 668       if (!GV->isConstant() && GV->hasInternalLinkage() &&
 669           GV->hasInitializer())
 670         LocalChange |= ProcessInternalGlobal(GV, GVI);
 671     }
 672     Changed |= LocalChange;
 673   }
 674   return Changed;
 675 }