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/IntrinsicInst.h"
  22 #include "llvm/Module.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Target/TargetData.h"
  26 #include "llvm/Transforms/Utils/Local.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/ADT/StringExtras.h"
  29 #include <set>
  30 #include <algorithm>
  31 using namespace llvm;
  32
  33 namespace {
  34   Statistic<> NumMarked   ("globalopt", "Number of globals marked constant");
  35   Statistic<> NumSRA      ("globalopt", "Number of aggregate globals broken "
  36                            "into scalars");
  37   Statistic<> NumSubstitute("globalopt",
  38                         "Number of globals with initializers stored into them");
  39   Statistic<> NumDeleted  ("globalopt", "Number of globals deleted");
  40   Statistic<> NumFnDeleted("globalopt", "Number of functions deleted");
  41   Statistic<> NumGlobUses ("globalopt", "Number of global uses devirtualized");
  42   Statistic<> NumLocalized("globalopt", "Number of globals localized");
  43   Statistic<> NumShrunkToBool("globalopt",
  44                               "Number of global vars shrunk to booleans");
  45
  46   struct GlobalOpt : public ModulePass {
  47     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  48       AU.addRequired<TargetData>();
  49     }
  50
  51     bool runOnModule(Module &M);
  52
  53   private:
  54     bool ProcessInternalGlobal(GlobalVariable *GV, Module::global_iterator &GVI);
  55   };
  56
  57   RegisterOpt<GlobalOpt> X("globalopt", "Global Variable Optimizer");
  58 }
  59
  60 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
  61
  62 /// GlobalStatus - As we analyze each global, keep track of some information
  63 /// about it.  If we find out that the address of the global is taken, none of
  64 /// this info will be accurate.
  65 struct GlobalStatus {
  66   /// isLoaded - True if the global is ever loaded.  If the global isn't ever
  67   /// loaded it can be deleted.
  68   bool isLoaded;
  69
  70   /// StoredType - Keep track of what stores to the global look like.
  71   ///
  72   enum StoredType {
  73     /// NotStored - There is no store to this global.  It can thus be marked
  74     /// constant.
  75     NotStored,
  76
  77     /// isInitializerStored - This global is stored to, but the only thing
  78     /// stored is the constant it was initialized with.  This is only tracked
  79     /// for scalar globals.
  80     isInitializerStored,
  81
  82     /// isStoredOnce - This global is stored to, but only its initializer and
  83     /// one other value is ever stored to it.  If this global isStoredOnce, we
  84     /// track the value stored to it in StoredOnceValue below.  This is only
  85     /// tracked for scalar globals.
  86     isStoredOnce,
  87
  88     /// isStored - This global is stored to by multiple values or something else
  89     /// that we cannot track.
  90     isStored
  91   } StoredType;
  92
  93   /// StoredOnceValue - If only one value (besides the initializer constant) is
  94   /// ever stored to this global, keep track of what value it is.
  95   Value *StoredOnceValue;
  96
  97   // AccessingFunction/HasMultipleAccessingFunctions - These start out
  98   // null/false.  When the first accessing function is noticed, it is recorded.
  99   // When a second different accessing function is noticed,
 100   // HasMultipleAccessingFunctions is set to true.
 101   Function *AccessingFunction;
 102   bool HasMultipleAccessingFunctions;
 103
 104   /// isNotSuitableForSRA - Keep track of whether any SRA preventing users of
 105   /// the global exist.  Such users include GEP instruction with variable
 106   /// indexes, and non-gep/load/store users like constant expr casts.
 107   bool isNotSuitableForSRA;
 108
 109   GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0),
 110                    AccessingFunction(0), HasMultipleAccessingFunctions(false),
 111                    isNotSuitableForSRA(false) {}
 112 };
 113
 114
 115
 116 /// ConstantIsDead - Return true if the specified constant is (transitively)
 117 /// dead.  The constant may be used by other constants (e.g. constant arrays and
 118 /// constant exprs) as long as they are dead, but it cannot be used by anything
 119 /// else.
 120 static bool ConstantIsDead(Constant *C) {
 121   if (isa<GlobalValue>(C)) return false;
 122
 123   for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI)
 124     if (Constant *CU = dyn_cast<Constant>(*UI)) {
 125       if (!ConstantIsDead(CU)) return false;
 126     } else
 127       return false;
 128   return true;
 129 }
 130
 131
 132 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus
 133 /// structure.  If the global has its address taken, return true to indicate we
 134 /// can't do anything with it.
 135 ///
 136 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
 137                           std::set<PHINode*> &PHIUsers) {
 138   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 139     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
 140       if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
 141       if (CE->getOpcode() != Instruction::GetElementPtr)
 142         GS.isNotSuitableForSRA = true;
 143       else if (!GS.isNotSuitableForSRA) {
 144         // Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
 145         // don't like < 3 operand CE's, and we don't like non-constant integer
 146         // indices.
 147         if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue())
 148           GS.isNotSuitableForSRA = true;
 149         else {
 150           for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
 151             if (!isa<ConstantInt>(CE->getOperand(i))) {
 152               GS.isNotSuitableForSRA = true;
 153               break;
 154             }
 155         }
 156       }
 157
 158     } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
 159       if (!GS.HasMultipleAccessingFunctions) {
 160         Function *F = I->getParent()->getParent();
 161         if (GS.AccessingFunction == 0)
 162           GS.AccessingFunction = F;
 163         else if (GS.AccessingFunction != F)
 164           GS.HasMultipleAccessingFunctions = true;
 165       }
 166       if (isa<LoadInst>(I)) {
 167         GS.isLoaded = true;
 168       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 169         // Don't allow a store OF the address, only stores TO the address.
 170         if (SI->getOperand(0) == V) return true;
 171
 172         // If this is a direct store to the global (i.e., the global is a scalar
 173         // value, not an aggregate), keep more specific information about
 174         // stores.
 175         if (GS.StoredType != GlobalStatus::isStored)
 176           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
 177             Value *StoredVal = SI->getOperand(0);
 178             if (StoredVal == GV->getInitializer()) {
 179               if (GS.StoredType < GlobalStatus::isInitializerStored)
 180                 GS.StoredType = GlobalStatus::isInitializerStored;
 181             } else if (isa<LoadInst>(StoredVal) &&
 182                        cast<LoadInst>(StoredVal)->getOperand(0) == GV) {
 183               // G = G
 184               if (GS.StoredType < GlobalStatus::isInitializerStored)
 185                 GS.StoredType = GlobalStatus::isInitializerStored;
 186             } else if (GS.StoredType < GlobalStatus::isStoredOnce) {
 187               GS.StoredType = GlobalStatus::isStoredOnce;
 188               GS.StoredOnceValue = StoredVal;
 189             } else if (GS.StoredType == GlobalStatus::isStoredOnce &&
 190                        GS.StoredOnceValue == StoredVal) {
 191               // noop.
 192             } else {
 193               GS.StoredType = GlobalStatus::isStored;
 194             }
 195           } else {
 196             GS.StoredType = GlobalStatus::isStored;
 197           }
 198       } else if (isa<GetElementPtrInst>(I)) {
 199         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 200
 201         // If the first two indices are constants, this can be SRA'd.
 202         if (isa<GlobalVariable>(I->getOperand(0))) {
 203           if (I->getNumOperands() < 3 || !isa<Constant>(I->getOperand(1)) ||
 204               !cast<Constant>(I->getOperand(1))->isNullValue() ||
 205               !isa<ConstantInt>(I->getOperand(2)))
 206             GS.isNotSuitableForSRA = true;
 207         } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I->getOperand(0))){
 208           if (CE->getOpcode() != Instruction::GetElementPtr ||
 209               CE->getNumOperands() < 3 || I->getNumOperands() < 2 ||
 210               !isa<Constant>(I->getOperand(0)) ||
 211               !cast<Constant>(I->getOperand(0))->isNullValue())
 212             GS.isNotSuitableForSRA = true;
 213         } else {
 214           GS.isNotSuitableForSRA = true;
 215         }
 216       } else if (isa<SelectInst>(I)) {
 217         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 218         GS.isNotSuitableForSRA = true;
 219       } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
 220         // PHI nodes we can check just like select or GEP instructions, but we
 221         // have to be careful about infinite recursion.
 222         if (PHIUsers.insert(PN).second)  // Not already visited.
 223           if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 224         GS.isNotSuitableForSRA = true;
 225       } else if (isa<SetCondInst>(I)) {
 226         GS.isNotSuitableForSRA = true;
 227       } else if (isa<MemCpyInst>(I) || isa<MemMoveInst>(I)) {
 228         if (I->getOperand(1) == V)
 229           GS.StoredType = GlobalStatus::isStored;
 230         if (I->getOperand(2) == V)
 231           GS.isLoaded = true;
 232         GS.isNotSuitableForSRA = true;
 233       } else if (isa<MemSetInst>(I)) {
 234         assert(I->getOperand(1) == V && "Memset only takes one pointer!");
 235         GS.StoredType = GlobalStatus::isStored;
 236         GS.isNotSuitableForSRA = true;
 237       } else {
 238         return true;  // Any other non-load instruction might take address!
 239       }
 240     } else if (Constant *C = dyn_cast<Constant>(*UI)) {
 241       // We might have a dead and dangling constant hanging off of here.
 242       if (!ConstantIsDead(C))
 243         return true;
 244     } else {
 245       // Otherwise must be a global or some other user.
 246       return true;
 247     }
 248
 249   return false;
 250 }
 251
 252 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) {
 253   ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
 254   if (!CI) return 0;
 255   unsigned IdxV = (unsigned)CI->getRawValue();
 256
 257   if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) {
 258     if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV);
 259   } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) {
 260     if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV);
 261   } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Agg)) {
 262     if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV);
 263   } else if (isa<ConstantAggregateZero>(Agg)) {
 264     if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
 265       if (IdxV < STy->getNumElements())
 266         return Constant::getNullValue(STy->getElementType(IdxV));
 267     } else if (const SequentialType *STy =
 268                dyn_cast<SequentialType>(Agg->getType())) {
 269       return Constant::getNullValue(STy->getElementType());
 270     }
 271   } else if (isa<UndefValue>(Agg)) {
 272     if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
 273       if (IdxV < STy->getNumElements())
 274         return UndefValue::get(STy->getElementType(IdxV));
 275     } else if (const SequentialType *STy =
 276                dyn_cast<SequentialType>(Agg->getType())) {
 277       return UndefValue::get(STy->getElementType());
 278     }
 279   }
 280   return 0;
 281 }
 282
 283 static Constant *TraverseGEPInitializer(User *GEP, Constant *Init) {
 284   if (Init == 0) return 0;
 285   if (GEP->getNumOperands() == 1 ||
 286       !isa<Constant>(GEP->getOperand(1)) ||
 287       !cast<Constant>(GEP->getOperand(1))->isNullValue())
 288     return 0;
 289
 290   for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) {
 291     ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
 292     if (!Idx) return 0;
 293     Init = getAggregateConstantElement(Init, Idx);
 294     if (Init == 0) return 0;
 295   }
 296   return Init;
 297 }
 298
 299 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
 300 /// users of the global, cleaning up the obvious ones.  This is largely just a
 301 /// quick scan over the use list to clean up the easy and obvious cruft.  This
 302 /// returns true if it made a change.
 303 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) {
 304   bool Changed = false;
 305   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) {
 306     User *U = *UI++;
 307
 308     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
 309       if (Init) {
 310         // Replace the load with the initializer.
 311         LI->replaceAllUsesWith(Init);
 312         LI->eraseFromParent();
 313         Changed = true;
 314       }
 315     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 316       // Store must be unreachable or storing Init into the global.
 317       SI->eraseFromParent();
 318       Changed = true;
 319     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 320       if (CE->getOpcode() == Instruction::GetElementPtr) {
 321         Constant *SubInit = TraverseGEPInitializer(CE, Init);
 322         Changed |= CleanupConstantGlobalUsers(CE, SubInit);
 323       } else if (CE->getOpcode() == Instruction::Cast &&
 324                  isa<PointerType>(CE->getType())) {
 325         // Pointer cast, delete any stores and memsets to the global.
 326         Changed |= CleanupConstantGlobalUsers(CE, 0);
 327       }
 328
 329       if (CE->use_empty()) {
 330         CE->destroyConstant();
 331         Changed = true;
 332       }
 333     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
 334       Constant *SubInit = TraverseGEPInitializer(GEP, Init);
 335       Changed |= CleanupConstantGlobalUsers(GEP, SubInit);
 336
 337       if (GEP->use_empty()) {
 338         GEP->eraseFromParent();
 339         Changed = true;
 340       }
 341     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
 342       if (MI->getRawDest() == V) {
 343         MI->eraseFromParent();
 344         Changed = true;
 345       }
 346
 347     } else if (Constant *C = dyn_cast<Constant>(U)) {
 348       // If we have a chain of dead constantexprs or other things dangling from
 349       // us, and if they are all dead, nuke them without remorse.
 350       if (ConstantIsDead(C)) {
 351         C->destroyConstant();
 352         // This could have invalidated UI, start over from scratch.
 353         CleanupConstantGlobalUsers(V, Init);
 354         return true;
 355       }
 356     }
 357   }
 358   return Changed;
 359 }
 360
 361 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
 362 /// variable.  This opens the door for other optimizations by exposing the
 363 /// behavior of the program in a more fine-grained way.  We have determined that
 364 /// this transformation is safe already.  We return the first global variable we
 365 /// insert so that the caller can reprocess it.
 366 static GlobalVariable *SRAGlobal(GlobalVariable *GV) {
 367   assert(GV->hasInternalLinkage() && !GV->isConstant());
 368   Constant *Init = GV->getInitializer();
 369   const Type *Ty = Init->getType();
 370
 371   std::vector<GlobalVariable*> NewGlobals;
 372   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
 373
 374   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 375     NewGlobals.reserve(STy->getNumElements());
 376     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
 377       Constant *In = getAggregateConstantElement(Init,
 378                                             ConstantUInt::get(Type::UIntTy, i));
 379       assert(In && "Couldn't get element of initializer?");
 380       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
 381                                                GlobalVariable::InternalLinkage,
 382                                                In, GV->getName()+"."+utostr(i));
 383       Globals.insert(GV, NGV);
 384       NewGlobals.push_back(NGV);
 385     }
 386   } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
 387     unsigned NumElements = 0;
 388     if (const ArrayType *ATy = dyn_cast<ArrayType>(STy))
 389       NumElements = ATy->getNumElements();
 390     else if (const PackedType *PTy = dyn_cast<PackedType>(STy))
 391       NumElements = PTy->getNumElements();
 392     else
 393       assert(0 && "Unknown aggregate sequential type!");
 394
 395     if (NumElements > 16 && GV->hasNUsesOrMore(16))
 396       return 0; // It's not worth it.
 397     NewGlobals.reserve(NumElements);
 398     for (unsigned i = 0, e = NumElements; i != e; ++i) {
 399       Constant *In = getAggregateConstantElement(Init,
 400                                             ConstantUInt::get(Type::UIntTy, i));
 401       assert(In && "Couldn't get element of initializer?");
 402
 403       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
 404                                                GlobalVariable::InternalLinkage,
 405                                                In, GV->getName()+"."+utostr(i));
 406       Globals.insert(GV, NGV);
 407       NewGlobals.push_back(NGV);
 408     }
 409   }
 410
 411   if (NewGlobals.empty())
 412     return 0;
 413
 414   DEBUG(std::cerr << "PERFORMING GLOBAL SRA ON: " << *GV);
 415
 416   Constant *NullInt = Constant::getNullValue(Type::IntTy);
 417
 418   // Loop over all of the uses of the global, replacing the constantexpr geps,
 419   // with smaller constantexpr geps or direct references.
 420   while (!GV->use_empty()) {
 421     User *GEP = GV->use_back();
 422     assert(((isa<ConstantExpr>(GEP) &&
 423              cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||
 424             isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!");
 425
 426     // Ignore the 1th operand, which has to be zero or else the program is quite
 427     // broken (undefined).  Get the 2nd operand, which is the structure or array
 428     // index.
 429     unsigned Val =
 430        (unsigned)cast<ConstantInt>(GEP->getOperand(2))->getRawValue();
 431     if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
 432
 433     Value *NewPtr = NewGlobals[Val];
 434
 435     // Form a shorter GEP if needed.
 436     if (GEP->getNumOperands() > 3)
 437       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
 438         std::vector<Constant*> Idxs;
 439         Idxs.push_back(NullInt);
 440         for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
 441           Idxs.push_back(CE->getOperand(i));
 442         NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), Idxs);
 443       } else {
 444         GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
 445         std::vector<Value*> Idxs;
 446         Idxs.push_back(NullInt);
 447         for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
 448           Idxs.push_back(GEPI->getOperand(i));
 449         NewPtr = new GetElementPtrInst(NewPtr, Idxs,
 450                                        GEPI->getName()+"."+utostr(Val), GEPI);
 451       }
 452     GEP->replaceAllUsesWith(NewPtr);
 453
 454     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
 455       GEPI->eraseFromParent();
 456     else
 457       cast<ConstantExpr>(GEP)->destroyConstant();
 458   }
 459
 460   // Delete the old global, now that it is dead.
 461   Globals.erase(GV);
 462   ++NumSRA;
 463
 464   // Loop over the new globals array deleting any globals that are obviously
 465   // dead.  This can arise due to scalarization of a structure or an array that
 466   // has elements that are dead.
 467   unsigned FirstGlobal = 0;
 468   for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i)
 469     if (NewGlobals[i]->use_empty()) {
 470       Globals.erase(NewGlobals[i]);
 471       if (FirstGlobal == i) ++FirstGlobal;
 472     }
 473
 474   return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0;
 475 }
 476
 477 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified
 478 /// value will trap if the value is dynamically null.
 479 static bool AllUsesOfValueWillTrapIfNull(Value *V) {
 480   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 481     if (isa<LoadInst>(*UI)) {
 482       // Will trap.
 483     } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
 484       if (SI->getOperand(0) == V) {
 485         //std::cerr << "NONTRAPPING USE: " << **UI;
 486         return false;  // Storing the value.
 487       }
 488     } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
 489       if (CI->getOperand(0) != V) {
 490         //std::cerr << "NONTRAPPING USE: " << **UI;
 491         return false;  // Not calling the ptr
 492       }
 493     } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) {
 494       if (II->getOperand(0) != V) {
 495         //std::cerr << "NONTRAPPING USE: " << **UI;
 496         return false;  // Not calling the ptr
 497       }
 498     } else if (CastInst *CI = dyn_cast<CastInst>(*UI)) {
 499       if (!AllUsesOfValueWillTrapIfNull(CI)) return false;
 500     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) {
 501       if (!AllUsesOfValueWillTrapIfNull(GEPI)) return false;
 502     } else if (isa<SetCondInst>(*UI) &&
 503                isa<ConstantPointerNull>(UI->getOperand(1))) {
 504       // Ignore setcc X, null
 505     } else {
 506       //std::cerr << "NONTRAPPING USE: " << **UI;
 507       return false;
 508     }
 509   return true;
 510 }
 511
 512 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads
 513 /// from GV will trap if the loaded value is null.  Note that this also permits
 514 /// comparisons of the loaded value against null, as a special case.
 515 static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) {
 516   for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI!=E; ++UI)
 517     if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
 518       if (!AllUsesOfValueWillTrapIfNull(LI))
 519         return false;
 520     } else if (isa<StoreInst>(*UI)) {
 521       // Ignore stores to the global.
 522     } else {
 523       // We don't know or understand this user, bail out.
 524       //std::cerr << "UNKNOWN USER OF GLOBAL!: " << **UI;
 525       return false;
 526     }
 527
 528   return true;
 529 }
 530
 531 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
 532   bool Changed = false;
 533   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) {
 534     Instruction *I = cast<Instruction>(*UI++);
 535     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 536       LI->setOperand(0, NewV);
 537       Changed = true;
 538     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 539       if (SI->getOperand(1) == V) {
 540         SI->setOperand(1, NewV);
 541         Changed = true;
 542       }
 543     } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
 544       if (I->getOperand(0) == V) {
 545         // Calling through the pointer!  Turn into a direct call, but be careful
 546         // that the pointer is not also being passed as an argument.
 547         I->setOperand(0, NewV);
 548         Changed = true;
 549         bool PassedAsArg = false;
 550         for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
 551           if (I->getOperand(i) == V) {
 552             PassedAsArg = true;
 553             I->setOperand(i, NewV);
 554           }
 555
 556         if (PassedAsArg) {
 557           // Being passed as an argument also.  Be careful to not invalidate UI!
 558           UI = V->use_begin();
 559         }
 560       }
 561     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
 562       Changed |= OptimizeAwayTrappingUsesOfValue(CI,
 563                                     ConstantExpr::getCast(NewV, CI->getType()));
 564       if (CI->use_empty()) {
 565         Changed = true;
 566         CI->eraseFromParent();
 567       }
 568     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
 569       // Should handle GEP here.
 570       std::vector<Constant*> Indices;
 571       Indices.reserve(GEPI->getNumOperands()-1);
 572       for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i)
 573         if (Constant *C = dyn_cast<Constant>(GEPI->getOperand(i)))
 574           Indices.push_back(C);
 575         else
 576           break;
 577       if (Indices.size() == GEPI->getNumOperands()-1)
 578         Changed |= OptimizeAwayTrappingUsesOfValue(GEPI,
 579                                 ConstantExpr::getGetElementPtr(NewV, Indices));
 580       if (GEPI->use_empty()) {
 581         Changed = true;
 582         GEPI->eraseFromParent();
 583       }
 584     }
 585   }
 586
 587   return Changed;
 588 }
 589
 590
 591 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null
 592 /// value stored into it.  If there are uses of the loaded value that would trap
 593 /// if the loaded value is dynamically null, then we know that they cannot be
 594 /// reachable with a null optimize away the load.
 595 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) {
 596   std::vector<LoadInst*> Loads;
 597   bool Changed = false;
 598
 599   // Replace all uses of loads with uses of uses of the stored value.
 600   for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end();
 601        GUI != E; ++GUI)
 602     if (LoadInst *LI = dyn_cast<LoadInst>(*GUI)) {
 603       Loads.push_back(LI);
 604       Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
 605     } else {
 606       assert(isa<StoreInst>(*GUI) && "Only expect load and stores!");
 607     }
 608
 609   if (Changed) {
 610     DEBUG(std::cerr << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV);
 611     ++NumGlobUses;
 612   }
 613
 614   // Delete all of the loads we can, keeping track of whether we nuked them all!
 615   bool AllLoadsGone = true;
 616   while (!Loads.empty()) {
 617     LoadInst *L = Loads.back();
 618     if (L->use_empty()) {
 619       L->eraseFromParent();
 620       Changed = true;
 621     } else {
 622       AllLoadsGone = false;
 623     }
 624     Loads.pop_back();
 625   }
 626
 627   // If we nuked all of the loads, then none of the stores are needed either,
 628   // nor is the global.
 629   if (AllLoadsGone) {
 630     DEBUG(std::cerr << "  *** GLOBAL NOW DEAD!\n");
 631     CleanupConstantGlobalUsers(GV, 0);
 632     if (GV->use_empty()) {
 633       GV->eraseFromParent();
 634       ++NumDeleted;
 635     }
 636     Changed = true;
 637   }
 638   return Changed;
 639 }
 640
 641 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the
 642 /// instructions that are foldable.
 643 static void ConstantPropUsersOf(Value *V) {
 644   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; )
 645     if (Instruction *I = dyn_cast<Instruction>(*UI++))
 646       if (Constant *NewC = ConstantFoldInstruction(I)) {
 647         I->replaceAllUsesWith(NewC);
 648
 649         // Advance UI to the next non-I use to avoid invalidating it!
 650         // Instructions could multiply use V.
 651         while (UI != E && *UI == I)
 652           ++UI;
 653         I->eraseFromParent();
 654       }
 655 }
 656
 657 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global
 658 /// variable, and transforms the program as if it always contained the result of
 659 /// the specified malloc.  Because it is always the result of the specified
 660 /// malloc, there is no reason to actually DO the malloc.  Instead, turn the
 661 /// malloc into a global, and any laods of GV as uses of the new global.
 662 static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV,
 663                                                      MallocInst *MI) {
 664   DEBUG(std::cerr << "PROMOTING MALLOC GLOBAL: " << *GV << "  MALLOC = " <<*MI);
 665   ConstantInt *NElements = cast<ConstantInt>(MI->getArraySize());
 666
 667   if (NElements->getRawValue() != 1) {
 668     // If we have an array allocation, transform it to a single element
 669     // allocation to make the code below simpler.
 670     Type *NewTy = ArrayType::get(MI->getAllocatedType(),
 671                                  (unsigned)NElements->getRawValue());
 672     MallocInst *NewMI =
 673       new MallocInst(NewTy, Constant::getNullValue(Type::UIntTy),
 674                      MI->getName(), MI);
 675     std::vector<Value*> Indices;
 676     Indices.push_back(Constant::getNullValue(Type::IntTy));
 677     Indices.push_back(Indices[0]);
 678     Value *NewGEP = new GetElementPtrInst(NewMI, Indices,
 679                                           NewMI->getName()+".el0", MI);
 680     MI->replaceAllUsesWith(NewGEP);
 681     MI->eraseFromParent();
 682     MI = NewMI;
 683   }
 684
 685   // Create the new global variable.  The contents of the malloc'd memory is
 686   // undefined, so initialize with an undef value.
 687   Constant *Init = UndefValue::get(MI->getAllocatedType());
 688   GlobalVariable *NewGV = new GlobalVariable(MI->getAllocatedType(), false,
 689                                              GlobalValue::InternalLinkage, Init,
 690                                              GV->getName()+".body");
 691   GV->getParent()->getGlobalList().insert(GV, NewGV);
 692
 693   // Anything that used the malloc now uses the global directly.
 694   MI->replaceAllUsesWith(NewGV);
 695
 696   Constant *RepValue = NewGV;
 697   if (NewGV->getType() != GV->getType()->getElementType())
 698     RepValue = ConstantExpr::getCast(RepValue, GV->getType()->getElementType());
 699
 700   // If there is a comparison against null, we will insert a global bool to
 701   // keep track of whether the global was initialized yet or not.
 702   GlobalVariable *InitBool =
 703     new GlobalVariable(Type::BoolTy, false, GlobalValue::InternalLinkage,
 704                        ConstantBool::False, GV->getName()+".init");
 705   bool InitBoolUsed = false;
 706
 707   // Loop over all uses of GV, processing them in turn.
 708   std::vector<StoreInst*> Stores;
 709   while (!GV->use_empty())
 710     if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) {
 711       while (!LI->use_empty()) {
 712         Use &LoadUse = LI->use_begin().getUse();
 713         if (!isa<SetCondInst>(LoadUse.getUser()))
 714           LoadUse = RepValue;
 715         else {
 716           // Replace the setcc X, 0 with a use of the bool value.
 717           SetCondInst *SCI = cast<SetCondInst>(LoadUse.getUser());
 718           Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", SCI);
 719           InitBoolUsed = true;
 720           switch (SCI->getOpcode()) {
 721           default: assert(0 && "Unknown opcode!");
 722           case Instruction::SetLT:
 723             LV = ConstantBool::False;   // X < null -> always false
 724             break;
 725           case Instruction::SetEQ:
 726           case Instruction::SetLE:
 727             LV = BinaryOperator::createNot(LV, "notinit", SCI);
 728             break;
 729           case Instruction::SetNE:
 730           case Instruction::SetGE:
 731           case Instruction::SetGT:
 732             break;  // no change.
 733           }
 734           SCI->replaceAllUsesWith(LV);
 735           SCI->eraseFromParent();
 736         }
 737       }
 738       LI->eraseFromParent();
 739     } else {
 740       StoreInst *SI = cast<StoreInst>(GV->use_back());
 741       // The global is initialized when the store to it occurs.
 742       new StoreInst(ConstantBool::True, InitBool, SI);
 743       SI->eraseFromParent();
 744     }
 745
 746   // If the initialization boolean was used, insert it, otherwise delete it.
 747   if (!InitBoolUsed) {
 748     while (!InitBool->use_empty())  // Delete initializations
 749       cast<Instruction>(InitBool->use_back())->eraseFromParent();
 750     delete InitBool;
 751   } else
 752     GV->getParent()->getGlobalList().insert(GV, InitBool);
 753
 754
 755   // Now the GV is dead, nuke it and the malloc.
 756   GV->eraseFromParent();
 757   MI->eraseFromParent();
 758
 759   // To further other optimizations, loop over all users of NewGV and try to
 760   // constant prop them.  This will promote GEP instructions with constant
 761   // indices into GEP constant-exprs, which will allow global-opt to hack on it.
 762   ConstantPropUsersOf(NewGV);
 763   if (RepValue != NewGV)
 764     ConstantPropUsersOf(RepValue);
 765
 766   return NewGV;
 767 }
 768
 769 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking
 770 /// to make sure that there are no complex uses of V.  We permit simple things
 771 /// like dereferencing the pointer, but not storing through the address, unless
 772 /// it is to the specified global.
 773 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Instruction *V,
 774                                                       GlobalVariable *GV) {
 775   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI)
 776     if (isa<LoadInst>(*UI) || isa<SetCondInst>(*UI)) {
 777       // Fine, ignore.
 778     } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
 779       if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
 780         return false;  // Storing the pointer itself... bad.
 781       // Otherwise, storing through it, or storing into GV... fine.
 782     } else if (isa<GetElementPtrInst>(*UI) || isa<SelectInst>(*UI)) {
 783       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(cast<Instruction>(*UI),GV))
 784         return false;
 785     } else {
 786       return false;
 787     }
 788   return true;
 789
 790 }
 791
 792 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge
 793 // that only one value (besides its initializer) is ever stored to the global.
 794 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
 795                                      Module::global_iterator &GVI, TargetData &TD) {
 796   if (CastInst *CI = dyn_cast<CastInst>(StoredOnceVal))
 797     StoredOnceVal = CI->getOperand(0);
 798   else if (GetElementPtrInst *GEPI =dyn_cast<GetElementPtrInst>(StoredOnceVal)){
 799     // "getelementptr Ptr, 0, 0, 0" is really just a cast.
 800     bool IsJustACast = true;
 801     for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i)
 802       if (!isa<Constant>(GEPI->getOperand(i)) ||
 803           !cast<Constant>(GEPI->getOperand(i))->isNullValue()) {
 804         IsJustACast = false;
 805         break;
 806       }
 807     if (IsJustACast)
 808       StoredOnceVal = GEPI->getOperand(0);
 809   }
 810
 811   // If we are dealing with a pointer global that is initialized to null and
 812   // only has one (non-null) value stored into it, then we can optimize any
 813   // users of the loaded value (often calls and loads) that would trap if the
 814   // value was null.
 815   if (isa<PointerType>(GV->getInitializer()->getType()) &&
 816       GV->getInitializer()->isNullValue()) {
 817     if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
 818       if (GV->getInitializer()->getType() != SOVC->getType())
 819         SOVC = ConstantExpr::getCast(SOVC, GV->getInitializer()->getType());
 820
 821       // Optimize away any trapping uses of the loaded value.
 822       if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC))
 823         return true;
 824     } else if (MallocInst *MI = dyn_cast<MallocInst>(StoredOnceVal)) {
 825       // If we have a global that is only initialized with a fixed size malloc,
 826       // and if all users of the malloc trap, and if the malloc'd address is not
 827       // put anywhere else, transform the program to use global memory instead
 828       // of malloc'd memory.  This eliminates dynamic allocation (good) and
 829       // exposes the resultant global to further GlobalOpt (even better).  Note
 830       // that we restrict this transformation to only working on small
 831       // allocations (2048 bytes currently), as we don't want to introduce a 16M
 832       // global or something.
 833       if (ConstantInt *NElements = dyn_cast<ConstantInt>(MI->getArraySize()))
 834         if (MI->getAllocatedType()->isSized() &&
 835             NElements->getRawValue()*
 836                      TD.getTypeSize(MI->getAllocatedType()) < 2048 &&
 837             AllUsesOfLoadedValueWillTrapIfNull(GV) &&
 838             ValueIsOnlyUsedLocallyOrStoredToOneGlobal(MI, GV)) {
 839           GVI = OptimizeGlobalAddressOfMalloc(GV, MI);
 840           return true;
 841         }
 842     }
 843   }
 844
 845   return false;
 846 }
 847
 848 /// ShrinkGlobalToBoolean - At this point, we have learned that the only two
 849 /// values ever stored into GV are its initializer and OtherVal.
 850 static void ShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
 851   // Create the new global, initializing it to false.
 852   GlobalVariable *NewGV = new GlobalVariable(Type::BoolTy, false,
 853          GlobalValue::InternalLinkage, ConstantBool::False, GV->getName()+".b");
 854   GV->getParent()->getGlobalList().insert(GV, NewGV);
 855
 856   Constant *InitVal = GV->getInitializer();
 857   assert(InitVal->getType() != Type::BoolTy && "No reason to shrink to bool!");
 858
 859   // If initialized to zero and storing one into the global, we can use a cast
 860   // instead of a select to synthesize the desired value.
 861   bool IsOneZero = false;
 862   if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal))
 863     IsOneZero = InitVal->isNullValue() && CI->equalsInt(1);
 864
 865   while (!GV->use_empty()) {
 866     Instruction *UI = cast<Instruction>(GV->use_back());
 867     if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
 868       // Change the store into a boolean store.
 869       bool StoringOther = SI->getOperand(0) == OtherVal;
 870       // Only do this if we weren't storing a loaded value.
 871       Value *StoreVal;
 872       if (StoringOther || SI->getOperand(0) == InitVal)
 873         StoreVal = ConstantBool::get(StoringOther);
 874       else {
 875         // Otherwise, we are storing a previously loaded copy.  To do this,
 876         // change the copy from copying the original value to just copying the
 877         // bool.
 878         Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
 879
 880         // If we're already replaced the input, StoredVal will be a cast or
 881         // select instruction.  If not, it will be a load of the original
 882         // global.
 883         if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
 884           assert(LI->getOperand(0) == GV && "Not a copy!");
 885           // Insert a new load, to preserve the saved value.
 886           StoreVal = new LoadInst(NewGV, LI->getName()+".b", LI);
 887         } else {
 888           assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&
 889                  "This is not a form that we understand!");
 890           StoreVal = StoredVal->getOperand(0);
 891           assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!");
 892         }
 893       }
 894       new StoreInst(StoreVal, NewGV, SI);
 895     } else if (!UI->use_empty()) {
 896       // Change the load into a load of bool then a select.
 897       LoadInst *LI = cast<LoadInst>(UI);
 898
 899       std::string Name = LI->getName(); LI->setName("");
 900       LoadInst *NLI = new LoadInst(NewGV, Name+".b", LI);
 901       Value *NSI;
 902       if (IsOneZero)
 903         NSI = new CastInst(NLI, LI->getType(), Name, LI);
 904       else
 905         NSI = new SelectInst(NLI, OtherVal, InitVal, Name, LI);
 906       LI->replaceAllUsesWith(NSI);
 907     }
 908     UI->eraseFromParent();
 909   }
 910
 911   GV->eraseFromParent();
 912 }
 913
 914
 915 /// ProcessInternalGlobal - Analyze the specified global variable and optimize
 916 /// it if possible.  If we make a change, return true.
 917 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
 918                                       Module::global_iterator &GVI) {
 919   std::set<PHINode*> PHIUsers;
 920   GlobalStatus GS;
 921   PHIUsers.clear();
 922   GV->removeDeadConstantUsers();
 923
 924   if (GV->use_empty()) {
 925     DEBUG(std::cerr << "GLOBAL DEAD: " << *GV);
 926     GV->eraseFromParent();
 927     ++NumDeleted;
 928     return true;
 929   }
 930
 931   if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
 932     // If this is a first class global and has only one accessing function
 933     // and this function is main (which we know is not recursive we can make
 934     // this global a local variable) we replace the global with a local alloca
 935     // in this function.
 936     //
 937     // NOTE: It doesn't make sense to promote non first class types since we
 938     // are just replacing static memory to stack memory.
 939     if (!GS.HasMultipleAccessingFunctions &&
 940         GS.AccessingFunction &&
 941         GV->getType()->getElementType()->isFirstClassType() &&
 942         GS.AccessingFunction->getName() == "main" &&
 943         GS.AccessingFunction->hasExternalLinkage()) {
 944       DEBUG(std::cerr << "LOCALIZING GLOBAL: " << *GV);
 945       Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin();
 946       const Type* ElemTy = GV->getType()->getElementType();
 947       AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), FirstI);
 948       if (!isa<UndefValue>(GV->getInitializer()))
 949         new StoreInst(GV->getInitializer(), Alloca, FirstI);
 950
 951       GV->replaceAllUsesWith(Alloca);
 952       GV->eraseFromParent();
 953       ++NumLocalized;
 954       return true;
 955     }
 956     // If the global is never loaded (but may be stored to), it is dead.
 957     // Delete it now.
 958     if (!GS.isLoaded) {
 959       DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV);
 960
 961       // Delete any stores we can find to the global.  We may not be able to
 962       // make it completely dead though.
 963       bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer());
 964
 965       // If the global is dead now, delete it.
 966       if (GV->use_empty()) {
 967         GV->eraseFromParent();
 968         ++NumDeleted;
 969         Changed = true;
 970       }
 971       return Changed;
 972
 973     } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
 974       DEBUG(std::cerr << "MARKING CONSTANT: " << *GV);
 975       GV->setConstant(true);
 976
 977       // Clean up any obviously simplifiable users now.
 978       CleanupConstantGlobalUsers(GV, GV->getInitializer());
 979
 980       // If the global is dead now, just nuke it.
 981       if (GV->use_empty()) {
 982         DEBUG(std::cerr << "   *** Marking constant allowed us to simplify "
 983               "all users and delete global!\n");
 984         GV->eraseFromParent();
 985         ++NumDeleted;
 986       }
 987
 988       ++NumMarked;
 989       return true;
 990     } else if (!GS.isNotSuitableForSRA &&
 991                !GV->getInitializer()->getType()->isFirstClassType()) {
 992       if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) {
 993         GVI = FirstNewGV;  // Don't skip the newly produced globals!
 994         return true;
 995       }
 996     } else if (GS.StoredType == GlobalStatus::isStoredOnce) {
 997       // If the initial value for the global was an undef value, and if only
 998       // one other value was stored into it, we can just change the
 999       // initializer to be an undef value, then delete all stores to the
1000       // global.  This allows us to mark it constant.
1001       if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
1002         if (isa<UndefValue>(GV->getInitializer())) {
1003           // Change the initial value here.
1004           GV->setInitializer(SOVConstant);
1005
1006           // Clean up any obviously simplifiable users now.
1007           CleanupConstantGlobalUsers(GV, GV->getInitializer());
1008
1009           if (GV->use_empty()) {
1010             DEBUG(std::cerr << "   *** Substituting initializer allowed us to "
1011                   "simplify all users and delete global!\n");
1012             GV->eraseFromParent();
1013             ++NumDeleted;
1014           } else {
1015             GVI = GV;
1016           }
1017           ++NumSubstitute;
1018           return true;
1019         }
1020
1021       // Try to optimize globals based on the knowledge that only one value
1022       // (besides its initializer) is ever stored to the global.
1023       if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GVI,
1024                                    getAnalysis<TargetData>()))
1025         return true;
1026
1027       // Otherwise, if the global was not a boolean, we can shrink it to be a
1028       // boolean.
1029       if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
1030         if (GV->getType()->getElementType() != Type::BoolTy &&
1031             !GV->getType()->getElementType()->isFloatingPoint()) {
1032           DEBUG(std::cerr << "   *** SHRINKING TO BOOL: " << *GV);
1033           ShrinkGlobalToBoolean(GV, SOVConstant);
1034           ++NumShrunkToBool;
1035           return true;
1036         }
1037     }
1038   }
1039   return false;
1040 }
1041
1042
1043 bool GlobalOpt::runOnModule(Module &M) {
1044   bool Changed = false;
1045
1046   // As a prepass, delete functions that are trivially dead.
1047   bool LocalChange = true;
1048   while (LocalChange) {
1049     LocalChange = false;
1050     for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
1051       Function *F = FI++;
1052       F->removeDeadConstantUsers();
1053       if (F->use_empty() && (F->hasInternalLinkage() ||
1054                              F->hasLinkOnceLinkage())) {
1055         M.getFunctionList().erase(F);
1056         LocalChange = true;
1057         ++NumFnDeleted;
1058       }
1059     }
1060     Changed |= LocalChange;
1061   }
1062
1063   LocalChange = true;
1064   while (LocalChange) {
1065     LocalChange = false;
1066     for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); GVI != E;) {
1067       GlobalVariable *GV = GVI++;
1068       if (!GV->isConstant() && GV->hasInternalLinkage() &&
1069           GV->hasInitializer())
1070         LocalChange |= ProcessInternalGlobal(GV, GVI);
1071     }
1072     Changed |= LocalChange;
1073   }
1074   return Changed;
1075 }