GlobalOpt.cpp revision 75a2db813395e577d844d0996b4528010ee09e1d
1//===- GlobalOpt.cpp - Optimize Global Variables --------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass transforms simple global variables that never have their address 11// taken. If obviously true, it marks read/write globals as constant, deletes 12// variables only stored to, etc. 13// 14//===----------------------------------------------------------------------===// 15 16#define DEBUG_TYPE "globalopt" 17#include "llvm/Transforms/IPO.h" 18#include "llvm/CallingConv.h" 19#include "llvm/Constants.h" 20#include "llvm/DerivedTypes.h" 21#include "llvm/Instructions.h" 22#include "llvm/IntrinsicInst.h" 23#include "llvm/Module.h" 24#include "llvm/Pass.h" 25#include "llvm/Analysis/ConstantFolding.h" 26#include "llvm/Target/TargetData.h" 27#include "llvm/Support/Compiler.h" 28#include "llvm/Support/Debug.h" 29#include "llvm/Support/GetElementPtrTypeIterator.h" 30#include "llvm/ADT/SmallPtrSet.h" 31#include "llvm/ADT/SmallVector.h" 32#include "llvm/ADT/Statistic.h" 33#include "llvm/ADT/StringExtras.h" 34#include <algorithm> 35#include <set> 36using namespace llvm; 37 38STATISTIC(NumMarked , "Number of globals marked constant"); 39STATISTIC(NumSRA , "Number of aggregate globals broken into scalars"); 40STATISTIC(NumHeapSRA , "Number of heap objects SRA'd"); 41STATISTIC(NumSubstitute,"Number of globals with initializers stored into them"); 42STATISTIC(NumDeleted , "Number of globals deleted"); 43STATISTIC(NumFnDeleted , "Number of functions deleted"); 44STATISTIC(NumGlobUses , "Number of global uses devirtualized"); 45STATISTIC(NumLocalized , "Number of globals localized"); 46STATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans"); 47STATISTIC(NumFastCallFns , "Number of functions converted to fastcc"); 48STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated"); 49 50namespace { 51 struct VISIBILITY_HIDDEN GlobalOpt : public ModulePass { 52 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 53 AU.addRequired<TargetData>(); 54 } 55 static char ID; // Pass identification, replacement for typeid 56 GlobalOpt() : ModulePass((intptr_t)&ID) {} 57 58 bool runOnModule(Module &M); 59 60 private: 61 GlobalVariable *FindGlobalCtors(Module &M); 62 bool OptimizeFunctions(Module &M); 63 bool OptimizeGlobalVars(Module &M); 64 bool OptimizeGlobalCtorsList(GlobalVariable *&GCL); 65 bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI); 66 }; 67 68 char GlobalOpt::ID = 0; 69 RegisterPass<GlobalOpt> X("globalopt", "Global Variable Optimizer"); 70} 71 72ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); } 73 74/// GlobalStatus - As we analyze each global, keep track of some information 75/// about it. If we find out that the address of the global is taken, none of 76/// this info will be accurate. 77struct VISIBILITY_HIDDEN GlobalStatus { 78 /// isLoaded - True if the global is ever loaded. If the global isn't ever 79 /// loaded it can be deleted. 80 bool isLoaded; 81 82 /// StoredType - Keep track of what stores to the global look like. 83 /// 84 enum StoredType { 85 /// NotStored - There is no store to this global. It can thus be marked 86 /// constant. 87 NotStored, 88 89 /// isInitializerStored - This global is stored to, but the only thing 90 /// stored is the constant it was initialized with. This is only tracked 91 /// for scalar globals. 92 isInitializerStored, 93 94 /// isStoredOnce - This global is stored to, but only its initializer and 95 /// one other value is ever stored to it. If this global isStoredOnce, we 96 /// track the value stored to it in StoredOnceValue below. This is only 97 /// tracked for scalar globals. 98 isStoredOnce, 99 100 /// isStored - This global is stored to by multiple values or something else 101 /// that we cannot track. 102 isStored 103 } StoredType; 104 105 /// StoredOnceValue - If only one value (besides the initializer constant) is 106 /// ever stored to this global, keep track of what value it is. 107 Value *StoredOnceValue; 108 109 /// AccessingFunction/HasMultipleAccessingFunctions - These start out 110 /// null/false. When the first accessing function is noticed, it is recorded. 111 /// When a second different accessing function is noticed, 112 /// HasMultipleAccessingFunctions is set to true. 113 Function *AccessingFunction; 114 bool HasMultipleAccessingFunctions; 115 116 /// HasNonInstructionUser - Set to true if this global has a user that is not 117 /// an instruction (e.g. a constant expr or GV initializer). 118 bool HasNonInstructionUser; 119 120 /// HasPHIUser - Set to true if this global has a user that is a PHI node. 121 bool HasPHIUser; 122 123 GlobalStatus() : isLoaded(false), StoredType(NotStored), StoredOnceValue(0), 124 AccessingFunction(0), HasMultipleAccessingFunctions(false), 125 HasNonInstructionUser(false), HasPHIUser(false) {} 126}; 127 128 129 130/// ConstantIsDead - Return true if the specified constant is (transitively) 131/// dead. The constant may be used by other constants (e.g. constant arrays and 132/// constant exprs) as long as they are dead, but it cannot be used by anything 133/// else. 134static bool ConstantIsDead(Constant *C) { 135 if (isa<GlobalValue>(C)) return false; 136 137 for (Value::use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; ++UI) 138 if (Constant *CU = dyn_cast<Constant>(*UI)) { 139 if (!ConstantIsDead(CU)) return false; 140 } else 141 return false; 142 return true; 143} 144 145 146/// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus 147/// structure. If the global has its address taken, return true to indicate we 148/// can't do anything with it. 149/// 150static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, 151 std::set<PHINode*> &PHIUsers) { 152 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 153 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) { 154 GS.HasNonInstructionUser = true; 155 156 if (AnalyzeGlobal(CE, GS, PHIUsers)) return true; 157 158 } else if (Instruction *I = dyn_cast<Instruction>(*UI)) { 159 if (!GS.HasMultipleAccessingFunctions) { 160 Function *F = I->getParent()->getParent(); 161 if (GS.AccessingFunction == 0) 162 GS.AccessingFunction = F; 163 else if (GS.AccessingFunction != F) 164 GS.HasMultipleAccessingFunctions = true; 165 } 166 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 167 GS.isLoaded = true; 168 if (LI->isVolatile()) return true; // Don't hack on volatile loads. 169 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 170 // Don't allow a store OF the address, only stores TO the address. 171 if (SI->getOperand(0) == V) return true; 172 173 if (SI->isVolatile()) return true; // Don't hack on volatile stores. 174 175 // If this is a direct store to the global (i.e., the global is a scalar 176 // value, not an aggregate), keep more specific information about 177 // stores. 178 if (GS.StoredType != GlobalStatus::isStored) 179 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(SI->getOperand(1))){ 180 Value *StoredVal = SI->getOperand(0); 181 if (StoredVal == GV->getInitializer()) { 182 if (GS.StoredType < GlobalStatus::isInitializerStored) 183 GS.StoredType = GlobalStatus::isInitializerStored; 184 } else if (isa<LoadInst>(StoredVal) && 185 cast<LoadInst>(StoredVal)->getOperand(0) == GV) { 186 // G = G 187 if (GS.StoredType < GlobalStatus::isInitializerStored) 188 GS.StoredType = GlobalStatus::isInitializerStored; 189 } else if (GS.StoredType < GlobalStatus::isStoredOnce) { 190 GS.StoredType = GlobalStatus::isStoredOnce; 191 GS.StoredOnceValue = StoredVal; 192 } else if (GS.StoredType == GlobalStatus::isStoredOnce && 193 GS.StoredOnceValue == StoredVal) { 194 // noop. 195 } else { 196 GS.StoredType = GlobalStatus::isStored; 197 } 198 } else { 199 GS.StoredType = GlobalStatus::isStored; 200 } 201 } else if (isa<GetElementPtrInst>(I)) { 202 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 203 } else if (isa<SelectInst>(I)) { 204 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 205 } else if (PHINode *PN = dyn_cast<PHINode>(I)) { 206 // PHI nodes we can check just like select or GEP instructions, but we 207 // have to be careful about infinite recursion. 208 if (PHIUsers.insert(PN).second) // Not already visited. 209 if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 210 GS.HasPHIUser = true; 211 } else if (isa<CmpInst>(I)) { 212 } else if (isa<MemCpyInst>(I) || isa<MemMoveInst>(I)) { 213 if (I->getOperand(1) == V) 214 GS.StoredType = GlobalStatus::isStored; 215 if (I->getOperand(2) == V) 216 GS.isLoaded = true; 217 } else if (isa<MemSetInst>(I)) { 218 assert(I->getOperand(1) == V && "Memset only takes one pointer!"); 219 GS.StoredType = GlobalStatus::isStored; 220 } else { 221 return true; // Any other non-load instruction might take address! 222 } 223 } else if (Constant *C = dyn_cast<Constant>(*UI)) { 224 GS.HasNonInstructionUser = true; 225 // We might have a dead and dangling constant hanging off of here. 226 if (!ConstantIsDead(C)) 227 return true; 228 } else { 229 GS.HasNonInstructionUser = true; 230 // Otherwise must be some other user. 231 return true; 232 } 233 234 return false; 235} 236 237static Constant *getAggregateConstantElement(Constant *Agg, Constant *Idx) { 238 ConstantInt *CI = dyn_cast<ConstantInt>(Idx); 239 if (!CI) return 0; 240 unsigned IdxV = CI->getZExtValue(); 241 242 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) { 243 if (IdxV < CS->getNumOperands()) return CS->getOperand(IdxV); 244 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) { 245 if (IdxV < CA->getNumOperands()) return CA->getOperand(IdxV); 246 } else if (ConstantVector *CP = dyn_cast<ConstantVector>(Agg)) { 247 if (IdxV < CP->getNumOperands()) return CP->getOperand(IdxV); 248 } else if (isa<ConstantAggregateZero>(Agg)) { 249 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) { 250 if (IdxV < STy->getNumElements()) 251 return Constant::getNullValue(STy->getElementType(IdxV)); 252 } else if (const SequentialType *STy = 253 dyn_cast<SequentialType>(Agg->getType())) { 254 return Constant::getNullValue(STy->getElementType()); 255 } 256 } else if (isa<UndefValue>(Agg)) { 257 if (const StructType *STy = dyn_cast<StructType>(Agg->getType())) { 258 if (IdxV < STy->getNumElements()) 259 return UndefValue::get(STy->getElementType(IdxV)); 260 } else if (const SequentialType *STy = 261 dyn_cast<SequentialType>(Agg->getType())) { 262 return UndefValue::get(STy->getElementType()); 263 } 264 } 265 return 0; 266} 267 268 269/// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all 270/// users of the global, cleaning up the obvious ones. This is largely just a 271/// quick scan over the use list to clean up the easy and obvious cruft. This 272/// returns true if it made a change. 273static bool CleanupConstantGlobalUsers(Value *V, Constant *Init) { 274 bool Changed = false; 275 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) { 276 User *U = *UI++; 277 278 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 279 if (Init) { 280 // Replace the load with the initializer. 281 LI->replaceAllUsesWith(Init); 282 LI->eraseFromParent(); 283 Changed = true; 284 } 285 } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 286 // Store must be unreachable or storing Init into the global. 287 SI->eraseFromParent(); 288 Changed = true; 289 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 290 if (CE->getOpcode() == Instruction::GetElementPtr) { 291 Constant *SubInit = 0; 292 if (Init) 293 SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); 294 Changed |= CleanupConstantGlobalUsers(CE, SubInit); 295 } else if (CE->getOpcode() == Instruction::BitCast && 296 isa<PointerType>(CE->getType())) { 297 // Pointer cast, delete any stores and memsets to the global. 298 Changed |= CleanupConstantGlobalUsers(CE, 0); 299 } 300 301 if (CE->use_empty()) { 302 CE->destroyConstant(); 303 Changed = true; 304 } 305 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 306 // Do not transform "gepinst (gep constexpr (GV))" here, because forming 307 // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold 308 // and will invalidate our notion of what Init is. 309 Constant *SubInit = 0; 310 if (!isa<ConstantExpr>(GEP->getOperand(0))) { 311 ConstantExpr *CE = 312 dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP)); 313 if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr) 314 SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); 315 } 316 Changed |= CleanupConstantGlobalUsers(GEP, SubInit); 317 318 if (GEP->use_empty()) { 319 GEP->eraseFromParent(); 320 Changed = true; 321 } 322 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv 323 if (MI->getRawDest() == V) { 324 MI->eraseFromParent(); 325 Changed = true; 326 } 327 328 } else if (Constant *C = dyn_cast<Constant>(U)) { 329 // If we have a chain of dead constantexprs or other things dangling from 330 // us, and if they are all dead, nuke them without remorse. 331 if (ConstantIsDead(C)) { 332 C->destroyConstant(); 333 // This could have invalidated UI, start over from scratch. 334 CleanupConstantGlobalUsers(V, Init); 335 return true; 336 } 337 } 338 } 339 return Changed; 340} 341 342/// isSafeSROAElementUse - Return true if the specified instruction is a safe 343/// user of a derived expression from a global that we want to SROA. 344static bool isSafeSROAElementUse(Value *V) { 345 // We might have a dead and dangling constant hanging off of here. 346 if (Constant *C = dyn_cast<Constant>(V)) 347 return ConstantIsDead(C); 348 349 Instruction *I = dyn_cast<Instruction>(V); 350 if (!I) return false; 351 352 // Loads are ok. 353 if (isa<LoadInst>(I)) return true; 354 355 // Stores *to* the pointer are ok. 356 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 357 return SI->getOperand(0) != V; 358 359 // Otherwise, it must be a GEP. 360 GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I); 361 if (GEPI == 0) return false; 362 363 if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) || 364 !cast<Constant>(GEPI->getOperand(1))->isNullValue()) 365 return false; 366 367 for (Value::use_iterator I = GEPI->use_begin(), E = GEPI->use_end(); 368 I != E; ++I) 369 if (!isSafeSROAElementUse(*I)) 370 return false; 371 return true; 372} 373 374 375/// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value. 376/// Look at it and its uses and decide whether it is safe to SROA this global. 377/// 378static bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) { 379 // The user of the global must be a GEP Inst or a ConstantExpr GEP. 380 if (!isa<GetElementPtrInst>(U) && 381 (!isa<ConstantExpr>(U) || 382 cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr)) 383 return false; 384 385 // Check to see if this ConstantExpr GEP is SRA'able. In particular, we 386 // don't like < 3 operand CE's, and we don't like non-constant integer 387 // indices. This enforces that all uses are 'gep GV, 0, C, ...' for some 388 // value of C. 389 if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) || 390 !cast<Constant>(U->getOperand(1))->isNullValue() || 391 !isa<ConstantInt>(U->getOperand(2))) 392 return false; 393 394 gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U); 395 ++GEPI; // Skip over the pointer index. 396 397 // If this is a use of an array allocation, do a bit more checking for sanity. 398 if (const ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) { 399 uint64_t NumElements = AT->getNumElements(); 400 ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2)); 401 402 // Check to make sure that index falls within the array. If not, 403 // something funny is going on, so we won't do the optimization. 404 // 405 if (Idx->getZExtValue() >= NumElements) 406 return false; 407 408 // We cannot scalar repl this level of the array unless any array 409 // sub-indices are in-range constants. In particular, consider: 410 // A[0][i]. We cannot know that the user isn't doing invalid things like 411 // allowing i to index an out-of-range subscript that accesses A[1]. 412 // 413 // Scalar replacing *just* the outer index of the array is probably not 414 // going to be a win anyway, so just give up. 415 for (++GEPI; // Skip array index. 416 GEPI != E && (isa<ArrayType>(*GEPI) || isa<VectorType>(*GEPI)); 417 ++GEPI) { 418 uint64_t NumElements; 419 if (const ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI)) 420 NumElements = SubArrayTy->getNumElements(); 421 else 422 NumElements = cast<VectorType>(*GEPI)->getNumElements(); 423 424 ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand()); 425 if (!IdxVal || IdxVal->getZExtValue() >= NumElements) 426 return false; 427 } 428 } 429 430 for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I) 431 if (!isSafeSROAElementUse(*I)) 432 return false; 433 return true; 434} 435 436/// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it 437/// is safe for us to perform this transformation. 438/// 439static bool GlobalUsersSafeToSRA(GlobalValue *GV) { 440 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 441 UI != E; ++UI) { 442 if (!IsUserOfGlobalSafeForSRA(*UI, GV)) 443 return false; 444 } 445 return true; 446} 447 448 449/// SRAGlobal - Perform scalar replacement of aggregates on the specified global 450/// variable. This opens the door for other optimizations by exposing the 451/// behavior of the program in a more fine-grained way. We have determined that 452/// this transformation is safe already. We return the first global variable we 453/// insert so that the caller can reprocess it. 454static GlobalVariable *SRAGlobal(GlobalVariable *GV) { 455 // Make sure this global only has simple uses that we can SRA. 456 if (!GlobalUsersSafeToSRA(GV)) 457 return 0; 458 459 assert(GV->hasInternalLinkage() && !GV->isConstant()); 460 Constant *Init = GV->getInitializer(); 461 const Type *Ty = Init->getType(); 462 463 std::vector<GlobalVariable*> NewGlobals; 464 Module::GlobalListType &Globals = GV->getParent()->getGlobalList(); 465 466 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 467 NewGlobals.reserve(STy->getNumElements()); 468 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 469 Constant *In = getAggregateConstantElement(Init, 470 ConstantInt::get(Type::Int32Ty, i)); 471 assert(In && "Couldn't get element of initializer?"); 472 GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false, 473 GlobalVariable::InternalLinkage, 474 In, GV->getName()+"."+utostr(i), 475 (Module *)NULL, 476 GV->isThreadLocal()); 477 Globals.insert(GV, NGV); 478 NewGlobals.push_back(NGV); 479 } 480 } else if (const SequentialType *STy = dyn_cast<SequentialType>(Ty)) { 481 unsigned NumElements = 0; 482 if (const ArrayType *ATy = dyn_cast<ArrayType>(STy)) 483 NumElements = ATy->getNumElements(); 484 else if (const VectorType *PTy = dyn_cast<VectorType>(STy)) 485 NumElements = PTy->getNumElements(); 486 else 487 assert(0 && "Unknown aggregate sequential type!"); 488 489 if (NumElements > 16 && GV->hasNUsesOrMore(16)) 490 return 0; // It's not worth it. 491 NewGlobals.reserve(NumElements); 492 for (unsigned i = 0, e = NumElements; i != e; ++i) { 493 Constant *In = getAggregateConstantElement(Init, 494 ConstantInt::get(Type::Int32Ty, i)); 495 assert(In && "Couldn't get element of initializer?"); 496 497 GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false, 498 GlobalVariable::InternalLinkage, 499 In, GV->getName()+"."+utostr(i), 500 (Module *)NULL, 501 GV->isThreadLocal()); 502 Globals.insert(GV, NGV); 503 NewGlobals.push_back(NGV); 504 } 505 } 506 507 if (NewGlobals.empty()) 508 return 0; 509 510 DOUT << "PERFORMING GLOBAL SRA ON: " << *GV; 511 512 Constant *NullInt = Constant::getNullValue(Type::Int32Ty); 513 514 // Loop over all of the uses of the global, replacing the constantexpr geps, 515 // with smaller constantexpr geps or direct references. 516 while (!GV->use_empty()) { 517 User *GEP = GV->use_back(); 518 assert(((isa<ConstantExpr>(GEP) && 519 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| 520 isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!"); 521 522 // Ignore the 1th operand, which has to be zero or else the program is quite 523 // broken (undefined). Get the 2nd operand, which is the structure or array 524 // index. 525 unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue(); 526 if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access. 527 528 Value *NewPtr = NewGlobals[Val]; 529 530 // Form a shorter GEP if needed. 531 if (GEP->getNumOperands() > 3) 532 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) { 533 SmallVector<Constant*, 8> Idxs; 534 Idxs.push_back(NullInt); 535 for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i) 536 Idxs.push_back(CE->getOperand(i)); 537 NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), 538 &Idxs[0], Idxs.size()); 539 } else { 540 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP); 541 SmallVector<Value*, 8> Idxs; 542 Idxs.push_back(NullInt); 543 for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i) 544 Idxs.push_back(GEPI->getOperand(i)); 545 NewPtr = new GetElementPtrInst(NewPtr, Idxs.begin(), Idxs.end(), 546 GEPI->getName()+"."+utostr(Val), GEPI); 547 } 548 GEP->replaceAllUsesWith(NewPtr); 549 550 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP)) 551 GEPI->eraseFromParent(); 552 else 553 cast<ConstantExpr>(GEP)->destroyConstant(); 554 } 555 556 // Delete the old global, now that it is dead. 557 Globals.erase(GV); 558 ++NumSRA; 559 560 // Loop over the new globals array deleting any globals that are obviously 561 // dead. This can arise due to scalarization of a structure or an array that 562 // has elements that are dead. 563 unsigned FirstGlobal = 0; 564 for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i) 565 if (NewGlobals[i]->use_empty()) { 566 Globals.erase(NewGlobals[i]); 567 if (FirstGlobal == i) ++FirstGlobal; 568 } 569 570 return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0; 571} 572 573/// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified 574/// value will trap if the value is dynamically null. PHIs keeps track of any 575/// phi nodes we've seen to avoid reprocessing them. 576static bool AllUsesOfValueWillTrapIfNull(Value *V, 577 SmallPtrSet<PHINode*, 8> &PHIs) { 578 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 579 if (isa<LoadInst>(*UI)) { 580 // Will trap. 581 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 582 if (SI->getOperand(0) == V) { 583 //cerr << "NONTRAPPING USE: " << **UI; 584 return false; // Storing the value. 585 } 586 } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) { 587 if (CI->getOperand(0) != V) { 588 //cerr << "NONTRAPPING USE: " << **UI; 589 return false; // Not calling the ptr 590 } 591 } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) { 592 if (II->getOperand(0) != V) { 593 //cerr << "NONTRAPPING USE: " << **UI; 594 return false; // Not calling the ptr 595 } 596 } else if (BitCastInst *CI = dyn_cast<BitCastInst>(*UI)) { 597 if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false; 598 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) { 599 if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false; 600 } else if (PHINode *PN = dyn_cast<PHINode>(*UI)) { 601 // If we've already seen this phi node, ignore it, it has already been 602 // checked. 603 if (PHIs.insert(PN)) 604 return AllUsesOfValueWillTrapIfNull(PN, PHIs); 605 } else if (isa<ICmpInst>(*UI) && 606 isa<ConstantPointerNull>(UI->getOperand(1))) { 607 // Ignore setcc X, null 608 } else { 609 //cerr << "NONTRAPPING USE: " << **UI; 610 return false; 611 } 612 return true; 613} 614 615/// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads 616/// from GV will trap if the loaded value is null. Note that this also permits 617/// comparisons of the loaded value against null, as a special case. 618static bool AllUsesOfLoadedValueWillTrapIfNull(GlobalVariable *GV) { 619 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI!=E; ++UI) 620 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 621 SmallPtrSet<PHINode*, 8> PHIs; 622 if (!AllUsesOfValueWillTrapIfNull(LI, PHIs)) 623 return false; 624 } else if (isa<StoreInst>(*UI)) { 625 // Ignore stores to the global. 626 } else { 627 // We don't know or understand this user, bail out. 628 //cerr << "UNKNOWN USER OF GLOBAL!: " << **UI; 629 return false; 630 } 631 632 return true; 633} 634 635static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { 636 bool Changed = false; 637 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) { 638 Instruction *I = cast<Instruction>(*UI++); 639 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 640 LI->setOperand(0, NewV); 641 Changed = true; 642 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 643 if (SI->getOperand(1) == V) { 644 SI->setOperand(1, NewV); 645 Changed = true; 646 } 647 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 648 if (I->getOperand(0) == V) { 649 // Calling through the pointer! Turn into a direct call, but be careful 650 // that the pointer is not also being passed as an argument. 651 I->setOperand(0, NewV); 652 Changed = true; 653 bool PassedAsArg = false; 654 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i) 655 if (I->getOperand(i) == V) { 656 PassedAsArg = true; 657 I->setOperand(i, NewV); 658 } 659 660 if (PassedAsArg) { 661 // Being passed as an argument also. Be careful to not invalidate UI! 662 UI = V->use_begin(); 663 } 664 } 665 } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 666 Changed |= OptimizeAwayTrappingUsesOfValue(CI, 667 ConstantExpr::getCast(CI->getOpcode(), 668 NewV, CI->getType())); 669 if (CI->use_empty()) { 670 Changed = true; 671 CI->eraseFromParent(); 672 } 673 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 674 // Should handle GEP here. 675 SmallVector<Constant*, 8> Idxs; 676 Idxs.reserve(GEPI->getNumOperands()-1); 677 for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i) 678 if (Constant *C = dyn_cast<Constant>(GEPI->getOperand(i))) 679 Idxs.push_back(C); 680 else 681 break; 682 if (Idxs.size() == GEPI->getNumOperands()-1) 683 Changed |= OptimizeAwayTrappingUsesOfValue(GEPI, 684 ConstantExpr::getGetElementPtr(NewV, &Idxs[0], 685 Idxs.size())); 686 if (GEPI->use_empty()) { 687 Changed = true; 688 GEPI->eraseFromParent(); 689 } 690 } 691 } 692 693 return Changed; 694} 695 696 697/// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null 698/// value stored into it. If there are uses of the loaded value that would trap 699/// if the loaded value is dynamically null, then we know that they cannot be 700/// reachable with a null optimize away the load. 701static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV) { 702 std::vector<LoadInst*> Loads; 703 bool Changed = false; 704 705 // Replace all uses of loads with uses of uses of the stored value. 706 for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); 707 GUI != E; ++GUI) 708 if (LoadInst *LI = dyn_cast<LoadInst>(*GUI)) { 709 Loads.push_back(LI); 710 Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV); 711 } else { 712 // If we get here we could have stores, selects, or phi nodes whose values 713 // are loaded. 714 assert((isa<StoreInst>(*GUI) || isa<PHINode>(*GUI) || 715 isa<SelectInst>(*GUI) || isa<ConstantExpr>(*GUI)) && 716 "Only expect load and stores!"); 717 } 718 719 if (Changed) { 720 DOUT << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV; 721 ++NumGlobUses; 722 } 723 724 // Delete all of the loads we can, keeping track of whether we nuked them all! 725 bool AllLoadsGone = true; 726 while (!Loads.empty()) { 727 LoadInst *L = Loads.back(); 728 if (L->use_empty()) { 729 L->eraseFromParent(); 730 Changed = true; 731 } else { 732 AllLoadsGone = false; 733 } 734 Loads.pop_back(); 735 } 736 737 // If we nuked all of the loads, then none of the stores are needed either, 738 // nor is the global. 739 if (AllLoadsGone) { 740 DOUT << " *** GLOBAL NOW DEAD!\n"; 741 CleanupConstantGlobalUsers(GV, 0); 742 if (GV->use_empty()) { 743 GV->eraseFromParent(); 744 ++NumDeleted; 745 } 746 Changed = true; 747 } 748 return Changed; 749} 750 751/// ConstantPropUsersOf - Walk the use list of V, constant folding all of the 752/// instructions that are foldable. 753static void ConstantPropUsersOf(Value *V) { 754 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) 755 if (Instruction *I = dyn_cast<Instruction>(*UI++)) 756 if (Constant *NewC = ConstantFoldInstruction(I)) { 757 I->replaceAllUsesWith(NewC); 758 759 // Advance UI to the next non-I use to avoid invalidating it! 760 // Instructions could multiply use V. 761 while (UI != E && *UI == I) 762 ++UI; 763 I->eraseFromParent(); 764 } 765} 766 767/// OptimizeGlobalAddressOfMalloc - This function takes the specified global 768/// variable, and transforms the program as if it always contained the result of 769/// the specified malloc. Because it is always the result of the specified 770/// malloc, there is no reason to actually DO the malloc. Instead, turn the 771/// malloc into a global, and any loads of GV as uses of the new global. 772static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, 773 MallocInst *MI) { 774 DOUT << "PROMOTING MALLOC GLOBAL: " << *GV << " MALLOC = " << *MI; 775 ConstantInt *NElements = cast<ConstantInt>(MI->getArraySize()); 776 777 if (NElements->getZExtValue() != 1) { 778 // If we have an array allocation, transform it to a single element 779 // allocation to make the code below simpler. 780 Type *NewTy = ArrayType::get(MI->getAllocatedType(), 781 NElements->getZExtValue()); 782 MallocInst *NewMI = 783 new MallocInst(NewTy, Constant::getNullValue(Type::Int32Ty), 784 MI->getAlignment(), MI->getName(), MI); 785 Value* Indices[2]; 786 Indices[0] = Indices[1] = Constant::getNullValue(Type::Int32Ty); 787 Value *NewGEP = new GetElementPtrInst(NewMI, Indices, Indices + 2, 788 NewMI->getName()+".el0", MI); 789 MI->replaceAllUsesWith(NewGEP); 790 MI->eraseFromParent(); 791 MI = NewMI; 792 } 793 794 // Create the new global variable. The contents of the malloc'd memory is 795 // undefined, so initialize with an undef value. 796 Constant *Init = UndefValue::get(MI->getAllocatedType()); 797 GlobalVariable *NewGV = new GlobalVariable(MI->getAllocatedType(), false, 798 GlobalValue::InternalLinkage, Init, 799 GV->getName()+".body", 800 (Module *)NULL, 801 GV->isThreadLocal()); 802 GV->getParent()->getGlobalList().insert(GV, NewGV); 803 804 // Anything that used the malloc now uses the global directly. 805 MI->replaceAllUsesWith(NewGV); 806 807 Constant *RepValue = NewGV; 808 if (NewGV->getType() != GV->getType()->getElementType()) 809 RepValue = ConstantExpr::getBitCast(RepValue, 810 GV->getType()->getElementType()); 811 812 // If there is a comparison against null, we will insert a global bool to 813 // keep track of whether the global was initialized yet or not. 814 GlobalVariable *InitBool = 815 new GlobalVariable(Type::Int1Ty, false, GlobalValue::InternalLinkage, 816 ConstantInt::getFalse(), GV->getName()+".init", 817 (Module *)NULL, GV->isThreadLocal()); 818 bool InitBoolUsed = false; 819 820 // Loop over all uses of GV, processing them in turn. 821 std::vector<StoreInst*> Stores; 822 while (!GV->use_empty()) 823 if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) { 824 while (!LI->use_empty()) { 825 Use &LoadUse = LI->use_begin().getUse(); 826 if (!isa<ICmpInst>(LoadUse.getUser())) 827 LoadUse = RepValue; 828 else { 829 ICmpInst *CI = cast<ICmpInst>(LoadUse.getUser()); 830 // Replace the cmp X, 0 with a use of the bool value. 831 Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", CI); 832 InitBoolUsed = true; 833 switch (CI->getPredicate()) { 834 default: assert(0 && "Unknown ICmp Predicate!"); 835 case ICmpInst::ICMP_ULT: 836 case ICmpInst::ICMP_SLT: 837 LV = ConstantInt::getFalse(); // X < null -> always false 838 break; 839 case ICmpInst::ICMP_ULE: 840 case ICmpInst::ICMP_SLE: 841 case ICmpInst::ICMP_EQ: 842 LV = BinaryOperator::createNot(LV, "notinit", CI); 843 break; 844 case ICmpInst::ICMP_NE: 845 case ICmpInst::ICMP_UGE: 846 case ICmpInst::ICMP_SGE: 847 case ICmpInst::ICMP_UGT: 848 case ICmpInst::ICMP_SGT: 849 break; // no change. 850 } 851 CI->replaceAllUsesWith(LV); 852 CI->eraseFromParent(); 853 } 854 } 855 LI->eraseFromParent(); 856 } else { 857 StoreInst *SI = cast<StoreInst>(GV->use_back()); 858 // The global is initialized when the store to it occurs. 859 new StoreInst(ConstantInt::getTrue(), InitBool, SI); 860 SI->eraseFromParent(); 861 } 862 863 // If the initialization boolean was used, insert it, otherwise delete it. 864 if (!InitBoolUsed) { 865 while (!InitBool->use_empty()) // Delete initializations 866 cast<Instruction>(InitBool->use_back())->eraseFromParent(); 867 delete InitBool; 868 } else 869 GV->getParent()->getGlobalList().insert(GV, InitBool); 870 871 872 // Now the GV is dead, nuke it and the malloc. 873 GV->eraseFromParent(); 874 MI->eraseFromParent(); 875 876 // To further other optimizations, loop over all users of NewGV and try to 877 // constant prop them. This will promote GEP instructions with constant 878 // indices into GEP constant-exprs, which will allow global-opt to hack on it. 879 ConstantPropUsersOf(NewGV); 880 if (RepValue != NewGV) 881 ConstantPropUsersOf(RepValue); 882 883 return NewGV; 884} 885 886/// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking 887/// to make sure that there are no complex uses of V. We permit simple things 888/// like dereferencing the pointer, but not storing through the address, unless 889/// it is to the specified global. 890static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Instruction *V, 891 GlobalVariable *GV, 892 SmallPtrSet<PHINode*, 8> &PHIs) { 893 for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) 894 if (isa<LoadInst>(*UI) || isa<CmpInst>(*UI)) { 895 // Fine, ignore. 896 } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 897 if (SI->getOperand(0) == V && SI->getOperand(1) != GV) 898 return false; // Storing the pointer itself... bad. 899 // Otherwise, storing through it, or storing into GV... fine. 900 } else if (isa<GetElementPtrInst>(*UI)) { 901 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(cast<Instruction>(*UI), 902 GV, PHIs)) 903 return false; 904 } else if (PHINode *PN = dyn_cast<PHINode>(*UI)) { 905 // PHIs are ok if all uses are ok. Don't infinitely recurse through PHI 906 // cycles. 907 if (PHIs.insert(PN)) 908 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs)) 909 return false; 910 } else { 911 return false; 912 } 913 return true; 914} 915 916/// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV 917/// somewhere. Transform all uses of the allocation into loads from the 918/// global and uses of the resultant pointer. Further, delete the store into 919/// GV. This assumes that these value pass the 920/// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate. 921static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc, 922 GlobalVariable *GV) { 923 while (!Alloc->use_empty()) { 924 Instruction *U = cast<Instruction>(*Alloc->use_begin()); 925 Instruction *InsertPt = U; 926 if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 927 // If this is the store of the allocation into the global, remove it. 928 if (SI->getOperand(1) == GV) { 929 SI->eraseFromParent(); 930 continue; 931 } 932 } else if (PHINode *PN = dyn_cast<PHINode>(U)) { 933 // Insert the load in the corresponding predecessor, not right before the 934 // PHI. 935 unsigned PredNo = Alloc->use_begin().getOperandNo()/2; 936 InsertPt = PN->getIncomingBlock(PredNo)->getTerminator(); 937 } 938 939 // Insert a load from the global, and use it instead of the malloc. 940 Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt); 941 U->replaceUsesOfWith(Alloc, NL); 942 } 943} 944 945/// GlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from 946/// GV are simple enough to perform HeapSRA, return true. 947static bool GlobalLoadUsesSimpleEnoughForHeapSRA(GlobalVariable *GV, 948 MallocInst *MI) { 949 for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E; 950 ++UI) 951 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 952 // We permit two users of the load: setcc comparing against the null 953 // pointer, and a getelementptr of a specific form. 954 for (Value::use_iterator UI = LI->use_begin(), E = LI->use_end(); UI != E; 955 ++UI) { 956 // Comparison against null is ok. 957 if (ICmpInst *ICI = dyn_cast<ICmpInst>(*UI)) { 958 if (!isa<ConstantPointerNull>(ICI->getOperand(1))) 959 return false; 960 continue; 961 } 962 963 // getelementptr is also ok, but only a simple form. 964 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) { 965 // Must index into the array and into the struct. 966 if (GEPI->getNumOperands() < 3) 967 return false; 968 969 // Otherwise the GEP is ok. 970 continue; 971 } 972 973 if (PHINode *PN = dyn_cast<PHINode>(*UI)) { 974 // We have a phi of a load from the global. We can only handle this 975 // if the other PHI'd values are actually the same. In this case, 976 // the rewriter will just drop the phi entirely. 977 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 978 Value *IV = PN->getIncomingValue(i); 979 if (IV == LI) continue; // Trivial the same. 980 981 // If the phi'd value is from the malloc that initializes the value, 982 // we can xform it. 983 if (IV == MI) continue; 984 985 // Otherwise, we don't know what it is. 986 return false; 987 } 988 return true; 989 } 990 991 // Otherwise we don't know what this is, not ok. 992 return false; 993 } 994 } 995 return true; 996} 997 998/// GetHeapSROALoad - Return the load for the specified field of the HeapSROA'd 999/// value, lazily creating it on demand. 1000static Value *GetHeapSROALoad(Instruction *Load, unsigned FieldNo, 1001 const std::vector<GlobalVariable*> &FieldGlobals, 1002 std::vector<Value *> &InsertedLoadsForPtr) { 1003 if (InsertedLoadsForPtr.size() <= FieldNo) 1004 InsertedLoadsForPtr.resize(FieldNo+1); 1005 if (InsertedLoadsForPtr[FieldNo] == 0) 1006 InsertedLoadsForPtr[FieldNo] = new LoadInst(FieldGlobals[FieldNo], 1007 Load->getName()+".f" + 1008 utostr(FieldNo), Load); 1009 return InsertedLoadsForPtr[FieldNo]; 1010} 1011 1012/// RewriteHeapSROALoadUser - Given a load instruction and a value derived from 1013/// the load, rewrite the derived value to use the HeapSRoA'd load. 1014static void RewriteHeapSROALoadUser(LoadInst *Load, Instruction *LoadUser, 1015 const std::vector<GlobalVariable*> &FieldGlobals, 1016 std::vector<Value *> &InsertedLoadsForPtr) { 1017 // If this is a comparison against null, handle it. 1018 if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) { 1019 assert(isa<ConstantPointerNull>(SCI->getOperand(1))); 1020 // If we have a setcc of the loaded pointer, we can use a setcc of any 1021 // field. 1022 Value *NPtr; 1023 if (InsertedLoadsForPtr.empty()) { 1024 NPtr = GetHeapSROALoad(Load, 0, FieldGlobals, InsertedLoadsForPtr); 1025 } else { 1026 NPtr = InsertedLoadsForPtr.back(); 1027 } 1028 1029 Value *New = new ICmpInst(SCI->getPredicate(), NPtr, 1030 Constant::getNullValue(NPtr->getType()), 1031 SCI->getName(), SCI); 1032 SCI->replaceAllUsesWith(New); 1033 SCI->eraseFromParent(); 1034 return; 1035 } 1036 1037 // Handle 'getelementptr Ptr, Idx, uint FieldNo ...' 1038 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) { 1039 assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2)) 1040 && "Unexpected GEPI!"); 1041 1042 // Load the pointer for this field. 1043 unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); 1044 Value *NewPtr = GetHeapSROALoad(Load, FieldNo, 1045 FieldGlobals, InsertedLoadsForPtr); 1046 1047 // Create the new GEP idx vector. 1048 SmallVector<Value*, 8> GEPIdx; 1049 GEPIdx.push_back(GEPI->getOperand(1)); 1050 GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end()); 1051 1052 Value *NGEPI = new GetElementPtrInst(NewPtr, GEPIdx.begin(), GEPIdx.end(), 1053 GEPI->getName(), GEPI); 1054 GEPI->replaceAllUsesWith(NGEPI); 1055 GEPI->eraseFromParent(); 1056 return; 1057 } 1058 1059 // Handle PHI nodes. PHI nodes must be merging in the same values, plus 1060 // potentially the original malloc. Insert phi nodes for each field, then 1061 // process uses of the PHI. 1062 PHINode *PN = cast<PHINode>(LoadUser); 1063 std::vector<Value *> PHIsForField; 1064 PHIsForField.resize(FieldGlobals.size()); 1065 for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 1066 Value *LoadV = GetHeapSROALoad(Load, i, FieldGlobals, InsertedLoadsForPtr); 1067 1068 PHINode *FieldPN = new PHINode(LoadV->getType(), 1069 PN->getName()+"."+utostr(i), PN); 1070 // Fill in the predecessor values. 1071 for (unsigned pred = 0, e = PN->getNumIncomingValues(); pred != e; ++pred) { 1072 // Each predecessor either uses the load or the original malloc. 1073 Value *InVal = PN->getIncomingValue(pred); 1074 BasicBlock *BB = PN->getIncomingBlock(pred); 1075 Value *NewVal; 1076 if (isa<MallocInst>(InVal)) { 1077 // Insert a reload from the global in the predecessor. 1078 NewVal = GetHeapSROALoad(BB->getTerminator(), i, FieldGlobals, 1079 PHIsForField); 1080 } else { 1081 NewVal = InsertedLoadsForPtr[i]; 1082 } 1083 FieldPN->addIncoming(NewVal, BB); 1084 } 1085 PHIsForField[i] = FieldPN; 1086 } 1087 1088 // Since PHIsForField specifies a phi for every input value, the lazy inserter 1089 // will never insert a load. 1090 while (!PN->use_empty()) 1091 RewriteHeapSROALoadUser(Load, PN->use_back(), FieldGlobals, PHIsForField); 1092 PN->eraseFromParent(); 1093} 1094 1095/// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global. Ptr 1096/// is a value loaded from the global. Eliminate all uses of Ptr, making them 1097/// use FieldGlobals instead. All uses of loaded values satisfy 1098/// GlobalLoadUsesSimpleEnoughForHeapSRA. 1099static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load, 1100 const std::vector<GlobalVariable*> &FieldGlobals) { 1101 std::vector<Value *> InsertedLoadsForPtr; 1102 //InsertedLoadsForPtr.resize(FieldGlobals.size()); 1103 while (!Load->use_empty()) 1104 RewriteHeapSROALoadUser(Load, Load->use_back(), 1105 FieldGlobals, InsertedLoadsForPtr); 1106} 1107 1108/// PerformHeapAllocSRoA - MI is an allocation of an array of structures. Break 1109/// it up into multiple allocations of arrays of the fields. 1110static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, MallocInst *MI){ 1111 DOUT << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *MI; 1112 const StructType *STy = cast<StructType>(MI->getAllocatedType()); 1113 1114 // There is guaranteed to be at least one use of the malloc (storing 1115 // it into GV). If there are other uses, change them to be uses of 1116 // the global to simplify later code. This also deletes the store 1117 // into GV. 1118 ReplaceUsesOfMallocWithGlobal(MI, GV); 1119 1120 // Okay, at this point, there are no users of the malloc. Insert N 1121 // new mallocs at the same place as MI, and N globals. 1122 std::vector<GlobalVariable*> FieldGlobals; 1123 std::vector<MallocInst*> FieldMallocs; 1124 1125 for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){ 1126 const Type *FieldTy = STy->getElementType(FieldNo); 1127 const Type *PFieldTy = PointerType::getUnqual(FieldTy); 1128 1129 GlobalVariable *NGV = 1130 new GlobalVariable(PFieldTy, false, GlobalValue::InternalLinkage, 1131 Constant::getNullValue(PFieldTy), 1132 GV->getName() + ".f" + utostr(FieldNo), GV, 1133 GV->isThreadLocal()); 1134 FieldGlobals.push_back(NGV); 1135 1136 MallocInst *NMI = new MallocInst(FieldTy, MI->getArraySize(), 1137 MI->getName() + ".f" + utostr(FieldNo),MI); 1138 FieldMallocs.push_back(NMI); 1139 new StoreInst(NMI, NGV, MI); 1140 } 1141 1142 // The tricky aspect of this transformation is handling the case when malloc 1143 // fails. In the original code, malloc failing would set the result pointer 1144 // of malloc to null. In this case, some mallocs could succeed and others 1145 // could fail. As such, we emit code that looks like this: 1146 // F0 = malloc(field0) 1147 // F1 = malloc(field1) 1148 // F2 = malloc(field2) 1149 // if (F0 == 0 || F1 == 0 || F2 == 0) { 1150 // if (F0) { free(F0); F0 = 0; } 1151 // if (F1) { free(F1); F1 = 0; } 1152 // if (F2) { free(F2); F2 = 0; } 1153 // } 1154 Value *RunningOr = 0; 1155 for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) { 1156 Value *Cond = new ICmpInst(ICmpInst::ICMP_EQ, FieldMallocs[i], 1157 Constant::getNullValue(FieldMallocs[i]->getType()), 1158 "isnull", MI); 1159 if (!RunningOr) 1160 RunningOr = Cond; // First seteq 1161 else 1162 RunningOr = BinaryOperator::createOr(RunningOr, Cond, "tmp", MI); 1163 } 1164 1165 // Split the basic block at the old malloc. 1166 BasicBlock *OrigBB = MI->getParent(); 1167 BasicBlock *ContBB = OrigBB->splitBasicBlock(MI, "malloc_cont"); 1168 1169 // Create the block to check the first condition. Put all these blocks at the 1170 // end of the function as they are unlikely to be executed. 1171 BasicBlock *NullPtrBlock = new BasicBlock("malloc_ret_null", 1172 OrigBB->getParent()); 1173 1174 // Remove the uncond branch from OrigBB to ContBB, turning it into a cond 1175 // branch on RunningOr. 1176 OrigBB->getTerminator()->eraseFromParent(); 1177 new BranchInst(NullPtrBlock, ContBB, RunningOr, OrigBB); 1178 1179 // Within the NullPtrBlock, we need to emit a comparison and branch for each 1180 // pointer, because some may be null while others are not. 1181 for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 1182 Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock); 1183 Value *Cmp = new ICmpInst(ICmpInst::ICMP_NE, GVVal, 1184 Constant::getNullValue(GVVal->getType()), 1185 "tmp", NullPtrBlock); 1186 BasicBlock *FreeBlock = new BasicBlock("free_it", OrigBB->getParent()); 1187 BasicBlock *NextBlock = new BasicBlock("next", OrigBB->getParent()); 1188 new BranchInst(FreeBlock, NextBlock, Cmp, NullPtrBlock); 1189 1190 // Fill in FreeBlock. 1191 new FreeInst(GVVal, FreeBlock); 1192 new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i], 1193 FreeBlock); 1194 new BranchInst(NextBlock, FreeBlock); 1195 1196 NullPtrBlock = NextBlock; 1197 } 1198 1199 new BranchInst(ContBB, NullPtrBlock); 1200 1201 1202 // MI is no longer needed, remove it. 1203 MI->eraseFromParent(); 1204 1205 1206 // Okay, the malloc site is completely handled. All of the uses of GV are now 1207 // loads, and all uses of those loads are simple. Rewrite them to use loads 1208 // of the per-field globals instead. 1209 while (!GV->use_empty()) { 1210 if (LoadInst *LI = dyn_cast<LoadInst>(GV->use_back())) { 1211 RewriteUsesOfLoadForHeapSRoA(LI, FieldGlobals); 1212 LI->eraseFromParent(); 1213 } else { 1214 // Must be a store of null. 1215 StoreInst *SI = cast<StoreInst>(GV->use_back()); 1216 assert(isa<Constant>(SI->getOperand(0)) && 1217 cast<Constant>(SI->getOperand(0))->isNullValue() && 1218 "Unexpected heap-sra user!"); 1219 1220 // Insert a store of null into each global. 1221 for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 1222 Constant *Null = 1223 Constant::getNullValue(FieldGlobals[i]->getType()->getElementType()); 1224 new StoreInst(Null, FieldGlobals[i], SI); 1225 } 1226 // Erase the original store. 1227 SI->eraseFromParent(); 1228 } 1229 } 1230 1231 // The old global is now dead, remove it. 1232 GV->eraseFromParent(); 1233 1234 ++NumHeapSRA; 1235 return FieldGlobals[0]; 1236} 1237 1238 1239// OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge 1240// that only one value (besides its initializer) is ever stored to the global. 1241static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, 1242 Module::global_iterator &GVI, 1243 TargetData &TD) { 1244 if (CastInst *CI = dyn_cast<CastInst>(StoredOnceVal)) 1245 StoredOnceVal = CI->getOperand(0); 1246 else if (GetElementPtrInst *GEPI =dyn_cast<GetElementPtrInst>(StoredOnceVal)){ 1247 // "getelementptr Ptr, 0, 0, 0" is really just a cast. 1248 bool IsJustACast = true; 1249 for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i) 1250 if (!isa<Constant>(GEPI->getOperand(i)) || 1251 !cast<Constant>(GEPI->getOperand(i))->isNullValue()) { 1252 IsJustACast = false; 1253 break; 1254 } 1255 if (IsJustACast) 1256 StoredOnceVal = GEPI->getOperand(0); 1257 } 1258 1259 // If we are dealing with a pointer global that is initialized to null and 1260 // only has one (non-null) value stored into it, then we can optimize any 1261 // users of the loaded value (often calls and loads) that would trap if the 1262 // value was null. 1263 if (isa<PointerType>(GV->getInitializer()->getType()) && 1264 GV->getInitializer()->isNullValue()) { 1265 if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) { 1266 if (GV->getInitializer()->getType() != SOVC->getType()) 1267 SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); 1268 1269 // Optimize away any trapping uses of the loaded value. 1270 if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC)) 1271 return true; 1272 } else if (MallocInst *MI = dyn_cast<MallocInst>(StoredOnceVal)) { 1273 // If this is a malloc of an abstract type, don't touch it. 1274 if (!MI->getAllocatedType()->isSized()) 1275 return false; 1276 1277 // We can't optimize this global unless all uses of it are *known* to be 1278 // of the malloc value, not of the null initializer value (consider a use 1279 // that compares the global's value against zero to see if the malloc has 1280 // been reached). To do this, we check to see if all uses of the global 1281 // would trap if the global were null: this proves that they must all 1282 // happen after the malloc. 1283 if (!AllUsesOfLoadedValueWillTrapIfNull(GV)) 1284 return false; 1285 1286 // We can't optimize this if the malloc itself is used in a complex way, 1287 // for example, being stored into multiple globals. This allows the 1288 // malloc to be stored into the specified global, loaded setcc'd, and 1289 // GEP'd. These are all things we could transform to using the global 1290 // for. 1291 { 1292 SmallPtrSet<PHINode*, 8> PHIs; 1293 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(MI, GV, PHIs)) 1294 return false; 1295 } 1296 1297 1298 // If we have a global that is only initialized with a fixed size malloc, 1299 // transform the program to use global memory instead of malloc'd memory. 1300 // This eliminates dynamic allocation, avoids an indirection accessing the 1301 // data, and exposes the resultant global to further GlobalOpt. 1302 if (ConstantInt *NElements = dyn_cast<ConstantInt>(MI->getArraySize())) { 1303 // Restrict this transformation to only working on small allocations 1304 // (2048 bytes currently), as we don't want to introduce a 16M global or 1305 // something. 1306 if (NElements->getZExtValue()* 1307 TD.getABITypeSize(MI->getAllocatedType()) < 2048) { 1308 GVI = OptimizeGlobalAddressOfMalloc(GV, MI); 1309 return true; 1310 } 1311 } 1312 1313 // If the allocation is an array of structures, consider transforming this 1314 // into multiple malloc'd arrays, one for each field. This is basically 1315 // SRoA for malloc'd memory. 1316 if (const StructType *AllocTy = 1317 dyn_cast<StructType>(MI->getAllocatedType())) { 1318 // This the structure has an unreasonable number of fields, leave it 1319 // alone. 1320 if (AllocTy->getNumElements() <= 16 && AllocTy->getNumElements() > 0 && 1321 GlobalLoadUsesSimpleEnoughForHeapSRA(GV, MI)) { 1322 GVI = PerformHeapAllocSRoA(GV, MI); 1323 return true; 1324 } 1325 } 1326 } 1327 } 1328 1329 return false; 1330} 1331 1332/// TryToShrinkGlobalToBoolean - At this point, we have learned that the only 1333/// two values ever stored into GV are its initializer and OtherVal. See if we 1334/// can shrink the global into a boolean and select between the two values 1335/// whenever it is used. This exposes the values to other scalar optimizations. 1336static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { 1337 const Type *GVElType = GV->getType()->getElementType(); 1338 1339 // If GVElType is already i1, it is already shrunk. If the type of the GV is 1340 // an FP value or vector, don't do this optimization because a select between 1341 // them is very expensive and unlikely to lead to later simplification. 1342 if (GVElType == Type::Int1Ty || GVElType->isFloatingPoint() || 1343 isa<VectorType>(GVElType)) 1344 return false; 1345 1346 // Walk the use list of the global seeing if all the uses are load or store. 1347 // If there is anything else, bail out. 1348 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I) 1349 if (!isa<LoadInst>(I) && !isa<StoreInst>(I)) 1350 return false; 1351 1352 DOUT << " *** SHRINKING TO BOOL: " << *GV; 1353 1354 // Create the new global, initializing it to false. 1355 GlobalVariable *NewGV = new GlobalVariable(Type::Int1Ty, false, 1356 GlobalValue::InternalLinkage, ConstantInt::getFalse(), 1357 GV->getName()+".b", 1358 (Module *)NULL, 1359 GV->isThreadLocal()); 1360 GV->getParent()->getGlobalList().insert(GV, NewGV); 1361 1362 Constant *InitVal = GV->getInitializer(); 1363 assert(InitVal->getType() != Type::Int1Ty && "No reason to shrink to bool!"); 1364 1365 // If initialized to zero and storing one into the global, we can use a cast 1366 // instead of a select to synthesize the desired value. 1367 bool IsOneZero = false; 1368 if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) 1369 IsOneZero = InitVal->isNullValue() && CI->isOne(); 1370 1371 while (!GV->use_empty()) { 1372 Instruction *UI = cast<Instruction>(GV->use_back()); 1373 if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 1374 // Change the store into a boolean store. 1375 bool StoringOther = SI->getOperand(0) == OtherVal; 1376 // Only do this if we weren't storing a loaded value. 1377 Value *StoreVal; 1378 if (StoringOther || SI->getOperand(0) == InitVal) 1379 StoreVal = ConstantInt::get(Type::Int1Ty, StoringOther); 1380 else { 1381 // Otherwise, we are storing a previously loaded copy. To do this, 1382 // change the copy from copying the original value to just copying the 1383 // bool. 1384 Instruction *StoredVal = cast<Instruction>(SI->getOperand(0)); 1385 1386 // If we're already replaced the input, StoredVal will be a cast or 1387 // select instruction. If not, it will be a load of the original 1388 // global. 1389 if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) { 1390 assert(LI->getOperand(0) == GV && "Not a copy!"); 1391 // Insert a new load, to preserve the saved value. 1392 StoreVal = new LoadInst(NewGV, LI->getName()+".b", LI); 1393 } else { 1394 assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && 1395 "This is not a form that we understand!"); 1396 StoreVal = StoredVal->getOperand(0); 1397 assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!"); 1398 } 1399 } 1400 new StoreInst(StoreVal, NewGV, SI); 1401 } else { 1402 // Change the load into a load of bool then a select. 1403 LoadInst *LI = cast<LoadInst>(UI); 1404 LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", LI); 1405 Value *NSI; 1406 if (IsOneZero) 1407 NSI = new ZExtInst(NLI, LI->getType(), "", LI); 1408 else 1409 NSI = new SelectInst(NLI, OtherVal, InitVal, "", LI); 1410 NSI->takeName(LI); 1411 LI->replaceAllUsesWith(NSI); 1412 } 1413 UI->eraseFromParent(); 1414 } 1415 1416 GV->eraseFromParent(); 1417 return true; 1418} 1419 1420 1421/// ProcessInternalGlobal - Analyze the specified global variable and optimize 1422/// it if possible. If we make a change, return true. 1423bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, 1424 Module::global_iterator &GVI) { 1425 std::set<PHINode*> PHIUsers; 1426 GlobalStatus GS; 1427 GV->removeDeadConstantUsers(); 1428 1429 if (GV->use_empty()) { 1430 DOUT << "GLOBAL DEAD: " << *GV; 1431 GV->eraseFromParent(); 1432 ++NumDeleted; 1433 return true; 1434 } 1435 1436 if (!AnalyzeGlobal(GV, GS, PHIUsers)) { 1437#if 0 1438 cerr << "Global: " << *GV; 1439 cerr << " isLoaded = " << GS.isLoaded << "\n"; 1440 cerr << " StoredType = "; 1441 switch (GS.StoredType) { 1442 case GlobalStatus::NotStored: cerr << "NEVER STORED\n"; break; 1443 case GlobalStatus::isInitializerStored: cerr << "INIT STORED\n"; break; 1444 case GlobalStatus::isStoredOnce: cerr << "STORED ONCE\n"; break; 1445 case GlobalStatus::isStored: cerr << "stored\n"; break; 1446 } 1447 if (GS.StoredType == GlobalStatus::isStoredOnce && GS.StoredOnceValue) 1448 cerr << " StoredOnceValue = " << *GS.StoredOnceValue << "\n"; 1449 if (GS.AccessingFunction && !GS.HasMultipleAccessingFunctions) 1450 cerr << " AccessingFunction = " << GS.AccessingFunction->getName() 1451 << "\n"; 1452 cerr << " HasMultipleAccessingFunctions = " 1453 << GS.HasMultipleAccessingFunctions << "\n"; 1454 cerr << " HasNonInstructionUser = " << GS.HasNonInstructionUser<<"\n"; 1455 cerr << "\n"; 1456#endif 1457 1458 // If this is a first class global and has only one accessing function 1459 // and this function is main (which we know is not recursive we can make 1460 // this global a local variable) we replace the global with a local alloca 1461 // in this function. 1462 // 1463 // NOTE: It doesn't make sense to promote non first class types since we 1464 // are just replacing static memory to stack memory. 1465 if (!GS.HasMultipleAccessingFunctions && 1466 GS.AccessingFunction && !GS.HasNonInstructionUser && 1467 GV->getType()->getElementType()->isFirstClassType() && 1468 GS.AccessingFunction->getName() == "main" && 1469 GS.AccessingFunction->hasExternalLinkage()) { 1470 DOUT << "LOCALIZING GLOBAL: " << *GV; 1471 Instruction* FirstI = GS.AccessingFunction->getEntryBlock().begin(); 1472 const Type* ElemTy = GV->getType()->getElementType(); 1473 // FIXME: Pass Global's alignment when globals have alignment 1474 AllocaInst* Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), FirstI); 1475 if (!isa<UndefValue>(GV->getInitializer())) 1476 new StoreInst(GV->getInitializer(), Alloca, FirstI); 1477 1478 GV->replaceAllUsesWith(Alloca); 1479 GV->eraseFromParent(); 1480 ++NumLocalized; 1481 return true; 1482 } 1483 1484 // If the global is never loaded (but may be stored to), it is dead. 1485 // Delete it now. 1486 if (!GS.isLoaded) { 1487 DOUT << "GLOBAL NEVER LOADED: " << *GV; 1488 1489 // Delete any stores we can find to the global. We may not be able to 1490 // make it completely dead though. 1491 bool Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer()); 1492 1493 // If the global is dead now, delete it. 1494 if (GV->use_empty()) { 1495 GV->eraseFromParent(); 1496 ++NumDeleted; 1497 Changed = true; 1498 } 1499 return Changed; 1500 1501 } else if (GS.StoredType <= GlobalStatus::isInitializerStored) { 1502 DOUT << "MARKING CONSTANT: " << *GV; 1503 GV->setConstant(true); 1504 1505 // Clean up any obviously simplifiable users now. 1506 CleanupConstantGlobalUsers(GV, GV->getInitializer()); 1507 1508 // If the global is dead now, just nuke it. 1509 if (GV->use_empty()) { 1510 DOUT << " *** Marking constant allowed us to simplify " 1511 << "all users and delete global!\n"; 1512 GV->eraseFromParent(); 1513 ++NumDeleted; 1514 } 1515 1516 ++NumMarked; 1517 return true; 1518 } else if (!GV->getInitializer()->getType()->isFirstClassType()) { 1519 if (GlobalVariable *FirstNewGV = SRAGlobal(GV)) { 1520 GVI = FirstNewGV; // Don't skip the newly produced globals! 1521 return true; 1522 } 1523 } else if (GS.StoredType == GlobalStatus::isStoredOnce) { 1524 // If the initial value for the global was an undef value, and if only 1525 // one other value was stored into it, we can just change the 1526 // initializer to be an undef value, then delete all stores to the 1527 // global. This allows us to mark it constant. 1528 if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 1529 if (isa<UndefValue>(GV->getInitializer())) { 1530 // Change the initial value here. 1531 GV->setInitializer(SOVConstant); 1532 1533 // Clean up any obviously simplifiable users now. 1534 CleanupConstantGlobalUsers(GV, GV->getInitializer()); 1535 1536 if (GV->use_empty()) { 1537 DOUT << " *** Substituting initializer allowed us to " 1538 << "simplify all users and delete global!\n"; 1539 GV->eraseFromParent(); 1540 ++NumDeleted; 1541 } else { 1542 GVI = GV; 1543 } 1544 ++NumSubstitute; 1545 return true; 1546 } 1547 1548 // Try to optimize globals based on the knowledge that only one value 1549 // (besides its initializer) is ever stored to the global. 1550 if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GVI, 1551 getAnalysis<TargetData>())) 1552 return true; 1553 1554 // Otherwise, if the global was not a boolean, we can shrink it to be a 1555 // boolean. 1556 if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 1557 if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) { 1558 ++NumShrunkToBool; 1559 return true; 1560 } 1561 } 1562 } 1563 return false; 1564} 1565 1566/// OnlyCalledDirectly - Return true if the specified function is only called 1567/// directly. In other words, its address is never taken. 1568static bool OnlyCalledDirectly(Function *F) { 1569 for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 1570 Instruction *User = dyn_cast<Instruction>(*UI); 1571 if (!User) return false; 1572 if (!isa<CallInst>(User) && !isa<InvokeInst>(User)) return false; 1573 1574 // See if the function address is passed as an argument. 1575 for (unsigned i = 1, e = User->getNumOperands(); i != e; ++i) 1576 if (User->getOperand(i) == F) return false; 1577 } 1578 return true; 1579} 1580 1581/// ChangeCalleesToFastCall - Walk all of the direct calls of the specified 1582/// function, changing them to FastCC. 1583static void ChangeCalleesToFastCall(Function *F) { 1584 for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 1585 Instruction *User = cast<Instruction>(*UI); 1586 if (CallInst *CI = dyn_cast<CallInst>(User)) 1587 CI->setCallingConv(CallingConv::Fast); 1588 else 1589 cast<InvokeInst>(User)->setCallingConv(CallingConv::Fast); 1590 } 1591} 1592 1593bool GlobalOpt::OptimizeFunctions(Module &M) { 1594 bool Changed = false; 1595 // Optimize functions. 1596 for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) { 1597 Function *F = FI++; 1598 F->removeDeadConstantUsers(); 1599 if (F->use_empty() && (F->hasInternalLinkage() || 1600 F->hasLinkOnceLinkage())) { 1601 M.getFunctionList().erase(F); 1602 Changed = true; 1603 ++NumFnDeleted; 1604 } else if (F->hasInternalLinkage() && 1605 F->getCallingConv() == CallingConv::C && !F->isVarArg() && 1606 OnlyCalledDirectly(F)) { 1607 // If this function has C calling conventions, is not a varargs 1608 // function, and is only called directly, promote it to use the Fast 1609 // calling convention. 1610 F->setCallingConv(CallingConv::Fast); 1611 ChangeCalleesToFastCall(F); 1612 ++NumFastCallFns; 1613 Changed = true; 1614 } 1615 } 1616 return Changed; 1617} 1618 1619bool GlobalOpt::OptimizeGlobalVars(Module &M) { 1620 bool Changed = false; 1621 for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 1622 GVI != E; ) { 1623 GlobalVariable *GV = GVI++; 1624 if (!GV->isConstant() && GV->hasInternalLinkage() && 1625 GV->hasInitializer()) 1626 Changed |= ProcessInternalGlobal(GV, GVI); 1627 } 1628 return Changed; 1629} 1630 1631/// FindGlobalCtors - Find the llvm.globalctors list, verifying that all 1632/// initializers have an init priority of 65535. 1633GlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) { 1634 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 1635 I != E; ++I) 1636 if (I->getName() == "llvm.global_ctors") { 1637 // Found it, verify it's an array of { int, void()* }. 1638 const ArrayType *ATy =dyn_cast<ArrayType>(I->getType()->getElementType()); 1639 if (!ATy) return 0; 1640 const StructType *STy = dyn_cast<StructType>(ATy->getElementType()); 1641 if (!STy || STy->getNumElements() != 2 || 1642 STy->getElementType(0) != Type::Int32Ty) return 0; 1643 const PointerType *PFTy = dyn_cast<PointerType>(STy->getElementType(1)); 1644 if (!PFTy) return 0; 1645 const FunctionType *FTy = dyn_cast<FunctionType>(PFTy->getElementType()); 1646 if (!FTy || FTy->getReturnType() != Type::VoidTy || FTy->isVarArg() || 1647 FTy->getNumParams() != 0) 1648 return 0; 1649 1650 // Verify that the initializer is simple enough for us to handle. 1651 if (!I->hasInitializer()) return 0; 1652 ConstantArray *CA = dyn_cast<ConstantArray>(I->getInitializer()); 1653 if (!CA) return 0; 1654 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) 1655 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(CA->getOperand(i))) { 1656 if (isa<ConstantPointerNull>(CS->getOperand(1))) 1657 continue; 1658 1659 // Must have a function or null ptr. 1660 if (!isa<Function>(CS->getOperand(1))) 1661 return 0; 1662 1663 // Init priority must be standard. 1664 ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 1665 if (!CI || CI->getZExtValue() != 65535) 1666 return 0; 1667 } else { 1668 return 0; 1669 } 1670 1671 return I; 1672 } 1673 return 0; 1674} 1675 1676/// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand, 1677/// return a list of the functions and null terminator as a vector. 1678static std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) { 1679 ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); 1680 std::vector<Function*> Result; 1681 Result.reserve(CA->getNumOperands()); 1682 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) { 1683 ConstantStruct *CS = cast<ConstantStruct>(CA->getOperand(i)); 1684 Result.push_back(dyn_cast<Function>(CS->getOperand(1))); 1685 } 1686 return Result; 1687} 1688 1689/// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the 1690/// specified array, returning the new global to use. 1691static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, 1692 const std::vector<Function*> &Ctors) { 1693 // If we made a change, reassemble the initializer list. 1694 std::vector<Constant*> CSVals; 1695 CSVals.push_back(ConstantInt::get(Type::Int32Ty, 65535)); 1696 CSVals.push_back(0); 1697 1698 // Create the new init list. 1699 std::vector<Constant*> CAList; 1700 for (unsigned i = 0, e = Ctors.size(); i != e; ++i) { 1701 if (Ctors[i]) { 1702 CSVals[1] = Ctors[i]; 1703 } else { 1704 const Type *FTy = FunctionType::get(Type::VoidTy, 1705 std::vector<const Type*>(), false); 1706 const PointerType *PFTy = PointerType::getUnqual(FTy); 1707 CSVals[1] = Constant::getNullValue(PFTy); 1708 CSVals[0] = ConstantInt::get(Type::Int32Ty, 2147483647); 1709 } 1710 CAList.push_back(ConstantStruct::get(CSVals)); 1711 } 1712 1713 // Create the array initializer. 1714 const Type *StructTy = 1715 cast<ArrayType>(GCL->getType()->getElementType())->getElementType(); 1716 Constant *CA = ConstantArray::get(ArrayType::get(StructTy, CAList.size()), 1717 CAList); 1718 1719 // If we didn't change the number of elements, don't create a new GV. 1720 if (CA->getType() == GCL->getInitializer()->getType()) { 1721 GCL->setInitializer(CA); 1722 return GCL; 1723 } 1724 1725 // Create the new global and insert it next to the existing list. 1726 GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(), 1727 GCL->getLinkage(), CA, "", 1728 (Module *)NULL, 1729 GCL->isThreadLocal()); 1730 GCL->getParent()->getGlobalList().insert(GCL, NGV); 1731 NGV->takeName(GCL); 1732 1733 // Nuke the old list, replacing any uses with the new one. 1734 if (!GCL->use_empty()) { 1735 Constant *V = NGV; 1736 if (V->getType() != GCL->getType()) 1737 V = ConstantExpr::getBitCast(V, GCL->getType()); 1738 GCL->replaceAllUsesWith(V); 1739 } 1740 GCL->eraseFromParent(); 1741 1742 if (Ctors.size()) 1743 return NGV; 1744 else 1745 return 0; 1746} 1747 1748 1749static Constant *getVal(std::map<Value*, Constant*> &ComputedValues, 1750 Value *V) { 1751 if (Constant *CV = dyn_cast<Constant>(V)) return CV; 1752 Constant *R = ComputedValues[V]; 1753 assert(R && "Reference to an uncomputed value!"); 1754 return R; 1755} 1756 1757/// isSimpleEnoughPointerToCommit - Return true if this constant is simple 1758/// enough for us to understand. In particular, if it is a cast of something, 1759/// we punt. We basically just support direct accesses to globals and GEP's of 1760/// globals. This should be kept up to date with CommitValueTo. 1761static bool isSimpleEnoughPointerToCommit(Constant *C) { 1762 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) { 1763 if (!GV->hasExternalLinkage() && !GV->hasInternalLinkage()) 1764 return false; // do not allow weak/linkonce/dllimport/dllexport linkage. 1765 return !GV->isDeclaration(); // reject external globals. 1766 } 1767 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 1768 // Handle a constantexpr gep. 1769 if (CE->getOpcode() == Instruction::GetElementPtr && 1770 isa<GlobalVariable>(CE->getOperand(0))) { 1771 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 1772 if (!GV->hasExternalLinkage() && !GV->hasInternalLinkage()) 1773 return false; // do not allow weak/linkonce/dllimport/dllexport linkage. 1774 return GV->hasInitializer() && 1775 ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); 1776 } 1777 return false; 1778} 1779 1780/// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global 1781/// initializer. This returns 'Init' modified to reflect 'Val' stored into it. 1782/// At this point, the GEP operands of Addr [0, OpNo) have been stepped into. 1783static Constant *EvaluateStoreInto(Constant *Init, Constant *Val, 1784 ConstantExpr *Addr, unsigned OpNo) { 1785 // Base case of the recursion. 1786 if (OpNo == Addr->getNumOperands()) { 1787 assert(Val->getType() == Init->getType() && "Type mismatch!"); 1788 return Val; 1789 } 1790 1791 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) { 1792 std::vector<Constant*> Elts; 1793 1794 // Break up the constant into its elements. 1795 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) { 1796 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) 1797 Elts.push_back(CS->getOperand(i)); 1798 } else if (isa<ConstantAggregateZero>(Init)) { 1799 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 1800 Elts.push_back(Constant::getNullValue(STy->getElementType(i))); 1801 } else if (isa<UndefValue>(Init)) { 1802 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 1803 Elts.push_back(UndefValue::get(STy->getElementType(i))); 1804 } else { 1805 assert(0 && "This code is out of sync with " 1806 " ConstantFoldLoadThroughGEPConstantExpr"); 1807 } 1808 1809 // Replace the element that we are supposed to. 1810 ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo)); 1811 unsigned Idx = CU->getZExtValue(); 1812 assert(Idx < STy->getNumElements() && "Struct index out of range!"); 1813 Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1); 1814 1815 // Return the modified struct. 1816 return ConstantStruct::get(&Elts[0], Elts.size(), STy->isPacked()); 1817 } else { 1818 ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo)); 1819 const ArrayType *ATy = cast<ArrayType>(Init->getType()); 1820 1821 // Break up the array into elements. 1822 std::vector<Constant*> Elts; 1823 if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) { 1824 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) 1825 Elts.push_back(CA->getOperand(i)); 1826 } else if (isa<ConstantAggregateZero>(Init)) { 1827 Constant *Elt = Constant::getNullValue(ATy->getElementType()); 1828 Elts.assign(ATy->getNumElements(), Elt); 1829 } else if (isa<UndefValue>(Init)) { 1830 Constant *Elt = UndefValue::get(ATy->getElementType()); 1831 Elts.assign(ATy->getNumElements(), Elt); 1832 } else { 1833 assert(0 && "This code is out of sync with " 1834 " ConstantFoldLoadThroughGEPConstantExpr"); 1835 } 1836 1837 assert(CI->getZExtValue() < ATy->getNumElements()); 1838 Elts[CI->getZExtValue()] = 1839 EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1); 1840 return ConstantArray::get(ATy, Elts); 1841 } 1842} 1843 1844/// CommitValueTo - We have decided that Addr (which satisfies the predicate 1845/// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen. 1846static void CommitValueTo(Constant *Val, Constant *Addr) { 1847 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) { 1848 assert(GV->hasInitializer()); 1849 GV->setInitializer(Val); 1850 return; 1851 } 1852 1853 ConstantExpr *CE = cast<ConstantExpr>(Addr); 1854 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 1855 1856 Constant *Init = GV->getInitializer(); 1857 Init = EvaluateStoreInto(Init, Val, CE, 2); 1858 GV->setInitializer(Init); 1859} 1860 1861/// ComputeLoadResult - Return the value that would be computed by a load from 1862/// P after the stores reflected by 'memory' have been performed. If we can't 1863/// decide, return null. 1864static Constant *ComputeLoadResult(Constant *P, 1865 const std::map<Constant*, Constant*> &Memory) { 1866 // If this memory location has been recently stored, use the stored value: it 1867 // is the most up-to-date. 1868 std::map<Constant*, Constant*>::const_iterator I = Memory.find(P); 1869 if (I != Memory.end()) return I->second; 1870 1871 // Access it. 1872 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { 1873 if (GV->hasInitializer()) 1874 return GV->getInitializer(); 1875 return 0; 1876 } 1877 1878 // Handle a constantexpr getelementptr. 1879 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) 1880 if (CE->getOpcode() == Instruction::GetElementPtr && 1881 isa<GlobalVariable>(CE->getOperand(0))) { 1882 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 1883 if (GV->hasInitializer()) 1884 return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); 1885 } 1886 1887 return 0; // don't know how to evaluate. 1888} 1889 1890/// EvaluateFunction - Evaluate a call to function F, returning true if 1891/// successful, false if we can't evaluate it. ActualArgs contains the formal 1892/// arguments for the function. 1893static bool EvaluateFunction(Function *F, Constant *&RetVal, 1894 const std::vector<Constant*> &ActualArgs, 1895 std::vector<Function*> &CallStack, 1896 std::map<Constant*, Constant*> &MutatedMemory, 1897 std::vector<GlobalVariable*> &AllocaTmps) { 1898 // Check to see if this function is already executing (recursion). If so, 1899 // bail out. TODO: we might want to accept limited recursion. 1900 if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end()) 1901 return false; 1902 1903 CallStack.push_back(F); 1904 1905 /// Values - As we compute SSA register values, we store their contents here. 1906 std::map<Value*, Constant*> Values; 1907 1908 // Initialize arguments to the incoming values specified. 1909 unsigned ArgNo = 0; 1910 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; 1911 ++AI, ++ArgNo) 1912 Values[AI] = ActualArgs[ArgNo]; 1913 1914 /// ExecutedBlocks - We only handle non-looping, non-recursive code. As such, 1915 /// we can only evaluate any one basic block at most once. This set keeps 1916 /// track of what we have executed so we can detect recursive cases etc. 1917 std::set<BasicBlock*> ExecutedBlocks; 1918 1919 // CurInst - The current instruction we're evaluating. 1920 BasicBlock::iterator CurInst = F->begin()->begin(); 1921 1922 // This is the main evaluation loop. 1923 while (1) { 1924 Constant *InstResult = 0; 1925 1926 if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) { 1927 if (SI->isVolatile()) return false; // no volatile accesses. 1928 Constant *Ptr = getVal(Values, SI->getOperand(1)); 1929 if (!isSimpleEnoughPointerToCommit(Ptr)) 1930 // If this is too complex for us to commit, reject it. 1931 return false; 1932 Constant *Val = getVal(Values, SI->getOperand(0)); 1933 MutatedMemory[Ptr] = Val; 1934 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) { 1935 InstResult = ConstantExpr::get(BO->getOpcode(), 1936 getVal(Values, BO->getOperand(0)), 1937 getVal(Values, BO->getOperand(1))); 1938 } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) { 1939 InstResult = ConstantExpr::getCompare(CI->getPredicate(), 1940 getVal(Values, CI->getOperand(0)), 1941 getVal(Values, CI->getOperand(1))); 1942 } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) { 1943 InstResult = ConstantExpr::getCast(CI->getOpcode(), 1944 getVal(Values, CI->getOperand(0)), 1945 CI->getType()); 1946 } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) { 1947 InstResult = ConstantExpr::getSelect(getVal(Values, SI->getOperand(0)), 1948 getVal(Values, SI->getOperand(1)), 1949 getVal(Values, SI->getOperand(2))); 1950 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) { 1951 Constant *P = getVal(Values, GEP->getOperand(0)); 1952 SmallVector<Constant*, 8> GEPOps; 1953 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i) 1954 GEPOps.push_back(getVal(Values, GEP->getOperand(i))); 1955 InstResult = ConstantExpr::getGetElementPtr(P, &GEPOps[0], GEPOps.size()); 1956 } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) { 1957 if (LI->isVolatile()) return false; // no volatile accesses. 1958 InstResult = ComputeLoadResult(getVal(Values, LI->getOperand(0)), 1959 MutatedMemory); 1960 if (InstResult == 0) return false; // Could not evaluate load. 1961 } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) { 1962 if (AI->isArrayAllocation()) return false; // Cannot handle array allocs. 1963 const Type *Ty = AI->getType()->getElementType(); 1964 AllocaTmps.push_back(new GlobalVariable(Ty, false, 1965 GlobalValue::InternalLinkage, 1966 UndefValue::get(Ty), 1967 AI->getName())); 1968 InstResult = AllocaTmps.back(); 1969 } else if (CallInst *CI = dyn_cast<CallInst>(CurInst)) { 1970 // Cannot handle inline asm. 1971 if (isa<InlineAsm>(CI->getOperand(0))) return false; 1972 1973 // Resolve function pointers. 1974 Function *Callee = dyn_cast<Function>(getVal(Values, CI->getOperand(0))); 1975 if (!Callee) return false; // Cannot resolve. 1976 1977 std::vector<Constant*> Formals; 1978 for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i) 1979 Formals.push_back(getVal(Values, CI->getOperand(i))); 1980 1981 if (Callee->isDeclaration()) { 1982 // If this is a function we can constant fold, do it. 1983 if (Constant *C = ConstantFoldCall(Callee, &Formals[0], 1984 Formals.size())) { 1985 InstResult = C; 1986 } else { 1987 return false; 1988 } 1989 } else { 1990 if (Callee->getFunctionType()->isVarArg()) 1991 return false; 1992 1993 Constant *RetVal; 1994 1995 // Execute the call, if successful, use the return value. 1996 if (!EvaluateFunction(Callee, RetVal, Formals, CallStack, 1997 MutatedMemory, AllocaTmps)) 1998 return false; 1999 InstResult = RetVal; 2000 } 2001 } else if (isa<TerminatorInst>(CurInst)) { 2002 BasicBlock *NewBB = 0; 2003 if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) { 2004 if (BI->isUnconditional()) { 2005 NewBB = BI->getSuccessor(0); 2006 } else { 2007 ConstantInt *Cond = 2008 dyn_cast<ConstantInt>(getVal(Values, BI->getCondition())); 2009 if (!Cond) return false; // Cannot determine. 2010 2011 NewBB = BI->getSuccessor(!Cond->getZExtValue()); 2012 } 2013 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) { 2014 ConstantInt *Val = 2015 dyn_cast<ConstantInt>(getVal(Values, SI->getCondition())); 2016 if (!Val) return false; // Cannot determine. 2017 NewBB = SI->getSuccessor(SI->findCaseValue(Val)); 2018 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(CurInst)) { 2019 if (RI->getNumOperands()) 2020 RetVal = getVal(Values, RI->getOperand(0)); 2021 2022 CallStack.pop_back(); // return from fn. 2023 return true; // We succeeded at evaluating this ctor! 2024 } else { 2025 // invoke, unwind, unreachable. 2026 return false; // Cannot handle this terminator. 2027 } 2028 2029 // Okay, we succeeded in evaluating this control flow. See if we have 2030 // executed the new block before. If so, we have a looping function, 2031 // which we cannot evaluate in reasonable time. 2032 if (!ExecutedBlocks.insert(NewBB).second) 2033 return false; // looped! 2034 2035 // Okay, we have never been in this block before. Check to see if there 2036 // are any PHI nodes. If so, evaluate them with information about where 2037 // we came from. 2038 BasicBlock *OldBB = CurInst->getParent(); 2039 CurInst = NewBB->begin(); 2040 PHINode *PN; 2041 for (; (PN = dyn_cast<PHINode>(CurInst)); ++CurInst) 2042 Values[PN] = getVal(Values, PN->getIncomingValueForBlock(OldBB)); 2043 2044 // Do NOT increment CurInst. We know that the terminator had no value. 2045 continue; 2046 } else { 2047 // Did not know how to evaluate this! 2048 return false; 2049 } 2050 2051 if (!CurInst->use_empty()) 2052 Values[CurInst] = InstResult; 2053 2054 // Advance program counter. 2055 ++CurInst; 2056 } 2057} 2058 2059/// EvaluateStaticConstructor - Evaluate static constructors in the function, if 2060/// we can. Return true if we can, false otherwise. 2061static bool EvaluateStaticConstructor(Function *F) { 2062 /// MutatedMemory - For each store we execute, we update this map. Loads 2063 /// check this to get the most up-to-date value. If evaluation is successful, 2064 /// this state is committed to the process. 2065 std::map<Constant*, Constant*> MutatedMemory; 2066 2067 /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable 2068 /// to represent its body. This vector is needed so we can delete the 2069 /// temporary globals when we are done. 2070 std::vector<GlobalVariable*> AllocaTmps; 2071 2072 /// CallStack - This is used to detect recursion. In pathological situations 2073 /// we could hit exponential behavior, but at least there is nothing 2074 /// unbounded. 2075 std::vector<Function*> CallStack; 2076 2077 // Call the function. 2078 Constant *RetValDummy; 2079 bool EvalSuccess = EvaluateFunction(F, RetValDummy, std::vector<Constant*>(), 2080 CallStack, MutatedMemory, AllocaTmps); 2081 if (EvalSuccess) { 2082 // We succeeded at evaluation: commit the result. 2083 DOUT << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" 2084 << F->getName() << "' to " << MutatedMemory.size() 2085 << " stores.\n"; 2086 for (std::map<Constant*, Constant*>::iterator I = MutatedMemory.begin(), 2087 E = MutatedMemory.end(); I != E; ++I) 2088 CommitValueTo(I->second, I->first); 2089 } 2090 2091 // At this point, we are done interpreting. If we created any 'alloca' 2092 // temporaries, release them now. 2093 while (!AllocaTmps.empty()) { 2094 GlobalVariable *Tmp = AllocaTmps.back(); 2095 AllocaTmps.pop_back(); 2096 2097 // If there are still users of the alloca, the program is doing something 2098 // silly, e.g. storing the address of the alloca somewhere and using it 2099 // later. Since this is undefined, we'll just make it be null. 2100 if (!Tmp->use_empty()) 2101 Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); 2102 delete Tmp; 2103 } 2104 2105 return EvalSuccess; 2106} 2107 2108 2109 2110/// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible. 2111/// Return true if anything changed. 2112bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) { 2113 std::vector<Function*> Ctors = ParseGlobalCtors(GCL); 2114 bool MadeChange = false; 2115 if (Ctors.empty()) return false; 2116 2117 // Loop over global ctors, optimizing them when we can. 2118 for (unsigned i = 0; i != Ctors.size(); ++i) { 2119 Function *F = Ctors[i]; 2120 // Found a null terminator in the middle of the list, prune off the rest of 2121 // the list. 2122 if (F == 0) { 2123 if (i != Ctors.size()-1) { 2124 Ctors.resize(i+1); 2125 MadeChange = true; 2126 } 2127 break; 2128 } 2129 2130 // We cannot simplify external ctor functions. 2131 if (F->empty()) continue; 2132 2133 // If we can evaluate the ctor at compile time, do. 2134 if (EvaluateStaticConstructor(F)) { 2135 Ctors.erase(Ctors.begin()+i); 2136 MadeChange = true; 2137 --i; 2138 ++NumCtorsEvaluated; 2139 continue; 2140 } 2141 } 2142 2143 if (!MadeChange) return false; 2144 2145 GCL = InstallGlobalCtors(GCL, Ctors); 2146 return true; 2147} 2148 2149 2150bool GlobalOpt::runOnModule(Module &M) { 2151 bool Changed = false; 2152 2153 // Try to find the llvm.globalctors list. 2154 GlobalVariable *GlobalCtors = FindGlobalCtors(M); 2155 2156 bool LocalChange = true; 2157 while (LocalChange) { 2158 LocalChange = false; 2159 2160 // Delete functions that are trivially dead, ccc -> fastcc 2161 LocalChange |= OptimizeFunctions(M); 2162 2163 // Optimize global_ctors list. 2164 if (GlobalCtors) 2165 LocalChange |= OptimizeGlobalCtorsList(GlobalCtors); 2166 2167 // Optimize non-address-taken globals. 2168 LocalChange |= OptimizeGlobalVars(M); 2169 Changed |= LocalChange; 2170 } 2171 2172 // TODO: Move all global ctors functions to the end of the module for code 2173 // layout. 2174 2175 return Changed; 2176} 2177