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 <set>
  26 #include <algorithm>
  27 using namespace llvm;
  28
  29 namespace {
  30   Statistic<> NumMarked ("globalopt", "Number of globals marked constant");
  31   Statistic<> NumDeleted("globalopt", "Number of globals deleted");
  32   Statistic<> NumFnDeleted("globalopt", "Number of functions deleted");
  33
  34   struct GlobalOpt : public ModulePass {
  35     bool runOnModule(Module &M);
  36   };
  37
  38   RegisterOpt<GlobalOpt> X("globalopt", "Global Variable Optimizer");
  39 }
  40
  41 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
  42
  43 /// GlobalStatus - As we analyze each global, keep track of some information
  44 /// about it.  If we find out that the address of the global is taken, none of
  45 /// the other info will be accurate.
  46 struct GlobalStatus {
  47   bool isLoaded;
  48   enum StoredType {
  49     NotStored, isInitializerStored, isMallocStored, isStored
  50   } StoredType;
  51   bool isNotSuitableForSRA;
  52
  53   GlobalStatus() : isLoaded(false), StoredType(NotStored),
  54                    isNotSuitableForSRA(false) {}
  55 };
  56
  57 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus
  58 /// structure.  If the global has its address taken, return true to indicate we
  59 /// can't do anything with it.
  60 ///
  61 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS,
  62                           std::set<PHINode*> &PHIUsers) {
  63   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
  64     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
  65       if (AnalyzeGlobal(CE, GS, PHIUsers)) return true;
  66       if (CE->getOpcode() != Instruction::GetElementPtr)
  67         GS.isNotSuitableForSRA = true;
  68     } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
  69       if (isa<LoadInst>(I)) {
  70         GS.isLoaded = true;
  71       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
  72         // Don't allow a store OF the address, only stores TO the address.
  73         if (SI->getOperand(0) == V) return true;
  74
  75         // If this store is just storing the initializer into a global (i.e. not
  76         // changing the value), ignore it.  For now we just handle direct
  77         // stores, no stores to fields of aggregates.
  78         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))) {
  79           if (SI->getOperand(0) == GV->getInitializer() &&
  80               GS.StoredType < GlobalStatus::isInitializerStored)
  81             GS.StoredType = GlobalStatus::isInitializerStored;
  82           else if (isa<MallocInst>(SI->getOperand(0)) &&
  83                    GS.StoredType < GlobalStatus::isMallocStored)
  84             GS.StoredType = GlobalStatus::isMallocStored;
  85           else
  86             GS.StoredType = GlobalStatus::isStored;
  87         } else {
  88           GS.StoredType = GlobalStatus::isStored;
  89         }
  90       } else if (I->getOpcode() == Instruction::GetElementPtr) {
  91         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
  92         if (!GS.isNotSuitableForSRA)
  93           for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
  94             if (!isa<Constant>(I->getOperand(i))) {
  95               GS.isNotSuitableForSRA = true;
  96               break;
  97             }
  98       } else if (I->getOpcode() == Instruction::Select) {
  99         if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 100         GS.isNotSuitableForSRA = true;
 101       } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
 102         // PHI nodes we can check just like select or GEP instructions, but we
 103         // have to be careful about infinite recursion.
 104         if (PHIUsers.insert(PN).second)  // Not already visited.
 105           if (AnalyzeGlobal(I, GS, PHIUsers)) return true;
 106         GS.isNotSuitableForSRA = true;
 107       } else if (isa<SetCondInst>(I)) {
 108         GS.isNotSuitableForSRA = true;
 109       } else {
 110         return true;  // Any other non-load instruction might take address!
 111       }
 112     } else {
 113       // Otherwise must be a global or some other user.
 114       return true;
 115     }
 116
 117   return false;
 118 }
 119
 120
 121
 122 static Constant *TraverseGEPInitializer(User *GEP, Constant *Init) {
 123   if (GEP->getNumOperands() == 1 ||
 124       !isa<Constant>(GEP->getOperand(1)) ||
 125       !cast<Constant>(GEP->getOperand(1))->isNullValue())
 126     return 0;
 127
 128   for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) {
 129     ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
 130     if (!Idx) return 0;
 131     uint64_t IdxV = Idx->getRawValue();
 132     if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
 133       if (IdxV >= CS->getNumOperands()) return 0;
 134       Init = CS->getOperand(IdxV);
 135     } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
 136       if (IdxV >= CA->getNumOperands()) return 0;
 137       Init = CA->getOperand(IdxV);
 138     } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Init)) {
 139       if (IdxV >= CP->getNumOperands()) return 0;
 140       Init = CP->getOperand(IdxV);
 141     } else if (ConstantAggregateZero *CAZ =
 142                dyn_cast<ConstantAggregateZero>(Init)) {
 143       if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
 144         if (IdxV >= STy->getNumElements()) return 0;
 145         Init = Constant::getNullValue(STy->getElementType(IdxV));
 146       } else if (const SequentialType *STy =
 147                  dyn_cast<SequentialType>(Init->getType())) {
 148         Init = Constant::getNullValue(STy->getElementType());
 149       } else {
 150         return 0;
 151       }
 152     } else {
 153       return 0;
 154     }
 155   }
 156   return Init;
 157 }
 158
 159 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
 160 /// users of the global, cleaning up the obvious ones.  This is largely just a
 161 /// quick scan over the use list to clean up the easy and obvious cruft.
 162 static void CleanupConstantGlobalUsers(Value *V, Constant *Init) {
 163   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) {
 164     User *U = *UI++;
 165
 166     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
 167       // Replace the load with the initializer.
 168       LI->replaceAllUsesWith(Init);
 169       LI->getParent()->getInstList().erase(LI);
 170     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 171       // Store must be unreachable or storing Init into the global.
 172       SI->getParent()->getInstList().erase(SI);
 173     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 174       if (CE->getOpcode() == Instruction::GetElementPtr) {
 175         if (Constant *SubInit = TraverseGEPInitializer(CE, Init))
 176           CleanupConstantGlobalUsers(CE, SubInit);
 177         if (CE->use_empty()) CE->destroyConstant();
 178       }
 179     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
 180       if (Constant *SubInit = TraverseGEPInitializer(GEP, Init))
 181         CleanupConstantGlobalUsers(GEP, SubInit);
 182       if (GEP->use_empty())
 183         GEP->getParent()->getInstList().erase(GEP);
 184     }
 185   }
 186 }
 187
 188 bool GlobalOpt::runOnModule(Module &M) {
 189   bool Changed = false;
 190
 191   // As a prepass, delete functions that are trivially dead.
 192   bool LocalChange = true;
 193   while (LocalChange) {
 194     LocalChange = false;
 195     for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
 196       Function *F = FI++;
 197       F->removeDeadConstantUsers();
 198       if (F->use_empty() && (F->hasInternalLinkage() || F->hasWeakLinkage())) {
 199         M.getFunctionList().erase(F);
 200         LocalChange = true;
 201         ++NumFnDeleted;
 202       }
 203     }
 204     Changed |= LocalChange;
 205   }
 206
 207   std::set<PHINode*> PHIUsers;
 208   for (Module::giterator GVI = M.gbegin(), E = M.gend(); GVI != E;) {
 209     GlobalVariable *GV = GVI++;
 210     if (!GV->isConstant() && GV->hasInternalLinkage() && GV->hasInitializer()) {
 211       GlobalStatus GS;
 212       PHIUsers.clear();
 213       GV->removeDeadConstantUsers();
 214       if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
 215         // If the global is never loaded (but may be stored to), it is dead.
 216         // Delete it now.
 217         if (!GS.isLoaded) {
 218           DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV);
 219           // Delete any stores we can find to the global.  We may not be able to
 220           // make it completely dead though.
 221           CleanupConstantGlobalUsers(GV, GV->getInitializer());
 222
 223           // If the global is dead now, delete it.
 224           if (GV->use_empty()) {
 225             M.getGlobalList().erase(GV);
 226             ++NumDeleted;
 227           }
 228           Changed = true;
 229
 230         } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
 231           DEBUG(std::cerr << "MARKING CONSTANT: " << *GV);
 232           GV->setConstant(true);
 233
 234           // Clean up any obviously simplifiable users now.
 235           CleanupConstantGlobalUsers(GV, GV->getInitializer());
 236
 237           // If the global is dead now, just nuke it.
 238           if (GV->use_empty()) {
 239             M.getGlobalList().erase(GV);
 240             ++NumDeleted;
 241           }
 242
 243           ++NumMarked;
 244           Changed = true;
 245         }
 246       }
 247     }
 248   }
 249   return Changed;
 250 }