1 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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"
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");
34 struct GlobalOpt : public ModulePass {
35 bool runOnModule(Module &M);
38 RegisterOpt<GlobalOpt> X("globalopt", "Global Variable Optimizer");
41 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
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.
49 NotStored, isInitializerStored, isMallocStored, isStored
51 bool isNotSuitableForSRA;
53 GlobalStatus() : isLoaded(false), StoredType(NotStored),
54 isNotSuitableForSRA(false) {}
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.
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)) {
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;
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;
86 GS.StoredType = GlobalStatus::isStored;
88 GS.StoredType = GlobalStatus::isStored;
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;
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;
110 return true; // Any other non-load instruction might take address!
113 // Otherwise must be a global or some other user.
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())
128 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) {
129 ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
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());
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;) {
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();
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);
188 bool GlobalOpt::runOnModule(Module &M) {
189 bool Changed = false;
191 // As a prepass, delete functions that are trivially dead.
192 bool LocalChange = true;
193 while (LocalChange) {
195 for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
197 F->removeDeadConstantUsers();
198 if (F->use_empty() && (F->hasInternalLinkage() || F->hasWeakLinkage())) {
199 M.getFunctionList().erase(F);
204 Changed |= LocalChange;
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()) {
213 GV->removeDeadConstantUsers();
214 if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
215 // If the global is never loaded (but may be stored to), it is dead.
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());
223 // If the global is dead now, delete it.
224 if (GV->use_empty()) {
225 M.getGlobalList().erase(GV);
230 } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
231 DEBUG(std::cerr << "MARKING CONSTANT: " << *GV);
232 GV->setConstant(true);
234 // Clean up any obviously simplifiable users now.
235 CleanupConstantGlobalUsers(GV, GV->getInitializer());
237 // If the global is dead now, just nuke it.
238 if (GV->use_empty()) {
239 M.getGlobalList().erase(GV);