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/CallingConv.h" 00019 #include "llvm/Constants.h" 00020 #include "llvm/DerivedTypes.h" 00021 #include "llvm/Instructions.h" 00022 #include "llvm/IntrinsicInst.h" 00023 #include "llvm/Module.h" 00024 #include "llvm/Pass.h" 00025 #include "llvm/Support/Debug.h" 00026 #include "llvm/Target/TargetData.h" 00027 #include "llvm/Transforms/Utils/Local.h" 00028 #include "llvm/ADT/Statistic.h" 00029 #include "llvm/ADT/StringExtras.h" 00030 #include <algorithm> 00031 #include <iostream> 00032 #include <set> 00033 using namespace llvm; 00034 00035 namespace { 00036 Statistic<> NumMarked ("globalopt", "Number of globals marked constant"); 00037 Statistic<> NumSRA ("globalopt", "Number of aggregate globals broken " 00038 "into scalars"); 00039 Statistic<> NumSubstitute("globalopt", 00040 "Number of globals with initializers stored into them"); 00041 Statistic<> NumDeleted ("globalopt", "Number of globals deleted"); 00042 Statistic<> NumFnDeleted("globalopt", "Number of functions deleted"); 00043 Statistic<> NumGlobUses ("globalopt", "Number of global uses devirtualized"); 00044 Statistic<> NumLocalized("globalopt", "Number of globals localized"); 00045 Statistic<> NumShrunkToBool("globalopt", 00046 "Number of global vars shrunk to booleans"); 00047 Statistic<> NumFastCallFns("globalopt", 00048 "Number of functions converted to fastcc"); 00049 Statistic<> NumCtorsEvaluated("globalopt","Number of static ctors evaluated"); 00050 00051 struct GlobalOpt : public ModulePass { 00052 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00053 AU.addRequired<TargetData>(); 00054 } 00055 00056 bool runOnModule(Module &M); 00057 00058 private: 00059 GlobalVariable *FindGlobalCtors(Module &M); 00060 bool OptimizeFunctions(Module &M); 00061 bool OptimizeGlobalVars(Module &M); 00062 bool OptimizeGlobalCtorsList(GlobalVariable *&GCL); 00063 bool ProcessInternalGlobal(GlobalVariable *GV, Module::global_iterator &GVI); 00064 }; 00065 00066 RegisterOpt<GlobalOpt> X("globalopt", "Global Variable Optimizer"); 00067 } 00068 00069 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); } 00070 00071 /// GlobalStatus - As we analyze each global, keep track of some information 00072 /// about it. If we find out that the address of the global is taken, none of 00073 /// this info will be accurate. 00074 struct GlobalStatus { 00075 /// isLoaded - True if the global is ever loaded. If the global isn't ever 00076 /// loaded it can be deleted. 00077 bool isLoaded; 00078 00079 /// StoredType - Keep track of what stores to the global look like. 00080 /// 00081 enum StoredType { 00082 /// NotStored - There is no store to this global. It can thus be marked 00083 /// constant. 00084 NotStored, 00085 00086 /// isInitializerStored - This global is stored to, but the only thing 00087 /// stored is the constant it was initialized with. This is only tracked 00088 /// for scalar globals. 00089 isInitializerStored, 00090 00091 /// isStoredOnce - This global is stored to, but only its initializer and 00092 /// one other value is ever stored to it. If this global isStoredOnce, we 00093 /// track the value stored to it in StoredOnceValue below. This is only 00094 /// tracked for scalar globals. 00095 isStoredOnce, 00096 00097 /// isStored - This global is stored to by multiple values or something else 00098 /// that we cannot track. 00099 isStored 00100 } StoredType; 00101 00102 /// StoredOnceValue - If only one value (besides the initializer constant) is 00103 /// ever stored to this global, keep track of what value it is. 00104 Value *StoredOnceValue; 00105 00106 // AccessingFunction/HasMultipleAccessingFunctions - These start out 00107 // null/false. When the first accessing function is noticed, it is recorded. 00108 // When a second different accessing function is noticed, 00109 // HasMultipleAccessingFunctions is set to true. 00110 Function *AccessingFunction; 00111 bool HasMultipleAccessingFunctions; 00112 00113 // HasNonInstructionUser - Set to true if this global has a user that is not 00114 // an instruction (e.g. a constant expr or GV initializer). 00115 bool HasNonInstructionUser; 00116 00117 /// isNotSuitableForSRA - Keep track of whether any SRA preventing users of 00118 /// the global exist. Such users include GEP instruction with variable 00119 /// indexes, and non-gep/load/store users like constant expr casts. 00120 bool isNotSuitableForSRA; 00121 00122 GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0), 00123 AccessingFunction(0), HasMultipleAccessingFunctions(false), 00124 HasNonInstructionUser(false), isNotSuitableForSRA(false) {} 00125 }; 00126 00127 00128 00129 /// ConstantIsDead - Return true if the specified constant is (transitively) 00130 /// dead. The constant may be used by other constants (e.g. constant arrays and 00131 /// constant exprs) as long as they are dead, but it cannot be used by anything 00132 /// else. 00133 static bool ConstantIsDead(Constant *C) { 00134 if (isa<GlobalValue>(C)) return false; 00135 00136 for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI) 00137 if (Constant *CU = dyn_cast<Constant>(*UI)) { 00138 if (!ConstantIsDead(CU)) return false; 00139 } else 00140 return false; 00141 return true; 00142 } 00143 00144 00145 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus 00146 /// structure. If the global has its address taken, return true to indicate we 00147 /// can't do anything with it. 00148 /// 00149 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, 00150 std::set<PHINode*> &PHIUsers) { 00151 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 00152 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) { 00153 GS.HasNonInstructionUser = true; 00154 00155 if (AnalyzeGlobal(CE, GS, PHIUsers)) return true; 00156 if (CE->getOpcode() != Instruction::GetElementPtr) 00157 GS.isNotSuitableForSRA = true; 00158 else if (!GS.isNotSuitableForSRA) { 00159 // Check to see if this ConstantExpr GEP is SRA'able. In particular, we 00160 // don't like < 3 operand CE's, and we don't like non-constant integer 00161 // indices. 00162 if (CE->getNumOperands() < 3 || !CE->getOperand(1)->isNullValue()) 00163 GS.isNotSuitableForSRA = true; 00164 else { 00165 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 00166 if (!isa<ConstantInt>(CE->getOperand(i))) { 00167 GS.isNotSuitableForSRA = true; 00168 break; 00169 } 00170 } 00171 } 00172 00173 } else if (Instruction *I = dyn_cast<Instruction>(*UI)) { 00174 if (!GS.HasMultipleAccessingFunctions) { 00175 Function *F = I->getParent()->getParent(); 00176 if (GS.AccessingFunction == 0) 00177 GS.AccessingFunction = F; 00178 else if (GS.AccessingFunction != F) 00179 GS.HasMultipleAccessingFunctions = true; 00180 } 00181 if (isa<LoadInst>(I)) { 00182 GS.isLoaded = true; 00183 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00184 // Don't allow a store OF the address, only stores TO the address. 00185 if (SI->getOperand(0) == V) return true; 00186 00187 // If this is a direct store to the global (i.e., the global is a scalar 00188 // value, not an aggregate), keep more specific information about 00189 // stores. 00190 if (GS.StoredType != GlobalStatus::isStored) 00191 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){ 00192 Value *StoredVal = SI->getOperand(0); 00193 if (StoredVal == GV->getInitializer()) { 00194 if (GS.StoredType < GlobalStatus::isInitializerStored) 00195 GS.StoredType = GlobalStatus::isInitializerStored; 00196 } else if (isa<LoadInst>(StoredVal) && 00197 cast<LoadInst>(StoredVal)->getOperand(0) == GV) { 00198 // G = G 00199 if (GS.StoredType < GlobalStatus::isInitializerStored) 00200 GS.StoredType = GlobalStatus::isInitializerStored; 00201 } else if (GS.StoredType < GlobalStatus::isStoredOnce) { 00202 GS.StoredType = GlobalStatus::isStoredOnce; 00203 GS.StoredOnceValue = StoredVal; 00204 } else if (GS.StoredType == GlobalStatus::isStoredOnce && 00205 GS.StoredOnceValue == StoredVal) { 00206 // noop. 00207 } else { 00208 GS.StoredType = GlobalStatus::isStored; 00209 } 00210 } else { 00211 GS.StoredType = GlobalStatus::isStored; 00212 } 00213 } else if (isa<GetElementPtrInst>(I)) { 00214 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00215 00216 // If the first two indices are constants, this can be SRA'd. 00217 if (isa<GlobalVariable>(I->getOperand(0))) { 00218 if (I->getNumOperands() < 3 || !isa<Constant>(I->getOperand(1)) || 00219 !cast<Constant>(I->getOperand(1))->isNullValue() || 00220 !isa<ConstantInt>(I->getOperand(2))) 00221 GS.isNotSuitableForSRA = true; 00222 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(I->getOperand(0))){ 00223 if (CE->getOpcode() != Instruction::GetElementPtr || 00224 CE->getNumOperands() < 3 || I->getNumOperands() < 2 || 00225 !isa<Constant>(I->getOperand(0)) || 00226 !cast<Constant>(I->getOperand(0))->isNullValue()) 00227 GS.isNotSuitableForSRA = true; 00228 } else { 00229 GS.isNotSuitableForSRA = true; 00230 } 00231 } else if (isa<SelectInst>(I)) { 00232 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00233 GS.isNotSuitableForSRA = true; 00234 } else if (PHINode *PN = dyn_cast<PHINode>(I)) { 00235 // PHI nodes we can check just like select or GEP instructions, but we 00236 // have to be careful about infinite recursion. 00237 if (PHIUsers.insert(PN).second) // Not already visited. 00238 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00239 GS.isNotSuitableForSRA = true; 00240 } else if (isa<SetCondInst>(I)) { 00241 GS.isNotSuitableForSRA = true; 00242 } else if (isa<MemCpyInst>(I) || isa<MemMoveInst>(I)) { 00243 if (I->getOperand(1) == V) 00244 GS.StoredType = GlobalStatus::isStored; 00245 if (I->getOperand(2) == V) 00246 GS.isLoaded = true; 00247 GS.isNotSuitableForSRA = true; 00248 } else if (isa<MemSetInst>(I)) { 00249 assert(I->getOperand(1) == V && "Memset only takes one pointer!"); 00250 GS.StoredType = GlobalStatus::isStored; 00251 GS.isNotSuitableForSRA = true; 00252 } else { 00253 return true; // Any other non-load instruction might take address! 00254 } 00255 } else if (Constant *C = dyn_cast<Constant>(*UI)) { 00256 GS.HasNonInstructionUser = true; 00257 // We might have a dead and dangling constant hanging off of here. 00258 if (!ConstantIsDead(C)) 00259 return true; 00260 } else { 00261 GS.HasNonInstructionUser = true; 00262 // Otherwise must be some other user. 00263 return true; 00264 } 00265 00266 return false; 00267 } 00268 00269 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) { 00270 ConstantInt *CI = dyn_cast<ConstantInt>(Idx); 00271 if (!CI) return 0; 00272 unsigned IdxV = (unsigned)CI->getRawValue(); 00273 00274 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) { 00275 if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV); 00276 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) { 00277 if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV); 00278 } else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Agg)) { 00279 if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV); 00280 } else if (isa<ConstantAggregateZero>(Agg)) { 00281 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) { 00282 if (IdxV < STy->getNumElements()) 00283 return Constant::getNullValue(STy->getElementType(IdxV)); 00284 } else if (const SequentialType *STy = 00285 dyn_cast<SequentialType>(Agg->getType())) { 00286 return Constant::getNullValue(STy->getElementType()); 00287 } 00288 } else if (isa<UndefValue>(Agg)) { 00289 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) { 00290 if (IdxV < STy->getNumElements()) 00291 return UndefValue::get(STy->getElementType(IdxV)); 00292 } else if (const SequentialType *STy = 00293 dyn_cast<SequentialType>(Agg->getType())) { 00294 return UndefValue::get(STy->getElementType()); 00295 } 00296 } 00297 return 0; 00298 } 00299 00300 00301 /// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all 00302 /// users of the global, cleaning up the obvious ones. This is largely just a 00303 /// quick scan over the use list to clean up the easy and obvious cruft. This 00304 /// returns true if it made a change. 00305 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) { 00306 bool Changed = false; 00307 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) { 00308 User *U = *UI++; 00309 00310 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 00311 if (Init) { 00312 // Replace the load with the initializer. 00313 LI->replaceAllUsesWith(Init); 00314 LI->eraseFromParent(); 00315 Changed = true; 00316 } 00317 } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 00318 // Store must be unreachable or storing Init into the global. 00319 SI->eraseFromParent(); 00320 Changed = true; 00321 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 00322 if (CE->getOpcode() == Instruction::GetElementPtr) { 00323 Constant *SubInit = 0; 00324 if (Init) 00325 SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); 00326 Changed |= CleanupConstantGlobalUsers(CE, SubInit); 00327 } else if (CE->getOpcode() == Instruction::Cast && 00328 isa<PointerType>(CE->getType())) { 00329 // Pointer cast, delete any stores and memsets to the global. 00330 Changed |= CleanupConstantGlobalUsers(CE, 0); 00331 } 00332 00333 if (CE->use_empty()) { 00334 CE->destroyConstant(); 00335 Changed = true; 00336 } 00337 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 00338 Constant *SubInit = 0; 00339 ConstantExpr *CE = 00340 dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP)); 00341 if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr) 00342 SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); 00343 Changed |= CleanupConstantGlobalUsers(GEP, SubInit); 00344 00345 if (GEP->use_empty()) { 00346 GEP->eraseFromParent(); 00347 Changed = true; 00348 } 00349 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv 00350 if (MI->getRawDest() == V) { 00351 MI->eraseFromParent(); 00352 Changed = true; 00353 } 00354 00355 } else if (Constant *C = dyn_cast<Constant>(U)) { 00356 // If we have a chain of dead constantexprs or other things dangling from 00357 // us, and if they are all dead, nuke them without remorse. 00358 if (ConstantIsDead(C)) { 00359 C->destroyConstant(); 00360 // This could have invalidated UI, start over from scratch. 00361 CleanupConstantGlobalUsers(V, Init); 00362 return true; 00363 } 00364 } 00365 } 00366 return Changed; 00367 } 00368 00369 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global 00370 /// variable. This opens the door for other optimizations by exposing the 00371 /// behavior of the program in a more fine-grained way. We have determined that 00372 /// this transformation is safe already. We return the first global variable we 00373 /// insert so that the caller can reprocess it. 00374 static GlobalVariable *SRAGlobal(GlobalVariable *GV) { 00375 assert(GV->hasInternalLinkage() && !GV->isConstant()); 00376 Constant *Init = GV->getInitializer(); 00377 const Type *Ty = Init->getType(); 00378 00379 std::vector<GlobalVariable*> NewGlobals; 00380 Module::GlobalListType &Globals = GV->getParent()->getGlobalList(); 00381 00382 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 00383 NewGlobals.reserve(STy->getNumElements()); 00384 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 00385 Constant *In = getAggregateConstantElement(Init, 00386 ConstantUInt::get(Type::UIntTy, i)); 00387 assert(In && "Couldn't get element of initializer?"); 00388 GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false, 00389 GlobalVariable::InternalLinkage, 00390 In, GV->getName()+"."+utostr(i)); 00391 Globals.insert(GV, NGV); 00392 NewGlobals.push_back(NGV); 00393 } 00394 } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) { 00395 unsigned NumElements = 0; 00396 if (const ArrayType *ATy = dyn_cast<ArrayType>(STy)) 00397 NumElements = ATy->getNumElements(); 00398 else if (const PackedType *PTy = dyn_cast<PackedType>(STy)) 00399 NumElements = PTy->getNumElements(); 00400 else 00401 assert(0 && "Unknown aggregate sequential type!"); 00402 00403 if (NumElements > 16 && GV->hasNUsesOrMore(16)) 00404 return 0; // It's not worth it. 00405 NewGlobals.reserve(NumElements); 00406 for (unsigned i = 0, e = NumElements; i != e; ++i) { 00407 Constant *In = getAggregateConstantElement(Init, 00408 ConstantUInt::get(Type::UIntTy, i)); 00409 assert(In && "Couldn't get element of initializer?"); 00410 00411 GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false, 00412 GlobalVariable::InternalLinkage, 00413 In, GV->getName()+"."+utostr(i)); 00414 Globals.insert(GV, NGV); 00415 NewGlobals.push_back(NGV); 00416 } 00417 } 00418 00419 if (NewGlobals.empty()) 00420 return 0; 00421 00422 DEBUG(std::cerr << "PERFORMING GLOBAL SRA ON: " << *GV); 00423 00424 Constant *NullInt = Constant::getNullValue(Type::IntTy); 00425 00426 // Loop over all of the uses of the global, replacing the constantexpr geps, 00427 // with smaller constantexpr geps or direct references. 00428 while (!GV->use_empty()) { 00429 User *GEP = GV->use_back(); 00430 assert(((isa<ConstantExpr>(GEP) && 00431 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| 00432 isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!"); 00433 00434 // Ignore the 1th operand, which has to be zero or else the program is quite 00435 // broken (undefined). Get the 2nd operand, which is the structure or array 00436 // index. 00437 unsigned Val = 00438 (unsigned)cast<ConstantInt>(GEP->getOperand(2))->getRawValue(); 00439 if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access. 00440 00441 Value *NewPtr = NewGlobals[Val]; 00442 00443 // Form a shorter GEP if needed. 00444 if (GEP->getNumOperands() > 3) 00445 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) { 00446 std::vector<Constant*> Idxs; 00447 Idxs.push_back(NullInt); 00448 for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i) 00449 Idxs.push_back(CE->getOperand(i)); 00450 NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), Idxs); 00451 } else { 00452 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP); 00453 std::vector<Value*> Idxs; 00454 Idxs.push_back(NullInt); 00455 for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i) 00456 Idxs.push_back(GEPI->getOperand(i)); 00457 NewPtr = new GetElementPtrInst(NewPtr, Idxs, 00458 GEPI->getName()+"."+utostr(Val), GEPI); 00459 } 00460 GEP->replaceAllUsesWith(NewPtr); 00461 00462 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP)) 00463 GEPI->eraseFromParent(); 00464 else 00465 cast<ConstantExpr>(GEP)->destroyConstant(); 00466 } 00467 00468 // Delete the old global, now that it is dead. 00469 Globals.erase(GV); 00470 ++NumSRA; 00471 00472 // Loop over the new globals array deleting any globals that are obviously 00473 // dead. This can arise due to scalarization of a structure or an array that 00474 // has elements that are dead. 00475 unsigned FirstGlobal = 0; 00476 for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i) 00477 if (NewGlobals[i]->use_empty()) { 00478 Globals.erase(NewGlobals[i]); 00479 if (FirstGlobal == i) ++FirstGlobal; 00480 } 00481 00482 return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0; 00483 } 00484 00485 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified 00486 /// value will trap if the value is dynamically null. 00487 static bool AllUsesOfValueWillTrapIfNull(Value *V) { 00488 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 00489 if (isa<LoadInst>(*UI)) { 00490 // Will trap. 00491 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 00492 if (SI->getOperand(0) == V) { 00493 //std::cerr << "NONTRAPPING USE: " << **UI; 00494 return false; // Storing the value. 00495 } 00496 } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) { 00497 if (CI->getOperand(0) != V) { 00498 //std::cerr << "NONTRAPPING USE: " << **UI; 00499 return false; // Not calling the ptr 00500 } 00501 } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) { 00502 if (II->getOperand(0) != V) { 00503 //std::cerr << "NONTRAPPING USE: " << **UI; 00504 return false; // Not calling the ptr 00505 } 00506 } else if (CastInst *CI = dyn_cast<CastInst>(*UI)) { 00507 if (!AllUsesOfValueWillTrapIfNull(CI)) return false; 00508 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) { 00509 if (!AllUsesOfValueWillTrapIfNull(GEPI)) return false; 00510 } else if (isa<SetCondInst>(*UI) && 00511 isa<ConstantPointerNull>(UI->getOperand(1))) { 00512 // Ignore setcc X, null 00513 } else { 00514 //std::cerr << "NONTRAPPING USE: " << **UI; 00515 return false; 00516 } 00517 return true; 00518 } 00519 00520 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads 00521 /// from GV will trap if the loaded value is null. Note that this also permits 00522 /// comparisons of the loaded value against null, as a special case. 00523 static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) { 00524 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI!=E; ++UI) 00525 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 00526 if (!AllUsesOfValueWillTrapIfNull(LI)) 00527 return false; 00528 } else if (isa<StoreInst>(*UI)) { 00529 // Ignore stores to the global. 00530 } else { 00531 // We don't know or understand this user, bail out. 00532 //std::cerr << "UNKNOWN USER OF GLOBAL!: " << **UI; 00533 return false; 00534 } 00535 00536 return true; 00537 } 00538 00539 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { 00540 bool Changed = false; 00541 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) { 00542 Instruction *I = cast<Instruction>(*UI++); 00543 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00544 LI->setOperand(0, NewV); 00545 Changed = true; 00546 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00547 if (SI->getOperand(1) == V) { 00548 SI->setOperand(1, NewV); 00549 Changed = true; 00550 } 00551 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 00552 if (I->getOperand(0) == V) { 00553 // Calling through the pointer! Turn into a direct call, but be careful 00554 // that the pointer is not also being passed as an argument. 00555 I->setOperand(0, NewV); 00556 Changed = true; 00557 bool PassedAsArg = false; 00558 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i) 00559 if (I->getOperand(i) == V) { 00560 PassedAsArg = true; 00561 I->setOperand(i, NewV); 00562 } 00563 00564 if (PassedAsArg) { 00565 // Being passed as an argument also. Be careful to not invalidate UI! 00566 UI = V->use_begin(); 00567 } 00568 } 00569 } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 00570 Changed |= OptimizeAwayTrappingUsesOfValue(CI, 00571 ConstantExpr::getCast(NewV, CI->getType())); 00572 if (CI->use_empty()) { 00573 Changed = true; 00574 CI->eraseFromParent(); 00575 } 00576 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 00577 // Should handle GEP here. 00578 std::vector<Constant*> Indices; 00579 Indices.reserve(GEPI->getNumOperands()-1); 00580 for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i) 00581 if (Constant *C = dyn_cast<Constant>(GEPI->getOperand(i))) 00582 Indices.push_back(C); 00583 else 00584 break; 00585 if (Indices.size() == GEPI->getNumOperands()-1) 00586 Changed |= OptimizeAwayTrappingUsesOfValue(GEPI, 00587 ConstantExpr::getGetElementPtr(NewV, Indices)); 00588 if (GEPI->use_empty()) { 00589 Changed = true; 00590 GEPI->eraseFromParent(); 00591 } 00592 } 00593 } 00594 00595 return Changed; 00596 } 00597 00598 00599 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null 00600 /// value stored into it. If there are uses of the loaded value that would trap 00601 /// if the loaded value is dynamically null, then we know that they cannot be 00602 /// reachable with a null optimize away the load. 00603 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) { 00604 std::vector<LoadInst*> Loads; 00605 bool Changed = false; 00606 00607 // Replace all uses of loads with uses of uses of the stored value. 00608 for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); 00609 GUI != E; ++GUI) 00610 if (LoadInst *LI = dyn_cast<LoadInst>(*GUI)) { 00611 Loads.push_back(LI); 00612 Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV); 00613 } else { 00614 assert(isa<StoreInst>(*GUI) && "Only expect load and stores!"); 00615 } 00616 00617 if (Changed) { 00618 DEBUG(std::cerr << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV); 00619 ++NumGlobUses; 00620 } 00621 00622 // Delete all of the loads we can, keeping track of whether we nuked them all! 00623 bool AllLoadsGone = true; 00624 while (!Loads.empty()) { 00625 LoadInst *L = Loads.back(); 00626 if (L->use_empty()) { 00627 L->eraseFromParent(); 00628 Changed = true; 00629 } else { 00630 AllLoadsGone = false; 00631 } 00632 Loads.pop_back(); 00633 } 00634 00635 // If we nuked all of the loads, then none of the stores are needed either, 00636 // nor is the global. 00637 if (AllLoadsGone) { 00638 DEBUG(std::cerr << " *** GLOBAL NOW DEAD!\n"); 00639 CleanupConstantGlobalUsers(GV, 0); 00640 if (GV->use_empty()) { 00641 GV->eraseFromParent(); 00642 ++NumDeleted; 00643 } 00644 Changed = true; 00645 } 00646 return Changed; 00647 } 00648 00649 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the 00650 /// instructions that are foldable. 00651 static void ConstantPropUsersOf(Value *V) { 00652 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) 00653 if (Instruction *I = dyn_cast<Instruction>(*UI++)) 00654 if (Constant *NewC = ConstantFoldInstruction(I)) { 00655 I->replaceAllUsesWith(NewC); 00656 00657 // Advance UI to the next non-I use to avoid invalidating it! 00658 // Instructions could multiply use V. 00659 while (UI != E && *UI == I) 00660 ++UI; 00661 I->eraseFromParent(); 00662 } 00663 } 00664 00665 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global 00666 /// variable, and transforms the program as if it always contained the result of 00667 /// the specified malloc. Because it is always the result of the specified 00668 /// malloc, there is no reason to actually DO the malloc. Instead, turn the 00669 /// malloc into a global, and any laods of GV as uses of the new global. 00670 static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, 00671 MallocInst *MI) { 00672 DEBUG(std::cerr << "PROMOTING MALLOC GLOBAL: " << *GV << " MALLOC = " <<*MI); 00673 ConstantInt *NElements = cast<ConstantInt>(MI->getArraySize()); 00674 00675 if (NElements->getRawValue() != 1) { 00676 // If we have an array allocation, transform it to a single element 00677 // allocation to make the code below simpler. 00678 Type *NewTy = ArrayType::get(MI->getAllocatedType(), 00679 (unsigned)NElements->getRawValue()); 00680 MallocInst *NewMI = 00681 new MallocInst(NewTy, Constant::getNullValue(Type::UIntTy), 00682 MI->getAlignment(), MI->getName(), MI); 00683 std::vector<Value*> Indices; 00684 Indices.push_back(Constant::getNullValue(Type::IntTy)); 00685 Indices.push_back(Indices[0]); 00686 Value *NewGEP = new GetElementPtrInst(NewMI, Indices, 00687 NewMI->getName()+".el0", MI); 00688 MI->replaceAllUsesWith(NewGEP); 00689 MI->eraseFromParent(); 00690 MI = NewMI; 00691 } 00692 00693 // Create the new global variable. The contents of the malloc'd memory is 00694 // undefined, so initialize with an undef value. 00695 Constant *Init = UndefValue::get(MI->getAllocatedType()); 00696 GlobalVariable *NewGV = new GlobalVariable(MI->getAllocatedType(), false, 00697 GlobalValue::InternalLinkage, Init, 00698 GV->getName()+".body"); 00699 GV->getParent()->getGlobalList().insert(GV, NewGV); 00700 00701 // Anything that used the malloc now uses the global directly. 00702 MI->replaceAllUsesWith(NewGV); 00703 00704 Constant *RepValue = NewGV; 00705 if (NewGV->getType() != GV->getType()->getElementType()) 00706 RepValue = ConstantExpr::getCast(RepValue, GV->getType()->getElementType()); 00707 00708 // If there is a comparison against null, we will insert a global bool to 00709 // keep track of whether the global was initialized yet or not. 00710 GlobalVariable *InitBool = 00711 new GlobalVariable(Type::BoolTy, false, GlobalValue::InternalLinkage, 00712 ConstantBool::False, GV->getName()+".init"); 00713 bool InitBoolUsed = false; 00714 00715 // Loop over all uses of GV, processing them in turn. 00716 std::vector<StoreInst*> Stores; 00717 while (!GV->use_empty()) 00718 if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) { 00719 while (!LI->use_empty()) { 00720 Use &LoadUse = LI->use_begin().getUse(); 00721 if (!isa<SetCondInst>(LoadUse.getUser())) 00722 LoadUse = RepValue; 00723 else { 00724 // Replace the setcc X, 0 with a use of the bool value. 00725 SetCondInst *SCI = cast<SetCondInst>(LoadUse.getUser()); 00726 Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", SCI); 00727 InitBoolUsed = true; 00728 switch (SCI->getOpcode()) { 00729 default: assert(0 && "Unknown opcode!"); 00730 case Instruction::SetLT: 00731 LV = ConstantBool::False; // X < null -> always false 00732 break; 00733 case Instruction::SetEQ: 00734 case Instruction::SetLE: 00735 LV = BinaryOperator::createNot(LV, "notinit", SCI); 00736 break; 00737 case Instruction::SetNE: 00738 case Instruction::SetGE: 00739 case Instruction::SetGT: 00740 break; // no change. 00741 } 00742 SCI->replaceAllUsesWith(LV); 00743 SCI->eraseFromParent(); 00744 } 00745 } 00746 LI->eraseFromParent(); 00747 } else { 00748 StoreInst *SI = cast<StoreInst>(GV->use_back()); 00749 // The global is initialized when the store to it occurs. 00750 new StoreInst(ConstantBool::True, InitBool, SI); 00751 SI->eraseFromParent(); 00752 } 00753 00754 // If the initialization boolean was used, insert it, otherwise delete it. 00755 if (!InitBoolUsed) { 00756 while (!InitBool->use_empty()) // Delete initializations 00757 cast<Instruction>(InitBool->use_back())->eraseFromParent(); 00758 delete InitBool; 00759 } else 00760 GV->getParent()->getGlobalList().insert(GV, InitBool); 00761 00762 00763 // Now the GV is dead, nuke it and the malloc. 00764 GV->eraseFromParent(); 00765 MI->eraseFromParent(); 00766 00767 // To further other optimizations, loop over all users of NewGV and try to 00768 // constant prop them. This will promote GEP instructions with constant 00769 // indices into GEP constant-exprs, which will allow global-opt to hack on it. 00770 ConstantPropUsersOf(NewGV); 00771 if (RepValue != NewGV) 00772 ConstantPropUsersOf(RepValue); 00773 00774 return NewGV; 00775 } 00776 00777 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking 00778 /// to make sure that there are no complex uses of V. We permit simple things 00779 /// like dereferencing the pointer, but not storing through the address, unless 00780 /// it is to the specified global. 00781 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Instruction *V, 00782 GlobalVariable *GV) { 00783 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI) 00784 if (isa<LoadInst>(*UI) || isa<SetCondInst>(*UI)) { 00785 // Fine, ignore. 00786 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 00787 if (SI->getOperand(0) == V && SI->getOperand(1) != GV) 00788 return false; // Storing the pointer itself... bad. 00789 // Otherwise, storing through it, or storing into GV... fine. 00790 } else if (isa<GetElementPtrInst>(*UI) || isa<SelectInst>(*UI)) { 00791 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(cast<Instruction>(*UI),GV)) 00792 return false; 00793 } else { 00794 return false; 00795 } 00796 return true; 00797 00798 } 00799 00800 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge 00801 // that only one value (besides its initializer) is ever stored to the global. 00802 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, 00803 Module::global_iterator &GVI, TargetData &TD) { 00804 if (CastInst *CI = dyn_cast<CastInst>(StoredOnceVal)) 00805 StoredOnceVal = CI->getOperand(0); 00806 else if (GetElementPtrInst *GEPI =dyn_cast<GetElementPtrInst>(StoredOnceVal)){ 00807 // "getelementptr Ptr, 0, 0, 0" is really just a cast. 00808 bool IsJustACast = true; 00809 for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i) 00810 if (!isa<Constant>(GEPI->getOperand(i)) || 00811 !cast<Constant>(GEPI->getOperand(i))->isNullValue()) { 00812 IsJustACast = false; 00813 break; 00814 } 00815 if (IsJustACast) 00816 StoredOnceVal = GEPI->getOperand(0); 00817 } 00818 00819 // If we are dealing with a pointer global that is initialized to null and 00820 // only has one (non-null) value stored into it, then we can optimize any 00821 // users of the loaded value (often calls and loads) that would trap if the 00822 // value was null. 00823 if (isa<PointerType>(GV->getInitializer()->getType()) && 00824 GV->getInitializer()->isNullValue()) { 00825 if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) { 00826 if (GV->getInitializer()->getType() != SOVC->getType()) 00827 SOVC = ConstantExpr::getCast(SOVC, GV->getInitializer()->getType()); 00828 00829 // Optimize away any trapping uses of the loaded value. 00830 if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC)) 00831 return true; 00832 } else if (MallocInst *MI = dyn_cast<MallocInst>(StoredOnceVal)) { 00833 // If we have a global that is only initialized with a fixed size malloc, 00834 // and if all users of the malloc trap, and if the malloc'd address is not 00835 // put anywhere else, transform the program to use global memory instead 00836 // of malloc'd memory. This eliminates dynamic allocation (good) and 00837 // exposes the resultant global to further GlobalOpt (even better). Note 00838 // that we restrict this transformation to only working on small 00839 // allocations (2048 bytes currently), as we don't want to introduce a 16M 00840 // global or something. 00841 if (ConstantInt *NElements = dyn_cast<ConstantInt>(MI->getArraySize())) 00842 if (MI->getAllocatedType()->isSized() && 00843 NElements->getRawValue()* 00844 TD.getTypeSize(MI->getAllocatedType()) < 2048 && 00845 AllUsesOfLoadedValueWillTrapIfNull(GV) && 00846 ValueIsOnlyUsedLocallyOrStoredToOneGlobal(MI, GV)) { 00847 GVI = OptimizeGlobalAddressOfMalloc(GV, MI); 00848 return true; 00849 } 00850 } 00851 } 00852 00853 return false; 00854 } 00855 00856 /// ShrinkGlobalToBoolean - At this point, we have learned that the only two 00857 /// values ever stored into GV are its initializer and OtherVal. 00858 static void ShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { 00859 // Create the new global, initializing it to false. 00860 GlobalVariable *NewGV = new GlobalVariable(Type::BoolTy, false, 00861 GlobalValue::InternalLinkage, ConstantBool::False, GV->getName()+".b"); 00862 GV->getParent()->getGlobalList().insert(GV, NewGV); 00863 00864 Constant *InitVal = GV->getInitializer(); 00865 assert(InitVal->getType() != Type::BoolTy && "No reason to shrink to bool!"); 00866 00867 // If initialized to zero and storing one into the global, we can use a cast 00868 // instead of a select to synthesize the desired value. 00869 bool IsOneZero = false; 00870 if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) 00871 IsOneZero = InitVal->isNullValue() && CI->equalsInt(1); 00872 00873 while (!GV->use_empty()) { 00874 Instruction *UI = cast<Instruction>(GV->use_back()); 00875 if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 00876 // Change the store into a boolean store. 00877 bool StoringOther = SI->getOperand(0) == OtherVal; 00878 // Only do this if we weren't storing a loaded value. 00879 Value *StoreVal; 00880 if (StoringOther || SI->getOperand(0) == InitVal) 00881 StoreVal = ConstantBool::get(StoringOther); 00882 else { 00883 // Otherwise, we are storing a previously loaded copy. To do this, 00884 // change the copy from copying the original value to just copying the 00885 // bool. 00886 Instruction *StoredVal = cast<Instruction>(SI->getOperand(0)); 00887 00888 // If we're already replaced the input, StoredVal will be a cast or 00889 // select instruction. If not, it will be a load of the original 00890 // global. 00891 if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) { 00892 assert(LI->getOperand(0) == GV && "Not a copy!"); 00893 // Insert a new load, to preserve the saved value. 00894 StoreVal = new LoadInst(NewGV, LI->getName()+".b", LI); 00895 } else { 00896 assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && 00897 "This is not a form that we understand!"); 00898 StoreVal = StoredVal->getOperand(0); 00899 assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!"); 00900 } 00901 } 00902 new StoreInst(StoreVal, NewGV, SI); 00903 } else if (!UI->use_empty()) { 00904 // Change the load into a load of bool then a select. 00905 LoadInst *LI = cast<LoadInst>(UI); 00906 00907 std::string Name = LI->getName(); LI->setName(""); 00908 LoadInst *NLI = new LoadInst(NewGV, Name+".b", LI); 00909 Value *NSI; 00910 if (IsOneZero) 00911 NSI = new CastInst(NLI, LI->getType(), Name, LI); 00912 else 00913 NSI = new SelectInst(NLI, OtherVal, InitVal, Name, LI); 00914 LI->replaceAllUsesWith(NSI); 00915 } 00916 UI->eraseFromParent(); 00917 } 00918 00919 GV->eraseFromParent(); 00920 } 00921 00922 00923 /// ProcessInternalGlobal - Analyze the specified global variable and optimize 00924 /// it if possible. If we make a change, return true. 00925 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, 00926 Module::global_iterator &GVI) { 00927 std::set<PHINode*> PHIUsers; 00928 GlobalStatus GS; 00929 GV->removeDeadConstantUsers(); 00930 00931 if (GV->use_empty()) { 00932 DEBUG(std::cerr << "GLOBAL DEAD: " << *GV); 00933 GV->eraseFromParent(); 00934 ++NumDeleted; 00935 return true; 00936 } 00937 00938 if (!AnalyzeGlobal(GV, GS, PHIUsers)) { 00939 // If this is a first class global and has only one accessing function 00940 // and this function is main (which we know is not recursive we can make 00941 // this global a local variable) we replace the global with a local alloca 00942 // in this function. 00943 // 00944 // NOTE: It doesn't make sense to promote non first class types since we 00945 // are just replacing static memory to stack memory. 00946 if (!GS.HasMultipleAccessingFunctions && 00947 GS.AccessingFunction && !GS.HasNonInstructionUser && 00948 GV->getType()->getElementType()->isFirstClassType() && 00949 GS.AccessingFunction->getName() == "main" && 00950 GS.AccessingFunction->hasExternalLinkage()) { 00951 DEBUG(std::cerr << "LOCALIZING GLOBAL: " << *GV); 00952 Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin(); 00953 const Type* ElemTy = GV->getType()->getElementType(); 00954 // FIXME: Pass Global's alignment when globals have alignment 00955 AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), FirstI); 00956 if (!isa<UndefValue>(GV->getInitializer())) 00957 new StoreInst(GV->getInitializer(), Alloca, FirstI); 00958 00959 GV->replaceAllUsesWith(Alloca); 00960 GV->eraseFromParent(); 00961 ++NumLocalized; 00962 return true; 00963 } 00964 // If the global is never loaded (but may be stored to), it is dead. 00965 // Delete it now. 00966 if (!GS.isLoaded) { 00967 DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV); 00968 00969 // Delete any stores we can find to the global. We may not be able to 00970 // make it completely dead though. 00971 bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer()); 00972 00973 // If the global is dead now, delete it. 00974 if (GV->use_empty()) { 00975 GV->eraseFromParent(); 00976 ++NumDeleted; 00977 Changed = true; 00978 } 00979 return Changed; 00980 00981 } else if (GS.StoredType <= GlobalStatus::isInitializerStored) { 00982 DEBUG(std::cerr << "MARKING CONSTANT: " << *GV); 00983 GV->setConstant(true); 00984 00985 // Clean up any obviously simplifiable users now. 00986 CleanupConstantGlobalUsers(GV, GV->getInitializer()); 00987 00988 // If the global is dead now, just nuke it. 00989 if (GV->use_empty()) { 00990 DEBUG(std::cerr << " *** Marking constant allowed us to simplify " 00991 "all users and delete global!\n"); 00992 GV->eraseFromParent(); 00993 ++NumDeleted; 00994 } 00995 00996 ++NumMarked; 00997 return true; 00998 } else if (!GS.isNotSuitableForSRA && 00999 !GV->getInitializer()->getType()->isFirstClassType()) { 01000 if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) { 01001 GVI = FirstNewGV; // Don't skip the newly produced globals! 01002 return true; 01003 } 01004 } else if (GS.StoredType == GlobalStatus::isStoredOnce) { 01005 // If the initial value for the global was an undef value, and if only 01006 // one other value was stored into it, we can just change the 01007 // initializer to be an undef value, then delete all stores to the 01008 // global. This allows us to mark it constant. 01009 if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 01010 if (isa<UndefValue>(GV->getInitializer())) { 01011 // Change the initial value here. 01012 GV->setInitializer(SOVConstant); 01013 01014 // Clean up any obviously simplifiable users now. 01015 CleanupConstantGlobalUsers(GV, GV->getInitializer()); 01016 01017 if (GV->use_empty()) { 01018 DEBUG(std::cerr << " *** Substituting initializer allowed us to " 01019 "simplify all users and delete global!\n"); 01020 GV->eraseFromParent(); 01021 ++NumDeleted; 01022 } else { 01023 GVI = GV; 01024 } 01025 ++NumSubstitute; 01026 return true; 01027 } 01028 01029 // Try to optimize globals based on the knowledge that only one value 01030 // (besides its initializer) is ever stored to the global. 01031 if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GVI, 01032 getAnalysis<TargetData>())) 01033 return true; 01034 01035 // Otherwise, if the global was not a boolean, we can shrink it to be a 01036 // boolean. 01037 if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 01038 if (GV->getType()->getElementType() != Type::BoolTy && 01039 !GV->getType()->getElementType()->isFloatingPoint()) { 01040 DEBUG(std::cerr << " *** SHRINKING TO BOOL: " << *GV); 01041 ShrinkGlobalToBoolean(GV, SOVConstant); 01042 ++NumShrunkToBool; 01043 return true; 01044 } 01045 } 01046 } 01047 return false; 01048 } 01049 01050 /// OnlyCalledDirectly - Return true if the specified function is only called 01051 /// directly. In other words, its address is never taken. 01052 static bool OnlyCalledDirectly(Function *F) { 01053 for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 01054 Instruction *User = dyn_cast<Instruction>(*UI); 01055 if (!User) return false; 01056 if (!isa<CallInst>(User) && !isa<InvokeInst>(User)) return false; 01057 01058 // See if the function address is passed as an argument. 01059 for (unsigned i = 1, e = User->getNumOperands(); i != e; ++i) 01060 if (User->getOperand(i) == F) return false; 01061 } 01062 return true; 01063 } 01064 01065 /// ChangeCalleesToFastCall - Walk all of the direct calls of the specified 01066 /// function, changing them to FastCC. 01067 static void ChangeCalleesToFastCall(Function *F) { 01068 for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 01069 Instruction *User = cast<Instruction>(*UI); 01070 if (CallInst *CI = dyn_cast<CallInst>(User)) 01071 CI->setCallingConv(CallingConv::Fast); 01072 else 01073 cast<InvokeInst>(User)->setCallingConv(CallingConv::Fast); 01074 } 01075 } 01076 01077 bool GlobalOpt::OptimizeFunctions(Module &M) { 01078 bool Changed = false; 01079 // Optimize functions. 01080 for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) { 01081 Function *F = FI++; 01082 F->removeDeadConstantUsers(); 01083 if (F->use_empty() && (F->hasInternalLinkage() || 01084 F->hasLinkOnceLinkage())) { 01085 M.getFunctionList().erase(F); 01086 Changed = true; 01087 ++NumFnDeleted; 01088 } else if (F->hasInternalLinkage() && 01089 F->getCallingConv() == CallingConv::C && !F->isVarArg() && 01090 OnlyCalledDirectly(F)) { 01091 // If this function has C calling conventions, is not a varargs 01092 // function, and is only called directly, promote it to use the Fast 01093 // calling convention. 01094 F->setCallingConv(CallingConv::Fast); 01095 ChangeCalleesToFastCall(F); 01096 ++NumFastCallFns; 01097 Changed = true; 01098 } 01099 } 01100 return Changed; 01101 } 01102 01103 bool GlobalOpt::OptimizeGlobalVars(Module &M) { 01104 bool Changed = false; 01105 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 01106 GVI != E; ) { 01107 GlobalVariable *GV = GVI++; 01108 if (!GV->isConstant() && GV->hasInternalLinkage() && 01109 GV->hasInitializer()) 01110 Changed |= ProcessInternalGlobal(GV, GVI); 01111 } 01112 return Changed; 01113 } 01114 01115 /// FindGlobalCtors - Find the llvm.globalctors list, verifying that all 01116 /// initializers have an init priority of 65535. 01117 GlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) { 01118 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 01119 I != E; ++I) 01120 if (I->getName() == "llvm.global_ctors") { 01121 // Found it, verify it's an array of { int, void()* }. 01122 const ArrayType *ATy =dyn_cast<ArrayType>(I->getType()->getElementType()); 01123 if (!ATy) return 0; 01124 const StructType *STy = dyn_cast<StructType>(ATy->getElementType()); 01125 if (!STy || STy->getNumElements() != 2 || 01126 STy->getElementType(0) != Type::IntTy) return 0; 01127 const PointerType *PFTy = dyn_cast<PointerType>(STy->getElementType(1)); 01128 if (!PFTy) return 0; 01129 const FunctionType *FTy = dyn_cast<FunctionType>(PFTy->getElementType()); 01130 if (!FTy || FTy->getReturnType() != Type::VoidTy || FTy->isVarArg() || 01131 FTy->getNumParams() != 0) 01132 return 0; 01133 01134 // Verify that the initializer is simple enough for us to handle. 01135 if (!I->hasInitializer()) return 0; 01136 ConstantArray *CA = dyn_cast<ConstantArray>(I->getInitializer()); 01137 if (!CA) return 0; 01138 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) 01139 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(CA->getOperand(i))) { 01140 if (isa<ConstantPointerNull>(CS->getOperand(1))) 01141 continue; 01142 01143 // Must have a function or null ptr. 01144 if (!isa<Function>(CS->getOperand(1))) 01145 return 0; 01146 01147 // Init priority must be standard. 01148 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 01149 if (!CI || CI->getRawValue() != 65535) 01150 return 0; 01151 } else { 01152 return 0; 01153 } 01154 01155 return I; 01156 } 01157 return 0; 01158 } 01159 01160 /// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand, 01161 /// return a list of the functions and null terminator as a vector. 01162 static std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) { 01163 ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); 01164 std::vector<Function*> Result; 01165 Result.reserve(CA->getNumOperands()); 01166 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) { 01167 ConstantStruct *CS = cast<ConstantStruct>(CA->getOperand(i)); 01168 Result.push_back(dyn_cast<Function>(CS->getOperand(1))); 01169 } 01170 return Result; 01171 } 01172 01173 /// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the 01174 /// specified array, returning the new global to use. 01175 static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, 01176 const std::vector<Function*> &Ctors) { 01177 // If we made a change, reassemble the initializer list. 01178 std::vector<Constant*> CSVals; 01179 CSVals.push_back(ConstantSInt::get(Type::IntTy, 65535)); 01180 CSVals.push_back(0); 01181 01182 // Create the new init list. 01183 std::vector<Constant*> CAList; 01184 for (unsigned i = 0, e = Ctors.size(); i != e; ++i) { 01185 if (Ctors[i]) { 01186 CSVals[1] = Ctors[i]; 01187 } else { 01188 const Type *FTy = FunctionType::get(Type::VoidTy, 01189 std::vector<const Type*>(), false); 01190 const PointerType *PFTy = PointerType::get(FTy); 01191 CSVals[1] = Constant::getNullValue(PFTy); 01192 CSVals[0] = ConstantSInt::get(Type::IntTy, 2147483647); 01193 } 01194 CAList.push_back(ConstantStruct::get(CSVals)); 01195 } 01196 01197 // Create the array initializer. 01198 const Type *StructTy = 01199 cast<ArrayType>(GCL->getType()->getElementType())->getElementType(); 01200 Constant *CA = ConstantArray::get(ArrayType::get(StructTy, CAList.size()), 01201 CAList); 01202 01203 // If we didn't change the number of elements, don't create a new GV. 01204 if (CA->getType() == GCL->getInitializer()->getType()) { 01205 GCL->setInitializer(CA); 01206 return GCL; 01207 } 01208 01209 // Create the new global and insert it next to the existing list. 01210 GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(), 01211 GCL->getLinkage(), CA, 01212 GCL->getName()); 01213 GCL->setName(""); 01214 GCL->getParent()->getGlobalList().insert(GCL, NGV); 01215 01216 // Nuke the old list, replacing any uses with the new one. 01217 if (!GCL->use_empty()) { 01218 Constant *V = NGV; 01219 if (V->getType() != GCL->getType()) 01220 V = ConstantExpr::getCast(V, GCL->getType()); 01221 GCL->replaceAllUsesWith(V); 01222 } 01223 GCL->eraseFromParent(); 01224 01225 if (Ctors.size()) 01226 return NGV; 01227 else 01228 return 0; 01229 } 01230 01231 01232 static Constant *getVal(std::map<Value*, Constant*> &ComputedValues, 01233 Value *V) { 01234 if (Constant *CV = dyn_cast<Constant>(V)) return CV; 01235 Constant *R = ComputedValues[V]; 01236 assert(R && "Reference to an uncomputed value!"); 01237 return R; 01238 } 01239 01240 /// isSimpleEnoughPointerToCommit - Return true if this constant is simple 01241 /// enough for us to understand. In particular, if it is a cast of something, 01242 /// we punt. We basically just support direct accesses to globals and GEP's of 01243 /// globals. This should be kept up to date with CommitValueTo. 01244 static bool isSimpleEnoughPointerToCommit(Constant *C) { 01245 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) { 01246 if (!GV->hasExternalLinkage() && !GV->hasInternalLinkage()) 01247 return false; // do not allow weak/linkonce linkage. 01248 return !GV->isExternal(); // reject external globals. 01249 } 01250 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 01251 // Handle a constantexpr gep. 01252 if (CE->getOpcode() == Instruction::GetElementPtr && 01253 isa<GlobalVariable>(CE->getOperand(0))) { 01254 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 01255 if (!GV->hasExternalLinkage() && !GV->hasInternalLinkage()) 01256 return false; // do not allow weak/linkonce linkage. 01257 return GV->hasInitializer() && 01258 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); 01259 } 01260 return false; 01261 } 01262 01263 /// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global 01264 /// initializer. This returns 'Init' modified to reflect 'Val' stored into it. 01265 /// At this point, the GEP operands of Addr [0, OpNo) have been stepped into. 01266 static Constant *EvaluateStoreInto(Constant *Init, Constant *Val, 01267 ConstantExpr *Addr, unsigned OpNo) { 01268 // Base case of the recursion. 01269 if (OpNo == Addr->getNumOperands()) { 01270 assert(Val->getType() == Init->getType() && "Type mismatch!"); 01271 return Val; 01272 } 01273 01274 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) { 01275 std::vector<Constant*> Elts; 01276 01277 // Break up the constant into its elements. 01278 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) { 01279 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) 01280 Elts.push_back(CS->getOperand(i)); 01281 } else if (isa<ConstantAggregateZero>(Init)) { 01282 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 01283 Elts.push_back(Constant::getNullValue(STy->getElementType(i))); 01284 } else if (isa<UndefValue>(Init)) { 01285 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 01286 Elts.push_back(UndefValue::get(STy->getElementType(i))); 01287 } else { 01288 assert(0 && "This code is out of sync with " 01289 " ConstantFoldLoadThroughGEPConstantExpr"); 01290 } 01291 01292 // Replace the element that we are supposed to. 01293 ConstantUInt *CU = cast<ConstantUInt>(Addr->getOperand(OpNo)); 01294 assert(CU->getValue() < STy->getNumElements() && 01295 "Struct index out of range!"); 01296 unsigned Idx = (unsigned)CU->getValue(); 01297 Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1); 01298 01299 // Return the modified struct. 01300 return ConstantStruct::get(Elts); 01301 } else { 01302 ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo)); 01303 const ArrayType *ATy = cast<ArrayType>(Init->getType()); 01304 01305 // Break up the array into elements. 01306 std::vector<Constant*> Elts; 01307 if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) { 01308 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) 01309 Elts.push_back(CA->getOperand(i)); 01310 } else if (isa<ConstantAggregateZero>(Init)) { 01311 Constant *Elt = Constant::getNullValue(ATy->getElementType()); 01312 Elts.assign(ATy->getNumElements(), Elt); 01313 } else if (isa<UndefValue>(Init)) { 01314 Constant *Elt = UndefValue::get(ATy->getElementType()); 01315 Elts.assign(ATy->getNumElements(), Elt); 01316 } else { 01317 assert(0 && "This code is out of sync with " 01318 " ConstantFoldLoadThroughGEPConstantExpr"); 01319 } 01320 01321 assert((uint64_t)CI->getRawValue() < ATy->getNumElements()); 01322 Elts[(uint64_t)CI->getRawValue()] = 01323 EvaluateStoreInto(Elts[(uint64_t)CI->getRawValue()], Val, Addr, OpNo+1); 01324 return ConstantArray::get(ATy, Elts); 01325 } 01326 } 01327 01328 /// CommitValueTo - We have decided that Addr (which satisfies the predicate 01329 /// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen. 01330 static void CommitValueTo(Constant *Val, Constant *Addr) { 01331 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) { 01332 assert(GV->hasInitializer()); 01333 GV->setInitializer(Val); 01334 return; 01335 } 01336 01337 ConstantExpr *CE = cast<ConstantExpr>(Addr); 01338 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 01339 01340 Constant *Init = GV->getInitializer(); 01341 Init = EvaluateStoreInto(Init, Val, CE, 2); 01342 GV->setInitializer(Init); 01343 } 01344 01345 /// ComputeLoadResult - Return the value that would be computed by a load from 01346 /// P after the stores reflected by 'memory' have been performed. If we can't 01347 /// decide, return null. 01348 static Constant *ComputeLoadResult(Constant *P, 01349 const std::map<Constant*, Constant*> &Memory) { 01350 // If this memory location has been recently stored, use the stored value: it 01351 // is the most up-to-date. 01352 std::map<Constant*, Constant*>::const_iterator I = Memory.find(P); 01353 if (I != Memory.end()) return I->second; 01354 01355 // Access it. 01356 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { 01357 if (GV->hasInitializer()) 01358 return GV->getInitializer(); 01359 return 0; 01360 } 01361 01362 // Handle a constantexpr getelementptr. 01363 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) 01364 if (CE->getOpcode() == Instruction::GetElementPtr && 01365 isa<GlobalVariable>(CE->getOperand(0))) { 01366 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 01367 if (GV->hasInitializer()) 01368 return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); 01369 } 01370 01371 return 0; // don't know how to evaluate. 01372 } 01373 01374 /// EvaluateFunction - Evaluate a call to function F, returning true if 01375 /// successful, false if we can't evaluate it. ActualArgs contains the formal 01376 /// arguments for the function. 01377 static bool EvaluateFunction(Function *F, Constant *&RetVal, 01378 const std::vector<Constant*> &ActualArgs, 01379 std::vector<Function*> &CallStack, 01380 std::map<Constant*, Constant*> &MutatedMemory, 01381 std::vector<GlobalVariable*> &AllocaTmps) { 01382 // Check to see if this function is already executing (recursion). If so, 01383 // bail out. TODO: we might want to accept limited recursion. 01384 if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end()) 01385 return false; 01386 01387 CallStack.push_back(F); 01388 01389 /// Values - As we compute SSA register values, we store their contents here. 01390 std::map<Value*, Constant*> Values; 01391 01392 // Initialize arguments to the incoming values specified. 01393 unsigned ArgNo = 0; 01394 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; 01395 ++AI, ++ArgNo) 01396 Values[AI] = ActualArgs[ArgNo]; 01397 01398 /// ExecutedBlocks - We only handle non-looping, non-recursive code. As such, 01399 /// we can only evaluate any one basic block at most once. This set keeps 01400 /// track of what we have executed so we can detect recursive cases etc. 01401 std::set<BasicBlock*> ExecutedBlocks; 01402 01403 // CurInst - The current instruction we're evaluating. 01404 BasicBlock::iterator CurInst = F->begin()->begin(); 01405 01406 // This is the main evaluation loop. 01407 while (1) { 01408 Constant *InstResult = 0; 01409 01410 if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) { 01411 if (SI->isVolatile()) return false; // no volatile accesses. 01412 Constant *Ptr = getVal(Values, SI->getOperand(1)); 01413 if (!isSimpleEnoughPointerToCommit(Ptr)) 01414 // If this is too complex for us to commit, reject it. 01415 return false; 01416 Constant *Val = getVal(Values, SI->getOperand(0)); 01417 MutatedMemory[Ptr] = Val; 01418 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) { 01419 InstResult = ConstantExpr::get(BO->getOpcode(), 01420 getVal(Values, BO->getOperand(0)), 01421 getVal(Values, BO->getOperand(1))); 01422 } else if (ShiftInst *SI = dyn_cast<ShiftInst>(CurInst)) { 01423 InstResult = ConstantExpr::get(SI->getOpcode(), 01424 getVal(Values, SI->getOperand(0)), 01425 getVal(Values, SI->getOperand(1))); 01426 } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) { 01427 InstResult = ConstantExpr::getCast(getVal(Values, CI->getOperand(0)), 01428 CI->getType()); 01429 } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) { 01430 InstResult = ConstantExpr::getSelect(getVal(Values, SI->getOperand(0)), 01431 getVal(Values, SI->getOperand(1)), 01432 getVal(Values, SI->getOperand(2))); 01433 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) { 01434 Constant *P = getVal(Values, GEP->getOperand(0)); 01435 std::vector<Constant*> GEPOps; 01436 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) 01437 GEPOps.push_back(getVal(Values, GEP->getOperand(i))); 01438 InstResult = ConstantExpr::getGetElementPtr(P, GEPOps); 01439 } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) { 01440 if (LI->isVolatile()) return false; // no volatile accesses. 01441 InstResult = ComputeLoadResult(getVal(Values, LI->getOperand(0)), 01442 MutatedMemory); 01443 if (InstResult == 0) return false; // Could not evaluate load. 01444 } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) { 01445 if (AI->isArrayAllocation()) return false; // Cannot handle array allocs. 01446 const Type *Ty = AI->getType()->getElementType(); 01447 AllocaTmps.push_back(new GlobalVariable(Ty, false, 01448 GlobalValue::InternalLinkage, 01449 UndefValue::get(Ty), 01450 AI->getName())); 01451 InstResult = AllocaTmps.back(); 01452 } else if (CallInst *CI = dyn_cast<CallInst>(CurInst)) { 01453 // Resolve function pointers. 01454 Function *Callee = dyn_cast<Function>(getVal(Values, CI->getOperand(0))); 01455 if (!Callee) return false; // Cannot resolve. 01456 01457 std::vector<Constant*> Formals; 01458 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) 01459 Formals.push_back(getVal(Values, CI->getOperand(i))); 01460 01461 if (Callee->isExternal()) { 01462 // If this is a function we can constant fold, do it. 01463 if (Constant *C = ConstantFoldCall(Callee, Formals)) { 01464 InstResult = C; 01465 } else { 01466 return false; 01467 } 01468 } else { 01469 if (Callee->getFunctionType()->isVarArg()) 01470 return false; 01471 01472 Constant *RetVal; 01473 01474 // Execute the call, if successful, use the return value. 01475 if (!EvaluateFunction(Callee, RetVal, Formals, CallStack, 01476 MutatedMemory, AllocaTmps)) 01477 return false; 01478 InstResult = RetVal; 01479 } 01480 } else if (TerminatorInst *TI = dyn_cast<TerminatorInst>(CurInst)) { 01481 BasicBlock *NewBB = 0; 01482 if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) { 01483 if (BI->isUnconditional()) { 01484 NewBB = BI->getSuccessor(0); 01485 } else { 01486 ConstantBool *Cond = 01487 dyn_cast<ConstantBool>(getVal(Values, BI->getCondition())); 01488 if (!Cond) return false; // Cannot determine. 01489 NewBB = BI->getSuccessor(!Cond->getValue()); 01490 } 01491 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) { 01492 ConstantInt *Val = 01493 dyn_cast<ConstantInt>(getVal(Values, SI->getCondition())); 01494 if (!Val) return false; // Cannot determine. 01495 NewBB = SI->getSuccessor(SI->findCaseValue(Val)); 01496 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(CurInst)) { 01497 if (RI->getNumOperands()) 01498 RetVal = getVal(Values, RI->getOperand(0)); 01499 01500 CallStack.pop_back(); // return from fn. 01501 return true; // We succeeded at evaluating this ctor! 01502 } else { 01503 // invoke, unwind, unreachable. 01504 return false; // Cannot handle this terminator. 01505 } 01506 01507 // Okay, we succeeded in evaluating this control flow. See if we have 01508 // executed the new block before. If so, we have a looping function, 01509 // which we cannot evaluate in reasonable time. 01510 if (!ExecutedBlocks.insert(NewBB).second) 01511 return false; // looped! 01512 01513 // Okay, we have never been in this block before. Check to see if there 01514 // are any PHI nodes. If so, evaluate them with information about where 01515 // we came from. 01516 BasicBlock *OldBB = CurInst->getParent(); 01517 CurInst = NewBB->begin(); 01518 PHINode *PN; 01519 for (; (PN = dyn_cast<PHINode>(CurInst)); ++CurInst) 01520 Values[PN] = getVal(Values, PN->getIncomingValueForBlock(OldBB)); 01521 01522 // Do NOT increment CurInst. We know that the terminator had no value. 01523 continue; 01524 } else { 01525 // Did not know how to evaluate this! 01526 return false; 01527 } 01528 01529 if (!CurInst->use_empty()) 01530 Values[CurInst] = InstResult; 01531 01532 // Advance program counter. 01533 ++CurInst; 01534 } 01535 } 01536 01537 /// EvaluateStaticConstructor - Evaluate static constructors in the function, if 01538 /// we can. Return true if we can, false otherwise. 01539 static bool EvaluateStaticConstructor(Function *F) { 01540 /// MutatedMemory - For each store we execute, we update this map. Loads 01541 /// check this to get the most up-to-date value. If evaluation is successful, 01542 /// this state is committed to the process. 01543 std::map<Constant*, Constant*> MutatedMemory; 01544 01545 /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable 01546 /// to represent its body. This vector is needed so we can delete the 01547 /// temporary globals when we are done. 01548 std::vector<GlobalVariable*> AllocaTmps; 01549 01550 /// CallStack - This is used to detect recursion. In pathological situations 01551 /// we could hit exponential behavior, but at least there is nothing 01552 /// unbounded. 01553 std::vector<Function*> CallStack; 01554 01555 // Call the function. 01556 Constant *RetValDummy; 01557 bool EvalSuccess = EvaluateFunction(F, RetValDummy, std::vector<Constant*>(), 01558 CallStack, MutatedMemory, AllocaTmps); 01559 if (EvalSuccess) { 01560 // We succeeded at evaluation: commit the result. 01561 DEBUG(std::cerr << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" << 01562 F->getName() << "' to " << MutatedMemory.size() << " stores.\n"); 01563 for (std::map<Constant*, Constant*>::iterator I = MutatedMemory.begin(), 01564 E = MutatedMemory.end(); I != E; ++I) 01565 CommitValueTo(I->second, I->first); 01566 } 01567 01568 // At this point, we are done interpreting. If we created any 'alloca' 01569 // temporaries, release them now. 01570 while (!AllocaTmps.empty()) { 01571 GlobalVariable *Tmp = AllocaTmps.back(); 01572 AllocaTmps.pop_back(); 01573 01574 // If there are still users of the alloca, the program is doing something 01575 // silly, e.g. storing the address of the alloca somewhere and using it 01576 // later. Since this is undefined, we'll just make it be null. 01577 if (!Tmp->use_empty()) 01578 Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); 01579 delete Tmp; 01580 } 01581 01582 return EvalSuccess; 01583 } 01584 01585 01586 01587 01588 /// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible. 01589 /// Return true if anything changed. 01590 bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) { 01591 std::vector<Function*> Ctors = ParseGlobalCtors(GCL); 01592 bool MadeChange = false; 01593 if (Ctors.empty()) return false; 01594 01595 // Loop over global ctors, optimizing them when we can. 01596 for (unsigned i = 0; i != Ctors.size(); ++i) { 01597 Function *F = Ctors[i]; 01598 // Found a null terminator in the middle of the list, prune off the rest of 01599 // the list. 01600 if (F == 0) { 01601 if (i != Ctors.size()-1) { 01602 Ctors.resize(i+1); 01603 MadeChange = true; 01604 } 01605 break; 01606 } 01607 01608 // We cannot simplify external ctor functions. 01609 if (F->empty()) continue; 01610 01611 // If we can evaluate the ctor at compile time, do. 01612 if (EvaluateStaticConstructor(F)) { 01613 Ctors.erase(Ctors.begin()+i); 01614 MadeChange = true; 01615 --i; 01616 ++NumCtorsEvaluated; 01617 continue; 01618 } 01619 } 01620 01621 if (!MadeChange) return false; 01622 01623 GCL = InstallGlobalCtors(GCL, Ctors); 01624 return true; 01625 } 01626 01627 01628 bool GlobalOpt::runOnModule(Module &M) { 01629 bool Changed = false; 01630 01631 // Try to find the llvm.globalctors list. 01632 GlobalVariable *GlobalCtors = FindGlobalCtors(M); 01633 01634 bool LocalChange = true; 01635 while (LocalChange) { 01636 LocalChange = false; 01637 01638 // Delete functions that are trivially dead, ccc -> fastcc 01639 LocalChange |= OptimizeFunctions(M); 01640 01641 // Optimize global_ctors list. 01642 if (GlobalCtors) 01643 LocalChange |= OptimizeGlobalCtorsList(GlobalCtors); 01644 01645 // Optimize non-address-taken globals. 01646 LocalChange |= OptimizeGlobalVars(M); 01647 Changed |= LocalChange; 01648 } 01649 01650 // TODO: Move all global ctors functions to the end of the module for code 01651 // layout. 01652 01653 return Changed; 01654 }