LLVM API Documentation
00001 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass transforms simple global variables that never have their address 00011 // taken. If obviously true, it marks read/write globals as constant, deletes 00012 // variables only stored to, etc. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #define DEBUG_TYPE "globalopt" 00017 #include "llvm/Transforms/IPO.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/DerivedTypes.h" 00020 #include "llvm/Instructions.h" 00021 #include "llvm/Module.h" 00022 #include "llvm/Pass.h" 00023 #include "llvm/Support/Debug.h" 00024 #include "llvm/Target/TargetData.h" 00025 #include "llvm/Transforms/Utils/Local.h" 00026 #include "llvm/ADT/Statistic.h" 00027 #include "llvm/ADT/StringExtras.h" 00028 #include <set> 00029 #include <algorithm> 00030 using namespace llvm; 00031 00032 namespace { 00033 Statistic<> NumMarked ("globalopt", "Number of globals marked constant"); 00034 Statistic<> NumSRA ("globalopt", "Number of aggregate globals broken " 00035 "into scalars"); 00036 Statistic<> NumSubstitute("globalopt", 00037 "Number of globals with initializers stored into them"); 00038 Statistic<> NumDeleted ("globalopt", "Number of globals deleted"); 00039 Statistic<> NumFnDeleted("globalopt", "Number of functions deleted"); 00040 Statistic<> NumGlobUses ("globalopt", "Number of global uses devirtualized"); 00041 00042 struct GlobalOpt : public ModulePass { 00043 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00044 AU.addRequired<TargetData>(); 00045 } 00046 00047 bool runOnModule(Module &M); 00048 00049 private: 00050 bool ProcessInternalGlobal(GlobalVariable *GV, Module::giterator &GVI); 00051 }; 00052 00053 RegisterOpt<GlobalOpt> X("globalopt", "Global Variable Optimizer"); 00054 } 00055 00056 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); } 00057 00058 /// GlobalStatus - As we analyze each global, keep track of some information 00059 /// about it. If we find out that the address of the global is taken, none of 00060 /// this info will be accurate. 00061 struct GlobalStatus { 00062 /// isLoaded - True if the global is ever loaded. If the global isn't ever 00063 /// loaded it can be deleted. 00064 bool isLoaded; 00065 00066 /// StoredType - Keep track of what stores to the global look like. 00067 /// 00068 enum StoredType { 00069 /// NotStored - There is no store to this global. It can thus be marked 00070 /// constant. 00071 NotStored, 00072 00073 /// isInitializerStored - This global is stored to, but the only thing 00074 /// stored is the constant it was initialized with. This is only tracked 00075 /// for scalar globals. 00076 isInitializerStored, 00077 00078 /// isStoredOnce - This global is stored to, but only its initializer and 00079 /// one other value is ever stored to it. If this global isStoredOnce, we 00080 /// track the value stored to it in StoredOnceValue below. This is only 00081 /// tracked for scalar globals. 00082 isStoredOnce, 00083 00084 /// isStored - This global is stored to by multiple values or something else 00085 /// that we cannot track. 00086 isStored 00087 } StoredType; 00088 00089 /// StoredOnceValue - If only one value (besides the initializer constant) is 00090 /// ever stored to this global, keep track of what value it is. 00091 Value *StoredOnceValue; 00092 00093 /// isNotSuitableForSRA - Keep track of whether any SRA preventing users of 00094 /// the global exist. Such users include GEP instruction with variable 00095 /// indexes, and non-gep/load/store users like constant expr casts. 00096 bool isNotSuitableForSRA; 00097 00098 GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0), 00099 isNotSuitableForSRA(false) {} 00100 }; 00101 00102 00103 00104 /// ConstantIsDead - Return true if the specified constant is (transitively) 00105 /// dead. The constant may be used by other constants (e.g. constant arrays and 00106 /// constant exprs) as long as they are dead, but it cannot be used by anything 00107 /// else. 00108 static bool ConstantIsDead(Constant *C) { 00109 if (isa<GlobalValue>(C)) return false; 00110 00111 for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI) 00112 if (Constant *CU = dyn_cast<Constant>(*UI)) { 00113 if (!ConstantIsDead(CU)) return false; 00114 } else 00115 return false; 00116 return true; 00117 } 00118 00119 00120 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus 00121 /// structure. If the global has its address taken, return true to indicate we 00122 /// can't do anything with it. 00123 /// 00124 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, 00125 std::set<PHINode*> &PHIUsers) { 00126 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 00127 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) { 00128 if (AnalyzeGlobal(CE, GS, PHIUsers)) return true; 00129 if (CE->getOpcode() != Instruction::GetElementPtr) 00130 GS.isNotSuitableForSRA = true; 00131 else if (!GS.isNotSuitableForSRA) { 00132 // Check to see if this ConstantExpr GEP is SRA'able. In particular, we 00133 // don't like < 3 operand CE's, and we don't like non-constant integer 00134 // indices. 00135 if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue()) 00136 GS.isNotSuitableForSRA = true; 00137 else { 00138 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 00139 if (!isa<ConstantInt>(CE->getOperand(i))) { 00140 GS.isNotSuitableForSRA = true; 00141 break; 00142 } 00143 } 00144 } 00145 00146 } else if (Instruction *I = dyn_cast<Instruction>(*UI)) { 00147 if (isa<LoadInst>(I)) { 00148 GS.isLoaded = true; 00149 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00150 // Don't allow a store OF the address, only stores TO the address. 00151 if (SI->getOperand(0) == V) return true; 00152 00153 // If this is a direct store to the global (i.e., the global is a scalar 00154 // value, not an aggregate), keep more specific information about 00155 // stores. 00156 if (GS.StoredType != GlobalStatus::isStored) 00157 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){ 00158 Value *StoredVal = SI->getOperand(0); 00159 if (StoredVal == GV->getInitializer()) { 00160 if (GS.StoredType < GlobalStatus::isInitializerStored) 00161 GS.StoredType = GlobalStatus::isInitializerStored; 00162 } else if (isa<LoadInst>(StoredVal) && 00163 cast<LoadInst>(StoredVal)->getOperand(0) == GV) { 00164 // G = G 00165 if (GS.StoredType < GlobalStatus::isInitializerStored) 00166 GS.StoredType = GlobalStatus::isInitializerStored; 00167 } else if (GS.StoredType < GlobalStatus::isStoredOnce) { 00168 GS.StoredType = GlobalStatus::isStoredOnce; 00169 GS.StoredOnceValue = StoredVal; 00170 } else if (GS.StoredType == GlobalStatus::isStoredOnce && 00171 GS.StoredOnceValue == StoredVal) { 00172 // noop. 00173 } else { 00174 GS.StoredType = GlobalStatus::isStored; 00175 } 00176 } else { 00177 GS.StoredType = GlobalStatus::isStored; 00178 } 00179 } else if (I->getOpcode() == Instruction::GetElementPtr) { 00180 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00181 00182 // If the first two indices are constants, this can be SRA'd. 00183 if (isa<GlobalVariable>(I->getOperand(0))) { 00184 if (I->getNumOperands() < 3 || !isa<Constant>(I->getOperand(1)) || 00185 !cast<Constant>(I->getOperand(1))->isNullValue() || 00186 !isa<ConstantInt>(I->getOperand(2))) 00187 GS.isNotSuitableForSRA = true; 00188 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I->getOperand(0))){ 00189 if (CE->getOpcode() != Instruction::GetElementPtr || 00190 CE->getNumOperands() < 3 || I->getNumOperands() < 2 || 00191 !isa<Constant>(I->getOperand(0)) || 00192 !cast<Constant>(I->getOperand(0))->isNullValue()) 00193 GS.isNotSuitableForSRA = true; 00194 } else { 00195 GS.isNotSuitableForSRA = true; 00196 } 00197 } else if (I->getOpcode() == Instruction::Select) { 00198 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00199 GS.isNotSuitableForSRA = true; 00200 } else if (PHINode *PN = dyn_cast<PHINode>(I)) { 00201 // PHI nodes we can check just like select or GEP instructions, but we 00202 // have to be careful about infinite recursion. 00203 if (PHIUsers.insert(PN).second) // Not already visited. 00204 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00205 GS.isNotSuitableForSRA = true; 00206 } else if (isa<SetCondInst>(I)) { 00207 GS.isNotSuitableForSRA = true; 00208 } else { 00209 return true; // Any other non-load instruction might take address! 00210 } 00211 } else if (Constant *C = dyn_cast<Constant>(*UI)) { 00212 // We might have a dead and dangling constant hanging off of here. 00213 if (!ConstantIsDead(C)) 00214 return true; 00215 } else { 00216 // Otherwise must be a global or some other user. 00217 return true; 00218 } 00219 00220 return false; 00221 } 00222 00223 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) { 00224 ConstantInt *CI = dyn_cast<ConstantInt>(Idx); 00225 if (!CI) return 0; 00226 uint64_t IdxV = CI->getRawValue(); 00227 00228 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) { 00229 if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV); 00230 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) { 00231 if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV); 00232 } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Agg)) { 00233 if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV); 00234 } else if (isa<ConstantAggregateZero>(Agg)) { 00235 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) { 00236 if (IdxV < STy->getNumElements()) 00237 return Constant::getNullValue(STy->getElementType(IdxV)); 00238 } else if (const SequentialType *STy = 00239 dyn_cast<SequentialType>(Agg->getType())) { 00240 return Constant::getNullValue(STy->getElementType()); 00241 } 00242 } else if (isa<UndefValue>(Agg)) { 00243 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) { 00244 if (IdxV < STy->getNumElements()) 00245 return UndefValue::get(STy->getElementType(IdxV)); 00246 } else if (const SequentialType *STy = 00247 dyn_cast<SequentialType>(Agg->getType())) { 00248 return UndefValue::get(STy->getElementType()); 00249 } 00250 } 00251 return 0; 00252 } 00253 00254 static Constant *TraverseGEPInitializer(User *GEP, Constant *Init) { 00255 if (GEP->getNumOperands() == 1 || 00256 !isa<Constant>(GEP->getOperand(1)) || 00257 !cast<Constant>(GEP->getOperand(1))->isNullValue()) 00258 return 0; 00259 00260 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) { 00261 ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(i)); 00262 if (!Idx) return 0; 00263 Init = getAggregateConstantElement(Init, Idx); 00264 if (Init == 0) return 0; 00265 } 00266 return Init; 00267 } 00268 00269 /// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all 00270 /// users of the global, cleaning up the obvious ones. This is largely just a 00271 /// quick scan over the use list to clean up the easy and obvious cruft. This 00272 /// returns true if it made a change. 00273 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) { 00274 bool Changed = false; 00275 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) { 00276 User *U = *UI++; 00277 00278 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 00279 // Replace the load with the initializer. 00280 LI->replaceAllUsesWith(Init); 00281 LI->eraseFromParent(); 00282 Changed = true; 00283 } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 00284 // Store must be unreachable or storing Init into the global. 00285 SI->eraseFromParent(); 00286 Changed = true; 00287 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 00288 if (CE->getOpcode() == Instruction::GetElementPtr) { 00289 if (Constant *SubInit = TraverseGEPInitializer(CE, Init)) 00290 Changed |= CleanupConstantGlobalUsers(CE, SubInit); 00291 if (CE->use_empty()) { 00292 CE->destroyConstant(); 00293 Changed = true; 00294 } 00295 } 00296 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 00297 if (Constant *SubInit = TraverseGEPInitializer(GEP, Init)) 00298 Changed |= CleanupConstantGlobalUsers(GEP, SubInit); 00299 else { 00300 // If this GEP has variable indexes, we should still be able to delete 00301 // any stores through it. 00302 for (Value::use_iterator GUI = GEP->use_begin(), E = GEP->use_end(); 00303 GUI != E;) 00304 if (StoreInst *SI = dyn_cast<StoreInst>(*GUI++)) { 00305 SI->eraseFromParent(); 00306 Changed = true; 00307 } 00308 } 00309 00310 if (GEP->use_empty()) { 00311 GEP->eraseFromParent(); 00312 Changed = true; 00313 } 00314 } else if (Constant *C = dyn_cast<Constant>(U)) { 00315 // If we have a chain of dead constantexprs or other things dangling from 00316 // us, and if they are all dead, nuke them without remorse. 00317 if (ConstantIsDead(C)) { 00318 C->destroyConstant(); 00319 // This could have incalidated UI, start over from scratch.x 00320 CleanupConstantGlobalUsers(V, Init); 00321 return true; 00322 } 00323 } 00324 } 00325 return Changed; 00326 } 00327 00328 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global 00329 /// variable. This opens the door for other optimizations by exposing the 00330 /// behavior of the program in a more fine-grained way. We have determined that 00331 /// this transformation is safe already. We return the first global variable we 00332 /// insert so that the caller can reprocess it. 00333 static GlobalVariable *SRAGlobal(GlobalVariable *GV) { 00334 assert(GV->hasInternalLinkage() && !GV->isConstant()); 00335 Constant *Init = GV->getInitializer(); 00336 const Type *Ty = Init->getType(); 00337 00338 std::vector<GlobalVariable*> NewGlobals; 00339 Module::GlobalListType &Globals = GV->getParent()->getGlobalList(); 00340 00341 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 00342 NewGlobals.reserve(STy->getNumElements()); 00343 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 00344 Constant *In = getAggregateConstantElement(Init, 00345 ConstantUInt::get(Type::UIntTy, i)); 00346 assert(In && "Couldn't get element of initializer?"); 00347 GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false, 00348 GlobalVariable::InternalLinkage, 00349 In, GV->getName()+"."+utostr(i)); 00350 Globals.insert(GV, NGV); 00351 NewGlobals.push_back(NGV); 00352 } 00353 } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) { 00354 unsigned NumElements = 0; 00355 if (const ArrayType *ATy = dyn_cast<ArrayType>(STy)) 00356 NumElements = ATy->getNumElements(); 00357 else if (const PackedType *PTy = dyn_cast<PackedType>(STy)) 00358 NumElements = PTy->getNumElements(); 00359 else 00360 assert(0 && "Unknown aggregate sequential type!"); 00361 00362 if (NumElements > 16 && GV->use_size() > 16) return 0; // It's not worth it. 00363 NewGlobals.reserve(NumElements); 00364 for (unsigned i = 0, e = NumElements; i != e; ++i) { 00365 Constant *In = getAggregateConstantElement(Init, 00366 ConstantUInt::get(Type::UIntTy, i)); 00367 assert(In && "Couldn't get element of initializer?"); 00368 00369 GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false, 00370 GlobalVariable::InternalLinkage, 00371 In, GV->getName()+"."+utostr(i)); 00372 Globals.insert(GV, NGV); 00373 NewGlobals.push_back(NGV); 00374 } 00375 } 00376 00377 if (NewGlobals.empty()) 00378 return 0; 00379 00380 DEBUG(std::cerr << "PERFORMING GLOBAL SRA ON: " << *GV); 00381 00382 Constant *NullInt = Constant::getNullValue(Type::IntTy); 00383 00384 // Loop over all of the uses of the global, replacing the constantexpr geps, 00385 // with smaller constantexpr geps or direct references. 00386 while (!GV->use_empty()) { 00387 User *GEP = GV->use_back(); 00388 assert(((isa<ConstantExpr>(GEP) && 00389 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| 00390 isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!"); 00391 00392 // Ignore the 1th operand, which has to be zero or else the program is quite 00393 // broken (undefined). Get the 2nd operand, which is the structure or array 00394 // index. 00395 unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getRawValue(); 00396 if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access. 00397 00398 Value *NewPtr = NewGlobals[Val]; 00399 00400 // Form a shorter GEP if needed. 00401 if (GEP->getNumOperands() > 3) 00402 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) { 00403 std::vector<Constant*> Idxs; 00404 Idxs.push_back(NullInt); 00405 for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i) 00406 Idxs.push_back(CE->getOperand(i)); 00407 NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), Idxs); 00408 } else { 00409 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP); 00410 std::vector<Value*> Idxs; 00411 Idxs.push_back(NullInt); 00412 for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i) 00413 Idxs.push_back(GEPI->getOperand(i)); 00414 NewPtr = new GetElementPtrInst(NewPtr, Idxs, 00415 GEPI->getName()+"."+utostr(Val), GEPI); 00416 } 00417 GEP->replaceAllUsesWith(NewPtr); 00418 00419 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP)) 00420 GEPI->eraseFromParent(); 00421 else 00422 cast<ConstantExpr>(GEP)->destroyConstant(); 00423 } 00424 00425 // Delete the old global, now that it is dead. 00426 Globals.erase(GV); 00427 ++NumSRA; 00428 00429 // Loop over the new globals array deleting any globals that are obviously 00430 // dead. This can arise due to scalarization of a structure or an array that 00431 // has elements that are dead. 00432 unsigned FirstGlobal = 0; 00433 for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i) 00434 if (NewGlobals[i]->use_empty()) { 00435 Globals.erase(NewGlobals[i]); 00436 if (FirstGlobal == i) ++FirstGlobal; 00437 } 00438 00439 return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0; 00440 } 00441 00442 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified 00443 /// value will trap if the value is dynamically null. 00444 static bool AllUsesOfValueWillTrapIfNull(Value *V) { 00445 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 00446 if (isa<LoadInst>(*UI)) { 00447 // Will trap. 00448 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 00449 if (SI->getOperand(0) == V) { 00450 //std::cerr << "NONTRAPPING USE: " << **UI; 00451 return false; // Storing the value. 00452 } 00453 } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) { 00454 if (CI->getOperand(0) != V) { 00455 //std::cerr << "NONTRAPPING USE: " << **UI; 00456 return false; // Not calling the ptr 00457 } 00458 } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) { 00459 if (II->getOperand(0) != V) { 00460 //std::cerr << "NONTRAPPING USE: " << **UI; 00461 return false; // Not calling the ptr 00462 } 00463 } else if (CastInst *CI = dyn_cast<CastInst>(*UI)) { 00464 if (!AllUsesOfValueWillTrapIfNull(CI)) return false; 00465 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) { 00466 if (!AllUsesOfValueWillTrapIfNull(GEPI)) return false; 00467 } else if (isa<SetCondInst>(*UI) && 00468 isa<ConstantPointerNull>(UI->getOperand(1))) { 00469 // Ignore setcc X, null 00470 } else { 00471 //std::cerr << "NONTRAPPING USE: " << **UI; 00472 return false; 00473 } 00474 return true; 00475 } 00476 00477 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads 00478 /// from GV will trap if the loaded value is null. Note that this also permits 00479 /// comparisons of the loaded value against null, as a special case. 00480 static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) { 00481 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI!=E; ++UI) 00482 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 00483 if (!AllUsesOfValueWillTrapIfNull(LI)) 00484 return false; 00485 } else if (isa<StoreInst>(*UI)) { 00486 // Ignore stores to the global. 00487 } else { 00488 // We don't know or understand this user, bail out. 00489 //std::cerr << "UNKNOWN USER OF GLOBAL!: " << **UI; 00490 return false; 00491 } 00492 00493 return true; 00494 } 00495 00496 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { 00497 bool Changed = false; 00498 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) { 00499 Instruction *I = cast<Instruction>(*UI++); 00500 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00501 LI->setOperand(0, NewV); 00502 Changed = true; 00503 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00504 if (SI->getOperand(1) == V) { 00505 SI->setOperand(1, NewV); 00506 Changed = true; 00507 } 00508 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 00509 if (I->getOperand(0) == V) { 00510 // Calling through the pointer! Turn into a direct call, but be careful 00511 // that the pointer is not also being passed as an argument. 00512 I->setOperand(0, NewV); 00513 Changed = true; 00514 bool PassedAsArg = false; 00515 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i) 00516 if (I->getOperand(i) == V) { 00517 PassedAsArg = true; 00518 I->setOperand(i, NewV); 00519 } 00520 00521 if (PassedAsArg) { 00522 // Being passed as an argument also. Be careful to not invalidate UI! 00523 UI = V->use_begin(); 00524 } 00525 } 00526 } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 00527 Changed |= OptimizeAwayTrappingUsesOfValue(CI, 00528 ConstantExpr::getCast(NewV, CI->getType())); 00529 if (CI->use_empty()) { 00530 Changed = true; 00531 CI->eraseFromParent(); 00532 } 00533 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 00534 // Should handle GEP here. 00535 std::vector<Constant*> Indices; 00536 Indices.reserve(GEPI->getNumOperands()-1); 00537 for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i) 00538 if (Constant *C = dyn_cast<Constant>(GEPI->getOperand(i))) 00539 Indices.push_back(C); 00540 else 00541 break; 00542 if (Indices.size() == GEPI->getNumOperands()-1) 00543 Changed |= OptimizeAwayTrappingUsesOfValue(GEPI, 00544 ConstantExpr::getGetElementPtr(NewV, Indices)); 00545 if (GEPI->use_empty()) { 00546 Changed = true; 00547 GEPI->eraseFromParent(); 00548 } 00549 } 00550 } 00551 00552 return Changed; 00553 } 00554 00555 00556 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null 00557 /// value stored into it. If there are uses of the loaded value that would trap 00558 /// if the loaded value is dynamically null, then we know that they cannot be 00559 /// reachable with a null optimize away the load. 00560 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) { 00561 std::vector<LoadInst*> Loads; 00562 bool Changed = false; 00563 00564 // Replace all uses of loads with uses of uses of the stored value. 00565 for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); 00566 GUI != E; ++GUI) 00567 if (LoadInst *LI = dyn_cast<LoadInst>(*GUI)) { 00568 Loads.push_back(LI); 00569 Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV); 00570 } else { 00571 assert(isa<StoreInst>(*GUI) && "Only expect load and stores!"); 00572 } 00573 00574 if (Changed) { 00575 DEBUG(std::cerr << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV); 00576 ++NumGlobUses; 00577 } 00578 00579 // Delete all of the loads we can, keeping track of whether we nuked them all! 00580 bool AllLoadsGone = true; 00581 while (!Loads.empty()) { 00582 LoadInst *L = Loads.back(); 00583 if (L->use_empty()) { 00584 L->eraseFromParent(); 00585 Changed = true; 00586 } else { 00587 AllLoadsGone = false; 00588 } 00589 Loads.pop_back(); 00590 } 00591 00592 // If we nuked all of the loads, then none of the stores are needed either, 00593 // nor is the global. 00594 if (AllLoadsGone) { 00595 DEBUG(std::cerr << " *** GLOBAL NOW DEAD!\n"); 00596 CleanupConstantGlobalUsers(GV, 0); 00597 if (GV->use_empty()) { 00598 GV->eraseFromParent(); 00599 ++NumDeleted; 00600 } 00601 Changed = true; 00602 } 00603 return Changed; 00604 } 00605 00606 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the 00607 /// instructions that are foldable. 00608 static void ConstantPropUsersOf(Value *V) { 00609 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) 00610 if (Instruction *I = dyn_cast<Instruction>(*UI++)) 00611 if (Constant *NewC = ConstantFoldInstruction(I)) { 00612 I->replaceAllUsesWith(NewC); 00613 00614 // Back up UI to avoid invalidating it! 00615 bool AtBegin = false; 00616 if (UI == V->use_begin()) 00617 AtBegin = true; 00618 else 00619 --UI; 00620 I->eraseFromParent(); 00621 if (AtBegin) 00622 UI = V->use_begin(); 00623 else 00624 ++UI; 00625 } 00626 } 00627 00628 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global 00629 /// variable, and transforms the program as if it always contained the result of 00630 /// the specified malloc. Because it is always the result of the specified 00631 /// malloc, there is no reason to actually DO the malloc. Instead, turn the 00632 /// malloc into a global, and any laods of GV as uses of the new global. 00633 static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, 00634 MallocInst *MI) { 00635 DEBUG(std::cerr << "PROMOTING MALLOC GLOBAL: " << *GV << " MALLOC = " <<*MI); 00636 ConstantInt *NElements = cast<ConstantInt>(MI->getArraySize()); 00637 00638 if (NElements->getRawValue() != 1) { 00639 // If we have an array allocation, transform it to a single element 00640 // allocation to make the code below simpler. 00641 Type *NewTy = ArrayType::get(MI->getAllocatedType(), 00642 NElements->getRawValue()); 00643 MallocInst *NewMI = 00644 new MallocInst(NewTy, Constant::getNullValue(Type::UIntTy), 00645 MI->getName(), MI); 00646 std::vector<Value*> Indices; 00647 Indices.push_back(Constant::getNullValue(Type::IntTy)); 00648 Indices.push_back(Indices[0]); 00649 Value *NewGEP = new GetElementPtrInst(NewMI, Indices, 00650 NewMI->getName()+".el0", MI); 00651 MI->replaceAllUsesWith(NewGEP); 00652 MI->eraseFromParent(); 00653 MI = NewMI; 00654 } 00655 00656 // Create the new global variable. The contents of the malloc'd memory is 00657 // undefined, so initialize with an undef value. 00658 Constant *Init = UndefValue::get(MI->getAllocatedType()); 00659 GlobalVariable *NewGV = new GlobalVariable(MI->getAllocatedType(), false, 00660 GlobalValue::InternalLinkage, Init, 00661 GV->getName()+".body"); 00662 GV->getParent()->getGlobalList().insert(GV, NewGV); 00663 00664 // Anything that used the malloc now uses the global directly. 00665 MI->replaceAllUsesWith(NewGV); 00666 00667 Constant *RepValue = NewGV; 00668 if (NewGV->getType() != GV->getType()->getElementType()) 00669 RepValue = ConstantExpr::getCast(RepValue, GV->getType()->getElementType()); 00670 00671 // If there is a comparison against null, we will insert a global bool to 00672 // keep track of whether the global was initialized yet or not. 00673 GlobalVariable *InitBool = 00674 new GlobalVariable(Type::BoolTy, false, GlobalValue::InternalLinkage, 00675 ConstantBool::False, GV->getName()+".init"); 00676 bool InitBoolUsed = false; 00677 00678 // Loop over all uses of GV, processing them in turn. 00679 std::vector<StoreInst*> Stores; 00680 while (!GV->use_empty()) 00681 if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) { 00682 while (!LI->use_empty()) { 00683 // FIXME: the iterator should expose a getUse() method. 00684 Use &LoadUse = *(const iplist<Use>::iterator&)LI->use_begin(); 00685 if (!isa<SetCondInst>(LoadUse.getUser())) 00686 LoadUse = RepValue; 00687 else { 00688 // Replace the setcc X, 0 with a use of the bool value. 00689 SetCondInst *SCI = cast<SetCondInst>(LoadUse.getUser()); 00690 Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", SCI); 00691 InitBoolUsed = true; 00692 switch (SCI->getOpcode()) { 00693 default: assert(0 && "Unknown opcode!"); 00694 case Instruction::SetLT: 00695 LV = ConstantBool::False; // X < null -> always false 00696 break; 00697 case Instruction::SetEQ: 00698 case Instruction::SetLE: 00699 LV = BinaryOperator::createNot(LV, "notinit", SCI); 00700 break; 00701 case Instruction::SetNE: 00702 case Instruction::SetGE: 00703 case Instruction::SetGT: 00704 break; // no change. 00705 } 00706 SCI->replaceAllUsesWith(LV); 00707 SCI->eraseFromParent(); 00708 } 00709 } 00710 LI->eraseFromParent(); 00711 } else { 00712 StoreInst *SI = cast<StoreInst>(GV->use_back()); 00713 // The global is initialized when the store to it occurs. 00714 new StoreInst(ConstantBool::True, InitBool, SI); 00715 SI->eraseFromParent(); 00716 } 00717 00718 // If the initialization boolean was used, insert it, otherwise delete it. 00719 if (!InitBoolUsed) { 00720 while (!InitBool->use_empty()) // Delete initializations 00721 cast<Instruction>(InitBool->use_back())->eraseFromParent(); 00722 delete InitBool; 00723 } else 00724 GV->getParent()->getGlobalList().insert(GV, InitBool); 00725 00726 00727 // Now the GV is dead, nuke it and the malloc. 00728 GV->eraseFromParent(); 00729 MI->eraseFromParent(); 00730 00731 // To further other optimizations, loop over all users of NewGV and try to 00732 // constant prop them. This will promote GEP instructions with constant 00733 // indices into GEP constant-exprs, which will allow global-opt to hack on it. 00734 ConstantPropUsersOf(NewGV); 00735 if (RepValue != NewGV) 00736 ConstantPropUsersOf(RepValue); 00737 00738 return NewGV; 00739 } 00740 00741 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking 00742 /// to make sure that there are no complex uses of V. We permit simple things 00743 /// like dereferencing the pointer, but not storing through the address, unless 00744 /// it is to the specified global. 00745 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Instruction *V, 00746 GlobalVariable *GV) { 00747 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI) 00748 if (isa<LoadInst>(*UI) || isa<SetCondInst>(*UI)) { 00749 // Fine, ignore. 00750 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 00751 if (SI->getOperand(0) == V && SI->getOperand(1) != GV) 00752 return false; // Storing the pointer itself... bad. 00753 // Otherwise, storing through it, or storing into GV... fine. 00754 } else if (isa<GetElementPtrInst>(*UI) || isa<SelectInst>(*UI)) { 00755 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(cast<Instruction>(*UI),GV)) 00756 return false; 00757 } else { 00758 return false; 00759 } 00760 return true; 00761 00762 } 00763 00764 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge 00765 // that only one value (besides its initializer) is ever stored to the global. 00766 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, 00767 Module::giterator &GVI, TargetData &TD) { 00768 if (CastInst *CI = dyn_cast<CastInst>(StoredOnceVal)) 00769 StoredOnceVal = CI->getOperand(0); 00770 else if (GetElementPtrInst *GEPI =dyn_cast<GetElementPtrInst>(StoredOnceVal)){ 00771 // "getelementptr Ptr, 0, 0, 0" is really just a cast. 00772 bool IsJustACast = true; 00773 for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i) 00774 if (!isa<Constant>(GEPI->getOperand(i)) || 00775 !cast<Constant>(GEPI->getOperand(i))->isNullValue()) { 00776 IsJustACast = false; 00777 break; 00778 } 00779 if (IsJustACast) 00780 StoredOnceVal = GEPI->getOperand(0); 00781 } 00782 00783 // If we are dealing with a pointer global that is initialized to null and 00784 // only has one (non-null) value stored into it, then we can optimize any 00785 // users of the loaded value (often calls and loads) that would trap if the 00786 // value was null. 00787 if (isa<PointerType>(GV->getInitializer()->getType()) && 00788 GV->getInitializer()->isNullValue()) { 00789 if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) { 00790 if (GV->getInitializer()->getType() != SOVC->getType()) 00791 SOVC = ConstantExpr::getCast(SOVC, GV->getInitializer()->getType()); 00792 00793 // Optimize away any trapping uses of the loaded value. 00794 if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC)) 00795 return true; 00796 } else if (MallocInst *MI = dyn_cast<MallocInst>(StoredOnceVal)) { 00797 // If we have a global that is only initialized with a fixed size malloc, 00798 // and if all users of the malloc trap, and if the malloc'd address is not 00799 // put anywhere else, transform the program to use global memory instead 00800 // of malloc'd memory. This eliminates dynamic allocation (good) and 00801 // exposes the resultant global to further GlobalOpt (even better). Note 00802 // that we restrict this transformation to only working on small 00803 // allocations (2048 bytes currently), as we don't want to introduce a 16M 00804 // global or something. 00805 if (ConstantInt *NElements = dyn_cast<ConstantInt>(MI->getArraySize())) 00806 if (MI->getAllocatedType()->isSized() && 00807 NElements->getRawValue()* 00808 TD.getTypeSize(MI->getAllocatedType()) < 2048 && 00809 AllUsesOfLoadedValueWillTrapIfNull(GV) && 00810 ValueIsOnlyUsedLocallyOrStoredToOneGlobal(MI, GV)) { 00811 GVI = OptimizeGlobalAddressOfMalloc(GV, MI); 00812 return true; 00813 } 00814 } 00815 } 00816 00817 return false; 00818 } 00819 00820 /// ProcessInternalGlobal - Analyze the specified global variable and optimize 00821 /// it if possible. If we make a change, return true. 00822 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, 00823 Module::giterator &GVI) { 00824 std::set<PHINode*> PHIUsers; 00825 GlobalStatus GS; 00826 PHIUsers.clear(); 00827 GV->removeDeadConstantUsers(); 00828 00829 if (GV->use_empty()) { 00830 DEBUG(std::cerr << "GLOBAL DEAD: " << *GV); 00831 GV->eraseFromParent(); 00832 ++NumDeleted; 00833 return true; 00834 } 00835 00836 if (!AnalyzeGlobal(GV, GS, PHIUsers)) { 00837 // If the global is never loaded (but may be stored to), it is dead. 00838 // Delete it now. 00839 if (!GS.isLoaded) { 00840 DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV); 00841 00842 // Delete any stores we can find to the global. We may not be able to 00843 // make it completely dead though. 00844 bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer()); 00845 00846 // If the global is dead now, delete it. 00847 if (GV->use_empty()) { 00848 GV->eraseFromParent(); 00849 ++NumDeleted; 00850 Changed = true; 00851 } 00852 return Changed; 00853 00854 } else if (GS.StoredType <= GlobalStatus::isInitializerStored) { 00855 DEBUG(std::cerr << "MARKING CONSTANT: " << *GV); 00856 GV->setConstant(true); 00857 00858 // Clean up any obviously simplifiable users now. 00859 CleanupConstantGlobalUsers(GV, GV->getInitializer()); 00860 00861 // If the global is dead now, just nuke it. 00862 if (GV->use_empty()) { 00863 DEBUG(std::cerr << " *** Marking constant allowed us to simplify " 00864 "all users and delete global!\n"); 00865 GV->eraseFromParent(); 00866 ++NumDeleted; 00867 } 00868 00869 ++NumMarked; 00870 return true; 00871 } else if (!GS.isNotSuitableForSRA && 00872 !GV->getInitializer()->getType()->isFirstClassType()) { 00873 if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) { 00874 GVI = FirstNewGV; // Don't skip the newly produced globals! 00875 return true; 00876 } 00877 } else if (GS.StoredType == GlobalStatus::isStoredOnce) { 00878 // If the initial value for the global was an undef value, and if only one 00879 // other value was stored into it, we can just change the initializer to 00880 // be an undef value, then delete all stores to the global. This allows 00881 // us to mark it constant. 00882 if (isa<UndefValue>(GV->getInitializer()) && 00883 isa<Constant>(GS.StoredOnceValue)) { 00884 // Change the initial value here. 00885 GV->setInitializer(cast<Constant>(GS.StoredOnceValue)); 00886 00887 // Clean up any obviously simplifiable users now. 00888 CleanupConstantGlobalUsers(GV, GV->getInitializer()); 00889 00890 if (GV->use_empty()) { 00891 DEBUG(std::cerr << " *** Substituting initializer allowed us to " 00892 "simplify all users and delete global!\n"); 00893 GV->eraseFromParent(); 00894 ++NumDeleted; 00895 } else { 00896 GVI = GV; 00897 } 00898 ++NumSubstitute; 00899 return true; 00900 } 00901 00902 // Try to optimize globals based on the knowledge that only one value 00903 // (besides its initializer) is ever stored to the global. 00904 if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GVI, 00905 getAnalysis<TargetData>())) 00906 return true; 00907 } 00908 } 00909 return false; 00910 } 00911 00912 00913 bool GlobalOpt::runOnModule(Module &M) { 00914 bool Changed = false; 00915 00916 // As a prepass, delete functions that are trivially dead. 00917 bool LocalChange = true; 00918 while (LocalChange) { 00919 LocalChange = false; 00920 for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) { 00921 Function *F = FI++; 00922 F->removeDeadConstantUsers(); 00923 if (F->use_empty() && (F->hasInternalLinkage() || 00924 F->hasLinkOnceLinkage())) { 00925 M.getFunctionList().erase(F); 00926 LocalChange = true; 00927 ++NumFnDeleted; 00928 } 00929 } 00930 Changed |= LocalChange; 00931 } 00932 00933 LocalChange = true; 00934 while (LocalChange) { 00935 LocalChange = false; 00936 for (Module::giterator GVI = M.gbegin(), E = M.gend(); GVI != E;) { 00937 GlobalVariable *GV = GVI++; 00938 if (!GV->isConstant() && GV->hasInternalLinkage() && 00939 GV->hasInitializer()) 00940 LocalChange |= ProcessInternalGlobal(GV, GVI); 00941 } 00942 Changed |= LocalChange; 00943 } 00944 return Changed; 00945 }