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 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus
  91 /// structure.  If the global has its address taken, return true to indicate we
  92 /// can't do anything with it.
  93 ///
  94 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
  95                           std::set<PHINode*> &PHIUsers) {
  96   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
  97     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
  98       if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
  99       if (CE->getOpcode() != Instruction::GetElementPtr)
 100         GS.isNotSuitableForSRA = true;
 101       else if (!GS.isNotSuitableForSRA) {
 102         // Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
 103         // don't like < 3 operand CE's, and we don't like non-constant integer
 104         // indices.
 105         if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue())
 106           GS.isNotSuitableForSRA = true;
 107         else {
 108           for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
 109             if (!isa<ConstantInt>(CE->getOperand(i))) {
 110               GS.isNotSuitableForSRA = true;
 111               break;
 112             }
 113         }
 114       }
 115
 116     } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
 117       if (isa<LoadInst>(I)) {
 118         GS.isLoaded = true;
 119       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 120         // Don't allow a store OF the address, only stores TO the address.
 121         if (SI->getOperand(0) == V) return true;
 122
 123         // If this is a direct store to the global (i.e., the global is a scalar
 124         // value, not an aggregate), keep more specific information about
 125         // stores.
 126         if (GS.StoredType != GlobalStatus::isStored)
 127           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){
 128             if (SI->getOperand(0) == GV->getInitializer()) {
 129               if (GS.StoredType < GlobalStatus::isInitializerStored)
 130                 GS.StoredType = GlobalStatus::isInitializerStored;
 131             } else if (GS.StoredType < GlobalStatus::isStoredOnce) {
 132               GS.StoredType = GlobalStatus::isStoredOnce;
 133               GS.StoredOnceValue = SI->getOperand(0);
 134             } else if (GS.StoredType == GlobalStatus::isStoredOnce &&
 135                        GS.StoredOnceValue == SI->getOperand(0)) {
 136               // noop.
 137             } else {
 138               GS.StoredType = GlobalStatus::isStored;
 139             }
 140           } else {
 141             GS.StoredType = GlobalStatus::isStored;
 142           }
 143       } else if (I->getOpcode() == Instruction::GetElementPtr) {
 144         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 145         // Theoretically we could SRA globals with GEP insts if all indexes are
 146         // constants.  In practice, these GEPs would already be constant exprs
 147         // if that was the case though.
 148         GS.isNotSuitableForSRA = true;
 149       } else if (I->getOpcode() == Instruction::Select) {
 150         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 151         GS.isNotSuitableForSRA = true;
 152       } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
 153         // PHI nodes we can check just like select or GEP instructions, but we
 154         // have to be careful about infinite recursion.
 155         if (PHIUsers.insert(PN).second)  // Not already visited.
 156           if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 157         GS.isNotSuitableForSRA = true;
 158       } else if (isa<SetCondInst>(I)) {
 159         GS.isNotSuitableForSRA = true;
 160       } else {
 161         return true;  // Any other non-load instruction might take address!
 162       }
 163     } else {
 164       // Otherwise must be a global or some other user.
 165       return true;
 166     }
 167
 168   return false;
 169 }
 170
 171 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) {
 172   ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
 173   if (!CI) return 0;
 174   uint64_t IdxV = CI->getRawValue();
 175
 176   if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) {
 177     if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV);
 178   } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) {
 179     if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV);
 180   } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Agg)) {
 181     if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV);
 182   } else if (ConstantAggregateZero *CAZ =
 183              dyn_cast<ConstantAggregateZero>(Agg)) {
 184     if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) {
 185       if (IdxV < STy->getNumElements())
 186         return Constant::getNullValue(STy->getElementType(IdxV));
 187     } else if (const SequentialType *STy =
 188                dyn_cast<SequentialType>(Agg->getType())) {
 189       return Constant::getNullValue(STy->getElementType());
 190     }
 191   }
 192   return 0;
 193 }
 194
 195 static Constant *TraverseGEPInitializer(User *GEP, Constant *Init) {
 196   if (GEP->getNumOperands() == 1 ||
 197       !isa<Constant>(GEP->getOperand(1)) ||
 198       !cast<Constant>(GEP->getOperand(1))->isNullValue())
 199     return 0;
 200
 201   for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) {
 202     ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
 203     if (!Idx) return 0;
 204     Init = getAggregateConstantElement(Init, Idx);
 205     if (Init == 0) return 0;
 206   }
 207   return Init;
 208 }
 209
 210 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
 211 /// users of the global, cleaning up the obvious ones.  This is largely just a
 212 /// quick scan over the use list to clean up the easy and obvious cruft.
 213 static void CleanupConstantGlobalUsers(Value *V, Constant *Init) {
 214   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) {
 215     User *U = *UI++;
 216
 217     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
 218       // Replace the load with the initializer.
 219       LI->replaceAllUsesWith(Init);
 220       LI->getParent()->getInstList().erase(LI);
 221     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 222       // Store must be unreachable or storing Init into the global.
 223       SI->getParent()->getInstList().erase(SI);
 224     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 225       if (CE->getOpcode() == Instruction::GetElementPtr) {
 226         if (Constant *SubInit = TraverseGEPInitializer(CE, Init))
 227           CleanupConstantGlobalUsers(CE, SubInit);
 228         if (CE->use_empty()) CE->destroyConstant();
 229       }
 230     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
 231       if (Constant *SubInit = TraverseGEPInitializer(GEP, Init))
 232         CleanupConstantGlobalUsers(GEP, SubInit);
 233       if (GEP->use_empty())
 234         GEP->getParent()->getInstList().erase(GEP);
 235     }
 236   }
 237 }
 238
 239 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
 240 /// variable.  This opens the door for other optimizations by exposing the
 241 /// behavior of the program in a more fine-grained way.  We have determined that
 242 /// this transformation is safe already.  We return the first global variable we
 243 /// insert so that the caller can reprocess it.
 244 static GlobalVariable *SRAGlobal(GlobalVariable *GV) {
 245   assert(GV->hasInternalLinkage() && !GV->isConstant());
 246   Constant *Init = GV->getInitializer();
 247   const Type *Ty = Init->getType();
 248
 249   std::vector<GlobalVariable*> NewGlobals;
 250   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
 251
 252   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 253     NewGlobals.reserve(STy->getNumElements());
 254     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
 255       Constant *In = getAggregateConstantElement(Init,
 256                                             ConstantUInt::get(Type::UIntTy, i));
 257       assert(In && "Couldn't get element of initializer?");
 258       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
 259                                                GlobalVariable::InternalLinkage,
 260                                                In, GV->getName()+"."+utostr(i));
 261       Globals.insert(GV, NGV);
 262       NewGlobals.push_back(NGV);
 263     }
 264   } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
 265     unsigned NumElements = 0;
 266     if (const ArrayType *ATy = dyn_cast<ArrayType>(STy))
 267       NumElements = ATy->getNumElements();
 268     else if (const PackedType *PTy = dyn_cast<PackedType>(STy))
 269       NumElements = PTy->getNumElements();
 270     else
 271       assert(0 && "Unknown aggregate sequential type!");
 272
 273     if (NumElements > 16) return 0; // It's not worth it.
 274     NewGlobals.reserve(NumElements);
 275     for (unsigned i = 0, e = NumElements; i != e; ++i) {
 276       Constant *In = getAggregateConstantElement(Init,
 277                                             ConstantUInt::get(Type::UIntTy, i));
 278       assert(In && "Couldn't get element of initializer?");
 279
 280       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
 281                                                GlobalVariable::InternalLinkage,
 282                                                In, GV->getName()+"."+utostr(i));
 283       Globals.insert(GV, NGV);
 284       NewGlobals.push_back(NGV);
 285     }
 286   }
 287
 288   if (NewGlobals.empty())
 289     return 0;
 290
 291   Constant *NullInt = Constant::getNullValue(Type::IntTy);
 292
 293   // Loop over all of the uses of the global, replacing the constantexpr geps,
 294   // with smaller constantexpr geps or direct references.
 295   while (!GV->use_empty()) {
 296     ConstantExpr *CE = cast<ConstantExpr>(GV->use_back());
 297     assert(CE->getOpcode() == Instruction::GetElementPtr &&
 298            "NonGEP CE's are not SRAable!");
 299     // Ignore the 1th operand, which has to be zero or else the program is quite
 300     // broken (undefined).  Get the 2nd operand, which is the structure or array
 301     // index.
 302     unsigned Val = cast<ConstantInt>(CE->getOperand(2))->getRawValue();
 303     if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
 304
 305     Constant *NewPtr = NewGlobals[Val];
 306
 307     // Form a shorter GEP if needed.
 308     if (CE->getNumOperands() > 3) {
 309       std::vector<Constant*> Idxs;
 310       Idxs.push_back(NullInt);
 311       for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
 312         Idxs.push_back(CE->getOperand(i));
 313       NewPtr = ConstantExpr::getGetElementPtr(NewPtr, Idxs);
 314     }
 315     CE->replaceAllUsesWith(NewPtr);
 316     CE->destroyConstant();
 317   }
 318
 319   ++NumSRA;
 320   return NewGlobals[0];
 321 }
 322
 323 bool GlobalOpt::runOnModule(Module &M) {
 324   bool Changed = false;
 325
 326   // As a prepass, delete functions that are trivially dead.
 327   bool LocalChange = true;
 328   while (LocalChange) {
 329     LocalChange = false;
 330     for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
 331       Function *F = FI++;
 332       F->removeDeadConstantUsers();
 333       if (F->use_empty() && (F->hasInternalLinkage() || F->hasWeakLinkage())) {
 334         M.getFunctionList().erase(F);
 335         LocalChange = true;
 336         ++NumFnDeleted;
 337       }
 338     }
 339     Changed |= LocalChange;
 340   }
 341
 342   std::set<PHINode*> PHIUsers;
 343   for (Module::giterator GVI = M.gbegin(), E = M.gend(); GVI != E;) {
 344     GlobalVariable *GV = GVI++;
 345     if (!GV->isConstant() && GV->hasInternalLinkage() && GV->hasInitializer()) {
 346       GlobalStatus GS;
 347       PHIUsers.clear();
 348       GV->removeDeadConstantUsers();
 349       if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
 350         // If the global is never loaded (but may be stored to), it is dead.
 351         // Delete it now.
 352         if (!GS.isLoaded) {
 353           DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV);
 354           // Delete any stores we can find to the global.  We may not be able to
 355           // make it completely dead though.
 356           CleanupConstantGlobalUsers(GV, GV->getInitializer());
 357
 358           // If the global is dead now, delete it.
 359           if (GV->use_empty()) {
 360             M.getGlobalList().erase(GV);
 361             ++NumDeleted;
 362           }
 363           Changed = true;
 364
 365         } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
 366           DEBUG(std::cerr << "MARKING CONSTANT: " << *GV);
 367           GV->setConstant(true);
 368
 369           // Clean up any obviously simplifiable users now.
 370           CleanupConstantGlobalUsers(GV, GV->getInitializer());
 371
 372           // If the global is dead now, just nuke it.
 373           if (GV->use_empty()) {
 374             M.getGlobalList().erase(GV);
 375             ++NumDeleted;
 376           }
 377
 378           ++NumMarked;
 379           Changed = true;
 380         } else if (!GS.isNotSuitableForSRA &&
 381                    !GV->getInitializer()->getType()->isFirstClassType()) {
 382           DEBUG(std::cerr << "PERFORMING GLOBAL SRA ON: " << *GV);
 383           if (GlobalVariable *FirstNewGV = SRAGlobal(GV))
 384             GVI = FirstNewGV;  // Don't skip the newly produced globals!
 385         }
 386       }
 387     }
 388   }
 389   return Changed;
 390 }