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
  37   struct GlobalOpt : public ModulePass {
  38     bool runOnModule(Module &M);
  39   };
  40
  41   RegisterOpt<GlobalOpt> X("globalopt", "Global Variable Optimizer");
  42 }
  43
  44 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
  45
  46 /// GlobalStatus - As we analyze each global, keep track of some information
  47 /// about it.  If we find out that the address of the global is taken, none of
  48 /// this info will be accurate.
  49 struct GlobalStatus {
  50   /// isLoaded - True if the global is ever loaded.  If the global isn't ever
  51   /// loaded it can be deleted.
  52   bool isLoaded;
  53
  54   /// StoredType - Keep track of what stores to the global look like.
  55   ///
  56   enum StoredType {
  57     /// NotStored - There is no store to this global.  It can thus be marked
  58     /// constant.
  59     NotStored,
  60
  61     /// isInitializerStored - This global is stored to, but the only thing
  62     /// stored is the constant it was initialized with.  This is only tracked
  63     /// for scalar globals.
  64     isInitializerStored,
  65
  66     /// isStoredOnce - This global is stored to, but only its initializer and
  67     /// one other value is ever stored to it.  If this global isStoredOnce, we
  68     /// track the value stored to it in StoredOnceValue below.  This is only
  69     /// tracked for scalar globals.
  70     isStoredOnce,
  71
  72     /// isStored - This global is stored to by multiple values or something else
  73     /// that we cannot track.
  74     isStored
  75   } StoredType;
  76
  77   /// StoredOnceValue - If only one value (besides the initializer constant) is
  78   /// ever stored to this global, keep track of what value it is.
  79   Value *StoredOnceValue;
  80
  81   /// isNotSuitableForSRA - Keep track of whether any SRA preventing users of
  82   /// the global exist.  Such users include GEP instruction with variable
  83   /// indexes, and non-gep/load/store users like constant expr casts.
  84   bool isNotSuitableForSRA;
  85
  86   GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0),
  87                    isNotSuitableForSRA(false) {}
  88 };
  89
  90
  91
  92 /// ConstantIsDead - Return true if the specified constant is (transitively)
  93 /// dead.  The constant may be used by other constants (e.g. constant arrays and
  94 /// constant exprs) as long as they are dead, but it cannot be used by anything
  95 /// else.
  96 static bool ConstantIsDead(Constant *C) {
  97   if (isa<GlobalValue>(C)) return false;
  98
  99   for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI)
 100     if (Constant *CU = dyn_cast<Constant>(*UI)) {
 101       if (!ConstantIsDead(CU)) return false;
 102     } else
 103       return false;
 104   return true;
 105 }
 106
 107
 108 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus
 109 /// structure.  If the global has its address taken, return true to indicate we
 110 /// can't do anything with it.
 111 ///
 112 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
 113                           std::set<PHINode*> &PHIUsers) {
 114   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
 115     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
 116       if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
 117       if (CE->getOpcode() != Instruction::GetElementPtr)
 118         GS.isNotSuitableForSRA = true;
 119       else if (!GS.isNotSuitableForSRA) {
 120         // Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
 121         // don't like < 3 operand CE's, and we don't like non-constant integer
 122         // indices.
 123         if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue())
 124           GS.isNotSuitableForSRA = true;
 125         else {
 126           for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
 127             if (!isa<ConstantInt>(CE->getOperand(i))) {
 128               GS.isNotSuitableForSRA = true;
 129               break;
 130             }
 131         }
 132       }
 133
 134     } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
 135       if (isa<LoadInst>(I)) {
 136         GS.isLoaded = true;
 137       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 138         // Don't allow a store OF the address, only stores TO the address.
 139         if (SI->getOperand(0) == V) return true;
 140
 141         // If this is a direct store to the global (i.e., the global is a scalar
 142         // value, not an aggregate), keep more specific information about
 143         // stores.
 144         if (GS.StoredType != GlobalStatus::isStored)
 145           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
 146             if (SI->getOperand(0) == GV->getInitializer()) {
 147               if (GS.StoredType < GlobalStatus::isInitializerStored)
 148                 GS.StoredType = GlobalStatus::isInitializerStored;
 149             } else if (GS.StoredType < GlobalStatus::isStoredOnce) {
 150               GS.StoredType = GlobalStatus::isStoredOnce;
 151               GS.StoredOnceValue = SI->getOperand(0);
 152             } else if (GS.StoredType == GlobalStatus::isStoredOnce &&
 153                        GS.StoredOnceValue == SI->getOperand(0)) {
 154               // noop.
 155             } else {
 156               GS.StoredType = GlobalStatus::isStored;
 157             }
 158           } else {
 159             GS.StoredType = GlobalStatus::isStored;
 160           }
 161       } else if (I->getOpcode() == Instruction::GetElementPtr) {
 162         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 163         // Theoretically we could SRA globals with GEP insts if all indexes are
 164         // constants.  In practice, these GEPs would already be constant exprs
 165         // if that was the case though.
 166         GS.isNotSuitableForSRA = true;
 167       } else if (I->getOpcode() == Instruction::Select) {
 168         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 169         GS.isNotSuitableForSRA = true;
 170       } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
 171         // PHI nodes we can check just like select or GEP instructions, but we
 172         // have to be careful about infinite recursion.
 173         if (PHIUsers.insert(PN).second)  // Not already visited.
 174           if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 175         GS.isNotSuitableForSRA = true;
 176       } else if (isa<SetCondInst>(I)) {
 177         GS.isNotSuitableForSRA = true;
 178       } else {
 179         return true;  // Any other non-load instruction might take address!
 180       }
 181     } else if (Constant *C = dyn_cast<Constant>(*UI)) {
 182       // We might have a dead and dangling constant hanging off of here.
 183       if (!ConstantIsDead(C))
 184         return true;
 185     } else {
 186       // Otherwise must be a global or some other user.
 187       return true;
 188     }
 189
 190   return false;
 191 }
 192
 193 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) {
 194   ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
 195   if (!CI) return 0;
 196   uint64_t IdxV = CI->getRawValue();
 197
 198   if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) {
 199     if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV);
 200   } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) {
 201     if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV);
 202   } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Agg)) {
 203     if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV);
 204   } else if (ConstantAggregateZero *CAZ =
 205              dyn_cast<ConstantAggregateZero>(Agg)) {
 206     if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
 207       if (IdxV < STy->getNumElements())
 208         return Constant::getNullValue(STy->getElementType(IdxV));
 209     } else if (const SequentialType *STy =
 210                dyn_cast<SequentialType>(Agg->getType())) {
 211       return Constant::getNullValue(STy->getElementType());
 212     }
 213   }
 214   return 0;
 215 }
 216
 217 static Constant *TraverseGEPInitializer(User *GEP, Constant *Init) {
 218   if (GEP->getNumOperands() == 1 ||
 219       !isa<Constant>(GEP->getOperand(1)) ||
 220       !cast<Constant>(GEP->getOperand(1))->isNullValue())
 221     return 0;
 222
 223   for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) {
 224     ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
 225     if (!Idx) return 0;
 226     Init = getAggregateConstantElement(Init, Idx);
 227     if (Init == 0) return 0;
 228   }
 229   return Init;
 230 }
 231
 232 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
 233 /// users of the global, cleaning up the obvious ones.  This is largely just a
 234 /// quick scan over the use list to clean up the easy and obvious cruft.
 235 static void CleanupConstantGlobalUsers(Value *V, Constant *Init) {
 236   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) {
 237     User *U = *UI++;
 238
 239     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
 240       // Replace the load with the initializer.
 241       LI->replaceAllUsesWith(Init);
 242       LI->getParent()->getInstList().erase(LI);
 243     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 244       // Store must be unreachable or storing Init into the global.
 245       SI->getParent()->getInstList().erase(SI);
 246     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 247       if (CE->getOpcode() == Instruction::GetElementPtr) {
 248         if (Constant *SubInit = TraverseGEPInitializer(CE, Init))
 249           CleanupConstantGlobalUsers(CE, SubInit);
 250         if (CE->use_empty()) CE->destroyConstant();
 251       }
 252     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
 253       if (Constant *SubInit = TraverseGEPInitializer(GEP, Init))
 254         CleanupConstantGlobalUsers(GEP, SubInit);
 255       if (GEP->use_empty())
 256         GEP->getParent()->getInstList().erase(GEP);
 257     } else if (Constant *C = dyn_cast<Constant>(U)) {
 258       // If we have a chain of dead constantexprs or other things dangling from
 259       // us, and if they are all dead, nuke them without remorse.
 260       if (ConstantIsDead(C)) {
 261         C->destroyConstant();
 262         // This could have incalidated UI, start over from scratch.x
 263         CleanupConstantGlobalUsers(V, Init);
 264         return;
 265       }
 266     }
 267   }
 268 }
 269
 270 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
 271 /// variable.  This opens the door for other optimizations by exposing the
 272 /// behavior of the program in a more fine-grained way.  We have determined that
 273 /// this transformation is safe already.  We return the first global variable we
 274 /// insert so that the caller can reprocess it.
 275 static GlobalVariable *SRAGlobal(GlobalVariable *GV) {
 276   assert(GV->hasInternalLinkage() && !GV->isConstant());
 277   Constant *Init = GV->getInitializer();
 278   const Type *Ty = Init->getType();
 279
 280   std::vector<GlobalVariable*> NewGlobals;
 281   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
 282
 283   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 284     NewGlobals.reserve(STy->getNumElements());
 285     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
 286       Constant *In = getAggregateConstantElement(Init,
 287                                             ConstantUInt::get(Type::UIntTy, i));
 288       assert(In && "Couldn't get element of initializer?");
 289       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
 290                                                GlobalVariable::InternalLinkage,
 291                                                In, GV->getName()+"."+utostr(i));
 292       Globals.insert(GV, NGV);
 293       NewGlobals.push_back(NGV);
 294     }
 295   } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
 296     unsigned NumElements = 0;
 297     if (const ArrayType *ATy = dyn_cast<ArrayType>(STy))
 298       NumElements = ATy->getNumElements();
 299     else if (const PackedType *PTy = dyn_cast<PackedType>(STy))
 300       NumElements = PTy->getNumElements();
 301     else
 302       assert(0 && "Unknown aggregate sequential type!");
 303
 304     if (NumElements > 16) return 0; // It's not worth it.
 305     NewGlobals.reserve(NumElements);
 306     for (unsigned i = 0, e = NumElements; i != e; ++i) {
 307       Constant *In = getAggregateConstantElement(Init,
 308                                             ConstantUInt::get(Type::UIntTy, i));
 309       assert(In && "Couldn't get element of initializer?");
 310
 311       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
 312                                                GlobalVariable::InternalLinkage,
 313                                                In, GV->getName()+"."+utostr(i));
 314       Globals.insert(GV, NGV);
 315       NewGlobals.push_back(NGV);
 316     }
 317   }
 318
 319   if (NewGlobals.empty())
 320     return 0;
 321
 322   Constant *NullInt = Constant::getNullValue(Type::IntTy);
 323
 324   // Loop over all of the uses of the global, replacing the constantexpr geps,
 325   // with smaller constantexpr geps or direct references.
 326   while (!GV->use_empty()) {
 327     ConstantExpr *CE = cast<ConstantExpr>(GV->use_back());
 328     assert(CE->getOpcode() == Instruction::GetElementPtr &&
 329            "NonGEP CE's are not SRAable!");
 330     // Ignore the 1th operand, which has to be zero or else the program is quite
 331     // broken (undefined).  Get the 2nd operand, which is the structure or array
 332     // index.
 333     unsigned Val = cast<ConstantInt>(CE->getOperand(2))->getRawValue();
 334     if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
 335
 336     Constant *NewPtr = NewGlobals[Val];
 337
 338     // Form a shorter GEP if needed.
 339     if (CE->getNumOperands() > 3) {
 340       std::vector<Constant*> Idxs;
 341       Idxs.push_back(NullInt);
 342       for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
 343         Idxs.push_back(CE->getOperand(i));
 344       NewPtr = ConstantExpr::getGetElementPtr(NewPtr, Idxs);
 345     }
 346     CE->replaceAllUsesWith(NewPtr);
 347     CE->destroyConstant();
 348   }
 349
 350   // Delete the old global, now that it is dead.
 351   Globals.erase(GV);
 352   ++NumSRA;
 353   return NewGlobals[0];
 354 }
 355
 356
 357 /// ProcessInternalGlobal - Analyze the specified global variable and optimize
 358 /// it if possible.  If we make a change, return true.
 359 static bool ProcessInternalGlobal(GlobalVariable *GV, Module::giterator &GVI) {
 360   std::set<PHINode*> PHIUsers;
 361   GlobalStatus GS;
 362   PHIUsers.clear();
 363   GV->removeDeadConstantUsers();
 364
 365   if (GV->use_empty()) {
 366     DEBUG(std::cerr << "GLOBAL DEAD: " << *GV);
 367     GV->getParent()->getGlobalList().erase(GV);
 368     ++NumDeleted;
 369     return true;
 370   }
 371
 372   if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
 373     // If the global is never loaded (but may be stored to), it is dead.
 374     // Delete it now.
 375     if (!GS.isLoaded) {
 376       DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV);
 377       // Delete any stores we can find to the global.  We may not be able to
 378       // make it completely dead though.
 379       CleanupConstantGlobalUsers(GV, GV->getInitializer());
 380
 381       // If the global is dead now, delete it.
 382       if (GV->use_empty()) {
 383         GV->getParent()->getGlobalList().erase(GV);
 384         ++NumDeleted;
 385       }
 386       return true;
 387
 388     } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
 389       DEBUG(std::cerr << "MARKING CONSTANT: " << *GV);
 390       GV->setConstant(true);
 391
 392       // Clean up any obviously simplifiable users now.
 393       CleanupConstantGlobalUsers(GV, GV->getInitializer());
 394
 395       // If the global is dead now, just nuke it.
 396       if (GV->use_empty()) {
 397         DEBUG(std::cerr << "   *** Marking constant allowed us to simplify "
 398               "all users and delete global!\n");
 399         GV->getParent()->getGlobalList().erase(GV);
 400         ++NumDeleted;
 401       }
 402
 403       ++NumMarked;
 404       return true;
 405     } else if (!GS.isNotSuitableForSRA &&
 406                !GV->getInitializer()->getType()->isFirstClassType()) {
 407       DEBUG(std::cerr << "PERFORMING GLOBAL SRA ON: " << *GV);
 408       if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) {
 409         GVI = FirstNewGV;  // Don't skip the newly produced globals!
 410         return true;
 411       }
 412     }
 413   }
 414   return false;
 415 }
 416
 417
 418 bool GlobalOpt::runOnModule(Module &M) {
 419   bool Changed = false;
 420
 421   // As a prepass, delete functions that are trivially dead.
 422   bool LocalChange = true;
 423   while (LocalChange) {
 424     LocalChange = false;
 425     for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
 426       Function *F = FI++;
 427       F->removeDeadConstantUsers();
 428       if (F->use_empty() && (F->hasInternalLinkage() || F->hasWeakLinkage())) {
 429         M.getFunctionList().erase(F);
 430         LocalChange = true;
 431         ++NumFnDeleted;
 432       }
 433     }
 434     Changed |= LocalChange;
 435   }
 436
 437   LocalChange = true;
 438   while (LocalChange) {
 439     LocalChange = false;
 440     for (Module::giterator GVI = M.gbegin(), E = M.gend(); GVI != E;) {
 441       GlobalVariable *GV = GVI++;
 442       if (!GV->isConstant() && GV->hasInternalLinkage() &&
 443           GV->hasInitializer())
 444         LocalChange |= ProcessInternalGlobal(GV, GVI);
 445     }
 446     Changed |= LocalChange;
 447   }
 448   return Changed;
 449 }