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"
25 #include "llvm/ADT/StringExtras.h"
31 Statistic<> NumMarked ("globalopt", "Number of globals marked constant");
32 Statistic<> NumSRA ("globalopt", "Number of aggregate globals broken "
34 Statistic<> NumDeleted ("globalopt", "Number of globals deleted");
35 Statistic<> NumFnDeleted("globalopt", "Number of functions deleted");
37 struct GlobalOpt : public ModulePass {
38 bool runOnModule(Module &M);
41 RegisterOpt<GlobalOpt> X("globalopt", "Global Variable Optimizer");
44 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
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.
50 /// isLoaded - True if the global is ever loaded. If the global isn't ever
51 /// loaded it can be deleted.
54 /// StoredType - Keep track of what stores to the global look like.
57 /// NotStored - There is no store to this global. It can thus be marked
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.
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.
72 /// isStored - This global is stored to by multiple values or something else
73 /// that we cannot track.
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;
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;
86 GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0),
87 isNotSuitableForSRA(false) {}
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
96 static bool ConstantIsDead(Constant *C) {
97 if (isa<GlobalValue>(C)) return false;
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;
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.
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
123 if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue())
124 GS.isNotSuitableForSRA = true;
126 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
127 if (!isa<ConstantInt>(CE->getOperand(i))) {
128 GS.isNotSuitableForSRA = true;
134 } else if (Instruction *I = dyn_cast<Instruction>(*UI)) {
135 if (isa<LoadInst>(I)) {
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;
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
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)) {
156 GS.StoredType = GlobalStatus::isStored;
159 GS.StoredType = GlobalStatus::isStored;
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;
179 return true; // Any other non-load instruction might take address!
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))
186 // Otherwise must be a global or some other user.
193 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) {
194 ConstantInt *CI = dyn_cast<ConstantInt>(Idx);
196 uint64_t IdxV = CI->getRawValue();
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());
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())
223 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) {
224 ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i));
226 Init = getAggregateConstantElement(Init, Idx);
227 if (Init == 0) return 0;
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;) {
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();
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);
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();
280 std::vector<GlobalVariable*> NewGlobals;
281 Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
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);
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();
302 assert(0 && "Unknown aggregate sequential type!");
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?");
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);
319 if (NewGlobals.empty())
322 Constant *NullInt = Constant::getNullValue(Type::IntTy);
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
333 unsigned Val = cast<ConstantInt>(CE->getOperand(2))->getRawValue();
334 if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
336 Constant *NewPtr = NewGlobals[Val];
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);
346 CE->replaceAllUsesWith(NewPtr);
347 CE->destroyConstant();
350 // Delete the old global, now that it is dead.
353 return NewGlobals[0];
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;
363 GV->removeDeadConstantUsers();
365 if (GV->use_empty()) {
366 DEBUG(std::cerr << "GLOBAL DEAD: " << *GV);
371 if (!AnalyzeGlobal(GV, GS, PHIUsers)) {
372 // If the global is never loaded (but may be stored to), it is dead.
375 DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV);
376 // Delete any stores we can find to the global. We may not be able to
377 // make it completely dead though.
378 CleanupConstantGlobalUsers(GV, GV->getInitializer());
380 // If the global is dead now, delete it.
381 if (GV->use_empty()) {
382 GV->getParent()->getGlobalList().erase(GV);
387 } else if (GS.StoredType <= GlobalStatus::isInitializerStored) {
388 DEBUG(std::cerr << "MARKING CONSTANT: " << *GV);
389 GV->setConstant(true);
391 // Clean up any obviously simplifiable users now.
392 CleanupConstantGlobalUsers(GV, GV->getInitializer());
394 // If the global is dead now, just nuke it.
395 if (GV->use_empty()) {
396 DEBUG(std::cerr << " *** Marking constant allowed us to simplify "
397 "all users and delete global!\n");
398 GV->getParent()->getGlobalList().erase(GV);
404 } else if (!GS.isNotSuitableForSRA &&
405 !GV->getInitializer()->getType()->isFirstClassType()) {
406 DEBUG(std::cerr << "PERFORMING GLOBAL SRA ON: " << *GV);
407 if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) {
408 GVI = FirstNewGV; // Don't skip the newly produced globals!
417 bool GlobalOpt::runOnModule(Module &M) {
418 bool Changed = false;
420 // As a prepass, delete functions that are trivially dead.
421 bool LocalChange = true;
422 while (LocalChange) {
424 for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
426 F->removeDeadConstantUsers();
427 if (F->use_empty() && (F->hasInternalLinkage() || F->hasWeakLinkage())) {
428 M.getFunctionList().erase(F);
433 Changed |= LocalChange;
437 while (LocalChange) {
439 for (Module::giterator GVI = M.gbegin(), E = M.gend(); GVI != E;) {
440 GlobalVariable *GV = GVI++;
441 if (!GV->isConstant() && GV->hasInternalLinkage() &&
442 GV->hasInitializer())
443 LocalChange |= ProcessInternalGlobal(GV, GVI);
445 Changed |= LocalChange;