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