LLVM API Documentation
00001 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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/LLVMContext.h" 00024 #include "llvm/Module.h" 00025 #include "llvm/Pass.h" 00026 #include "llvm/Analysis/ConstantFolding.h" 00027 #include "llvm/Target/TargetData.h" 00028 #include "llvm/Support/CallSite.h" 00029 #include "llvm/Support/Compiler.h" 00030 #include "llvm/Support/Debug.h" 00031 #include "llvm/Support/ErrorHandling.h" 00032 #include "llvm/Support/GetElementPtrTypeIterator.h" 00033 #include "llvm/Support/MathExtras.h" 00034 #include "llvm/Support/raw_ostream.h" 00035 #include "llvm/ADT/DenseMap.h" 00036 #include "llvm/ADT/SmallPtrSet.h" 00037 #include "llvm/ADT/SmallVector.h" 00038 #include "llvm/ADT/Statistic.h" 00039 #include "llvm/ADT/STLExtras.h" 00040 #include <algorithm> 00041 using namespace llvm; 00042 00043 STATISTIC(NumMarked , "Number of globals marked constant"); 00044 STATISTIC(NumSRA , "Number of aggregate globals broken into scalars"); 00045 STATISTIC(NumHeapSRA , "Number of heap objects SRA'd"); 00046 STATISTIC(NumSubstitute,"Number of globals with initializers stored into them"); 00047 STATISTIC(NumDeleted , "Number of globals deleted"); 00048 STATISTIC(NumFnDeleted , "Number of functions deleted"); 00049 STATISTIC(NumGlobUses , "Number of global uses devirtualized"); 00050 STATISTIC(NumLocalized , "Number of globals localized"); 00051 STATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans"); 00052 STATISTIC(NumFastCallFns , "Number of functions converted to fastcc"); 00053 STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated"); 00054 STATISTIC(NumNestRemoved , "Number of nest attributes removed"); 00055 STATISTIC(NumAliasesResolved, "Number of global aliases resolved"); 00056 STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated"); 00057 00058 namespace { 00059 struct VISIBILITY_HIDDEN GlobalOpt : public ModulePass { 00060 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00061 } 00062 static char ID; // Pass identification, replacement for typeid 00063 GlobalOpt() : ModulePass(&ID) {} 00064 00065 bool runOnModule(Module &M); 00066 00067 private: 00068 GlobalVariable *FindGlobalCtors(Module &M); 00069 bool OptimizeFunctions(Module &M); 00070 bool OptimizeGlobalVars(Module &M); 00071 bool OptimizeGlobalAliases(Module &M); 00072 bool OptimizeGlobalCtorsList(GlobalVariable *&GCL); 00073 bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI); 00074 }; 00075 } 00076 00077 char GlobalOpt::ID = 0; 00078 static RegisterPass<GlobalOpt> X("globalopt", "Global Variable Optimizer"); 00079 00080 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); } 00081 00082 namespace { 00083 00084 /// GlobalStatus - As we analyze each global, keep track of some information 00085 /// about it. If we find out that the address of the global is taken, none of 00086 /// this info will be accurate. 00087 struct VISIBILITY_HIDDEN GlobalStatus { 00088 /// isLoaded - True if the global is ever loaded. If the global isn't ever 00089 /// loaded it can be deleted. 00090 bool isLoaded; 00091 00092 /// StoredType - Keep track of what stores to the global look like. 00093 /// 00094 enum StoredType { 00095 /// NotStored - There is no store to this global. It can thus be marked 00096 /// constant. 00097 NotStored, 00098 00099 /// isInitializerStored - This global is stored to, but the only thing 00100 /// stored is the constant it was initialized with. This is only tracked 00101 /// for scalar globals. 00102 isInitializerStored, 00103 00104 /// isStoredOnce - This global is stored to, but only its initializer and 00105 /// one other value is ever stored to it. If this global isStoredOnce, we 00106 /// track the value stored to it in StoredOnceValue below. This is only 00107 /// tracked for scalar globals. 00108 isStoredOnce, 00109 00110 /// isStored - This global is stored to by multiple values or something else 00111 /// that we cannot track. 00112 isStored 00113 } StoredType; 00114 00115 /// StoredOnceValue - If only one value (besides the initializer constant) is 00116 /// ever stored to this global, keep track of what value it is. 00117 Value *StoredOnceValue; 00118 00119 /// AccessingFunction/HasMultipleAccessingFunctions - These start out 00120 /// null/false. When the first accessing function is noticed, it is recorded. 00121 /// When a second different accessing function is noticed, 00122 /// HasMultipleAccessingFunctions is set to true. 00123 Function *AccessingFunction; 00124 bool HasMultipleAccessingFunctions; 00125 00126 /// HasNonInstructionUser - Set to true if this global has a user that is not 00127 /// an instruction (e.g. a constant expr or GV initializer). 00128 bool HasNonInstructionUser; 00129 00130 /// HasPHIUser - Set to true if this global has a user that is a PHI node. 00131 bool HasPHIUser; 00132 00133 GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0), 00134 AccessingFunction(0), HasMultipleAccessingFunctions(false), 00135 HasNonInstructionUser(false), HasPHIUser(false) {} 00136 }; 00137 00138 } 00139 00140 // SafeToDestroyConstant - It is safe to destroy a constant iff it is only used 00141 // by constants itself. Note that constants cannot be cyclic, so this test is 00142 // pretty easy to implement recursively. 00143 // 00144 static bool SafeToDestroyConstant(Constant *C) { 00145 if (isa<GlobalValue>(C)) return false; 00146 00147 for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI) 00148 if (Constant *CU = dyn_cast<Constant>(*UI)) { 00149 if (!SafeToDestroyConstant(CU)) return false; 00150 } else 00151 return false; 00152 return true; 00153 } 00154 00155 00156 /// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus 00157 /// structure. If the global has its address taken, return true to indicate we 00158 /// can't do anything with it. 00159 /// 00160 static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, 00161 SmallPtrSet<PHINode*, 16> &PHIUsers) { 00162 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 00163 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) { 00164 GS.HasNonInstructionUser = true; 00165 00166 if (AnalyzeGlobal(CE, GS, PHIUsers)) return true; 00167 00168 } else if (Instruction *I = dyn_cast<Instruction>(*UI)) { 00169 if (!GS.HasMultipleAccessingFunctions) { 00170 Function *F = I->getParent()->getParent(); 00171 if (GS.AccessingFunction == 0) 00172 GS.AccessingFunction = F; 00173 else if (GS.AccessingFunction != F) 00174 GS.HasMultipleAccessingFunctions = true; 00175 } 00176 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00177 GS.isLoaded = true; 00178 if (LI->isVolatile()) return true; // Don't hack on volatile loads. 00179 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00180 // Don't allow a store OF the address, only stores TO the address. 00181 if (SI->getOperand(0) == V) return true; 00182 00183 if (SI->isVolatile()) return true; // Don't hack on volatile stores. 00184 00185 // If this is a direct store to the global (i.e., the global is a scalar 00186 // value, not an aggregate), keep more specific information about 00187 // stores. 00188 if (GS.StoredType != GlobalStatus::isStored) { 00189 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){ 00190 Value *StoredVal = SI->getOperand(0); 00191 if (StoredVal == GV->getInitializer()) { 00192 if (GS.StoredType < GlobalStatus::isInitializerStored) 00193 GS.StoredType = GlobalStatus::isInitializerStored; 00194 } else if (isa<LoadInst>(StoredVal) && 00195 cast<LoadInst>(StoredVal)->getOperand(0) == GV) { 00196 // G = G 00197 if (GS.StoredType < GlobalStatus::isInitializerStored) 00198 GS.StoredType = GlobalStatus::isInitializerStored; 00199 } else if (GS.StoredType < GlobalStatus::isStoredOnce) { 00200 GS.StoredType = GlobalStatus::isStoredOnce; 00201 GS.StoredOnceValue = StoredVal; 00202 } else if (GS.StoredType == GlobalStatus::isStoredOnce && 00203 GS.StoredOnceValue == StoredVal) { 00204 // noop. 00205 } else { 00206 GS.StoredType = GlobalStatus::isStored; 00207 } 00208 } else { 00209 GS.StoredType = GlobalStatus::isStored; 00210 } 00211 } 00212 } else if (isa<GetElementPtrInst>(I)) { 00213 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00214 } else if (isa<SelectInst>(I)) { 00215 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00216 } else if (PHINode *PN = dyn_cast<PHINode>(I)) { 00217 // PHI nodes we can check just like select or GEP instructions, but we 00218 // have to be careful about infinite recursion. 00219 if (PHIUsers.insert(PN)) // Not already visited. 00220 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 00221 GS.HasPHIUser = true; 00222 } else if (isa<CmpInst>(I)) { 00223 } else if (isa<MemTransferInst>(I)) { 00224 if (I->getOperand(1) == V) 00225 GS.StoredType = GlobalStatus::isStored; 00226 if (I->getOperand(2) == V) 00227 GS.isLoaded = true; 00228 } else if (isa<MemSetInst>(I)) { 00229 assert(I->getOperand(1) == V && "Memset only takes one pointer!"); 00230 GS.StoredType = GlobalStatus::isStored; 00231 } else { 00232 return true; // Any other non-load instruction might take address! 00233 } 00234 } else if (Constant *C = dyn_cast<Constant>(*UI)) { 00235 GS.HasNonInstructionUser = true; 00236 // We might have a dead and dangling constant hanging off of here. 00237 if (!SafeToDestroyConstant(C)) 00238 return true; 00239 } else { 00240 GS.HasNonInstructionUser = true; 00241 // Otherwise must be some other user. 00242 return true; 00243 } 00244 00245 return false; 00246 } 00247 00248 static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx, 00249 LLVMContext &Context) { 00250 ConstantInt *CI = dyn_cast<ConstantInt>(Idx); 00251 if (!CI) return 0; 00252 unsigned IdxV = CI->getZExtValue(); 00253 00254 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) { 00255 if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV); 00256 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) { 00257 if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV); 00258 } else if (ConstantVector *CP = dyn_cast<ConstantVector>(Agg)) { 00259 if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV); 00260 } else if (isa<ConstantAggregateZero>(Agg)) { 00261 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) { 00262 if (IdxV < STy->getNumElements()) 00263 return Constant::getNullValue(STy->getElementType(IdxV)); 00264 } else if (const SequentialType *STy = 00265 dyn_cast<SequentialType>(Agg->getType())) { 00266 return Constant::getNullValue(STy->getElementType()); 00267 } 00268 } else if (isa<UndefValue>(Agg)) { 00269 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) { 00270 if (IdxV < STy->getNumElements()) 00271 return UndefValue::get(STy->getElementType(IdxV)); 00272 } else if (const SequentialType *STy = 00273 dyn_cast<SequentialType>(Agg->getType())) { 00274 return UndefValue::get(STy->getElementType()); 00275 } 00276 } 00277 return 0; 00278 } 00279 00280 00281 /// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all 00282 /// users of the global, cleaning up the obvious ones. This is largely just a 00283 /// quick scan over the use list to clean up the easy and obvious cruft. This 00284 /// returns true if it made a change. 00285 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init, 00286 LLVMContext &Context) { 00287 bool Changed = false; 00288 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) { 00289 User *U = *UI++; 00290 00291 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 00292 if (Init) { 00293 // Replace the load with the initializer. 00294 LI->replaceAllUsesWith(Init); 00295 LI->eraseFromParent(); 00296 Changed = true; 00297 } 00298 } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 00299 // Store must be unreachable or storing Init into the global. 00300 SI->eraseFromParent(); 00301 Changed = true; 00302 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 00303 if (CE->getOpcode() == Instruction::GetElementPtr) { 00304 Constant *SubInit = 0; 00305 if (Init) 00306 SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE, Context); 00307 Changed |= CleanupConstantGlobalUsers(CE, SubInit, Context); 00308 } else if (CE->getOpcode() == Instruction::BitCast && 00309 isa<PointerType>(CE->getType())) { 00310 // Pointer cast, delete any stores and memsets to the global. 00311 Changed |= CleanupConstantGlobalUsers(CE, 0, Context); 00312 } 00313 00314 if (CE->use_empty()) { 00315 CE->destroyConstant(); 00316 Changed = true; 00317 } 00318 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 00319 // Do not transform "gepinst (gep constexpr (GV))" here, because forming 00320 // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold 00321 // and will invalidate our notion of what Init is. 00322 Constant *SubInit = 0; 00323 if (!isa<ConstantExpr>(GEP->getOperand(0))) { 00324 ConstantExpr *CE = 00325 dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP, Context)); 00326 if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr) 00327 SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE, Context); 00328 } 00329 Changed |= CleanupConstantGlobalUsers(GEP, SubInit, Context); 00330 00331 if (GEP->use_empty()) { 00332 GEP->eraseFromParent(); 00333 Changed = true; 00334 } 00335 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv 00336 if (MI->getRawDest() == V) { 00337 MI->eraseFromParent(); 00338 Changed = true; 00339 } 00340 00341 } else if (Constant *C = dyn_cast<Constant>(U)) { 00342 // If we have a chain of dead constantexprs or other things dangling from 00343 // us, and if they are all dead, nuke them without remorse. 00344 if (SafeToDestroyConstant(C)) { 00345 C->destroyConstant(); 00346 // This could have invalidated UI, start over from scratch. 00347 CleanupConstantGlobalUsers(V, Init, Context); 00348 return true; 00349 } 00350 } 00351 } 00352 return Changed; 00353 } 00354 00355 /// isSafeSROAElementUse - Return true if the specified instruction is a safe 00356 /// user of a derived expression from a global that we want to SROA. 00357 static bool isSafeSROAElementUse(Value *V) { 00358 // We might have a dead and dangling constant hanging off of here. 00359 if (Constant *C = dyn_cast<Constant>(V)) 00360 return SafeToDestroyConstant(C); 00361 00362 Instruction *I = dyn_cast<Instruction>(V); 00363 if (!I) return false; 00364 00365 // Loads are ok. 00366 if (isa<LoadInst>(I)) return true; 00367 00368 // Stores *to* the pointer are ok. 00369 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 00370 return SI->getOperand(0) != V; 00371 00372 // Otherwise, it must be a GEP. 00373 GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I); 00374 if (GEPI == 0) return false; 00375 00376 if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) || 00377 !cast<Constant>(GEPI->getOperand(1))->isNullValue()) 00378 return false; 00379 00380 for (Value::use_iterator I = GEPI->use_begin(), E = GEPI->use_end(); 00381 I != E; ++I) 00382 if (!isSafeSROAElementUse(*I)) 00383 return false; 00384 return true; 00385 } 00386 00387 00388 /// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value. 00389 /// Look at it and its uses and decide whether it is safe to SROA this global. 00390 /// 00391 static bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) { 00392 // The user of the global must be a GEP Inst or a ConstantExpr GEP. 00393 if (!isa<GetElementPtrInst>(U) && 00394 (!isa<ConstantExpr>(U) || 00395 cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr)) 00396 return false; 00397 00398 // Check to see if this ConstantExpr GEP is SRA'able. In particular, we 00399 // don't like < 3 operand CE's, and we don't like non-constant integer 00400 // indices. This enforces that all uses are 'gep GV, 0, C, ...' for some 00401 // value of C. 00402 if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) || 00403 !cast<Constant>(U->getOperand(1))->isNullValue() || 00404 !isa<ConstantInt>(U->getOperand(2))) 00405 return false; 00406 00407 gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U); 00408 ++GEPI; // Skip over the pointer index. 00409 00410 // If this is a use of an array allocation, do a bit more checking for sanity. 00411 if (const ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) { 00412 uint64_t NumElements = AT->getNumElements(); 00413 ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2)); 00414 00415 // Check to make sure that index falls within the array. If not, 00416 // something funny is going on, so we won't do the optimization. 00417 // 00418 if (Idx->getZExtValue() >= NumElements) 00419 return false; 00420 00421 // We cannot scalar repl this level of the array unless any array 00422 // sub-indices are in-range constants. In particular, consider: 00423 // A[0][i]. We cannot know that the user isn't doing invalid things like 00424 // allowing i to index an out-of-range subscript that accesses A[1]. 00425 // 00426 // Scalar replacing *just* the outer index of the array is probably not 00427 // going to be a win anyway, so just give up. 00428 for (++GEPI; // Skip array index. 00429 GEPI != E; 00430 ++GEPI) { 00431 uint64_t NumElements; 00432 if (const ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI)) 00433 NumElements = SubArrayTy->getNumElements(); 00434 else if (const VectorType *SubVectorTy = dyn_cast<VectorType>(*GEPI)) 00435 NumElements = SubVectorTy->getNumElements(); 00436 else { 00437 assert(isa<StructType>(*GEPI) && 00438 "Indexed GEP type is not array, vector, or struct!"); 00439 continue; 00440 } 00441 00442 ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand()); 00443 if (!IdxVal || IdxVal->getZExtValue() >= NumElements) 00444 return false; 00445 } 00446 } 00447 00448 for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I) 00449 if (!isSafeSROAElementUse(*I)) 00450 return false; 00451 return true; 00452 } 00453 00454 /// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it 00455 /// is safe for us to perform this transformation. 00456 /// 00457 static bool GlobalUsersSafeToSRA(GlobalValue *GV) { 00458 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 00459 UI != E; ++UI) { 00460 if (!IsUserOfGlobalSafeForSRA(*UI, GV)) 00461 return false; 00462 } 00463 return true; 00464 } 00465 00466 00467 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global 00468 /// variable. This opens the door for other optimizations by exposing the 00469 /// behavior of the program in a more fine-grained way. We have determined that 00470 /// this transformation is safe already. We return the first global variable we 00471 /// insert so that the caller can reprocess it. 00472 static GlobalVariable *SRAGlobal(GlobalVariable *GV, const TargetData &TD, 00473 LLVMContext &Context) { 00474 // Make sure this global only has simple uses that we can SRA. 00475 if (!GlobalUsersSafeToSRA(GV)) 00476 return 0; 00477 00478 assert(GV->hasLocalLinkage() && !GV->isConstant()); 00479 Constant *Init = GV->getInitializer(); 00480 const Type *Ty = Init->getType(); 00481 00482 std::vector<GlobalVariable*> NewGlobals; 00483 Module::GlobalListType &Globals = GV->getParent()->getGlobalList(); 00484 00485 // Get the alignment of the global, either explicit or target-specific. 00486 unsigned StartAlignment = GV->getAlignment(); 00487 if (StartAlignment == 0) 00488 StartAlignment = TD.getABITypeAlignment(GV->getType()); 00489 00490 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 00491 NewGlobals.reserve(STy->getNumElements()); 00492 const StructLayout &Layout = *TD.getStructLayout(STy); 00493 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 00494 Constant *In = getAggregateConstantElement(Init, 00495 ConstantInt::get(Type::getInt32Ty(Context), i), 00496 Context); 00497 assert(In && "Couldn't get element of initializer?"); 00498 GlobalVariable *NGV = new GlobalVariable(Context, 00499 STy->getElementType(i), false, 00500 GlobalVariable::InternalLinkage, 00501 In, GV->getName()+"."+Twine(i), 00502 GV->isThreadLocal(), 00503 GV->getType()->getAddressSpace()); 00504 Globals.insert(GV, NGV); 00505 NewGlobals.push_back(NGV); 00506 00507 // Calculate the known alignment of the field. If the original aggregate 00508 // had 256 byte alignment for example, something might depend on that: 00509 // propagate info to each field. 00510 uint64_t FieldOffset = Layout.getElementOffset(i); 00511 unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset); 00512 if (NewAlign > TD.getABITypeAlignment(STy->getElementType(i))) 00513 NGV->setAlignment(NewAlign); 00514 } 00515 } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) { 00516 unsigned NumElements = 0; 00517 if (const ArrayType *ATy = dyn_cast<ArrayType>(STy)) 00518 NumElements = ATy->getNumElements(); 00519 else 00520 NumElements = cast<VectorType>(STy)->getNumElements(); 00521 00522 if (NumElements > 16 && GV->hasNUsesOrMore(16)) 00523 return 0; // It's not worth it. 00524 NewGlobals.reserve(NumElements); 00525 00526 uint64_t EltSize = TD.getTypeAllocSize(STy->getElementType()); 00527 unsigned EltAlign = TD.getABITypeAlignment(STy->getElementType()); 00528 for (unsigned i = 0, e = NumElements; i != e; ++i) { 00529 Constant *In = getAggregateConstantElement(Init, 00530 ConstantInt::get(Type::getInt32Ty(Context), i), 00531 Context); 00532 assert(In && "Couldn't get element of initializer?"); 00533 00534 GlobalVariable *NGV = new GlobalVariable(Context, 00535 STy->getElementType(), false, 00536 GlobalVariable::InternalLinkage, 00537 In, GV->getName()+"."+Twine(i), 00538 GV->isThreadLocal(), 00539 GV->getType()->getAddressSpace()); 00540 Globals.insert(GV, NGV); 00541 NewGlobals.push_back(NGV); 00542 00543 // Calculate the known alignment of the field. If the original aggregate 00544 // had 256 byte alignment for example, something might depend on that: 00545 // propagate info to each field. 00546 unsigned NewAlign = (unsigned)MinAlign(StartAlignment, EltSize*i); 00547 if (NewAlign > EltAlign) 00548 NGV->setAlignment(NewAlign); 00549 } 00550 } 00551 00552 if (NewGlobals.empty()) 00553 return 0; 00554 00555 DOUT << "PERFORMING GLOBAL SRA ON: " << *GV; 00556 00557 Constant *NullInt = Constant::getNullValue(Type::getInt32Ty(Context)); 00558 00559 // Loop over all of the uses of the global, replacing the constantexpr geps, 00560 // with smaller constantexpr geps or direct references. 00561 while (!GV->use_empty()) { 00562 User *GEP = GV->use_back(); 00563 assert(((isa<ConstantExpr>(GEP) && 00564 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| 00565 isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!"); 00566 00567 // Ignore the 1th operand, which has to be zero or else the program is quite 00568 // broken (undefined). Get the 2nd operand, which is the structure or array 00569 // index. 00570 unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue(); 00571 if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access. 00572 00573 Value *NewPtr = NewGlobals[Val]; 00574 00575 // Form a shorter GEP if needed. 00576 if (GEP->getNumOperands() > 3) { 00577 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) { 00578 SmallVector<Constant*, 8> Idxs; 00579 Idxs.push_back(NullInt); 00580 for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i) 00581 Idxs.push_back(CE->getOperand(i)); 00582 NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), 00583 &Idxs[0], Idxs.size()); 00584 } else { 00585 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP); 00586 SmallVector<Value*, 8> Idxs; 00587 Idxs.push_back(NullInt); 00588 for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i) 00589 Idxs.push_back(GEPI->getOperand(i)); 00590 NewPtr = GetElementPtrInst::Create(NewPtr, Idxs.begin(), Idxs.end(), 00591 GEPI->getName()+"."+Twine(Val),GEPI); 00592 } 00593 } 00594 GEP->replaceAllUsesWith(NewPtr); 00595 00596 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP)) 00597 GEPI->eraseFromParent(); 00598 else 00599 cast<ConstantExpr>(GEP)->destroyConstant(); 00600 } 00601 00602 // Delete the old global, now that it is dead. 00603 Globals.erase(GV); 00604 ++NumSRA; 00605 00606 // Loop over the new globals array deleting any globals that are obviously 00607 // dead. This can arise due to scalarization of a structure or an array that 00608 // has elements that are dead. 00609 unsigned FirstGlobal = 0; 00610 for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i) 00611 if (NewGlobals[i]->use_empty()) { 00612 Globals.erase(NewGlobals[i]); 00613 if (FirstGlobal == i) ++FirstGlobal; 00614 } 00615 00616 return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0; 00617 } 00618 00619 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified 00620 /// value will trap if the value is dynamically null. PHIs keeps track of any 00621 /// phi nodes we've seen to avoid reprocessing them. 00622 static bool AllUsesOfValueWillTrapIfNull(Value *V, 00623 SmallPtrSet<PHINode*, 8> &PHIs) { 00624 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 00625 if (isa<LoadInst>(*UI)) { 00626 // Will trap. 00627 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 00628 if (SI->getOperand(0) == V) { 00629 //cerr << "NONTRAPPING USE: " << **UI; 00630 return false; // Storing the value. 00631 } 00632 } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) { 00633 if (CI->getOperand(0) != V) { 00634 //cerr << "NONTRAPPING USE: " << **UI; 00635 return false; // Not calling the ptr 00636 } 00637 } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) { 00638 if (II->getOperand(0) != V) { 00639 //cerr << "NONTRAPPING USE: " << **UI; 00640 return false; // Not calling the ptr 00641 } 00642 } else if (BitCastInst *CI = dyn_cast<BitCastInst>(*UI)) { 00643 if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false; 00644 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) { 00645 if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false; 00646 } else if (PHINode *PN = dyn_cast<PHINode>(*UI)) { 00647 // If we've already seen this phi node, ignore it, it has already been 00648 // checked. 00649 if (PHIs.insert(PN)) 00650 return AllUsesOfValueWillTrapIfNull(PN, PHIs); 00651 } else if (isa<ICmpInst>(*UI) && 00652 isa<ConstantPointerNull>(UI->getOperand(1))) { 00653 // Ignore setcc X, null 00654 } else { 00655 //cerr << "NONTRAPPING USE: " << **UI; 00656 return false; 00657 } 00658 return true; 00659 } 00660 00661 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads 00662 /// from GV will trap if the loaded value is null. Note that this also permits 00663 /// comparisons of the loaded value against null, as a special case. 00664 static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) { 00665 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI!=E; ++UI) 00666 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 00667 SmallPtrSet<PHINode*, 8> PHIs; 00668 if (!AllUsesOfValueWillTrapIfNull(LI, PHIs)) 00669 return false; 00670 } else if (isa<StoreInst>(*UI)) { 00671 // Ignore stores to the global. 00672 } else { 00673 // We don't know or understand this user, bail out. 00674 //cerr << "UNKNOWN USER OF GLOBAL!: " << **UI; 00675 return false; 00676 } 00677 00678 return true; 00679 } 00680 00681 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV, 00682 LLVMContext &Context) { 00683 bool Changed = false; 00684 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) { 00685 Instruction *I = cast<Instruction>(*UI++); 00686 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00687 LI->setOperand(0, NewV); 00688 Changed = true; 00689 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00690 if (SI->getOperand(1) == V) { 00691 SI->setOperand(1, NewV); 00692 Changed = true; 00693 } 00694 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 00695 if (I->getOperand(0) == V) { 00696 // Calling through the pointer! Turn into a direct call, but be careful 00697 // that the pointer is not also being passed as an argument. 00698 I->setOperand(0, NewV); 00699 Changed = true; 00700 bool PassedAsArg = false; 00701 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i) 00702 if (I->getOperand(i) == V) { 00703 PassedAsArg = true; 00704 I->setOperand(i, NewV); 00705 } 00706 00707 if (PassedAsArg) { 00708 // Being passed as an argument also. Be careful to not invalidate UI! 00709 UI = V->use_begin(); 00710 } 00711 } 00712 } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 00713 Changed |= OptimizeAwayTrappingUsesOfValue(CI, 00714 ConstantExpr::getCast(CI->getOpcode(), 00715 NewV, CI->getType()), Context); 00716 if (CI->use_empty()) { 00717 Changed = true; 00718 CI->eraseFromParent(); 00719 } 00720 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 00721 // Should handle GEP here. 00722 SmallVector<Constant*, 8> Idxs; 00723 Idxs.reserve(GEPI->getNumOperands()-1); 00724 for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end(); 00725 i != e; ++i) 00726 if (Constant *C = dyn_cast<Constant>(*i)) 00727 Idxs.push_back(C); 00728 else 00729 break; 00730 if (Idxs.size() == GEPI->getNumOperands()-1) 00731 Changed |= OptimizeAwayTrappingUsesOfValue(GEPI, 00732 ConstantExpr::getGetElementPtr(NewV, &Idxs[0], 00733 Idxs.size()), Context); 00734 if (GEPI->use_empty()) { 00735 Changed = true; 00736 GEPI->eraseFromParent(); 00737 } 00738 } 00739 } 00740 00741 return Changed; 00742 } 00743 00744 00745 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null 00746 /// value stored into it. If there are uses of the loaded value that would trap 00747 /// if the loaded value is dynamically null, then we know that they cannot be 00748 /// reachable with a null optimize away the load. 00749 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV, 00750 LLVMContext &Context) { 00751 bool Changed = false; 00752 00753 // Keep track of whether we are able to remove all the uses of the global 00754 // other than the store that defines it. 00755 bool AllNonStoreUsesGone = true; 00756 00757 // Replace all uses of loads with uses of uses of the stored value. 00758 for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); GUI != E;){ 00759 User *GlobalUser = *GUI++; 00760 if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) { 00761 Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV, Context); 00762 // If we were able to delete all uses of the loads 00763 if (LI->use_empty()) { 00764 LI->eraseFromParent(); 00765 Changed = true; 00766 } else { 00767 AllNonStoreUsesGone = false; 00768 } 00769 } else if (isa<StoreInst>(GlobalUser)) { 00770 // Ignore the store that stores "LV" to the global. 00771 assert(GlobalUser->getOperand(1) == GV && 00772 "Must be storing *to* the global"); 00773 } else { 00774 AllNonStoreUsesGone = false; 00775 00776 // If we get here we could have other crazy uses that are transitively 00777 // loaded. 00778 assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || 00779 isa<ConstantExpr>(GlobalUser)) && "Only expect load and stores!"); 00780 } 00781 } 00782 00783 if (Changed) { 00784 DOUT << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV; 00785 ++NumGlobUses; 00786 } 00787 00788 // If we nuked all of the loads, then none of the stores are needed either, 00789 // nor is the global. 00790 if (AllNonStoreUsesGone) { 00791 DOUT << " *** GLOBAL NOW DEAD!\n"; 00792 CleanupConstantGlobalUsers(GV, 0, Context); 00793 if (GV->use_empty()) { 00794 GV->eraseFromParent(); 00795 ++NumDeleted; 00796 } 00797 Changed = true; 00798 } 00799 return Changed; 00800 } 00801 00802 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the 00803 /// instructions that are foldable. 00804 static void ConstantPropUsersOf(Value *V, LLVMContext &Context) { 00805 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) 00806 if (Instruction *I = dyn_cast<Instruction>(*UI++)) 00807 if (Constant *NewC = ConstantFoldInstruction(I, Context)) { 00808 I->replaceAllUsesWith(NewC); 00809 00810 // Advance UI to the next non-I use to avoid invalidating it! 00811 // Instructions could multiply use V. 00812 while (UI != E && *UI == I) 00813 ++UI; 00814 I->eraseFromParent(); 00815 } 00816 } 00817 00818 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global 00819 /// variable, and transforms the program as if it always contained the result of 00820 /// the specified malloc. Because it is always the result of the specified 00821 /// malloc, there is no reason to actually DO the malloc. Instead, turn the 00822 /// malloc into a global, and any loads of GV as uses of the new global. 00823 static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, 00824 MallocInst *MI, 00825 LLVMContext &Context) { 00826 DOUT << "PROMOTING MALLOC GLOBAL: " << *GV << " MALLOC = " << *MI; 00827 ConstantInt *NElements = cast<ConstantInt>(MI->getArraySize()); 00828 00829 if (NElements->getZExtValue() != 1) { 00830 // If we have an array allocation, transform it to a single element 00831 // allocation to make the code below simpler. 00832 Type *NewTy = ArrayType::get(MI->getAllocatedType(), 00833 NElements->getZExtValue()); 00834 MallocInst *NewMI = 00835 new MallocInst(NewTy, Constant::getNullValue(Type::getInt32Ty(Context)), 00836 MI->getAlignment(), MI->getName(), MI); 00837 Value* Indices[2]; 00838 Indices[0] = Indices[1] = Constant::getNullValue(Type::getInt32Ty(Context)); 00839 Value *NewGEP = GetElementPtrInst::Create(NewMI, Indices, Indices + 2, 00840 NewMI->getName()+".el0", MI); 00841 MI->replaceAllUsesWith(NewGEP); 00842 MI->eraseFromParent(); 00843 MI = NewMI; 00844 } 00845 00846 // Create the new global variable. The contents of the malloc'd memory is 00847 // undefined, so initialize with an undef value. 00848 // FIXME: This new global should have the alignment returned by malloc. Code 00849 // could depend on malloc returning large alignment (on the mac, 16 bytes) but 00850 // this would only guarantee some lower alignment. 00851 Constant *Init = UndefValue::get(MI->getAllocatedType()); 00852 GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(), 00853 MI->getAllocatedType(), false, 00854 GlobalValue::InternalLinkage, Init, 00855 GV->getName()+".body", 00856 GV, 00857 GV->isThreadLocal()); 00858 00859 // Anything that used the malloc now uses the global directly. 00860 MI->replaceAllUsesWith(NewGV); 00861 00862 Constant *RepValue = NewGV; 00863 if (NewGV->getType() != GV->getType()->getElementType()) 00864 RepValue = ConstantExpr::getBitCast(RepValue, 00865 GV->getType()->getElementType()); 00866 00867 // If there is a comparison against null, we will insert a global bool to 00868 // keep track of whether the global was initialized yet or not. 00869 GlobalVariable *InitBool = 00870 new GlobalVariable(Context, Type::getInt1Ty(Context), false, 00871 GlobalValue::InternalLinkage, 00872 ConstantInt::getFalse(Context), GV->getName()+".init", 00873 GV->isThreadLocal()); 00874 bool InitBoolUsed = false; 00875 00876 // Loop over all uses of GV, processing them in turn. 00877 std::vector<StoreInst*> Stores; 00878 while (!GV->use_empty()) 00879 if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) { 00880 while (!LI->use_empty()) { 00881 Use &LoadUse = LI->use_begin().getUse(); 00882 if (!isa<ICmpInst>(LoadUse.getUser())) 00883 LoadUse = RepValue; 00884 else { 00885 ICmpInst *CI = cast<ICmpInst>(LoadUse.getUser()); 00886 // Replace the cmp X, 0 with a use of the bool value. 00887 Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", CI); 00888 InitBoolUsed = true; 00889 switch (CI->getPredicate()) { 00890 default: llvm_unreachable("Unknown ICmp Predicate!"); 00891 case ICmpInst::ICMP_ULT: 00892 case ICmpInst::ICMP_SLT: 00893 LV = ConstantInt::getFalse(Context); // X < null -> always false 00894 break; 00895 case ICmpInst::ICMP_ULE: 00896 case ICmpInst::ICMP_SLE: 00897 case ICmpInst::ICMP_EQ: 00898 LV = BinaryOperator::CreateNot(LV, "notinit", CI); 00899 break; 00900 case ICmpInst::ICMP_NE: 00901 case ICmpInst::ICMP_UGE: 00902 case ICmpInst::ICMP_SGE: 00903 case ICmpInst::ICMP_UGT: 00904 case ICmpInst::ICMP_SGT: 00905 break; // no change. 00906 } 00907 CI->replaceAllUsesWith(LV); 00908 CI->eraseFromParent(); 00909 } 00910 } 00911 LI->eraseFromParent(); 00912 } else { 00913 StoreInst *SI = cast<StoreInst>(GV->use_back()); 00914 // The global is initialized when the store to it occurs. 00915 new StoreInst(ConstantInt::getTrue(Context), InitBool, SI); 00916 SI->eraseFromParent(); 00917 } 00918 00919 // If the initialization boolean was used, insert it, otherwise delete it. 00920 if (!InitBoolUsed) { 00921 while (!InitBool->use_empty()) // Delete initializations 00922 cast<Instruction>(InitBool->use_back())->eraseFromParent(); 00923 delete InitBool; 00924 } else 00925 GV->getParent()->getGlobalList().insert(GV, InitBool); 00926 00927 00928 // Now the GV is dead, nuke it and the malloc. 00929 GV->eraseFromParent(); 00930 MI->eraseFromParent(); 00931 00932 // To further other optimizations, loop over all users of NewGV and try to 00933 // constant prop them. This will promote GEP instructions with constant 00934 // indices into GEP constant-exprs, which will allow global-opt to hack on it. 00935 ConstantPropUsersOf(NewGV, Context); 00936 if (RepValue != NewGV) 00937 ConstantPropUsersOf(RepValue, Context); 00938 00939 return NewGV; 00940 } 00941 00942 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking 00943 /// to make sure that there are no complex uses of V. We permit simple things 00944 /// like dereferencing the pointer, but not storing through the address, unless 00945 /// it is to the specified global. 00946 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Instruction *V, 00947 GlobalVariable *GV, 00948 SmallPtrSet<PHINode*, 8> &PHIs) { 00949 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){ 00950 Instruction *Inst = cast<Instruction>(*UI); 00951 00952 if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) { 00953 continue; // Fine, ignore. 00954 } 00955 00956 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 00957 if (SI->getOperand(0) == V && SI->getOperand(1) != GV) 00958 return false; // Storing the pointer itself... bad. 00959 continue; // Otherwise, storing through it, or storing into GV... fine. 00960 } 00961 00962 if (isa<GetElementPtrInst>(Inst)) { 00963 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs)) 00964 return false; 00965 continue; 00966 } 00967 00968 if (PHINode *PN = dyn_cast<PHINode>(Inst)) { 00969 // PHIs are ok if all uses are ok. Don't infinitely recurse through PHI 00970 // cycles. 00971 if (PHIs.insert(PN)) 00972 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs)) 00973 return false; 00974 continue; 00975 } 00976 00977 if (BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) { 00978 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs)) 00979 return false; 00980 continue; 00981 } 00982 00983 return false; 00984 } 00985 return true; 00986 } 00987 00988 /// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV 00989 /// somewhere. Transform all uses of the allocation into loads from the 00990 /// global and uses of the resultant pointer. Further, delete the store into 00991 /// GV. This assumes that these value pass the 00992 /// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate. 00993 static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc, 00994 GlobalVariable *GV) { 00995 while (!Alloc->use_empty()) { 00996 Instruction *U = cast<Instruction>(*Alloc->use_begin()); 00997 Instruction *InsertPt = U; 00998 if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 00999 // If this is the store of the allocation into the global, remove it. 01000 if (SI->getOperand(1) == GV) { 01001 SI->eraseFromParent(); 01002 continue; 01003 } 01004 } else if (PHINode *PN = dyn_cast<PHINode>(U)) { 01005 // Insert the load in the corresponding predecessor, not right before the 01006 // PHI. 01007 InsertPt = PN->getIncomingBlock(Alloc->use_begin())->getTerminator(); 01008 } else if (isa<BitCastInst>(U)) { 01009 // Must be bitcast between the malloc and store to initialize the global. 01010 ReplaceUsesOfMallocWithGlobal(U, GV); 01011 U->eraseFromParent(); 01012 continue; 01013 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 01014 // If this is a "GEP bitcast" and the user is a store to the global, then 01015 // just process it as a bitcast. 01016 if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse()) 01017 if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->use_back())) 01018 if (SI->getOperand(1) == GV) { 01019 // Must be bitcast GEP between the malloc and store to initialize 01020 // the global. 01021 ReplaceUsesOfMallocWithGlobal(GEPI, GV); 01022 GEPI->eraseFromParent(); 01023 continue; 01024 } 01025 } 01026 01027 // Insert a load from the global, and use it instead of the malloc. 01028 Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt); 01029 U->replaceUsesOfWith(Alloc, NL); 01030 } 01031 } 01032 01033 /// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi 01034 /// of a load) are simple enough to perform heap SRA on. This permits GEP's 01035 /// that index through the array and struct field, icmps of null, and PHIs. 01036 static bool LoadUsesSimpleEnoughForHeapSRA(Value *V, 01037 SmallPtrSet<PHINode*, 32> &LoadUsingPHIs, 01038 SmallPtrSet<PHINode*, 32> &LoadUsingPHIsPerLoad) { 01039 // We permit two users of the load: setcc comparing against the null 01040 // pointer, and a getelementptr of a specific form. 01041 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){ 01042 Instruction *User = cast<Instruction>(*UI); 01043 01044 // Comparison against null is ok. 01045 if (ICmpInst *ICI = dyn_cast<ICmpInst>(User)) { 01046 if (!isa<ConstantPointerNull>(ICI->getOperand(1))) 01047 return false; 01048 continue; 01049 } 01050 01051 // getelementptr is also ok, but only a simple form. 01052 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 01053 // Must index into the array and into the struct. 01054 if (GEPI->getNumOperands() < 3) 01055 return false; 01056 01057 // Otherwise the GEP is ok. 01058 continue; 01059 } 01060 01061 if (PHINode *PN = dyn_cast<PHINode>(User)) { 01062 if (!LoadUsingPHIsPerLoad.insert(PN)) 01063 // This means some phi nodes are dependent on each other. 01064 // Avoid infinite looping! 01065 return false; 01066 if (!LoadUsingPHIs.insert(PN)) 01067 // If we have already analyzed this PHI, then it is safe. 01068 continue; 01069 01070 // Make sure all uses of the PHI are simple enough to transform. 01071 if (!LoadUsesSimpleEnoughForHeapSRA(PN, 01072 LoadUsingPHIs, LoadUsingPHIsPerLoad)) 01073 return false; 01074 01075 continue; 01076 } 01077 01078 // Otherwise we don't know what this is, not ok. 01079 return false; 01080 } 01081 01082 return true; 01083 } 01084 01085 01086 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from 01087 /// GV are simple enough to perform HeapSRA, return true. 01088 static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV, 01089 MallocInst *MI) { 01090 SmallPtrSet<PHINode*, 32> LoadUsingPHIs; 01091 SmallPtrSet<PHINode*, 32> LoadUsingPHIsPerLoad; 01092 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E; 01093 ++UI) 01094 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 01095 if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs, 01096 LoadUsingPHIsPerLoad)) 01097 return false; 01098 LoadUsingPHIsPerLoad.clear(); 01099 } 01100 01101 // If we reach here, we know that all uses of the loads and transitive uses 01102 // (through PHI nodes) are simple enough to transform. However, we don't know 01103 // that all inputs the to the PHI nodes are in the same equivalence sets. 01104 // Check to verify that all operands of the PHIs are either PHIS that can be 01105 // transformed, loads from GV, or MI itself. 01106 for (SmallPtrSet<PHINode*, 32>::iterator I = LoadUsingPHIs.begin(), 01107 E = LoadUsingPHIs.end(); I != E; ++I) { 01108 PHINode *PN = *I; 01109 for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) { 01110 Value *InVal = PN->getIncomingValue(op); 01111 01112 // PHI of the stored value itself is ok. 01113 if (InVal == MI) continue; 01114 01115 if (PHINode *InPN = dyn_cast<PHINode>(InVal)) { 01116 // One of the PHIs in our set is (optimistically) ok. 01117 if (LoadUsingPHIs.count(InPN)) 01118 continue; 01119 return false; 01120 } 01121 01122 // Load from GV is ok. 01123 if (LoadInst *LI = dyn_cast<LoadInst>(InVal)) 01124 if (LI->getOperand(0) == GV) 01125 continue; 01126 01127 // UNDEF? NULL? 01128 01129 // Anything else is rejected. 01130 return false; 01131 } 01132 } 01133 01134 return true; 01135 } 01136 01137 static Value *GetHeapSROAValue(Value *V, unsigned FieldNo, 01138 DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 01139 std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite, 01140 LLVMContext &Context) { 01141 std::vector<Value*> &FieldVals = InsertedScalarizedValues[V]; 01142 01143 if (FieldNo >= FieldVals.size()) 01144 FieldVals.resize(FieldNo+1); 01145 01146 // If we already have this value, just reuse the previously scalarized 01147 // version. 01148 if (Value *FieldVal = FieldVals[FieldNo]) 01149 return FieldVal; 01150 01151 // Depending on what instruction this is, we have several cases. 01152 Value *Result; 01153 if (LoadInst *LI = dyn_cast<LoadInst>(V)) { 01154 // This is a scalarized version of the load from the global. Just create 01155 // a new Load of the scalarized global. 01156 Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo, 01157 InsertedScalarizedValues, 01158 PHIsToRewrite, Context), 01159 LI->getName()+".f"+Twine(FieldNo), LI); 01160 } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 01161 // PN's type is pointer to struct. Make a new PHI of pointer to struct 01162 // field. 01163 const StructType *ST = 01164 cast<StructType>(cast<PointerType>(PN->getType())->getElementType()); 01165 01166 Result = 01167 PHINode::Create(PointerType::getUnqual(ST->getElementType(FieldNo)), 01168 PN->getName()+".f"+Twine(FieldNo), PN); 01169 PHIsToRewrite.push_back(std::make_pair(PN, FieldNo)); 01170 } else { 01171 llvm_unreachable("Unknown usable value"); 01172 Result = 0; 01173 } 01174 01175 return FieldVals[FieldNo] = Result; 01176 } 01177 01178 /// RewriteHeapSROALoadUser - Given a load instruction and a value derived from 01179 /// the load, rewrite the derived value to use the HeapSRoA'd load. 01180 static void RewriteHeapSROALoadUser(Instruction *LoadUser, 01181 DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 01182 std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite, 01183 LLVMContext &Context) { 01184 // If this is a comparison against null, handle it. 01185 if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) { 01186 assert(isa<ConstantPointerNull>(SCI->getOperand(1))); 01187 // If we have a setcc of the loaded pointer, we can use a setcc of any 01188 // field. 01189 Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0, 01190 InsertedScalarizedValues, PHIsToRewrite, 01191 Context); 01192 01193 Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr, 01194 Constant::getNullValue(NPtr->getType()), 01195 SCI->getName()); 01196 SCI->replaceAllUsesWith(New); 01197 SCI->eraseFromParent(); 01198 return; 01199 } 01200 01201 // Handle 'getelementptr Ptr, Idx, i32 FieldNo ...' 01202 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) { 01203 assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2)) 01204 && "Unexpected GEPI!"); 01205 01206 // Load the pointer for this field. 01207 unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); 01208 Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo, 01209 InsertedScalarizedValues, PHIsToRewrite, 01210 Context); 01211 01212 // Create the new GEP idx vector. 01213 SmallVector<Value*, 8> GEPIdx; 01214 GEPIdx.push_back(GEPI->getOperand(1)); 01215 GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end()); 01216 01217 Value *NGEPI = GetElementPtrInst::Create(NewPtr, 01218 GEPIdx.begin(), GEPIdx.end(), 01219 GEPI->getName(), GEPI); 01220 GEPI->replaceAllUsesWith(NGEPI); 01221 GEPI->eraseFromParent(); 01222 return; 01223 } 01224 01225 // Recursively transform the users of PHI nodes. This will lazily create the 01226 // PHIs that are needed for individual elements. Keep track of what PHIs we 01227 // see in InsertedScalarizedValues so that we don't get infinite loops (very 01228 // antisocial). If the PHI is already in InsertedScalarizedValues, it has 01229 // already been seen first by another load, so its uses have already been 01230 // processed. 01231 PHINode *PN = cast<PHINode>(LoadUser); 01232 bool Inserted; 01233 DenseMap<Value*, std::vector<Value*> >::iterator InsertPos; 01234 tie(InsertPos, Inserted) = 01235 InsertedScalarizedValues.insert(std::make_pair(PN, std::vector<Value*>())); 01236 if (!Inserted) return; 01237 01238 // If this is the first time we've seen this PHI, recursively process all 01239 // users. 01240 for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; ) { 01241 Instruction *User = cast<Instruction>(*UI++); 01242 RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite, 01243 Context); 01244 } 01245 } 01246 01247 /// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global. Ptr 01248 /// is a value loaded from the global. Eliminate all uses of Ptr, making them 01249 /// use FieldGlobals instead. All uses of loaded values satisfy 01250 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA. 01251 static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load, 01252 DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 01253 std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite, 01254 LLVMContext &Context) { 01255 for (Value::use_iterator UI = Load->use_begin(), E = Load->use_end(); 01256 UI != E; ) { 01257 Instruction *User = cast<Instruction>(*UI++); 01258 RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite, 01259 Context); 01260 } 01261 01262 if (Load->use_empty()) { 01263 Load->eraseFromParent(); 01264 InsertedScalarizedValues.erase(Load); 01265 } 01266 } 01267 01268 /// PerformHeapAllocSRoA - MI is an allocation of an array of structures. Break 01269 /// it up into multiple allocations of arrays of the fields. 01270 static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI, 01271 LLVMContext &Context){ 01272 DOUT << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *MI; 01273 const StructType *STy = cast<StructType>(MI->getAllocatedType()); 01274 01275 // There is guaranteed to be at least one use of the malloc (storing 01276 // it into GV). If there are other uses, change them to be uses of 01277 // the global to simplify later code. This also deletes the store 01278 // into GV. 01279 ReplaceUsesOfMallocWithGlobal(MI, GV); 01280 01281 // Okay, at this point, there are no users of the malloc. Insert N 01282 // new mallocs at the same place as MI, and N globals. 01283 std::vector<Value*> FieldGlobals; 01284 std::vector<MallocInst*> FieldMallocs; 01285 01286 for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){ 01287 const Type *FieldTy = STy->getElementType(FieldNo); 01288 const Type *PFieldTy = PointerType::getUnqual(FieldTy); 01289 01290 GlobalVariable *NGV = 01291 new GlobalVariable(*GV->getParent(), 01292 PFieldTy, false, GlobalValue::InternalLinkage, 01293 Constant::getNullValue(PFieldTy), 01294 GV->getName() + ".f" + Twine(FieldNo), GV, 01295 GV->isThreadLocal()); 01296 FieldGlobals.push_back(NGV); 01297 01298 MallocInst *NMI = new MallocInst(FieldTy, MI->getArraySize(), 01299 MI->getName() + ".f" + Twine(FieldNo), MI); 01300 FieldMallocs.push_back(NMI); 01301 new StoreInst(NMI, NGV, MI); 01302 } 01303 01304 // The tricky aspect of this transformation is handling the case when malloc 01305 // fails. In the original code, malloc failing would set the result pointer 01306 // of malloc to null. In this case, some mallocs could succeed and others 01307 // could fail. As such, we emit code that looks like this: 01308 // F0 = malloc(field0) 01309 // F1 = malloc(field1) 01310 // F2 = malloc(field2) 01311 // if (F0 == 0 || F1 == 0 || F2 == 0) { 01312 // if (F0) { free(F0); F0 = 0; } 01313 // if (F1) { free(F1); F1 = 0; } 01314 // if (F2) { free(F2); F2 = 0; } 01315 // } 01316 Value *RunningOr = 0; 01317 for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) { 01318 Value *Cond = new ICmpInst(MI, ICmpInst::ICMP_EQ, FieldMallocs[i], 01319 Constant::getNullValue(FieldMallocs[i]->getType()), 01320 "isnull"); 01321 if (!RunningOr) 01322 RunningOr = Cond; // First seteq 01323 else 01324 RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", MI); 01325 } 01326 01327 // Split the basic block at the old malloc. 01328 BasicBlock *OrigBB = MI->getParent(); 01329 BasicBlock *ContBB = OrigBB->splitBasicBlock(MI, "malloc_cont"); 01330 01331 // Create the block to check the first condition. Put all these blocks at the 01332 // end of the function as they are unlikely to be executed. 01333 BasicBlock *NullPtrBlock = BasicBlock::Create(Context, "malloc_ret_null", 01334 OrigBB->getParent()); 01335 01336 // Remove the uncond branch from OrigBB to ContBB, turning it into a cond 01337 // branch on RunningOr. 01338 OrigBB->getTerminator()->eraseFromParent(); 01339 BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB); 01340 01341 // Within the NullPtrBlock, we need to emit a comparison and branch for each 01342 // pointer, because some may be null while others are not. 01343 for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 01344 Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock); 01345 Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal, 01346 Constant::getNullValue(GVVal->getType()), 01347 "tmp"); 01348 BasicBlock *FreeBlock = BasicBlock::Create(Context, "free_it", 01349 OrigBB->getParent()); 01350 BasicBlock *NextBlock = BasicBlock::Create(Context, "next", 01351 OrigBB->getParent()); 01352 BranchInst::Create(FreeBlock, NextBlock, Cmp, NullPtrBlock); 01353 01354 // Fill in FreeBlock. 01355 new FreeInst(GVVal, FreeBlock); 01356 new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i], 01357 FreeBlock); 01358 BranchInst::Create(NextBlock, FreeBlock); 01359 01360 NullPtrBlock = NextBlock; 01361 } 01362 01363 BranchInst::Create(ContBB, NullPtrBlock); 01364 01365 // MI is no longer needed, remove it. 01366 MI->eraseFromParent(); 01367 01368 /// InsertedScalarizedLoads - As we process loads, if we can't immediately 01369 /// update all uses of the load, keep track of what scalarized loads are 01370 /// inserted for a given load. 01371 DenseMap<Value*, std::vector<Value*> > InsertedScalarizedValues; 01372 InsertedScalarizedValues[GV] = FieldGlobals; 01373 01374 std::vector<std::pair<PHINode*, unsigned> > PHIsToRewrite; 01375 01376 // Okay, the malloc site is completely handled. All of the uses of GV are now 01377 // loads, and all uses of those loads are simple. Rewrite them to use loads 01378 // of the per-field globals instead. 01379 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;) { 01380 Instruction *User = cast<Instruction>(*UI++); 01381 01382 if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 01383 RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite, 01384 Context); 01385 continue; 01386 } 01387 01388 // Must be a store of null. 01389 StoreInst *SI = cast<StoreInst>(User); 01390 assert(isa<ConstantPointerNull>(SI->getOperand(0)) && 01391 "Unexpected heap-sra user!"); 01392 01393 // Insert a store of null into each global. 01394 for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 01395 const PointerType *PT = cast<PointerType>(FieldGlobals[i]->getType()); 01396 Constant *Null = Constant::getNullValue(PT->getElementType()); 01397 new StoreInst(Null, FieldGlobals[i], SI); 01398 } 01399 // Erase the original store. 01400 SI->eraseFromParent(); 01401 } 01402 01403 // While we have PHIs that are interesting to rewrite, do it. 01404 while (!PHIsToRewrite.empty()) { 01405 PHINode *PN = PHIsToRewrite.back().first; 01406 unsigned FieldNo = PHIsToRewrite.back().second; 01407 PHIsToRewrite.pop_back(); 01408 PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]); 01409 assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi"); 01410 01411 // Add all the incoming values. This can materialize more phis. 01412 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 01413 Value *InVal = PN->getIncomingValue(i); 01414 InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues, 01415 PHIsToRewrite, Context); 01416 FieldPN->addIncoming(InVal, PN->getIncomingBlock(i)); 01417 } 01418 } 01419 01420 // Drop all inter-phi links and any loads that made it this far. 01421 for (DenseMap<Value*, std::vector<Value*> >::iterator 01422 I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end(); 01423 I != E; ++I) { 01424 if (PHINode *PN = dyn_cast<PHINode>(I->first)) 01425 PN->dropAllReferences(); 01426 else if (LoadInst *LI = dyn_cast<LoadInst>(I->first)) 01427 LI->dropAllReferences(); 01428 } 01429 01430 // Delete all the phis and loads now that inter-references are dead. 01431 for (DenseMap<Value*, std::vector<Value*> >::iterator 01432 I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end(); 01433 I != E; ++I) { 01434 if (PHINode *PN = dyn_cast<PHINode>(I->first)) 01435 PN->eraseFromParent(); 01436 else if (LoadInst *LI = dyn_cast<LoadInst>(I->first)) 01437 LI->eraseFromParent(); 01438 } 01439 01440 // The old global is now dead, remove it. 01441 GV->eraseFromParent(); 01442 01443 ++NumHeapSRA; 01444 return cast<GlobalVariable>(FieldGlobals[0]); 01445 } 01446 01447 /// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a 01448 /// pointer global variable with a single value stored it that is a malloc or 01449 /// cast of malloc. 01450 static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, 01451 MallocInst *MI, 01452 Module::global_iterator &GVI, 01453 TargetData *TD, 01454 LLVMContext &Context) { 01455 // If this is a malloc of an abstract type, don't touch it. 01456 if (!MI->getAllocatedType()->isSized()) 01457 return false; 01458 01459 // We can't optimize this global unless all uses of it are *known* to be 01460 // of the malloc value, not of the null initializer value (consider a use 01461 // that compares the global's value against zero to see if the malloc has 01462 // been reached). To do this, we check to see if all uses of the global 01463 // would trap if the global were null: this proves that they must all 01464 // happen after the malloc. 01465 if (!AllUsesOfLoadedValueWillTrapIfNull(GV)) 01466 return false; 01467 01468 // We can't optimize this if the malloc itself is used in a complex way, 01469 // for example, being stored into multiple globals. This allows the 01470 // malloc to be stored into the specified global, loaded setcc'd, and 01471 // GEP'd. These are all things we could transform to using the global 01472 // for. 01473 { 01474 SmallPtrSet<PHINode*, 8> PHIs; 01475 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(MI, GV, PHIs)) 01476 return false; 01477 } 01478 01479 01480 // If we have a global that is only initialized with a fixed size malloc, 01481 // transform the program to use global memory instead of malloc'd memory. 01482 // This eliminates dynamic allocation, avoids an indirection accessing the 01483 // data, and exposes the resultant global to further GlobalOpt. 01484 if (ConstantInt *NElements = dyn_cast<ConstantInt>(MI->getArraySize())) { 01485 // Restrict this transformation to only working on small allocations 01486 // (2048 bytes currently), as we don't want to introduce a 16M global or 01487 // something. 01488 if (TD && 01489 NElements->getZExtValue()* 01490 TD->getTypeAllocSize(MI->getAllocatedType()) < 2048) { 01491 GVI = OptimizeGlobalAddressOfMalloc(GV, MI, Context); 01492 return true; 01493 } 01494 } 01495 01496 // If the allocation is an array of structures, consider transforming this 01497 // into multiple malloc'd arrays, one for each field. This is basically 01498 // SRoA for malloc'd memory. 01499 const Type *AllocTy = MI->getAllocatedType(); 01500 01501 // If this is an allocation of a fixed size array of structs, analyze as a 01502 // variable size array. malloc [100 x struct],1 -> malloc struct, 100 01503 if (!MI->isArrayAllocation()) 01504 if (const ArrayType *AT = dyn_cast<ArrayType>(AllocTy)) 01505 AllocTy = AT->getElementType(); 01506 01507 if (const StructType *AllocSTy = dyn_cast<StructType>(AllocTy)) { 01508 // This the structure has an unreasonable number of fields, leave it 01509 // alone. 01510 if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 && 01511 AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV, MI)) { 01512 01513 // If this is a fixed size array, transform the Malloc to be an alloc of 01514 // structs. malloc [100 x struct],1 -> malloc struct, 100 01515 if (const ArrayType *AT = dyn_cast<ArrayType>(MI->getAllocatedType())) { 01516 MallocInst *NewMI = 01517 new MallocInst(AllocSTy, 01518 ConstantInt::get(Type::getInt32Ty(Context), 01519 AT->getNumElements()), 01520 "", MI); 01521 NewMI->takeName(MI); 01522 Value *Cast = new BitCastInst(NewMI, MI->getType(), "tmp", MI); 01523 MI->replaceAllUsesWith(Cast); 01524 MI->eraseFromParent(); 01525 MI = NewMI; 01526 } 01527 01528 GVI = PerformHeapAllocSRoA(GV, MI, Context); 01529 return true; 01530 } 01531 } 01532 01533 return false; 01534 } 01535 01536 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge 01537 // that only one value (besides its initializer) is ever stored to the global. 01538 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, 01539 Module::global_iterator &GVI, 01540 TargetData *TD, LLVMContext &Context) { 01541 // Ignore no-op GEPs and bitcasts. 01542 StoredOnceVal = StoredOnceVal->stripPointerCasts(); 01543 01544 // If we are dealing with a pointer global that is initialized to null and 01545 // only has one (non-null) value stored into it, then we can optimize any 01546 // users of the loaded value (often calls and loads) that would trap if the 01547 // value was null. 01548 if (isa<PointerType>(GV->getInitializer()->getType()) && 01549 GV->getInitializer()->isNullValue()) { 01550 if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) { 01551 if (GV->getInitializer()->getType() != SOVC->getType()) 01552 SOVC = 01553 ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); 01554 01555 // Optimize away any trapping uses of the loaded value. 01556 if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, Context)) 01557 return true; 01558 } else if (MallocInst *MI = dyn_cast<MallocInst>(StoredOnceVal)) { 01559 if (TryToOptimizeStoreOfMallocToGlobal(GV, MI, GVI, TD, Context)) 01560 return true; 01561 } 01562 } 01563 01564 return false; 01565 } 01566 01567 /// TryToShrinkGlobalToBoolean - At this point, we have learned that the only 01568 /// two values ever stored into GV are its initializer and OtherVal. See if we 01569 /// can shrink the global into a boolean and select between the two values 01570 /// whenever it is used. This exposes the values to other scalar optimizations. 01571 static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal, 01572 LLVMContext &Context) { 01573 const Type *GVElType = GV->getType()->getElementType(); 01574 01575 // If GVElType is already i1, it is already shrunk. If the type of the GV is 01576 // an FP value, pointer or vector, don't do this optimization because a select 01577 // between them is very expensive and unlikely to lead to later 01578 // simplification. In these cases, we typically end up with "cond ? v1 : v2" 01579 // where v1 and v2 both require constant pool loads, a big loss. 01580 if (GVElType == Type::getInt1Ty(Context) || GVElType->isFloatingPoint() || 01581 isa<PointerType>(GVElType) || isa<VectorType>(GVElType)) 01582 return false; 01583 01584 // Walk the use list of the global seeing if all the uses are load or store. 01585 // If there is anything else, bail out. 01586 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I) 01587 if (!isa<LoadInst>(I) && !isa<StoreInst>(I)) 01588 return false; 01589 01590 DOUT << " *** SHRINKING TO BOOL: " << *GV; 01591 01592 // Create the new global, initializing it to false. 01593 GlobalVariable *NewGV = new GlobalVariable(Context, 01594 Type::getInt1Ty(Context), false, 01595 GlobalValue::InternalLinkage, ConstantInt::getFalse(Context), 01596 GV->getName()+".b", 01597 GV->isThreadLocal()); 01598 GV->getParent()->getGlobalList().insert(GV, NewGV); 01599 01600 Constant *InitVal = GV->getInitializer(); 01601 assert(InitVal->getType() != Type::getInt1Ty(Context) && 01602 "No reason to shrink to bool!"); 01603 01604 // If initialized to zero and storing one into the global, we can use a cast 01605 // instead of a select to synthesize the desired value. 01606 bool IsOneZero = false; 01607 if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) 01608 IsOneZero = InitVal->isNullValue() && CI->isOne(); 01609 01610 while (!GV->use_empty()) { 01611 Instruction *UI = cast<Instruction>(GV->use_back()); 01612 if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 01613 // Change the store into a boolean store. 01614 bool StoringOther = SI->getOperand(0) == OtherVal; 01615 // Only do this if we weren't storing a loaded value. 01616 Value *StoreVal; 01617 if (StoringOther || SI->getOperand(0) == InitVal) 01618 StoreVal = ConstantInt::get(Type::getInt1Ty(Context), StoringOther); 01619 else { 01620 // Otherwise, we are storing a previously loaded copy. To do this, 01621 // change the copy from copying the original value to just copying the 01622 // bool. 01623 Instruction *StoredVal = cast<Instruction>(SI->getOperand(0)); 01624 01625 // If we're already replaced the input, StoredVal will be a cast or 01626 // select instruction. If not, it will be a load of the original 01627 // global. 01628 if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) { 01629 assert(LI->getOperand(0) == GV && "Not a copy!"); 01630 // Insert a new load, to preserve the saved value. 01631 StoreVal = new LoadInst(NewGV, LI->getName()+".b", LI); 01632 } else { 01633 assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && 01634 "This is not a form that we understand!"); 01635 StoreVal = StoredVal->getOperand(0); 01636 assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!"); 01637 } 01638 } 01639 new StoreInst(StoreVal, NewGV, SI); 01640 } else { 01641 // Change the load into a load of bool then a select. 01642 LoadInst *LI = cast<LoadInst>(UI); 01643 LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", LI); 01644 Value *NSI; 01645 if (IsOneZero) 01646 NSI = new ZExtInst(NLI, LI->getType(), "", LI); 01647 else 01648 NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI); 01649 NSI->takeName(LI); 01650 LI->replaceAllUsesWith(NSI); 01651 } 01652 UI->eraseFromParent(); 01653 } 01654 01655 GV->eraseFromParent(); 01656 return true; 01657 } 01658 01659 01660 /// ProcessInternalGlobal - Analyze the specified global variable and optimize 01661 /// it if possible. If we make a change, return true. 01662 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, 01663 Module::global_iterator &GVI) { 01664 SmallPtrSet<PHINode*, 16> PHIUsers; 01665 GlobalStatus GS; 01666 GV->removeDeadConstantUsers(); 01667 01668 if (GV->use_empty()) { 01669 DOUT << "GLOBAL DEAD: " << *GV; 01670 GV->eraseFromParent(); 01671 ++NumDeleted; 01672 return true; 01673 } 01674 01675 if (!AnalyzeGlobal(GV, GS, PHIUsers)) { 01676 #if 0 01677 cerr << "Global: " << *GV; 01678 cerr << " isLoaded = " << GS.isLoaded << "\n"; 01679 cerr << " StoredType = "; 01680 switch (GS.StoredType) { 01681 case GlobalStatus::NotStored: cerr << "NEVER STORED\n"; break; 01682 case GlobalStatus::isInitializerStored: cerr << "INIT STORED\n"; break; 01683 case GlobalStatus::isStoredOnce: cerr << "STORED ONCE\n"; break; 01684 case GlobalStatus::isStored: cerr << "stored\n"; break; 01685 } 01686 if (GS.StoredType == GlobalStatus::isStoredOnce && GS.StoredOnceValue) 01687 cerr << " StoredOnceValue = " << *GS.StoredOnceValue << "\n"; 01688 if (GS.AccessingFunction && !GS.HasMultipleAccessingFunctions) 01689 cerr << " AccessingFunction = " << GS.AccessingFunction->getName() 01690 << "\n"; 01691 cerr << " HasMultipleAccessingFunctions = " 01692 << GS.HasMultipleAccessingFunctions << "\n"; 01693 cerr << " HasNonInstructionUser = " << GS.HasNonInstructionUser<<"\n"; 01694 cerr << "\n"; 01695 #endif 01696 01697 // If this is a first class global and has only one accessing function 01698 // and this function is main (which we know is not recursive we can make 01699 // this global a local variable) we replace the global with a local alloca 01700 // in this function. 01701 // 01702 // NOTE: It doesn't make sense to promote non single-value types since we 01703 // are just replacing static memory to stack memory. 01704 // 01705 // If the global is in different address space, don't bring it to stack. 01706 if (!GS.HasMultipleAccessingFunctions && 01707 GS.AccessingFunction && !GS.HasNonInstructionUser && 01708 GV->getType()->getElementType()->isSingleValueType() && 01709 GS.AccessingFunction->getName() == "main" && 01710 GS.AccessingFunction->hasExternalLinkage() && 01711 GV->getType()->getAddressSpace() == 0) { 01712 DOUT << "LOCALIZING GLOBAL: " << *GV; 01713 Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin(); 01714 const Type* ElemTy = GV->getType()->getElementType(); 01715 // FIXME: Pass Global's alignment when globals have alignment 01716 AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), FirstI); 01717 if (!isa<UndefValue>(GV->getInitializer())) 01718 new StoreInst(GV->getInitializer(), Alloca, FirstI); 01719 01720 GV->replaceAllUsesWith(Alloca); 01721 GV->eraseFromParent(); 01722 ++NumLocalized; 01723 return true; 01724 } 01725 01726 // If the global is never loaded (but may be stored to), it is dead. 01727 // Delete it now. 01728 if (!GS.isLoaded) { 01729 DOUT << "GLOBAL NEVER LOADED: " << *GV; 01730 01731 // Delete any stores we can find to the global. We may not be able to 01732 // make it completely dead though. 01733 bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), 01734 GV->getContext()); 01735 01736 // If the global is dead now, delete it. 01737 if (GV->use_empty()) { 01738 GV->eraseFromParent(); 01739 ++NumDeleted; 01740 Changed = true; 01741 } 01742 return Changed; 01743 01744 } else if (GS.StoredType <= GlobalStatus::isInitializerStored) { 01745 DOUT << "MARKING CONSTANT: " << *GV; 01746 GV->setConstant(true); 01747 01748 // Clean up any obviously simplifiable users now. 01749 CleanupConstantGlobalUsers(GV, GV->getInitializer(), GV->getContext()); 01750 01751 // If the global is dead now, just nuke it. 01752 if (GV->use_empty()) { 01753 DOUT << " *** Marking constant allowed us to simplify " 01754 << "all users and delete global!\n"; 01755 GV->eraseFromParent(); 01756 ++NumDeleted; 01757 } 01758 01759 ++NumMarked; 01760 return true; 01761 } else if (!GV->getInitializer()->getType()->isSingleValueType()) { 01762 if (TargetData *TD = getAnalysisIfAvailable<TargetData>()) 01763 if (GlobalVariable *FirstNewGV = SRAGlobal(GV, *TD, 01764 GV->getContext())) { 01765 GVI = FirstNewGV; // Don't skip the newly produced globals! 01766 return true; 01767 } 01768 } else if (GS.StoredType == GlobalStatus::isStoredOnce) { 01769 // If the initial value for the global was an undef value, and if only 01770 // one other value was stored into it, we can just change the 01771 // initializer to be the stored value, then delete all stores to the 01772 // global. This allows us to mark it constant. 01773 if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 01774 if (isa<UndefValue>(GV->getInitializer())) { 01775 // Change the initial value here. 01776 GV->setInitializer(SOVConstant); 01777 01778 // Clean up any obviously simplifiable users now. 01779 CleanupConstantGlobalUsers(GV, GV->getInitializer(), 01780 GV->getContext()); 01781 01782 if (GV->use_empty()) { 01783 DOUT << " *** Substituting initializer allowed us to " 01784 << "simplify all users and delete global!\n"; 01785 GV->eraseFromParent(); 01786 ++NumDeleted; 01787 } else { 01788 GVI = GV; 01789 } 01790 ++NumSubstitute; 01791 return true; 01792 } 01793 01794 // Try to optimize globals based on the knowledge that only one value 01795 // (besides its initializer) is ever stored to the global. 01796 if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GVI, 01797 getAnalysisIfAvailable<TargetData>(), 01798 GV->getContext())) 01799 return true; 01800 01801 // Otherwise, if the global was not a boolean, we can shrink it to be a 01802 // boolean. 01803 if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 01804 if (TryToShrinkGlobalToBoolean(GV, SOVConstant, GV->getContext())) { 01805 ++NumShrunkToBool; 01806 return true; 01807 } 01808 } 01809 } 01810 return false; 01811 } 01812 01813 /// ChangeCalleesToFastCall - Walk all of the direct calls of the specified 01814 /// function, changing them to FastCC. 01815 static void ChangeCalleesToFastCall(Function *F) { 01816 for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 01817 CallSite User(cast<Instruction>(*UI)); 01818 User.setCallingConv(CallingConv::Fast); 01819 } 01820 } 01821 01822 static AttrListPtr StripNest(const AttrListPtr &Attrs) { 01823 for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) { 01824 if ((Attrs.getSlot(i).Attrs & Attribute::Nest) == 0) 01825 continue; 01826 01827 // There can be only one. 01828 return Attrs.removeAttr(Attrs.getSlot(i).Index, Attribute::Nest); 01829 } 01830 01831 return Attrs; 01832 } 01833 01834 static void RemoveNestAttribute(Function *F) { 01835 F->setAttributes(StripNest(F->getAttributes())); 01836 for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 01837 CallSite User(cast<Instruction>(*UI)); 01838 User.setAttributes(StripNest(User.getAttributes())); 01839 } 01840 } 01841 01842 bool GlobalOpt::OptimizeFunctions(Module &M) { 01843 bool Changed = false; 01844 // Optimize functions. 01845 for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) { 01846 Function *F = FI++; 01847 // Functions without names cannot be referenced outside this module. 01848 if (!F->hasName() && !F->isDeclaration()) 01849 F->setLinkage(GlobalValue::InternalLinkage); 01850 F->removeDeadConstantUsers(); 01851 if (F->use_empty() && (F->hasLocalLinkage() || 01852 F->hasLinkOnceLinkage())) { 01853 M.getFunctionList().erase(F); 01854 Changed = true; 01855 ++NumFnDeleted; 01856 } else if (F->hasLocalLinkage()) { 01857 if (F->getCallingConv() == CallingConv::C && !F->isVarArg() && 01858 !F->hasAddressTaken()) { 01859 // If this function has C calling conventions, is not a varargs 01860 // function, and is only called directly, promote it to use the Fast 01861 // calling convention. 01862 F->setCallingConv(CallingConv::Fast); 01863 ChangeCalleesToFastCall(F); 01864 ++NumFastCallFns; 01865 Changed = true; 01866 } 01867 01868 if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) && 01869 !F->hasAddressTaken()) { 01870 // The function is not used by a trampoline intrinsic, so it is safe 01871 // to remove the 'nest' attribute. 01872 RemoveNestAttribute(F); 01873 ++NumNestRemoved; 01874 Changed = true; 01875 } 01876 } 01877 } 01878 return Changed; 01879 } 01880 01881 bool GlobalOpt::OptimizeGlobalVars(Module &M) { 01882 bool Changed = false; 01883 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 01884 GVI != E; ) { 01885 GlobalVariable *GV = GVI++; 01886 // Global variables without names cannot be referenced outside this module. 01887 if (!GV->hasName() && !GV->isDeclaration()) 01888 GV->setLinkage(GlobalValue::InternalLinkage); 01889 if (!GV->isConstant() && GV->hasLocalLinkage() && 01890 GV->hasInitializer()) 01891 Changed |= ProcessInternalGlobal(GV, GVI); 01892 } 01893 return Changed; 01894 } 01895 01896 /// FindGlobalCtors - Find the llvm.globalctors list, verifying that all 01897 /// initializers have an init priority of 65535. 01898 GlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) { 01899 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 01900 I != E; ++I) 01901 if (I->getName() == "llvm.global_ctors") { 01902 // Found it, verify it's an array of { int, void()* }. 01903 const ArrayType *ATy =dyn_cast<ArrayType>(I->getType()->getElementType()); 01904 if (!ATy) return 0; 01905 const StructType *STy = dyn_cast<StructType>(ATy->getElementType()); 01906 if (!STy || STy->getNumElements() != 2 || 01907 STy->getElementType(0) != Type::getInt32Ty(M.getContext())) return 0; 01908 const PointerType *PFTy = dyn_cast<PointerType>(STy->getElementType(1)); 01909 if (!PFTy) return 0; 01910 const FunctionType *FTy = dyn_cast<FunctionType>(PFTy->getElementType()); 01911 if (!FTy || FTy->getReturnType() != Type::getVoidTy(M.getContext()) || 01912 FTy->isVarArg() || FTy->getNumParams() != 0) 01913 return 0; 01914 01915 // Verify that the initializer is simple enough for us to handle. 01916 if (!I->hasDefinitiveInitializer()) return 0; 01917 ConstantArray *CA = dyn_cast<ConstantArray>(I->getInitializer()); 01918 if (!CA) return 0; 01919 for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) 01920 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(*i)) { 01921 if (isa<ConstantPointerNull>(CS->getOperand(1))) 01922 continue; 01923 01924 // Must have a function or null ptr. 01925 if (!isa<Function>(CS->getOperand(1))) 01926 return 0; 01927 01928 // Init priority must be standard. 01929 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 01930 if (!CI || CI->getZExtValue() != 65535) 01931 return 0; 01932 } else { 01933 return 0; 01934 } 01935 01936 return I; 01937 } 01938 return 0; 01939 } 01940 01941 /// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand, 01942 /// return a list of the functions and null terminator as a vector. 01943 static std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) { 01944 ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); 01945 std::vector<Function*> Result; 01946 Result.reserve(CA->getNumOperands()); 01947 for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) { 01948 ConstantStruct *CS = cast<ConstantStruct>(*i); 01949 Result.push_back(dyn_cast<Function>(CS->getOperand(1))); 01950 } 01951 return Result; 01952 } 01953 01954 /// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the 01955 /// specified array, returning the new global to use. 01956 static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, 01957 const std::vector<Function*> &Ctors, 01958 LLVMContext &Context) { 01959 // If we made a change, reassemble the initializer list. 01960 std::vector<Constant*> CSVals; 01961 CSVals.push_back(ConstantInt::get(Type::getInt32Ty(Context), 65535)); 01962 CSVals.push_back(0); 01963 01964 // Create the new init list. 01965 std::vector<Constant*> CAList; 01966 for (unsigned i = 0, e = Ctors.size(); i != e; ++i) { 01967 if (Ctors[i]) { 01968 CSVals[1] = Ctors[i]; 01969 } else { 01970 const Type *FTy = FunctionType::get(Type::getVoidTy(Context), false); 01971 const PointerType *PFTy = PointerType::getUnqual(FTy); 01972 CSVals[1] = Constant::getNullValue(PFTy); 01973 CSVals[0] = ConstantInt::get(Type::getInt32Ty(Context), 2147483647); 01974 } 01975 CAList.push_back(ConstantStruct::get(Context, CSVals)); 01976 } 01977 01978 // Create the array initializer. 01979 const Type *StructTy = 01980 cast<ArrayType>(GCL->getType()->getElementType())->getElementType(); 01981 Constant *CA = ConstantArray::get(ArrayType::get(StructTy, 01982 CAList.size()), CAList); 01983 01984 // If we didn't change the number of elements, don't create a new GV. 01985 if (CA->getType() == GCL->getInitializer()->getType()) { 01986 GCL->setInitializer(CA); 01987 return GCL; 01988 } 01989 01990 // Create the new global and insert it next to the existing list. 01991 GlobalVariable *NGV = new GlobalVariable(Context, CA->getType(), 01992 GCL->isConstant(), 01993 GCL->getLinkage(), CA, "", 01994 GCL->isThreadLocal()); 01995 GCL->getParent()->getGlobalList().insert(GCL, NGV); 01996 NGV->takeName(GCL); 01997 01998 // Nuke the old list, replacing any uses with the new one. 01999 if (!GCL->use_empty()) { 02000 Constant *V = NGV; 02001 if (V->getType() != GCL->getType()) 02002 V = ConstantExpr::getBitCast(V, GCL->getType()); 02003 GCL->replaceAllUsesWith(V); 02004 } 02005 GCL->eraseFromParent(); 02006 02007 if (Ctors.size()) 02008 return NGV; 02009 else 02010 return 0; 02011 } 02012 02013 02014 static Constant *getVal(DenseMap<Value*, Constant*> &ComputedValues, 02015 Value *V) { 02016 if (Constant *CV = dyn_cast<Constant>(V)) return CV; 02017 Constant *R = ComputedValues[V]; 02018 assert(R && "Reference to an uncomputed value!"); 02019 return R; 02020 } 02021 02022 /// isSimpleEnoughPointerToCommit - Return true if this constant is simple 02023 /// enough for us to understand. In particular, if it is a cast of something, 02024 /// we punt. We basically just support direct accesses to globals and GEP's of 02025 /// globals. This should be kept up to date with CommitValueTo. 02026 static bool isSimpleEnoughPointerToCommit(Constant *C, LLVMContext &Context) { 02027 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) { 02028 if (!GV->hasExternalLinkage() && !GV->hasLocalLinkage()) 02029 return false; // do not allow weak/linkonce/dllimport/dllexport linkage. 02030 return !GV->isDeclaration(); // reject external globals. 02031 } 02032 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 02033 // Handle a constantexpr gep. 02034 if (CE->getOpcode() == Instruction::GetElementPtr && 02035 isa<GlobalVariable>(CE->getOperand(0))) { 02036 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 02037 if (!GV->hasExternalLinkage() && !GV->hasLocalLinkage()) 02038 return false; // do not allow weak/linkonce/dllimport/dllexport linkage. 02039 return GV->hasInitializer() && 02040 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE, 02041 Context); 02042 } 02043 return false; 02044 } 02045 02046 /// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global 02047 /// initializer. This returns 'Init' modified to reflect 'Val' stored into it. 02048 /// At this point, the GEP operands of Addr [0, OpNo) have been stepped into. 02049 static Constant *EvaluateStoreInto(Constant *Init, Constant *Val, 02050 ConstantExpr *Addr, unsigned OpNo, 02051 LLVMContext &Context) { 02052 // Base case of the recursion. 02053 if (OpNo == Addr->getNumOperands()) { 02054 assert(Val->getType() == Init->getType() && "Type mismatch!"); 02055 return Val; 02056 } 02057 02058 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) { 02059 std::vector<Constant*> Elts; 02060 02061 // Break up the constant into its elements. 02062 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) { 02063 for (User::op_iterator i = CS->op_begin(), e = CS->op_end(); i != e; ++i) 02064 Elts.push_back(cast<Constant>(*i)); 02065 } else if (isa<ConstantAggregateZero>(Init)) { 02066 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 02067 Elts.push_back(Constant::getNullValue(STy->getElementType(i))); 02068 } else if (isa<UndefValue>(Init)) { 02069 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 02070 Elts.push_back(UndefValue::get(STy->getElementType(i))); 02071 } else { 02072 llvm_unreachable("This code is out of sync with " 02073 " ConstantFoldLoadThroughGEPConstantExpr"); 02074 } 02075 02076 // Replace the element that we are supposed to. 02077 ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo)); 02078 unsigned Idx = CU->getZExtValue(); 02079 assert(Idx < STy->getNumElements() && "Struct index out of range!"); 02080 Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1, Context); 02081 02082 // Return the modified struct. 02083 return ConstantStruct::get(Context, &Elts[0], Elts.size(), STy->isPacked()); 02084 } else { 02085 ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo)); 02086 const ArrayType *ATy = cast<ArrayType>(Init->getType()); 02087 02088 // Break up the array into elements. 02089 std::vector<Constant*> Elts; 02090 if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) { 02091 for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) 02092 Elts.push_back(cast<Constant>(*i)); 02093 } else if (isa<ConstantAggregateZero>(Init)) { 02094 Constant *Elt = Constant::getNullValue(ATy->getElementType()); 02095 Elts.assign(ATy->getNumElements(), Elt); 02096 } else if (isa<UndefValue>(Init)) { 02097 Constant *Elt = UndefValue::get(ATy->getElementType()); 02098 Elts.assign(ATy->getNumElements(), Elt); 02099 } else { 02100 llvm_unreachable("This code is out of sync with " 02101 " ConstantFoldLoadThroughGEPConstantExpr"); 02102 } 02103 02104 assert(CI->getZExtValue() < ATy->getNumElements()); 02105 Elts[CI->getZExtValue()] = 02106 EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1, Context); 02107 return ConstantArray::get(ATy, Elts); 02108 } 02109 } 02110 02111 /// CommitValueTo - We have decided that Addr (which satisfies the predicate 02112 /// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen. 02113 static void CommitValueTo(Constant *Val, Constant *Addr, 02114 LLVMContext &Context) { 02115 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) { 02116 assert(GV->hasInitializer()); 02117 GV->setInitializer(Val); 02118 return; 02119 } 02120 02121 ConstantExpr *CE = cast<ConstantExpr>(Addr); 02122 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 02123 02124 Constant *Init = GV->getInitializer(); 02125 Init = EvaluateStoreInto(Init, Val, CE, 2, Context); 02126 GV->setInitializer(Init); 02127 } 02128 02129 /// ComputeLoadResult - Return the value that would be computed by a load from 02130 /// P after the stores reflected by 'memory' have been performed. If we can't 02131 /// decide, return null. 02132 static Constant *ComputeLoadResult(Constant *P, 02133 const DenseMap<Constant*, Constant*> &Memory, 02134 LLVMContext &Context) { 02135 // If this memory location has been recently stored, use the stored value: it 02136 // is the most up-to-date. 02137 DenseMap<Constant*, Constant*>::const_iterator I = Memory.find(P); 02138 if (I != Memory.end()) return I->second; 02139 02140 // Access it. 02141 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { 02142 if (GV->hasDefinitiveInitializer()) 02143 return GV->getInitializer(); 02144 return 0; 02145 } 02146 02147 // Handle a constantexpr getelementptr. 02148 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) 02149 if (CE->getOpcode() == Instruction::GetElementPtr && 02150 isa<GlobalVariable>(CE->getOperand(0))) { 02151 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 02152 if (GV->hasDefinitiveInitializer()) 02153 return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE, 02154 Context); 02155 } 02156 02157 return 0; // don't know how to evaluate. 02158 } 02159 02160 /// EvaluateFunction - Evaluate a call to function F, returning true if 02161 /// successful, false if we can't evaluate it. ActualArgs contains the formal 02162 /// arguments for the function. 02163 static bool EvaluateFunction(Function *F, Constant *&RetVal, 02164 const SmallVectorImpl<Constant*> &ActualArgs, 02165 std::vector<Function*> &CallStack, 02166 DenseMap<Constant*, Constant*> &MutatedMemory, 02167 std::vector<GlobalVariable*> &AllocaTmps) { 02168 // Check to see if this function is already executing (recursion). If so, 02169 // bail out. TODO: we might want to accept limited recursion. 02170 if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end()) 02171 return false; 02172 02173 LLVMContext &Context = F->getContext(); 02174 02175 CallStack.push_back(F); 02176 02177 /// Values - As we compute SSA register values, we store their contents here. 02178 DenseMap<Value*, Constant*> Values; 02179 02180 // Initialize arguments to the incoming values specified. 02181 unsigned ArgNo = 0; 02182 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; 02183 ++AI, ++ArgNo) 02184 Values[AI] = ActualArgs[ArgNo]; 02185 02186 /// ExecutedBlocks - We only handle non-looping, non-recursive code. As such, 02187 /// we can only evaluate any one basic block at most once. This set keeps 02188 /// track of what we have executed so we can detect recursive cases etc. 02189 SmallPtrSet<BasicBlock*, 32> ExecutedBlocks; 02190 02191 // CurInst - The current instruction we're evaluating. 02192 BasicBlock::iterator CurInst = F->begin()->begin(); 02193 02194 // This is the main evaluation loop. 02195 while (1) { 02196 Constant *InstResult = 0; 02197 02198 if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) { 02199 if (SI->isVolatile()) return false; // no volatile accesses. 02200 Constant *Ptr = getVal(Values, SI->getOperand(1)); 02201 if (!isSimpleEnoughPointerToCommit(Ptr, Context)) 02202 // If this is too complex for us to commit, reject it. 02203 return false; 02204 Constant *Val = getVal(Values, SI->getOperand(0)); 02205 MutatedMemory[Ptr] = Val; 02206 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) { 02207 InstResult = ConstantExpr::get(BO->getOpcode(), 02208 getVal(Values, BO->getOperand(0)), 02209 getVal(Values, BO->getOperand(1))); 02210 } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) { 02211 InstResult = ConstantExpr::getCompare(CI->getPredicate(), 02212 getVal(Values, CI->getOperand(0)), 02213 getVal(Values, CI->getOperand(1))); 02214 } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) { 02215 InstResult = ConstantExpr::getCast(CI->getOpcode(), 02216 getVal(Values, CI->getOperand(0)), 02217 CI->getType()); 02218 } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) { 02219 InstResult = 02220 ConstantExpr::getSelect(getVal(Values, SI->getOperand(0)), 02221 getVal(Values, SI->getOperand(1)), 02222 getVal(Values, SI->getOperand(2))); 02223 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) { 02224 Constant *P = getVal(Values, GEP->getOperand(0)); 02225 SmallVector<Constant*, 8> GEPOps; 02226 for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); 02227 i != e; ++i) 02228 GEPOps.push_back(getVal(Values, *i)); 02229 InstResult = 02230 ConstantExpr::getGetElementPtr(P, &GEPOps[0], GEPOps.size()); 02231 } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) { 02232 if (LI->isVolatile()) return false; // no volatile accesses. 02233 InstResult = ComputeLoadResult(getVal(Values, LI->getOperand(0)), 02234 MutatedMemory, Context); 02235 if (InstResult == 0) return false; // Could not evaluate load. 02236 } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) { 02237 if (AI->isArrayAllocation()) return false; // Cannot handle array allocs. 02238 const Type *Ty = AI->getType()->getElementType(); 02239 AllocaTmps.push_back(new GlobalVariable(Context, Ty, false, 02240 GlobalValue::InternalLinkage, 02241 UndefValue::get(Ty), 02242 AI->getName())); 02243 InstResult = AllocaTmps.back(); 02244 } else if (CallInst *CI = dyn_cast<CallInst>(CurInst)) { 02245 02246 // Debug info can safely be ignored here. 02247 if (isa<DbgInfoIntrinsic>(CI)) { 02248 ++CurInst; 02249 continue; 02250 } 02251 02252 // Cannot handle inline asm. 02253 if (isa<InlineAsm>(CI->getOperand(0))) return false; 02254 02255 // Resolve function pointers. 02256 Function *Callee = dyn_cast<Function>(getVal(Values, CI->getOperand(0))); 02257 if (!Callee) return false; // Cannot resolve. 02258 02259 SmallVector<Constant*, 8> Formals; 02260 for (User::op_iterator i = CI->op_begin() + 1, e = CI->op_end(); 02261 i != e; ++i) 02262 Formals.push_back(getVal(Values, *i)); 02263 02264 if (Callee->isDeclaration()) { 02265 // If this is a function we can constant fold, do it. 02266 if (Constant *C = ConstantFoldCall(Callee, Formals.data(), 02267 Formals.size())) { 02268 InstResult = C; 02269 } else { 02270 return false; 02271 } 02272 } else { 02273 if (Callee->getFunctionType()->isVarArg()) 02274 return false; 02275 02276 Constant *RetVal; 02277 // Execute the call, if successful, use the return value. 02278 if (!EvaluateFunction(Callee, RetVal, Formals, CallStack, 02279 MutatedMemory, AllocaTmps)) 02280 return false; 02281 InstResult = RetVal; 02282 } 02283 } else if (isa<TerminatorInst>(CurInst)) { 02284 BasicBlock *NewBB = 0; 02285 if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) { 02286 if (BI->isUnconditional()) { 02287 NewBB = BI->getSuccessor(0); 02288 } else { 02289 ConstantInt *Cond = 02290 dyn_cast<ConstantInt>(getVal(Values, BI->getCondition())); 02291 if (!Cond) return false; // Cannot determine. 02292 02293 NewBB = BI->getSuccessor(!Cond->getZExtValue()); 02294 } 02295 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) { 02296 ConstantInt *Val = 02297 dyn_cast<ConstantInt>(getVal(Values, SI->getCondition())); 02298 if (!Val) return false; // Cannot determine. 02299 NewBB = SI->getSuccessor(SI->findCaseValue(Val)); 02300 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(CurInst)) { 02301 if (RI->getNumOperands()) 02302 RetVal = getVal(Values, RI->getOperand(0)); 02303 02304 CallStack.pop_back(); // return from fn. 02305 return true; // We succeeded at evaluating this ctor! 02306 } else { 02307 // invoke, unwind, unreachable. 02308 return false; // Cannot handle this terminator. 02309 } 02310 02311 // Okay, we succeeded in evaluating this control flow. See if we have 02312 // executed the new block before. If so, we have a looping function, 02313 // which we cannot evaluate in reasonable time. 02314 if (!ExecutedBlocks.insert(NewBB)) 02315 return false; // looped! 02316 02317 // Okay, we have never been in this block before. Check to see if there 02318 // are any PHI nodes. If so, evaluate them with information about where 02319 // we came from. 02320 BasicBlock *OldBB = CurInst->getParent(); 02321 CurInst = NewBB->begin(); 02322 PHINode *PN; 02323 for (; (PN = dyn_cast<PHINode>(CurInst)); ++CurInst) 02324 Values[PN] = getVal(Values, PN->getIncomingValueForBlock(OldBB)); 02325 02326 // Do NOT increment CurInst. We know that the terminator had no value. 02327 continue; 02328 } else { 02329 // Did not know how to evaluate this! 02330 return false; 02331 } 02332 02333 if (!CurInst->use_empty()) 02334 Values[CurInst] = InstResult; 02335 02336 // Advance program counter. 02337 ++CurInst; 02338 } 02339 } 02340 02341 /// EvaluateStaticConstructor - Evaluate static constructors in the function, if 02342 /// we can. Return true if we can, false otherwise. 02343 static bool EvaluateStaticConstructor(Function *F) { 02344 /// MutatedMemory - For each store we execute, we update this map. Loads 02345 /// check this to get the most up-to-date value. If evaluation is successful, 02346 /// this state is committed to the process. 02347 DenseMap<Constant*, Constant*> MutatedMemory; 02348 02349 /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable 02350 /// to represent its body. This vector is needed so we can delete the 02351 /// temporary globals when we are done. 02352 std::vector<GlobalVariable*> AllocaTmps; 02353 02354 /// CallStack - This is used to detect recursion. In pathological situations 02355 /// we could hit exponential behavior, but at least there is nothing 02356 /// unbounded. 02357 std::vector<Function*> CallStack; 02358 02359 // Call the function. 02360 Constant *RetValDummy; 02361 bool EvalSuccess = EvaluateFunction(F, RetValDummy, 02362 SmallVector<Constant*, 0>(), CallStack, 02363 MutatedMemory, AllocaTmps); 02364 if (EvalSuccess) { 02365 // We succeeded at evaluation: commit the result. 02366 DEBUG(errs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" 02367 << F->getName() << "' to " << MutatedMemory.size() 02368 << " stores.\n"); 02369 for (DenseMap<Constant*, Constant*>::iterator I = MutatedMemory.begin(), 02370 E = MutatedMemory.end(); I != E; ++I) 02371 CommitValueTo(I->second, I->first, F->getContext()); 02372 } 02373 02374 // At this point, we are done interpreting. If we created any 'alloca' 02375 // temporaries, release them now. 02376 while (!AllocaTmps.empty()) { 02377 GlobalVariable *Tmp = AllocaTmps.back(); 02378 AllocaTmps.pop_back(); 02379 02380 // If there are still users of the alloca, the program is doing something 02381 // silly, e.g. storing the address of the alloca somewhere and using it 02382 // later. Since this is undefined, we'll just make it be null. 02383 if (!Tmp->use_empty()) 02384 Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); 02385 delete Tmp; 02386 } 02387 02388 return EvalSuccess; 02389 } 02390 02391 02392 02393 /// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible. 02394 /// Return true if anything changed. 02395 bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) { 02396 std::vector<Function*> Ctors = ParseGlobalCtors(GCL); 02397 bool MadeChange = false; 02398 if (Ctors.empty()) return false; 02399 02400 // Loop over global ctors, optimizing them when we can. 02401 for (unsigned i = 0; i != Ctors.size(); ++i) { 02402 Function *F = Ctors[i]; 02403 // Found a null terminator in the middle of the list, prune off the rest of 02404 // the list. 02405 if (F == 0) { 02406 if (i != Ctors.size()-1) { 02407 Ctors.resize(i+1); 02408 MadeChange = true; 02409 } 02410 break; 02411 } 02412 02413 // We cannot simplify external ctor functions. 02414 if (F->empty()) continue; 02415 02416 // If we can evaluate the ctor at compile time, do. 02417 if (EvaluateStaticConstructor(F)) { 02418 Ctors.erase(Ctors.begin()+i); 02419 MadeChange = true; 02420 --i; 02421 ++NumCtorsEvaluated; 02422 continue; 02423 } 02424 } 02425 02426 if (!MadeChange) return false; 02427 02428 GCL = InstallGlobalCtors(GCL, Ctors, GCL->getContext()); 02429 return true; 02430 } 02431 02432 bool GlobalOpt::OptimizeGlobalAliases(Module &M) { 02433 bool Changed = false; 02434 02435 for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); 02436 I != E;) { 02437 Module::alias_iterator J = I++; 02438 // Aliases without names cannot be referenced outside this module. 02439 if (!J->hasName() && !J->isDeclaration()) 02440 J->setLinkage(GlobalValue::InternalLinkage); 02441 // If the aliasee may change at link time, nothing can be done - bail out. 02442 if (J->mayBeOverridden()) 02443 continue; 02444 02445 Constant *Aliasee = J->getAliasee(); 02446 GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts()); 02447 Target->removeDeadConstantUsers(); 02448 bool hasOneUse = Target->hasOneUse() && Aliasee->hasOneUse(); 02449 02450 // Make all users of the alias use the aliasee instead. 02451 if (!J->use_empty()) { 02452 J->replaceAllUsesWith(Aliasee); 02453 ++NumAliasesResolved; 02454 Changed = true; 02455 } 02456 02457 // If the aliasee has internal linkage, give it the name and linkage 02458 // of the alias, and delete the alias. This turns: 02459 // define internal ... @f(...) 02460 // @a = alias ... @f 02461 // into: 02462 // define ... @a(...) 02463 if (!Target->hasLocalLinkage()) 02464 continue; 02465 02466 // The transform is only useful if the alias does not have internal linkage. 02467 if (J->hasLocalLinkage()) 02468 continue; 02469 02470 // Do not perform the transform if multiple aliases potentially target the 02471 // aliasee. This check also ensures that it is safe to replace the section 02472 // and other attributes of the aliasee with those of the alias. 02473 if (!hasOneUse) 02474 continue; 02475 02476 // Give the aliasee the name, linkage and other attributes of the alias. 02477 Target->takeName(J); 02478 Target->setLinkage(J->getLinkage()); 02479 Target->GlobalValue::copyAttributesFrom(J); 02480 02481 // Delete the alias. 02482 M.getAliasList().erase(J); 02483 ++NumAliasesRemoved; 02484 Changed = true; 02485 } 02486 02487 return Changed; 02488 } 02489 02490 bool GlobalOpt::runOnModule(Module &M) { 02491 bool Changed = false; 02492 02493 // Try to find the llvm.globalctors list. 02494 GlobalVariable *GlobalCtors = FindGlobalCtors(M); 02495 02496 bool LocalChange = true; 02497 while (LocalChange) { 02498 LocalChange = false; 02499 02500 // Delete functions that are trivially dead, ccc -> fastcc 02501 LocalChange |= OptimizeFunctions(M); 02502 02503 // Optimize global_ctors list. 02504 if (GlobalCtors) 02505 LocalChange |= OptimizeGlobalCtorsList(GlobalCtors); 02506 02507 // Optimize non-address-taken globals. 02508 LocalChange |= OptimizeGlobalVars(M); 02509 02510 // Resolve aliases, when possible. 02511 LocalChange |= OptimizeGlobalAliases(M); 02512 Changed |= LocalChange; 02513 } 02514 02515 // TODO: Move all global ctors functions to the end of the module for code 02516 // layout. 02517 02518 return Changed; 02519 }