1193323Sed//===- GlobalOpt.cpp - Optimize Global Variables --------------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This pass transforms simple global variables that never have their address 11193323Sed// taken. If obviously true, it marks read/write globals as constant, deletes 12193323Sed// variables only stored to, etc. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#define DEBUG_TYPE "globalopt" 17193323Sed#include "llvm/Transforms/IPO.h" 18249423Sdim#include "llvm/ADT/DenseMap.h" 19249423Sdim#include "llvm/ADT/STLExtras.h" 20249423Sdim#include "llvm/ADT/SmallPtrSet.h" 21249423Sdim#include "llvm/ADT/SmallVector.h" 22249423Sdim#include "llvm/ADT/Statistic.h" 23193323Sed#include "llvm/Analysis/ConstantFolding.h" 24198892Srdivacky#include "llvm/Analysis/MemoryBuiltins.h" 25249423Sdim#include "llvm/IR/CallingConv.h" 26249423Sdim#include "llvm/IR/Constants.h" 27249423Sdim#include "llvm/IR/DataLayout.h" 28249423Sdim#include "llvm/IR/DerivedTypes.h" 29249423Sdim#include "llvm/IR/Instructions.h" 30249423Sdim#include "llvm/IR/IntrinsicInst.h" 31249423Sdim#include "llvm/IR/Module.h" 32249423Sdim#include "llvm/IR/Operator.h" 33249423Sdim#include "llvm/Pass.h" 34193323Sed#include "llvm/Support/CallSite.h" 35193323Sed#include "llvm/Support/Debug.h" 36198090Srdivacky#include "llvm/Support/ErrorHandling.h" 37193323Sed#include "llvm/Support/GetElementPtrTypeIterator.h" 38193323Sed#include "llvm/Support/MathExtras.h" 39198090Srdivacky#include "llvm/Support/raw_ostream.h" 40249423Sdim#include "llvm/Target/TargetLibraryInfo.h" 41193323Sed#include <algorithm> 42193323Sedusing namespace llvm; 43193323Sed 44193323SedSTATISTIC(NumMarked , "Number of globals marked constant"); 45218893SdimSTATISTIC(NumUnnamed , "Number of globals marked unnamed_addr"); 46193323SedSTATISTIC(NumSRA , "Number of aggregate globals broken into scalars"); 47193323SedSTATISTIC(NumHeapSRA , "Number of heap objects SRA'd"); 48193323SedSTATISTIC(NumSubstitute,"Number of globals with initializers stored into them"); 49193323SedSTATISTIC(NumDeleted , "Number of globals deleted"); 50193323SedSTATISTIC(NumFnDeleted , "Number of functions deleted"); 51193323SedSTATISTIC(NumGlobUses , "Number of global uses devirtualized"); 52193323SedSTATISTIC(NumLocalized , "Number of globals localized"); 53193323SedSTATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans"); 54193323SedSTATISTIC(NumFastCallFns , "Number of functions converted to fastcc"); 55193323SedSTATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated"); 56193323SedSTATISTIC(NumNestRemoved , "Number of nest attributes removed"); 57193323SedSTATISTIC(NumAliasesResolved, "Number of global aliases resolved"); 58193323SedSTATISTIC(NumAliasesRemoved, "Number of global aliases eliminated"); 59221345SdimSTATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed"); 60193323Sed 61193323Sednamespace { 62218893Sdim struct GlobalStatus; 63198892Srdivacky struct GlobalOpt : public ModulePass { 64193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 65234353Sdim AU.addRequired<TargetLibraryInfo>(); 66193323Sed } 67193323Sed static char ID; // Pass identification, replacement for typeid 68218893Sdim GlobalOpt() : ModulePass(ID) { 69218893Sdim initializeGlobalOptPass(*PassRegistry::getPassRegistry()); 70218893Sdim } 71193323Sed 72193323Sed bool runOnModule(Module &M); 73193323Sed 74193323Sed private: 75193323Sed GlobalVariable *FindGlobalCtors(Module &M); 76193323Sed bool OptimizeFunctions(Module &M); 77193323Sed bool OptimizeGlobalVars(Module &M); 78193323Sed bool OptimizeGlobalAliases(Module &M); 79193323Sed bool OptimizeGlobalCtorsList(GlobalVariable *&GCL); 80218893Sdim bool ProcessGlobal(GlobalVariable *GV,Module::global_iterator &GVI); 81218893Sdim bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI, 82218893Sdim const SmallPtrSet<const PHINode*, 16> &PHIUsers, 83218893Sdim const GlobalStatus &GS); 84221345Sdim bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn); 85234353Sdim 86243830Sdim DataLayout *TD; 87234353Sdim TargetLibraryInfo *TLI; 88193323Sed }; 89193323Sed} 90193323Sed 91193323Sedchar GlobalOpt::ID = 0; 92234353SdimINITIALIZE_PASS_BEGIN(GlobalOpt, "globalopt", 93218893Sdim "Global Variable Optimizer", false, false) 94234353SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 95234353SdimINITIALIZE_PASS_END(GlobalOpt, "globalopt", 96234353Sdim "Global Variable Optimizer", false, false) 97193323Sed 98193323SedModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); } 99193323Sed 100193323Sednamespace { 101193323Sed 102193323Sed/// GlobalStatus - As we analyze each global, keep track of some information 103193323Sed/// about it. If we find out that the address of the global is taken, none of 104193323Sed/// this info will be accurate. 105198892Srdivackystruct GlobalStatus { 106218893Sdim /// isCompared - True if the global's address is used in a comparison. 107218893Sdim bool isCompared; 108218893Sdim 109193323Sed /// isLoaded - True if the global is ever loaded. If the global isn't ever 110193323Sed /// loaded it can be deleted. 111193323Sed bool isLoaded; 112193323Sed 113193323Sed /// StoredType - Keep track of what stores to the global look like. 114193323Sed /// 115193323Sed enum StoredType { 116193323Sed /// NotStored - There is no store to this global. It can thus be marked 117193323Sed /// constant. 118193323Sed NotStored, 119193323Sed 120193323Sed /// isInitializerStored - This global is stored to, but the only thing 121193323Sed /// stored is the constant it was initialized with. This is only tracked 122193323Sed /// for scalar globals. 123193323Sed isInitializerStored, 124193323Sed 125193323Sed /// isStoredOnce - This global is stored to, but only its initializer and 126193323Sed /// one other value is ever stored to it. If this global isStoredOnce, we 127193323Sed /// track the value stored to it in StoredOnceValue below. This is only 128193323Sed /// tracked for scalar globals. 129193323Sed isStoredOnce, 130193323Sed 131193323Sed /// isStored - This global is stored to by multiple values or something else 132193323Sed /// that we cannot track. 133193323Sed isStored 134193323Sed } StoredType; 135193323Sed 136193323Sed /// StoredOnceValue - If only one value (besides the initializer constant) is 137193323Sed /// ever stored to this global, keep track of what value it is. 138193323Sed Value *StoredOnceValue; 139193323Sed 140193323Sed /// AccessingFunction/HasMultipleAccessingFunctions - These start out 141193323Sed /// null/false. When the first accessing function is noticed, it is recorded. 142193323Sed /// When a second different accessing function is noticed, 143193323Sed /// HasMultipleAccessingFunctions is set to true. 144206083Srdivacky const Function *AccessingFunction; 145193323Sed bool HasMultipleAccessingFunctions; 146193323Sed 147193323Sed /// HasNonInstructionUser - Set to true if this global has a user that is not 148193323Sed /// an instruction (e.g. a constant expr or GV initializer). 149193323Sed bool HasNonInstructionUser; 150193323Sed 151234353Sdim /// AtomicOrdering - Set to the strongest atomic ordering requirement. 152234353Sdim AtomicOrdering Ordering; 153234353Sdim 154218893Sdim GlobalStatus() : isCompared(false), isLoaded(false), StoredType(NotStored), 155218893Sdim StoredOnceValue(0), AccessingFunction(0), 156234353Sdim HasMultipleAccessingFunctions(false), 157249423Sdim HasNonInstructionUser(false), Ordering(NotAtomic) {} 158193323Sed}; 159193323Sed 160193323Sed} 161193323Sed 162234353Sdim/// StrongerOrdering - Return the stronger of the two ordering. If the two 163234353Sdim/// orderings are acquire and release, then return AcquireRelease. 164234353Sdim/// 165234353Sdimstatic AtomicOrdering StrongerOrdering(AtomicOrdering X, AtomicOrdering Y) { 166234353Sdim if (X == Acquire && Y == Release) return AcquireRelease; 167234353Sdim if (Y == Acquire && X == Release) return AcquireRelease; 168234353Sdim return (AtomicOrdering)std::max(X, Y); 169234353Sdim} 170234353Sdim 171234353Sdim/// SafeToDestroyConstant - It is safe to destroy a constant iff it is only used 172234353Sdim/// by constants itself. Note that constants cannot be cyclic, so this test is 173234353Sdim/// pretty easy to implement recursively. 174234353Sdim/// 175206083Srdivackystatic bool SafeToDestroyConstant(const Constant *C) { 176193323Sed if (isa<GlobalValue>(C)) return false; 177193323Sed 178207618Srdivacky for (Value::const_use_iterator UI = C->use_begin(), E = C->use_end(); UI != E; 179207618Srdivacky ++UI) 180206083Srdivacky if (const Constant *CU = dyn_cast<Constant>(*UI)) { 181194178Sed if (!SafeToDestroyConstant(CU)) return false; 182193323Sed } else 183193323Sed return false; 184193323Sed return true; 185193323Sed} 186193323Sed 187193323Sed 188193323Sed/// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus 189193323Sed/// structure. If the global has its address taken, return true to indicate we 190193323Sed/// can't do anything with it. 191193323Sed/// 192206083Srdivackystatic bool AnalyzeGlobal(const Value *V, GlobalStatus &GS, 193206083Srdivacky SmallPtrSet<const PHINode*, 16> &PHIUsers) { 194207618Srdivacky for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; 195210299Sed ++UI) { 196210299Sed const User *U = *UI; 197210299Sed if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 198193323Sed GS.HasNonInstructionUser = true; 199249423Sdim 200218893Sdim // If the result of the constantexpr isn't pointer type, then we won't 201218893Sdim // know to expect it in various places. Just reject early. 202218893Sdim if (!isa<PointerType>(CE->getType())) return true; 203249423Sdim 204193323Sed if (AnalyzeGlobal(CE, GS, PHIUsers)) return true; 205210299Sed } else if (const Instruction *I = dyn_cast<Instruction>(U)) { 206193323Sed if (!GS.HasMultipleAccessingFunctions) { 207206083Srdivacky const Function *F = I->getParent()->getParent(); 208193323Sed if (GS.AccessingFunction == 0) 209193323Sed GS.AccessingFunction = F; 210193323Sed else if (GS.AccessingFunction != F) 211193323Sed GS.HasMultipleAccessingFunctions = true; 212193323Sed } 213206083Srdivacky if (const LoadInst *LI = dyn_cast<LoadInst>(I)) { 214193323Sed GS.isLoaded = true; 215234353Sdim // Don't hack on volatile loads. 216234353Sdim if (LI->isVolatile()) return true; 217234353Sdim GS.Ordering = StrongerOrdering(GS.Ordering, LI->getOrdering()); 218206083Srdivacky } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) { 219193323Sed // Don't allow a store OF the address, only stores TO the address. 220193323Sed if (SI->getOperand(0) == V) return true; 221193323Sed 222234353Sdim // Don't hack on volatile stores. 223234353Sdim if (SI->isVolatile()) return true; 224243830Sdim 225234353Sdim GS.Ordering = StrongerOrdering(GS.Ordering, SI->getOrdering()); 226193323Sed 227193323Sed // If this is a direct store to the global (i.e., the global is a scalar 228193323Sed // value, not an aggregate), keep more specific information about 229193323Sed // stores. 230193323Sed if (GS.StoredType != GlobalStatus::isStored) { 231207618Srdivacky if (const GlobalVariable *GV = dyn_cast<GlobalVariable>( 232207618Srdivacky SI->getOperand(1))) { 233193323Sed Value *StoredVal = SI->getOperand(0); 234243830Sdim 235243830Sdim if (Constant *C = dyn_cast<Constant>(StoredVal)) { 236243830Sdim if (C->isThreadDependent()) { 237243830Sdim // The stored value changes between threads; don't track it. 238243830Sdim return true; 239243830Sdim } 240243830Sdim } 241243830Sdim 242193323Sed if (StoredVal == GV->getInitializer()) { 243193323Sed if (GS.StoredType < GlobalStatus::isInitializerStored) 244193323Sed GS.StoredType = GlobalStatus::isInitializerStored; 245193323Sed } else if (isa<LoadInst>(StoredVal) && 246193323Sed cast<LoadInst>(StoredVal)->getOperand(0) == GV) { 247193323Sed if (GS.StoredType < GlobalStatus::isInitializerStored) 248193323Sed GS.StoredType = GlobalStatus::isInitializerStored; 249193323Sed } else if (GS.StoredType < GlobalStatus::isStoredOnce) { 250193323Sed GS.StoredType = GlobalStatus::isStoredOnce; 251193323Sed GS.StoredOnceValue = StoredVal; 252193323Sed } else if (GS.StoredType == GlobalStatus::isStoredOnce && 253193323Sed GS.StoredOnceValue == StoredVal) { 254193323Sed // noop. 255193323Sed } else { 256193323Sed GS.StoredType = GlobalStatus::isStored; 257193323Sed } 258193323Sed } else { 259193323Sed GS.StoredType = GlobalStatus::isStored; 260193323Sed } 261193323Sed } 262239462Sdim } else if (isa<BitCastInst>(I)) { 263239462Sdim if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 264193323Sed } else if (isa<GetElementPtrInst>(I)) { 265193323Sed if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 266193323Sed } else if (isa<SelectInst>(I)) { 267193323Sed if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 268206083Srdivacky } else if (const PHINode *PN = dyn_cast<PHINode>(I)) { 269193323Sed // PHI nodes we can check just like select or GEP instructions, but we 270193323Sed // have to be careful about infinite recursion. 271193323Sed if (PHIUsers.insert(PN)) // Not already visited. 272193323Sed if (AnalyzeGlobal(I, GS, PHIUsers)) return true; 273193323Sed } else if (isa<CmpInst>(I)) { 274218893Sdim GS.isCompared = true; 275223017Sdim } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) { 276223017Sdim if (MTI->isVolatile()) return true; 277210299Sed if (MTI->getArgOperand(0) == V) 278193323Sed GS.StoredType = GlobalStatus::isStored; 279210299Sed if (MTI->getArgOperand(1) == V) 280193323Sed GS.isLoaded = true; 281223017Sdim } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) { 282223017Sdim assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!"); 283223017Sdim if (MSI->isVolatile()) return true; 284193323Sed GS.StoredType = GlobalStatus::isStored; 285193323Sed } else { 286193323Sed return true; // Any other non-load instruction might take address! 287193323Sed } 288210299Sed } else if (const Constant *C = dyn_cast<Constant>(U)) { 289193323Sed GS.HasNonInstructionUser = true; 290193323Sed // We might have a dead and dangling constant hanging off of here. 291194178Sed if (!SafeToDestroyConstant(C)) 292193323Sed return true; 293193323Sed } else { 294193323Sed GS.HasNonInstructionUser = true; 295193323Sed // Otherwise must be some other user. 296193323Sed return true; 297193323Sed } 298210299Sed } 299193323Sed 300193323Sed return false; 301193323Sed} 302193323Sed 303239462Sdim/// isLeakCheckerRoot - Is this global variable possibly used by a leak checker 304239462Sdim/// as a root? If so, we might not really want to eliminate the stores to it. 305239462Sdimstatic bool isLeakCheckerRoot(GlobalVariable *GV) { 306239462Sdim // A global variable is a root if it is a pointer, or could plausibly contain 307239462Sdim // a pointer. There are two challenges; one is that we could have a struct 308239462Sdim // the has an inner member which is a pointer. We recurse through the type to 309239462Sdim // detect these (up to a point). The other is that we may actually be a union 310239462Sdim // of a pointer and another type, and so our LLVM type is an integer which 311239462Sdim // gets converted into a pointer, or our type is an [i8 x #] with a pointer 312239462Sdim // potentially contained here. 313239462Sdim 314239462Sdim if (GV->hasPrivateLinkage()) 315239462Sdim return false; 316239462Sdim 317239462Sdim SmallVector<Type *, 4> Types; 318239462Sdim Types.push_back(cast<PointerType>(GV->getType())->getElementType()); 319239462Sdim 320239462Sdim unsigned Limit = 20; 321239462Sdim do { 322239462Sdim Type *Ty = Types.pop_back_val(); 323239462Sdim switch (Ty->getTypeID()) { 324239462Sdim default: break; 325239462Sdim case Type::PointerTyID: return true; 326239462Sdim case Type::ArrayTyID: 327239462Sdim case Type::VectorTyID: { 328239462Sdim SequentialType *STy = cast<SequentialType>(Ty); 329239462Sdim Types.push_back(STy->getElementType()); 330239462Sdim break; 331239462Sdim } 332239462Sdim case Type::StructTyID: { 333239462Sdim StructType *STy = cast<StructType>(Ty); 334239462Sdim if (STy->isOpaque()) return true; 335239462Sdim for (StructType::element_iterator I = STy->element_begin(), 336239462Sdim E = STy->element_end(); I != E; ++I) { 337239462Sdim Type *InnerTy = *I; 338239462Sdim if (isa<PointerType>(InnerTy)) return true; 339239462Sdim if (isa<CompositeType>(InnerTy)) 340239462Sdim Types.push_back(InnerTy); 341239462Sdim } 342239462Sdim break; 343239462Sdim } 344239462Sdim } 345239462Sdim if (--Limit == 0) return true; 346239462Sdim } while (!Types.empty()); 347239462Sdim return false; 348239462Sdim} 349239462Sdim 350239462Sdim/// Given a value that is stored to a global but never read, determine whether 351239462Sdim/// it's safe to remove the store and the chain of computation that feeds the 352239462Sdim/// store. 353243830Sdimstatic bool IsSafeComputationToRemove(Value *V, const TargetLibraryInfo *TLI) { 354239462Sdim do { 355239462Sdim if (isa<Constant>(V)) 356239462Sdim return true; 357239462Sdim if (!V->hasOneUse()) 358239462Sdim return false; 359239462Sdim if (isa<LoadInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V) || 360239462Sdim isa<GlobalValue>(V)) 361239462Sdim return false; 362243830Sdim if (isAllocationFn(V, TLI)) 363239462Sdim return true; 364239462Sdim 365239462Sdim Instruction *I = cast<Instruction>(V); 366239462Sdim if (I->mayHaveSideEffects()) 367239462Sdim return false; 368239462Sdim if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) { 369239462Sdim if (!GEP->hasAllConstantIndices()) 370239462Sdim return false; 371239462Sdim } else if (I->getNumOperands() != 1) { 372239462Sdim return false; 373239462Sdim } 374239462Sdim 375239462Sdim V = I->getOperand(0); 376239462Sdim } while (1); 377239462Sdim} 378239462Sdim 379239462Sdim/// CleanupPointerRootUsers - This GV is a pointer root. Loop over all users 380239462Sdim/// of the global and clean up any that obviously don't assign the global a 381239462Sdim/// value that isn't dynamically allocated. 382239462Sdim/// 383243830Sdimstatic bool CleanupPointerRootUsers(GlobalVariable *GV, 384243830Sdim const TargetLibraryInfo *TLI) { 385239462Sdim // A brief explanation of leak checkers. The goal is to find bugs where 386239462Sdim // pointers are forgotten, causing an accumulating growth in memory 387239462Sdim // usage over time. The common strategy for leak checkers is to whitelist the 388239462Sdim // memory pointed to by globals at exit. This is popular because it also 389239462Sdim // solves another problem where the main thread of a C++ program may shut down 390239462Sdim // before other threads that are still expecting to use those globals. To 391239462Sdim // handle that case, we expect the program may create a singleton and never 392239462Sdim // destroy it. 393239462Sdim 394239462Sdim bool Changed = false; 395239462Sdim 396239462Sdim // If Dead[n].first is the only use of a malloc result, we can delete its 397239462Sdim // chain of computation and the store to the global in Dead[n].second. 398239462Sdim SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead; 399239462Sdim 400239462Sdim // Constants can't be pointers to dynamically allocated memory. 401239462Sdim for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 402239462Sdim UI != E;) { 403239462Sdim User *U = *UI++; 404239462Sdim if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 405239462Sdim Value *V = SI->getValueOperand(); 406239462Sdim if (isa<Constant>(V)) { 407239462Sdim Changed = true; 408239462Sdim SI->eraseFromParent(); 409239462Sdim } else if (Instruction *I = dyn_cast<Instruction>(V)) { 410239462Sdim if (I->hasOneUse()) 411239462Sdim Dead.push_back(std::make_pair(I, SI)); 412239462Sdim } 413239462Sdim } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) { 414239462Sdim if (isa<Constant>(MSI->getValue())) { 415239462Sdim Changed = true; 416239462Sdim MSI->eraseFromParent(); 417239462Sdim } else if (Instruction *I = dyn_cast<Instruction>(MSI->getValue())) { 418239462Sdim if (I->hasOneUse()) 419239462Sdim Dead.push_back(std::make_pair(I, MSI)); 420239462Sdim } 421239462Sdim } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) { 422239462Sdim GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(MTI->getSource()); 423239462Sdim if (MemSrc && MemSrc->isConstant()) { 424239462Sdim Changed = true; 425239462Sdim MTI->eraseFromParent(); 426239462Sdim } else if (Instruction *I = dyn_cast<Instruction>(MemSrc)) { 427239462Sdim if (I->hasOneUse()) 428239462Sdim Dead.push_back(std::make_pair(I, MTI)); 429239462Sdim } 430239462Sdim } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 431239462Sdim if (CE->use_empty()) { 432239462Sdim CE->destroyConstant(); 433239462Sdim Changed = true; 434239462Sdim } 435239462Sdim } else if (Constant *C = dyn_cast<Constant>(U)) { 436239462Sdim if (SafeToDestroyConstant(C)) { 437239462Sdim C->destroyConstant(); 438239462Sdim // This could have invalidated UI, start over from scratch. 439239462Sdim Dead.clear(); 440243830Sdim CleanupPointerRootUsers(GV, TLI); 441239462Sdim return true; 442239462Sdim } 443239462Sdim } 444239462Sdim } 445239462Sdim 446239462Sdim for (int i = 0, e = Dead.size(); i != e; ++i) { 447243830Sdim if (IsSafeComputationToRemove(Dead[i].first, TLI)) { 448239462Sdim Dead[i].second->eraseFromParent(); 449239462Sdim Instruction *I = Dead[i].first; 450239462Sdim do { 451249423Sdim if (isAllocationFn(I, TLI)) 452249423Sdim break; 453239462Sdim Instruction *J = dyn_cast<Instruction>(I->getOperand(0)); 454239462Sdim if (!J) 455239462Sdim break; 456239462Sdim I->eraseFromParent(); 457239462Sdim I = J; 458239462Sdim } while (1); 459239462Sdim I->eraseFromParent(); 460239462Sdim } 461239462Sdim } 462239462Sdim 463239462Sdim return Changed; 464239462Sdim} 465239462Sdim 466193323Sed/// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all 467193323Sed/// users of the global, cleaning up the obvious ones. This is largely just a 468193323Sed/// quick scan over the use list to clean up the easy and obvious cruft. This 469193323Sed/// returns true if it made a change. 470234353Sdimstatic bool CleanupConstantGlobalUsers(Value *V, Constant *Init, 471243830Sdim DataLayout *TD, TargetLibraryInfo *TLI) { 472193323Sed bool Changed = false; 473249423Sdim SmallVector<User*, 8> WorkList(V->use_begin(), V->use_end()); 474249423Sdim while (!WorkList.empty()) { 475249423Sdim User *U = WorkList.pop_back_val(); 476193323Sed 477193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 478193323Sed if (Init) { 479193323Sed // Replace the load with the initializer. 480193323Sed LI->replaceAllUsesWith(Init); 481193323Sed LI->eraseFromParent(); 482193323Sed Changed = true; 483193323Sed } 484193323Sed } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 485193323Sed // Store must be unreachable or storing Init into the global. 486193323Sed SI->eraseFromParent(); 487193323Sed Changed = true; 488193323Sed } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 489193323Sed if (CE->getOpcode() == Instruction::GetElementPtr) { 490193323Sed Constant *SubInit = 0; 491193323Sed if (Init) 492193323Sed SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); 493234353Sdim Changed |= CleanupConstantGlobalUsers(CE, SubInit, TD, TLI); 494218893Sdim } else if (CE->getOpcode() == Instruction::BitCast && 495204642Srdivacky CE->getType()->isPointerTy()) { 496193323Sed // Pointer cast, delete any stores and memsets to the global. 497234353Sdim Changed |= CleanupConstantGlobalUsers(CE, 0, TD, TLI); 498193323Sed } 499193323Sed 500193323Sed if (CE->use_empty()) { 501193323Sed CE->destroyConstant(); 502193323Sed Changed = true; 503193323Sed } 504193323Sed } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 505193323Sed // Do not transform "gepinst (gep constexpr (GV))" here, because forming 506193323Sed // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold 507193323Sed // and will invalidate our notion of what Init is. 508193323Sed Constant *SubInit = 0; 509193323Sed if (!isa<ConstantExpr>(GEP->getOperand(0))) { 510218893Sdim ConstantExpr *CE = 511234353Sdim dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP, TD, TLI)); 512193323Sed if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr) 513193323Sed SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); 514234353Sdim 515234353Sdim // If the initializer is an all-null value and we have an inbounds GEP, 516234353Sdim // we already know what the result of any load from that GEP is. 517234353Sdim // TODO: Handle splats. 518234353Sdim if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds()) 519234353Sdim SubInit = Constant::getNullValue(GEP->getType()->getElementType()); 520193323Sed } 521234353Sdim Changed |= CleanupConstantGlobalUsers(GEP, SubInit, TD, TLI); 522193323Sed 523193323Sed if (GEP->use_empty()) { 524193323Sed GEP->eraseFromParent(); 525193323Sed Changed = true; 526193323Sed } 527193323Sed } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv 528193323Sed if (MI->getRawDest() == V) { 529193323Sed MI->eraseFromParent(); 530193323Sed Changed = true; 531193323Sed } 532193323Sed 533193323Sed } else if (Constant *C = dyn_cast<Constant>(U)) { 534193323Sed // If we have a chain of dead constantexprs or other things dangling from 535193323Sed // us, and if they are all dead, nuke them without remorse. 536194178Sed if (SafeToDestroyConstant(C)) { 537193323Sed C->destroyConstant(); 538234353Sdim CleanupConstantGlobalUsers(V, Init, TD, TLI); 539193323Sed return true; 540193323Sed } 541193323Sed } 542193323Sed } 543193323Sed return Changed; 544193323Sed} 545193323Sed 546193323Sed/// isSafeSROAElementUse - Return true if the specified instruction is a safe 547193323Sed/// user of a derived expression from a global that we want to SROA. 548193323Sedstatic bool isSafeSROAElementUse(Value *V) { 549193323Sed // We might have a dead and dangling constant hanging off of here. 550193323Sed if (Constant *C = dyn_cast<Constant>(V)) 551194178Sed return SafeToDestroyConstant(C); 552218893Sdim 553193323Sed Instruction *I = dyn_cast<Instruction>(V); 554193323Sed if (!I) return false; 555193323Sed 556193323Sed // Loads are ok. 557193323Sed if (isa<LoadInst>(I)) return true; 558193323Sed 559193323Sed // Stores *to* the pointer are ok. 560193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(I)) 561193323Sed return SI->getOperand(0) != V; 562218893Sdim 563193323Sed // Otherwise, it must be a GEP. 564193323Sed GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I); 565193323Sed if (GEPI == 0) return false; 566218893Sdim 567193323Sed if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) || 568193323Sed !cast<Constant>(GEPI->getOperand(1))->isNullValue()) 569193323Sed return false; 570218893Sdim 571193323Sed for (Value::use_iterator I = GEPI->use_begin(), E = GEPI->use_end(); 572193323Sed I != E; ++I) 573193323Sed if (!isSafeSROAElementUse(*I)) 574193323Sed return false; 575193323Sed return true; 576193323Sed} 577193323Sed 578193323Sed 579193323Sed/// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value. 580193323Sed/// Look at it and its uses and decide whether it is safe to SROA this global. 581193323Sed/// 582193323Sedstatic bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) { 583193323Sed // The user of the global must be a GEP Inst or a ConstantExpr GEP. 584218893Sdim if (!isa<GetElementPtrInst>(U) && 585218893Sdim (!isa<ConstantExpr>(U) || 586193323Sed cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr)) 587193323Sed return false; 588218893Sdim 589193323Sed // Check to see if this ConstantExpr GEP is SRA'able. In particular, we 590193323Sed // don't like < 3 operand CE's, and we don't like non-constant integer 591193323Sed // indices. This enforces that all uses are 'gep GV, 0, C, ...' for some 592193323Sed // value of C. 593193323Sed if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) || 594193323Sed !cast<Constant>(U->getOperand(1))->isNullValue() || 595193323Sed !isa<ConstantInt>(U->getOperand(2))) 596193323Sed return false; 597193323Sed 598193323Sed gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U); 599193323Sed ++GEPI; // Skip over the pointer index. 600218893Sdim 601193323Sed // If this is a use of an array allocation, do a bit more checking for sanity. 602226633Sdim if (ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) { 603193323Sed uint64_t NumElements = AT->getNumElements(); 604193323Sed ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2)); 605218893Sdim 606193323Sed // Check to make sure that index falls within the array. If not, 607193323Sed // something funny is going on, so we won't do the optimization. 608193323Sed // 609193323Sed if (Idx->getZExtValue() >= NumElements) 610193323Sed return false; 611218893Sdim 612193323Sed // We cannot scalar repl this level of the array unless any array 613193323Sed // sub-indices are in-range constants. In particular, consider: 614193323Sed // A[0][i]. We cannot know that the user isn't doing invalid things like 615193323Sed // allowing i to index an out-of-range subscript that accesses A[1]. 616193323Sed // 617193323Sed // Scalar replacing *just* the outer index of the array is probably not 618193323Sed // going to be a win anyway, so just give up. 619193323Sed for (++GEPI; // Skip array index. 620198090Srdivacky GEPI != E; 621193323Sed ++GEPI) { 622193323Sed uint64_t NumElements; 623226633Sdim if (ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI)) 624193323Sed NumElements = SubArrayTy->getNumElements(); 625226633Sdim else if (VectorType *SubVectorTy = dyn_cast<VectorType>(*GEPI)) 626198090Srdivacky NumElements = SubVectorTy->getNumElements(); 627198090Srdivacky else { 628204642Srdivacky assert((*GEPI)->isStructTy() && 629198090Srdivacky "Indexed GEP type is not array, vector, or struct!"); 630198090Srdivacky continue; 631198090Srdivacky } 632218893Sdim 633193323Sed ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand()); 634193323Sed if (!IdxVal || IdxVal->getZExtValue() >= NumElements) 635193323Sed return false; 636193323Sed } 637193323Sed } 638193323Sed 639193323Sed for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I) 640193323Sed if (!isSafeSROAElementUse(*I)) 641193323Sed return false; 642193323Sed return true; 643193323Sed} 644193323Sed 645193323Sed/// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it 646193323Sed/// is safe for us to perform this transformation. 647193323Sed/// 648193323Sedstatic bool GlobalUsersSafeToSRA(GlobalValue *GV) { 649193323Sed for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 650193323Sed UI != E; ++UI) { 651193323Sed if (!IsUserOfGlobalSafeForSRA(*UI, GV)) 652193323Sed return false; 653193323Sed } 654193323Sed return true; 655193323Sed} 656193323Sed 657218893Sdim 658193323Sed/// SRAGlobal - Perform scalar replacement of aggregates on the specified global 659193323Sed/// variable. This opens the door for other optimizations by exposing the 660193323Sed/// behavior of the program in a more fine-grained way. We have determined that 661193323Sed/// this transformation is safe already. We return the first global variable we 662193323Sed/// insert so that the caller can reprocess it. 663243830Sdimstatic GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &TD) { 664193323Sed // Make sure this global only has simple uses that we can SRA. 665193323Sed if (!GlobalUsersSafeToSRA(GV)) 666193323Sed return 0; 667218893Sdim 668193323Sed assert(GV->hasLocalLinkage() && !GV->isConstant()); 669193323Sed Constant *Init = GV->getInitializer(); 670226633Sdim Type *Ty = Init->getType(); 671193323Sed 672193323Sed std::vector<GlobalVariable*> NewGlobals; 673193323Sed Module::GlobalListType &Globals = GV->getParent()->getGlobalList(); 674193323Sed 675193323Sed // Get the alignment of the global, either explicit or target-specific. 676193323Sed unsigned StartAlignment = GV->getAlignment(); 677193323Sed if (StartAlignment == 0) 678193323Sed StartAlignment = TD.getABITypeAlignment(GV->getType()); 679218893Sdim 680226633Sdim if (StructType *STy = dyn_cast<StructType>(Ty)) { 681193323Sed NewGlobals.reserve(STy->getNumElements()); 682193323Sed const StructLayout &Layout = *TD.getStructLayout(STy); 683193323Sed for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 684234353Sdim Constant *In = Init->getAggregateElement(i); 685193323Sed assert(In && "Couldn't get element of initializer?"); 686199481Srdivacky GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false, 687193323Sed GlobalVariable::InternalLinkage, 688198090Srdivacky In, GV->getName()+"."+Twine(i), 689239462Sdim GV->getThreadLocalMode(), 690198090Srdivacky GV->getType()->getAddressSpace()); 691193323Sed Globals.insert(GV, NGV); 692193323Sed NewGlobals.push_back(NGV); 693218893Sdim 694193323Sed // Calculate the known alignment of the field. If the original aggregate 695193323Sed // had 256 byte alignment for example, something might depend on that: 696193323Sed // propagate info to each field. 697193323Sed uint64_t FieldOffset = Layout.getElementOffset(i); 698193323Sed unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset); 699193323Sed if (NewAlign > TD.getABITypeAlignment(STy->getElementType(i))) 700193323Sed NGV->setAlignment(NewAlign); 701193323Sed } 702226633Sdim } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) { 703193323Sed unsigned NumElements = 0; 704226633Sdim if (ArrayType *ATy = dyn_cast<ArrayType>(STy)) 705193323Sed NumElements = ATy->getNumElements(); 706193323Sed else 707193323Sed NumElements = cast<VectorType>(STy)->getNumElements(); 708193323Sed 709193323Sed if (NumElements > 16 && GV->hasNUsesOrMore(16)) 710193323Sed return 0; // It's not worth it. 711193323Sed NewGlobals.reserve(NumElements); 712218893Sdim 713193323Sed uint64_t EltSize = TD.getTypeAllocSize(STy->getElementType()); 714193323Sed unsigned EltAlign = TD.getABITypeAlignment(STy->getElementType()); 715193323Sed for (unsigned i = 0, e = NumElements; i != e; ++i) { 716234353Sdim Constant *In = Init->getAggregateElement(i); 717193323Sed assert(In && "Couldn't get element of initializer?"); 718193323Sed 719199481Srdivacky GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false, 720193323Sed GlobalVariable::InternalLinkage, 721198090Srdivacky In, GV->getName()+"."+Twine(i), 722239462Sdim GV->getThreadLocalMode(), 723198090Srdivacky GV->getType()->getAddressSpace()); 724193323Sed Globals.insert(GV, NGV); 725193323Sed NewGlobals.push_back(NGV); 726218893Sdim 727193323Sed // Calculate the known alignment of the field. If the original aggregate 728193323Sed // had 256 byte alignment for example, something might depend on that: 729193323Sed // propagate info to each field. 730193323Sed unsigned NewAlign = (unsigned)MinAlign(StartAlignment, EltSize*i); 731193323Sed if (NewAlign > EltAlign) 732193323Sed NGV->setAlignment(NewAlign); 733193323Sed } 734193323Sed } 735193323Sed 736193323Sed if (NewGlobals.empty()) 737193323Sed return 0; 738218893Sdim 739202375Srdivacky DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV); 740193323Sed 741199481Srdivacky Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext())); 742193323Sed 743193323Sed // Loop over all of the uses of the global, replacing the constantexpr geps, 744193323Sed // with smaller constantexpr geps or direct references. 745193323Sed while (!GV->use_empty()) { 746193323Sed User *GEP = GV->use_back(); 747193323Sed assert(((isa<ConstantExpr>(GEP) && 748193323Sed cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| 749193323Sed isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!"); 750193323Sed 751193323Sed // Ignore the 1th operand, which has to be zero or else the program is quite 752193323Sed // broken (undefined). Get the 2nd operand, which is the structure or array 753193323Sed // index. 754193323Sed unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue(); 755193323Sed if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access. 756193323Sed 757193323Sed Value *NewPtr = NewGlobals[Val]; 758193323Sed 759193323Sed // Form a shorter GEP if needed. 760193323Sed if (GEP->getNumOperands() > 3) { 761193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) { 762193323Sed SmallVector<Constant*, 8> Idxs; 763193323Sed Idxs.push_back(NullInt); 764193323Sed for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i) 765193323Sed Idxs.push_back(CE->getOperand(i)); 766226633Sdim NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), Idxs); 767193323Sed } else { 768193323Sed GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP); 769193323Sed SmallVector<Value*, 8> Idxs; 770193323Sed Idxs.push_back(NullInt); 771193323Sed for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i) 772193323Sed Idxs.push_back(GEPI->getOperand(i)); 773226633Sdim NewPtr = GetElementPtrInst::Create(NewPtr, Idxs, 774198090Srdivacky GEPI->getName()+"."+Twine(Val),GEPI); 775193323Sed } 776193323Sed } 777193323Sed GEP->replaceAllUsesWith(NewPtr); 778193323Sed 779193323Sed if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP)) 780193323Sed GEPI->eraseFromParent(); 781193323Sed else 782193323Sed cast<ConstantExpr>(GEP)->destroyConstant(); 783193323Sed } 784193323Sed 785193323Sed // Delete the old global, now that it is dead. 786193323Sed Globals.erase(GV); 787193323Sed ++NumSRA; 788193323Sed 789193323Sed // Loop over the new globals array deleting any globals that are obviously 790193323Sed // dead. This can arise due to scalarization of a structure or an array that 791193323Sed // has elements that are dead. 792193323Sed unsigned FirstGlobal = 0; 793193323Sed for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i) 794193323Sed if (NewGlobals[i]->use_empty()) { 795193323Sed Globals.erase(NewGlobals[i]); 796193323Sed if (FirstGlobal == i) ++FirstGlobal; 797193323Sed } 798193323Sed 799193323Sed return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0; 800193323Sed} 801193323Sed 802193323Sed/// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified 803218893Sdim/// value will trap if the value is dynamically null. PHIs keeps track of any 804193323Sed/// phi nodes we've seen to avoid reprocessing them. 805207618Srdivackystatic bool AllUsesOfValueWillTrapIfNull(const Value *V, 806207618Srdivacky SmallPtrSet<const PHINode*, 8> &PHIs) { 807207618Srdivacky for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; 808207618Srdivacky ++UI) { 809207618Srdivacky const User *U = *UI; 810207618Srdivacky 811207618Srdivacky if (isa<LoadInst>(U)) { 812193323Sed // Will trap. 813207618Srdivacky } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 814193323Sed if (SI->getOperand(0) == V) { 815207618Srdivacky //cerr << "NONTRAPPING USE: " << *U; 816193323Sed return false; // Storing the value. 817193323Sed } 818207618Srdivacky } else if (const CallInst *CI = dyn_cast<CallInst>(U)) { 819205407Srdivacky if (CI->getCalledValue() != V) { 820207618Srdivacky //cerr << "NONTRAPPING USE: " << *U; 821193323Sed return false; // Not calling the ptr 822193323Sed } 823207618Srdivacky } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) { 824205407Srdivacky if (II->getCalledValue() != V) { 825207618Srdivacky //cerr << "NONTRAPPING USE: " << *U; 826193323Sed return false; // Not calling the ptr 827193323Sed } 828207618Srdivacky } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) { 829193323Sed if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false; 830207618Srdivacky } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 831193323Sed if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false; 832207618Srdivacky } else if (const PHINode *PN = dyn_cast<PHINode>(U)) { 833193323Sed // If we've already seen this phi node, ignore it, it has already been 834193323Sed // checked. 835203954Srdivacky if (PHIs.insert(PN) && !AllUsesOfValueWillTrapIfNull(PN, PHIs)) 836203954Srdivacky return false; 837207618Srdivacky } else if (isa<ICmpInst>(U) && 838193323Sed isa<ConstantPointerNull>(UI->getOperand(1))) { 839204642Srdivacky // Ignore icmp X, null 840193323Sed } else { 841207618Srdivacky //cerr << "NONTRAPPING USE: " << *U; 842193323Sed return false; 843193323Sed } 844207618Srdivacky } 845193323Sed return true; 846193323Sed} 847193323Sed 848193323Sed/// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads 849193323Sed/// from GV will trap if the loaded value is null. Note that this also permits 850193323Sed/// comparisons of the loaded value against null, as a special case. 851207618Srdivackystatic bool AllUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) { 852207618Srdivacky for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); 853207618Srdivacky UI != E; ++UI) { 854207618Srdivacky const User *U = *UI; 855207618Srdivacky 856207618Srdivacky if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { 857207618Srdivacky SmallPtrSet<const PHINode*, 8> PHIs; 858193323Sed if (!AllUsesOfValueWillTrapIfNull(LI, PHIs)) 859193323Sed return false; 860207618Srdivacky } else if (isa<StoreInst>(U)) { 861193323Sed // Ignore stores to the global. 862193323Sed } else { 863193323Sed // We don't know or understand this user, bail out. 864207618Srdivacky //cerr << "UNKNOWN USER OF GLOBAL!: " << *U; 865193323Sed return false; 866193323Sed } 867207618Srdivacky } 868193323Sed return true; 869193323Sed} 870193323Sed 871199481Srdivackystatic bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { 872193323Sed bool Changed = false; 873193323Sed for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) { 874193323Sed Instruction *I = cast<Instruction>(*UI++); 875193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 876193323Sed LI->setOperand(0, NewV); 877193323Sed Changed = true; 878193323Sed } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 879193323Sed if (SI->getOperand(1) == V) { 880193323Sed SI->setOperand(1, NewV); 881193323Sed Changed = true; 882193323Sed } 883193323Sed } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 884207618Srdivacky CallSite CS(I); 885207618Srdivacky if (CS.getCalledValue() == V) { 886193323Sed // Calling through the pointer! Turn into a direct call, but be careful 887193323Sed // that the pointer is not also being passed as an argument. 888207618Srdivacky CS.setCalledFunction(NewV); 889193323Sed Changed = true; 890193323Sed bool PassedAsArg = false; 891207618Srdivacky for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) 892207618Srdivacky if (CS.getArgument(i) == V) { 893193323Sed PassedAsArg = true; 894207618Srdivacky CS.setArgument(i, NewV); 895193323Sed } 896193323Sed 897193323Sed if (PassedAsArg) { 898193323Sed // Being passed as an argument also. Be careful to not invalidate UI! 899193323Sed UI = V->use_begin(); 900193323Sed } 901193323Sed } 902193323Sed } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 903193323Sed Changed |= OptimizeAwayTrappingUsesOfValue(CI, 904193323Sed ConstantExpr::getCast(CI->getOpcode(), 905199481Srdivacky NewV, CI->getType())); 906193323Sed if (CI->use_empty()) { 907193323Sed Changed = true; 908193323Sed CI->eraseFromParent(); 909193323Sed } 910193323Sed } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 911193323Sed // Should handle GEP here. 912193323Sed SmallVector<Constant*, 8> Idxs; 913193323Sed Idxs.reserve(GEPI->getNumOperands()-1); 914193323Sed for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end(); 915193323Sed i != e; ++i) 916193323Sed if (Constant *C = dyn_cast<Constant>(*i)) 917193323Sed Idxs.push_back(C); 918193323Sed else 919193323Sed break; 920193323Sed if (Idxs.size() == GEPI->getNumOperands()-1) 921193323Sed Changed |= OptimizeAwayTrappingUsesOfValue(GEPI, 922226633Sdim ConstantExpr::getGetElementPtr(NewV, Idxs)); 923193323Sed if (GEPI->use_empty()) { 924193323Sed Changed = true; 925193323Sed GEPI->eraseFromParent(); 926193323Sed } 927193323Sed } 928193323Sed } 929193323Sed 930193323Sed return Changed; 931193323Sed} 932193323Sed 933193323Sed 934193323Sed/// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null 935193323Sed/// value stored into it. If there are uses of the loaded value that would trap 936193323Sed/// if the loaded value is dynamically null, then we know that they cannot be 937193323Sed/// reachable with a null optimize away the load. 938234353Sdimstatic bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV, 939243830Sdim DataLayout *TD, 940234353Sdim TargetLibraryInfo *TLI) { 941193323Sed bool Changed = false; 942193323Sed 943193323Sed // Keep track of whether we are able to remove all the uses of the global 944193323Sed // other than the store that defines it. 945193323Sed bool AllNonStoreUsesGone = true; 946218893Sdim 947193323Sed // Replace all uses of loads with uses of uses of the stored value. 948193323Sed for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); GUI != E;){ 949193323Sed User *GlobalUser = *GUI++; 950193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) { 951199481Srdivacky Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV); 952193323Sed // If we were able to delete all uses of the loads 953193323Sed if (LI->use_empty()) { 954193323Sed LI->eraseFromParent(); 955193323Sed Changed = true; 956193323Sed } else { 957193323Sed AllNonStoreUsesGone = false; 958193323Sed } 959193323Sed } else if (isa<StoreInst>(GlobalUser)) { 960193323Sed // Ignore the store that stores "LV" to the global. 961193323Sed assert(GlobalUser->getOperand(1) == GV && 962193323Sed "Must be storing *to* the global"); 963193323Sed } else { 964193323Sed AllNonStoreUsesGone = false; 965193323Sed 966193323Sed // If we get here we could have other crazy uses that are transitively 967193323Sed // loaded. 968193323Sed assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || 969243830Sdim isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || 970243830Sdim isa<BitCastInst>(GlobalUser) || 971243830Sdim isa<GetElementPtrInst>(GlobalUser)) && 972223017Sdim "Only expect load and stores!"); 973193323Sed } 974193323Sed } 975193323Sed 976193323Sed if (Changed) { 977202375Srdivacky DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV); 978193323Sed ++NumGlobUses; 979193323Sed } 980193323Sed 981193323Sed // If we nuked all of the loads, then none of the stores are needed either, 982193323Sed // nor is the global. 983193323Sed if (AllNonStoreUsesGone) { 984239462Sdim if (isLeakCheckerRoot(GV)) { 985243830Sdim Changed |= CleanupPointerRootUsers(GV, TLI); 986239462Sdim } else { 987239462Sdim Changed = true; 988239462Sdim CleanupConstantGlobalUsers(GV, 0, TD, TLI); 989239462Sdim } 990193323Sed if (GV->use_empty()) { 991239462Sdim DEBUG(dbgs() << " *** GLOBAL NOW DEAD!\n"); 992239462Sdim Changed = true; 993193323Sed GV->eraseFromParent(); 994193323Sed ++NumDeleted; 995193323Sed } 996193323Sed } 997193323Sed return Changed; 998193323Sed} 999193323Sed 1000193323Sed/// ConstantPropUsersOf - Walk the use list of V, constant folding all of the 1001193323Sed/// instructions that are foldable. 1002234353Sdimstatic void ConstantPropUsersOf(Value *V, 1003243830Sdim DataLayout *TD, TargetLibraryInfo *TLI) { 1004193323Sed for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) 1005193323Sed if (Instruction *I = dyn_cast<Instruction>(*UI++)) 1006234353Sdim if (Constant *NewC = ConstantFoldInstruction(I, TD, TLI)) { 1007193323Sed I->replaceAllUsesWith(NewC); 1008193323Sed 1009193323Sed // Advance UI to the next non-I use to avoid invalidating it! 1010193323Sed // Instructions could multiply use V. 1011193323Sed while (UI != E && *UI == I) 1012193323Sed ++UI; 1013193323Sed I->eraseFromParent(); 1014193323Sed } 1015193323Sed} 1016193323Sed 1017193323Sed/// OptimizeGlobalAddressOfMalloc - This function takes the specified global 1018193323Sed/// variable, and transforms the program as if it always contained the result of 1019193323Sed/// the specified malloc. Because it is always the result of the specified 1020193323Sed/// malloc, there is no reason to actually DO the malloc. Instead, turn the 1021193323Sed/// malloc into a global, and any loads of GV as uses of the new global. 1022193323Sedstatic GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, 1023198090Srdivacky CallInst *CI, 1024226633Sdim Type *AllocTy, 1025204642Srdivacky ConstantInt *NElements, 1026243830Sdim DataLayout *TD, 1027234353Sdim TargetLibraryInfo *TLI) { 1028204642Srdivacky DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << " CALL = " << *CI << '\n'); 1029218893Sdim 1030226633Sdim Type *GlobalType; 1031204642Srdivacky if (NElements->getZExtValue() == 1) 1032204642Srdivacky GlobalType = AllocTy; 1033204642Srdivacky else 1034204642Srdivacky // If we have an array allocation, the global variable is of an array. 1035204642Srdivacky GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue()); 1036198953Srdivacky 1037198090Srdivacky // Create the new global variable. The contents of the malloc'd memory is 1038198090Srdivacky // undefined, so initialize with an undef value. 1039218893Sdim GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(), 1040204642Srdivacky GlobalType, false, 1041204642Srdivacky GlobalValue::InternalLinkage, 1042204642Srdivacky UndefValue::get(GlobalType), 1043198090Srdivacky GV->getName()+".body", 1044198090Srdivacky GV, 1045239462Sdim GV->getThreadLocalMode()); 1046218893Sdim 1047204642Srdivacky // If there are bitcast users of the malloc (which is typical, usually we have 1048204642Srdivacky // a malloc + bitcast) then replace them with uses of the new global. Update 1049204642Srdivacky // other users to use the global as well. 1050204642Srdivacky BitCastInst *TheBC = 0; 1051204642Srdivacky while (!CI->use_empty()) { 1052204642Srdivacky Instruction *User = cast<Instruction>(CI->use_back()); 1053204642Srdivacky if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { 1054204642Srdivacky if (BCI->getType() == NewGV->getType()) { 1055204642Srdivacky BCI->replaceAllUsesWith(NewGV); 1056204642Srdivacky BCI->eraseFromParent(); 1057204642Srdivacky } else { 1058204642Srdivacky BCI->setOperand(0, NewGV); 1059204642Srdivacky } 1060204642Srdivacky } else { 1061204642Srdivacky if (TheBC == 0) 1062204642Srdivacky TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI); 1063204642Srdivacky User->replaceUsesOfWith(CI, TheBC); 1064204642Srdivacky } 1065204642Srdivacky } 1066218893Sdim 1067198090Srdivacky Constant *RepValue = NewGV; 1068198090Srdivacky if (NewGV->getType() != GV->getType()->getElementType()) 1069218893Sdim RepValue = ConstantExpr::getBitCast(RepValue, 1070198090Srdivacky GV->getType()->getElementType()); 1071198090Srdivacky 1072198090Srdivacky // If there is a comparison against null, we will insert a global bool to 1073198090Srdivacky // keep track of whether the global was initialized yet or not. 1074198090Srdivacky GlobalVariable *InitBool = 1075199481Srdivacky new GlobalVariable(Type::getInt1Ty(GV->getContext()), false, 1076198090Srdivacky GlobalValue::InternalLinkage, 1077199481Srdivacky ConstantInt::getFalse(GV->getContext()), 1078239462Sdim GV->getName()+".init", GV->getThreadLocalMode()); 1079198090Srdivacky bool InitBoolUsed = false; 1080198090Srdivacky 1081198090Srdivacky // Loop over all uses of GV, processing them in turn. 1082204642Srdivacky while (!GV->use_empty()) { 1083204642Srdivacky if (StoreInst *SI = dyn_cast<StoreInst>(GV->use_back())) { 1084198090Srdivacky // The global is initialized when the store to it occurs. 1085234353Sdim new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, false, 0, 1086234353Sdim SI->getOrdering(), SI->getSynchScope(), SI); 1087198090Srdivacky SI->eraseFromParent(); 1088204642Srdivacky continue; 1089198090Srdivacky } 1090218893Sdim 1091204642Srdivacky LoadInst *LI = cast<LoadInst>(GV->use_back()); 1092204642Srdivacky while (!LI->use_empty()) { 1093204642Srdivacky Use &LoadUse = LI->use_begin().getUse(); 1094204642Srdivacky if (!isa<ICmpInst>(LoadUse.getUser())) { 1095204642Srdivacky LoadUse = RepValue; 1096204642Srdivacky continue; 1097204642Srdivacky } 1098218893Sdim 1099204642Srdivacky ICmpInst *ICI = cast<ICmpInst>(LoadUse.getUser()); 1100204642Srdivacky // Replace the cmp X, 0 with a use of the bool value. 1101234353Sdim // Sink the load to where the compare was, if atomic rules allow us to. 1102234353Sdim Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", false, 0, 1103234353Sdim LI->getOrdering(), LI->getSynchScope(), 1104234353Sdim LI->isUnordered() ? (Instruction*)ICI : LI); 1105204642Srdivacky InitBoolUsed = true; 1106204642Srdivacky switch (ICI->getPredicate()) { 1107204642Srdivacky default: llvm_unreachable("Unknown ICmp Predicate!"); 1108204642Srdivacky case ICmpInst::ICMP_ULT: 1109204642Srdivacky case ICmpInst::ICMP_SLT: // X < null -> always false 1110204642Srdivacky LV = ConstantInt::getFalse(GV->getContext()); 1111204642Srdivacky break; 1112204642Srdivacky case ICmpInst::ICMP_ULE: 1113204642Srdivacky case ICmpInst::ICMP_SLE: 1114204642Srdivacky case ICmpInst::ICMP_EQ: 1115204642Srdivacky LV = BinaryOperator::CreateNot(LV, "notinit", ICI); 1116204642Srdivacky break; 1117204642Srdivacky case ICmpInst::ICMP_NE: 1118204642Srdivacky case ICmpInst::ICMP_UGE: 1119204642Srdivacky case ICmpInst::ICMP_SGE: 1120204642Srdivacky case ICmpInst::ICMP_UGT: 1121204642Srdivacky case ICmpInst::ICMP_SGT: 1122204642Srdivacky break; // no change. 1123204642Srdivacky } 1124204642Srdivacky ICI->replaceAllUsesWith(LV); 1125204642Srdivacky ICI->eraseFromParent(); 1126204642Srdivacky } 1127204642Srdivacky LI->eraseFromParent(); 1128204642Srdivacky } 1129198090Srdivacky 1130198090Srdivacky // If the initialization boolean was used, insert it, otherwise delete it. 1131198090Srdivacky if (!InitBoolUsed) { 1132198090Srdivacky while (!InitBool->use_empty()) // Delete initializations 1133204642Srdivacky cast<StoreInst>(InitBool->use_back())->eraseFromParent(); 1134198090Srdivacky delete InitBool; 1135198090Srdivacky } else 1136198090Srdivacky GV->getParent()->getGlobalList().insert(GV, InitBool); 1137198090Srdivacky 1138204642Srdivacky // Now the GV is dead, nuke it and the malloc.. 1139198090Srdivacky GV->eraseFromParent(); 1140198090Srdivacky CI->eraseFromParent(); 1141198090Srdivacky 1142198090Srdivacky // To further other optimizations, loop over all users of NewGV and try to 1143198090Srdivacky // constant prop them. This will promote GEP instructions with constant 1144198090Srdivacky // indices into GEP constant-exprs, which will allow global-opt to hack on it. 1145234353Sdim ConstantPropUsersOf(NewGV, TD, TLI); 1146198090Srdivacky if (RepValue != NewGV) 1147234353Sdim ConstantPropUsersOf(RepValue, TD, TLI); 1148198090Srdivacky 1149198090Srdivacky return NewGV; 1150198090Srdivacky} 1151198090Srdivacky 1152193323Sed/// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking 1153193323Sed/// to make sure that there are no complex uses of V. We permit simple things 1154193323Sed/// like dereferencing the pointer, but not storing through the address, unless 1155193323Sed/// it is to the specified global. 1156207618Srdivackystatic bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction *V, 1157207618Srdivacky const GlobalVariable *GV, 1158207618Srdivacky SmallPtrSet<const PHINode*, 8> &PHIs) { 1159207618Srdivacky for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); 1160207618Srdivacky UI != E; ++UI) { 1161207618Srdivacky const Instruction *Inst = cast<Instruction>(*UI); 1162207618Srdivacky 1163193323Sed if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) { 1164193323Sed continue; // Fine, ignore. 1165193323Sed } 1166218893Sdim 1167207618Srdivacky if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 1168193323Sed if (SI->getOperand(0) == V && SI->getOperand(1) != GV) 1169193323Sed return false; // Storing the pointer itself... bad. 1170193323Sed continue; // Otherwise, storing through it, or storing into GV... fine. 1171193323Sed } 1172218893Sdim 1173207618Srdivacky // Must index into the array and into the struct. 1174207618Srdivacky if (isa<GetElementPtrInst>(Inst) && Inst->getNumOperands() >= 3) { 1175193323Sed if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs)) 1176193323Sed return false; 1177193323Sed continue; 1178193323Sed } 1179218893Sdim 1180207618Srdivacky if (const PHINode *PN = dyn_cast<PHINode>(Inst)) { 1181193323Sed // PHIs are ok if all uses are ok. Don't infinitely recurse through PHI 1182193323Sed // cycles. 1183193323Sed if (PHIs.insert(PN)) 1184193323Sed if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs)) 1185193323Sed return false; 1186193323Sed continue; 1187193323Sed } 1188218893Sdim 1189207618Srdivacky if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) { 1190193323Sed if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs)) 1191193323Sed return false; 1192193323Sed continue; 1193193323Sed } 1194218893Sdim 1195193323Sed return false; 1196193323Sed } 1197193323Sed return true; 1198193323Sed} 1199193323Sed 1200193323Sed/// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV 1201193323Sed/// somewhere. Transform all uses of the allocation into loads from the 1202193323Sed/// global and uses of the resultant pointer. Further, delete the store into 1203218893Sdim/// GV. This assumes that these value pass the 1204193323Sed/// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate. 1205218893Sdimstatic void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc, 1206193323Sed GlobalVariable *GV) { 1207193323Sed while (!Alloc->use_empty()) { 1208193323Sed Instruction *U = cast<Instruction>(*Alloc->use_begin()); 1209193323Sed Instruction *InsertPt = U; 1210193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 1211193323Sed // If this is the store of the allocation into the global, remove it. 1212193323Sed if (SI->getOperand(1) == GV) { 1213193323Sed SI->eraseFromParent(); 1214193323Sed continue; 1215193323Sed } 1216193323Sed } else if (PHINode *PN = dyn_cast<PHINode>(U)) { 1217193323Sed // Insert the load in the corresponding predecessor, not right before the 1218193323Sed // PHI. 1219193323Sed InsertPt = PN->getIncomingBlock(Alloc->use_begin())->getTerminator(); 1220193323Sed } else if (isa<BitCastInst>(U)) { 1221193323Sed // Must be bitcast between the malloc and store to initialize the global. 1222193323Sed ReplaceUsesOfMallocWithGlobal(U, GV); 1223193323Sed U->eraseFromParent(); 1224193323Sed continue; 1225193323Sed } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 1226193323Sed // If this is a "GEP bitcast" and the user is a store to the global, then 1227193323Sed // just process it as a bitcast. 1228193323Sed if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse()) 1229193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->use_back())) 1230193323Sed if (SI->getOperand(1) == GV) { 1231193323Sed // Must be bitcast GEP between the malloc and store to initialize 1232193323Sed // the global. 1233193323Sed ReplaceUsesOfMallocWithGlobal(GEPI, GV); 1234193323Sed GEPI->eraseFromParent(); 1235193323Sed continue; 1236193323Sed } 1237193323Sed } 1238218893Sdim 1239193323Sed // Insert a load from the global, and use it instead of the malloc. 1240193323Sed Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt); 1241193323Sed U->replaceUsesOfWith(Alloc, NL); 1242193323Sed } 1243193323Sed} 1244193323Sed 1245193323Sed/// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi 1246193323Sed/// of a load) are simple enough to perform heap SRA on. This permits GEP's 1247193323Sed/// that index through the array and struct field, icmps of null, and PHIs. 1248206083Srdivackystatic bool LoadUsesSimpleEnoughForHeapSRA(const Value *V, 1249207618Srdivacky SmallPtrSet<const PHINode*, 32> &LoadUsingPHIs, 1250207618Srdivacky SmallPtrSet<const PHINode*, 32> &LoadUsingPHIsPerLoad) { 1251193323Sed // We permit two users of the load: setcc comparing against the null 1252193323Sed // pointer, and a getelementptr of a specific form. 1253207618Srdivacky for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; 1254207618Srdivacky ++UI) { 1255206083Srdivacky const Instruction *User = cast<Instruction>(*UI); 1256218893Sdim 1257193323Sed // Comparison against null is ok. 1258206083Srdivacky if (const ICmpInst *ICI = dyn_cast<ICmpInst>(User)) { 1259193323Sed if (!isa<ConstantPointerNull>(ICI->getOperand(1))) 1260193323Sed return false; 1261193323Sed continue; 1262193323Sed } 1263218893Sdim 1264193323Sed // getelementptr is also ok, but only a simple form. 1265206083Srdivacky if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 1266193323Sed // Must index into the array and into the struct. 1267193323Sed if (GEPI->getNumOperands() < 3) 1268193323Sed return false; 1269218893Sdim 1270193323Sed // Otherwise the GEP is ok. 1271193323Sed continue; 1272193323Sed } 1273218893Sdim 1274206083Srdivacky if (const PHINode *PN = dyn_cast<PHINode>(User)) { 1275193323Sed if (!LoadUsingPHIsPerLoad.insert(PN)) 1276193323Sed // This means some phi nodes are dependent on each other. 1277193323Sed // Avoid infinite looping! 1278193323Sed return false; 1279193323Sed if (!LoadUsingPHIs.insert(PN)) 1280193323Sed // If we have already analyzed this PHI, then it is safe. 1281193323Sed continue; 1282218893Sdim 1283193323Sed // Make sure all uses of the PHI are simple enough to transform. 1284193323Sed if (!LoadUsesSimpleEnoughForHeapSRA(PN, 1285193323Sed LoadUsingPHIs, LoadUsingPHIsPerLoad)) 1286193323Sed return false; 1287218893Sdim 1288193323Sed continue; 1289193323Sed } 1290218893Sdim 1291193323Sed // Otherwise we don't know what this is, not ok. 1292193323Sed return false; 1293193323Sed } 1294218893Sdim 1295193323Sed return true; 1296193323Sed} 1297193323Sed 1298193323Sed 1299193323Sed/// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from 1300193323Sed/// GV are simple enough to perform HeapSRA, return true. 1301206083Srdivackystatic bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable *GV, 1302198090Srdivacky Instruction *StoredVal) { 1303206083Srdivacky SmallPtrSet<const PHINode*, 32> LoadUsingPHIs; 1304206083Srdivacky SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad; 1305207618Srdivacky for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); 1306207618Srdivacky UI != E; ++UI) 1307206083Srdivacky if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 1308193323Sed if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs, 1309193323Sed LoadUsingPHIsPerLoad)) 1310193323Sed return false; 1311193323Sed LoadUsingPHIsPerLoad.clear(); 1312193323Sed } 1313218893Sdim 1314193323Sed // If we reach here, we know that all uses of the loads and transitive uses 1315193323Sed // (through PHI nodes) are simple enough to transform. However, we don't know 1316218893Sdim // that all inputs the to the PHI nodes are in the same equivalence sets. 1317193323Sed // Check to verify that all operands of the PHIs are either PHIS that can be 1318193323Sed // transformed, loads from GV, or MI itself. 1319207618Srdivacky for (SmallPtrSet<const PHINode*, 32>::const_iterator I = LoadUsingPHIs.begin() 1320207618Srdivacky , E = LoadUsingPHIs.end(); I != E; ++I) { 1321206083Srdivacky const PHINode *PN = *I; 1322193323Sed for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) { 1323193323Sed Value *InVal = PN->getIncomingValue(op); 1324218893Sdim 1325193323Sed // PHI of the stored value itself is ok. 1326198090Srdivacky if (InVal == StoredVal) continue; 1327218893Sdim 1328206083Srdivacky if (const PHINode *InPN = dyn_cast<PHINode>(InVal)) { 1329193323Sed // One of the PHIs in our set is (optimistically) ok. 1330193323Sed if (LoadUsingPHIs.count(InPN)) 1331193323Sed continue; 1332193323Sed return false; 1333193323Sed } 1334218893Sdim 1335193323Sed // Load from GV is ok. 1336206083Srdivacky if (const LoadInst *LI = dyn_cast<LoadInst>(InVal)) 1337193323Sed if (LI->getOperand(0) == GV) 1338193323Sed continue; 1339218893Sdim 1340193323Sed // UNDEF? NULL? 1341218893Sdim 1342193323Sed // Anything else is rejected. 1343193323Sed return false; 1344193323Sed } 1345193323Sed } 1346218893Sdim 1347193323Sed return true; 1348193323Sed} 1349193323Sed 1350193323Sedstatic Value *GetHeapSROAValue(Value *V, unsigned FieldNo, 1351193323Sed DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 1352199481Srdivacky std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { 1353193323Sed std::vector<Value*> &FieldVals = InsertedScalarizedValues[V]; 1354218893Sdim 1355193323Sed if (FieldNo >= FieldVals.size()) 1356193323Sed FieldVals.resize(FieldNo+1); 1357218893Sdim 1358193323Sed // If we already have this value, just reuse the previously scalarized 1359193323Sed // version. 1360193323Sed if (Value *FieldVal = FieldVals[FieldNo]) 1361193323Sed return FieldVal; 1362218893Sdim 1363193323Sed // Depending on what instruction this is, we have several cases. 1364193323Sed Value *Result; 1365193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(V)) { 1366193323Sed // This is a scalarized version of the load from the global. Just create 1367193323Sed // a new Load of the scalarized global. 1368193323Sed Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo, 1369193323Sed InsertedScalarizedValues, 1370199481Srdivacky PHIsToRewrite), 1371198090Srdivacky LI->getName()+".f"+Twine(FieldNo), LI); 1372193323Sed } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 1373193323Sed // PN's type is pointer to struct. Make a new PHI of pointer to struct 1374193323Sed // field. 1375226633Sdim StructType *ST = 1376193323Sed cast<StructType>(cast<PointerType>(PN->getType())->getElementType()); 1377218893Sdim 1378221345Sdim PHINode *NewPN = 1379198090Srdivacky PHINode::Create(PointerType::getUnqual(ST->getElementType(FieldNo)), 1380221345Sdim PN->getNumIncomingValues(), 1381198090Srdivacky PN->getName()+".f"+Twine(FieldNo), PN); 1382221345Sdim Result = NewPN; 1383193323Sed PHIsToRewrite.push_back(std::make_pair(PN, FieldNo)); 1384193323Sed } else { 1385198090Srdivacky llvm_unreachable("Unknown usable value"); 1386193323Sed } 1387218893Sdim 1388193323Sed return FieldVals[FieldNo] = Result; 1389193323Sed} 1390193323Sed 1391193323Sed/// RewriteHeapSROALoadUser - Given a load instruction and a value derived from 1392193323Sed/// the load, rewrite the derived value to use the HeapSRoA'd load. 1393218893Sdimstatic void RewriteHeapSROALoadUser(Instruction *LoadUser, 1394193323Sed DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 1395199481Srdivacky std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { 1396193323Sed // If this is a comparison against null, handle it. 1397193323Sed if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) { 1398193323Sed assert(isa<ConstantPointerNull>(SCI->getOperand(1))); 1399193323Sed // If we have a setcc of the loaded pointer, we can use a setcc of any 1400193323Sed // field. 1401193323Sed Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0, 1402199481Srdivacky InsertedScalarizedValues, PHIsToRewrite); 1403218893Sdim 1404198090Srdivacky Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr, 1405218893Sdim Constant::getNullValue(NPtr->getType()), 1406198090Srdivacky SCI->getName()); 1407193323Sed SCI->replaceAllUsesWith(New); 1408193323Sed SCI->eraseFromParent(); 1409193323Sed return; 1410193323Sed } 1411218893Sdim 1412193323Sed // Handle 'getelementptr Ptr, Idx, i32 FieldNo ...' 1413193323Sed if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) { 1414193323Sed assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2)) 1415193323Sed && "Unexpected GEPI!"); 1416218893Sdim 1417193323Sed // Load the pointer for this field. 1418193323Sed unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); 1419193323Sed Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo, 1420199481Srdivacky InsertedScalarizedValues, PHIsToRewrite); 1421218893Sdim 1422193323Sed // Create the new GEP idx vector. 1423193323Sed SmallVector<Value*, 8> GEPIdx; 1424193323Sed GEPIdx.push_back(GEPI->getOperand(1)); 1425193323Sed GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end()); 1426218893Sdim 1427226633Sdim Value *NGEPI = GetElementPtrInst::Create(NewPtr, GEPIdx, 1428193323Sed GEPI->getName(), GEPI); 1429193323Sed GEPI->replaceAllUsesWith(NGEPI); 1430193323Sed GEPI->eraseFromParent(); 1431193323Sed return; 1432193323Sed } 1433193323Sed 1434193323Sed // Recursively transform the users of PHI nodes. This will lazily create the 1435193323Sed // PHIs that are needed for individual elements. Keep track of what PHIs we 1436193323Sed // see in InsertedScalarizedValues so that we don't get infinite loops (very 1437193323Sed // antisocial). If the PHI is already in InsertedScalarizedValues, it has 1438193323Sed // already been seen first by another load, so its uses have already been 1439193323Sed // processed. 1440193323Sed PHINode *PN = cast<PHINode>(LoadUser); 1441226633Sdim if (!InsertedScalarizedValues.insert(std::make_pair(PN, 1442226633Sdim std::vector<Value*>())).second) 1443226633Sdim return; 1444218893Sdim 1445193323Sed // If this is the first time we've seen this PHI, recursively process all 1446193323Sed // users. 1447193323Sed for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; ) { 1448193323Sed Instruction *User = cast<Instruction>(*UI++); 1449199481Srdivacky RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite); 1450193323Sed } 1451193323Sed} 1452193323Sed 1453193323Sed/// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global. Ptr 1454193323Sed/// is a value loaded from the global. Eliminate all uses of Ptr, making them 1455193323Sed/// use FieldGlobals instead. All uses of loaded values satisfy 1456193323Sed/// AllGlobalLoadUsesSimpleEnoughForHeapSRA. 1457218893Sdimstatic void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load, 1458193323Sed DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 1459199481Srdivacky std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { 1460193323Sed for (Value::use_iterator UI = Load->use_begin(), E = Load->use_end(); 1461193323Sed UI != E; ) { 1462193323Sed Instruction *User = cast<Instruction>(*UI++); 1463199481Srdivacky RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite); 1464193323Sed } 1465218893Sdim 1466193323Sed if (Load->use_empty()) { 1467193323Sed Load->eraseFromParent(); 1468193323Sed InsertedScalarizedValues.erase(Load); 1469193323Sed } 1470193323Sed} 1471193323Sed 1472198090Srdivacky/// PerformHeapAllocSRoA - CI is an allocation of an array of structures. Break 1473198090Srdivacky/// it up into multiple allocations of arrays of the fields. 1474198953Srdivackystatic GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI, 1475243830Sdim Value *NElems, DataLayout *TD, 1476243830Sdim const TargetLibraryInfo *TLI) { 1477202375Srdivacky DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *CI << '\n'); 1478243830Sdim Type *MAT = getMallocAllocatedType(CI, TLI); 1479226633Sdim StructType *STy = cast<StructType>(MAT); 1480198090Srdivacky 1481198090Srdivacky // There is guaranteed to be at least one use of the malloc (storing 1482198090Srdivacky // it into GV). If there are other uses, change them to be uses of 1483198090Srdivacky // the global to simplify later code. This also deletes the store 1484198090Srdivacky // into GV. 1485198953Srdivacky ReplaceUsesOfMallocWithGlobal(CI, GV); 1486198953Srdivacky 1487198090Srdivacky // Okay, at this point, there are no users of the malloc. Insert N 1488198090Srdivacky // new mallocs at the same place as CI, and N globals. 1489198090Srdivacky std::vector<Value*> FieldGlobals; 1490198090Srdivacky std::vector<Value*> FieldMallocs; 1491218893Sdim 1492198090Srdivacky for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){ 1493226633Sdim Type *FieldTy = STy->getElementType(FieldNo); 1494226633Sdim PointerType *PFieldTy = PointerType::getUnqual(FieldTy); 1495218893Sdim 1496198090Srdivacky GlobalVariable *NGV = 1497198090Srdivacky new GlobalVariable(*GV->getParent(), 1498198090Srdivacky PFieldTy, false, GlobalValue::InternalLinkage, 1499198090Srdivacky Constant::getNullValue(PFieldTy), 1500198090Srdivacky GV->getName() + ".f" + Twine(FieldNo), GV, 1501239462Sdim GV->getThreadLocalMode()); 1502198090Srdivacky FieldGlobals.push_back(NGV); 1503218893Sdim 1504198953Srdivacky unsigned TypeSize = TD->getTypeAllocSize(FieldTy); 1505226633Sdim if (StructType *ST = dyn_cast<StructType>(FieldTy)) 1506198953Srdivacky TypeSize = TD->getStructLayout(ST)->getSizeInBytes(); 1507226633Sdim Type *IntPtrTy = TD->getIntPtrType(CI->getContext()); 1508198953Srdivacky Value *NMI = CallInst::CreateMalloc(CI, IntPtrTy, FieldTy, 1509198953Srdivacky ConstantInt::get(IntPtrTy, TypeSize), 1510210299Sed NElems, 0, 1511198953Srdivacky CI->getName() + ".f" + Twine(FieldNo)); 1512204642Srdivacky FieldMallocs.push_back(NMI); 1513198953Srdivacky new StoreInst(NMI, NGV, CI); 1514198090Srdivacky } 1515218893Sdim 1516198090Srdivacky // The tricky aspect of this transformation is handling the case when malloc 1517198090Srdivacky // fails. In the original code, malloc failing would set the result pointer 1518198090Srdivacky // of malloc to null. In this case, some mallocs could succeed and others 1519198090Srdivacky // could fail. As such, we emit code that looks like this: 1520198090Srdivacky // F0 = malloc(field0) 1521198090Srdivacky // F1 = malloc(field1) 1522198090Srdivacky // F2 = malloc(field2) 1523198090Srdivacky // if (F0 == 0 || F1 == 0 || F2 == 0) { 1524198090Srdivacky // if (F0) { free(F0); F0 = 0; } 1525198090Srdivacky // if (F1) { free(F1); F1 = 0; } 1526198090Srdivacky // if (F2) { free(F2); F2 = 0; } 1527198090Srdivacky // } 1528199481Srdivacky // The malloc can also fail if its argument is too large. 1529210299Sed Constant *ConstantZero = ConstantInt::get(CI->getArgOperand(0)->getType(), 0); 1530210299Sed Value *RunningOr = new ICmpInst(CI, ICmpInst::ICMP_SLT, CI->getArgOperand(0), 1531199481Srdivacky ConstantZero, "isneg"); 1532198090Srdivacky for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) { 1533198953Srdivacky Value *Cond = new ICmpInst(CI, ICmpInst::ICMP_EQ, FieldMallocs[i], 1534198953Srdivacky Constant::getNullValue(FieldMallocs[i]->getType()), 1535198953Srdivacky "isnull"); 1536199481Srdivacky RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI); 1537198090Srdivacky } 1538198090Srdivacky 1539198090Srdivacky // Split the basic block at the old malloc. 1540198953Srdivacky BasicBlock *OrigBB = CI->getParent(); 1541198953Srdivacky BasicBlock *ContBB = OrigBB->splitBasicBlock(CI, "malloc_cont"); 1542218893Sdim 1543198090Srdivacky // Create the block to check the first condition. Put all these blocks at the 1544198090Srdivacky // end of the function as they are unlikely to be executed. 1545199481Srdivacky BasicBlock *NullPtrBlock = BasicBlock::Create(OrigBB->getContext(), 1546199481Srdivacky "malloc_ret_null", 1547198090Srdivacky OrigBB->getParent()); 1548218893Sdim 1549198090Srdivacky // Remove the uncond branch from OrigBB to ContBB, turning it into a cond 1550198090Srdivacky // branch on RunningOr. 1551198090Srdivacky OrigBB->getTerminator()->eraseFromParent(); 1552198090Srdivacky BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB); 1553218893Sdim 1554198090Srdivacky // Within the NullPtrBlock, we need to emit a comparison and branch for each 1555198090Srdivacky // pointer, because some may be null while others are not. 1556198090Srdivacky for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 1557198090Srdivacky Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock); 1558218893Sdim Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal, 1559226633Sdim Constant::getNullValue(GVVal->getType())); 1560199481Srdivacky BasicBlock *FreeBlock = BasicBlock::Create(Cmp->getContext(), "free_it", 1561198090Srdivacky OrigBB->getParent()); 1562199481Srdivacky BasicBlock *NextBlock = BasicBlock::Create(Cmp->getContext(), "next", 1563198090Srdivacky OrigBB->getParent()); 1564198892Srdivacky Instruction *BI = BranchInst::Create(FreeBlock, NextBlock, 1565198892Srdivacky Cmp, NullPtrBlock); 1566198090Srdivacky 1567198090Srdivacky // Fill in FreeBlock. 1568198892Srdivacky CallInst::CreateFree(GVVal, BI); 1569198090Srdivacky new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i], 1570198090Srdivacky FreeBlock); 1571198090Srdivacky BranchInst::Create(NextBlock, FreeBlock); 1572218893Sdim 1573198090Srdivacky NullPtrBlock = NextBlock; 1574198090Srdivacky } 1575218893Sdim 1576198090Srdivacky BranchInst::Create(ContBB, NullPtrBlock); 1577198953Srdivacky 1578198953Srdivacky // CI is no longer needed, remove it. 1579198090Srdivacky CI->eraseFromParent(); 1580198090Srdivacky 1581198090Srdivacky /// InsertedScalarizedLoads - As we process loads, if we can't immediately 1582198090Srdivacky /// update all uses of the load, keep track of what scalarized loads are 1583198090Srdivacky /// inserted for a given load. 1584198090Srdivacky DenseMap<Value*, std::vector<Value*> > InsertedScalarizedValues; 1585198090Srdivacky InsertedScalarizedValues[GV] = FieldGlobals; 1586218893Sdim 1587198090Srdivacky std::vector<std::pair<PHINode*, unsigned> > PHIsToRewrite; 1588218893Sdim 1589198090Srdivacky // Okay, the malloc site is completely handled. All of the uses of GV are now 1590198090Srdivacky // loads, and all uses of those loads are simple. Rewrite them to use loads 1591198090Srdivacky // of the per-field globals instead. 1592198090Srdivacky for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;) { 1593198090Srdivacky Instruction *User = cast<Instruction>(*UI++); 1594218893Sdim 1595198090Srdivacky if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 1596199481Srdivacky RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite); 1597198090Srdivacky continue; 1598198090Srdivacky } 1599218893Sdim 1600198090Srdivacky // Must be a store of null. 1601198090Srdivacky StoreInst *SI = cast<StoreInst>(User); 1602198090Srdivacky assert(isa<ConstantPointerNull>(SI->getOperand(0)) && 1603198090Srdivacky "Unexpected heap-sra user!"); 1604218893Sdim 1605198090Srdivacky // Insert a store of null into each global. 1606198090Srdivacky for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 1607226633Sdim PointerType *PT = cast<PointerType>(FieldGlobals[i]->getType()); 1608198090Srdivacky Constant *Null = Constant::getNullValue(PT->getElementType()); 1609198090Srdivacky new StoreInst(Null, FieldGlobals[i], SI); 1610198090Srdivacky } 1611198090Srdivacky // Erase the original store. 1612198090Srdivacky SI->eraseFromParent(); 1613198090Srdivacky } 1614198090Srdivacky 1615198090Srdivacky // While we have PHIs that are interesting to rewrite, do it. 1616198090Srdivacky while (!PHIsToRewrite.empty()) { 1617198090Srdivacky PHINode *PN = PHIsToRewrite.back().first; 1618198090Srdivacky unsigned FieldNo = PHIsToRewrite.back().second; 1619198090Srdivacky PHIsToRewrite.pop_back(); 1620198090Srdivacky PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]); 1621198090Srdivacky assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi"); 1622198090Srdivacky 1623198090Srdivacky // Add all the incoming values. This can materialize more phis. 1624198090Srdivacky for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1625198090Srdivacky Value *InVal = PN->getIncomingValue(i); 1626198090Srdivacky InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues, 1627199481Srdivacky PHIsToRewrite); 1628198090Srdivacky FieldPN->addIncoming(InVal, PN->getIncomingBlock(i)); 1629198090Srdivacky } 1630198090Srdivacky } 1631218893Sdim 1632198090Srdivacky // Drop all inter-phi links and any loads that made it this far. 1633198090Srdivacky for (DenseMap<Value*, std::vector<Value*> >::iterator 1634198090Srdivacky I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end(); 1635198090Srdivacky I != E; ++I) { 1636198090Srdivacky if (PHINode *PN = dyn_cast<PHINode>(I->first)) 1637198090Srdivacky PN->dropAllReferences(); 1638198090Srdivacky else if (LoadInst *LI = dyn_cast<LoadInst>(I->first)) 1639198090Srdivacky LI->dropAllReferences(); 1640198090Srdivacky } 1641218893Sdim 1642198090Srdivacky // Delete all the phis and loads now that inter-references are dead. 1643198090Srdivacky for (DenseMap<Value*, std::vector<Value*> >::iterator 1644198090Srdivacky I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end(); 1645198090Srdivacky I != E; ++I) { 1646198090Srdivacky if (PHINode *PN = dyn_cast<PHINode>(I->first)) 1647198090Srdivacky PN->eraseFromParent(); 1648198090Srdivacky else if (LoadInst *LI = dyn_cast<LoadInst>(I->first)) 1649198090Srdivacky LI->eraseFromParent(); 1650198090Srdivacky } 1651218893Sdim 1652198090Srdivacky // The old global is now dead, remove it. 1653198090Srdivacky GV->eraseFromParent(); 1654198090Srdivacky 1655198090Srdivacky ++NumHeapSRA; 1656198090Srdivacky return cast<GlobalVariable>(FieldGlobals[0]); 1657198090Srdivacky} 1658198090Srdivacky 1659193323Sed/// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a 1660193323Sed/// pointer global variable with a single value stored it that is a malloc or 1661193323Sed/// cast of malloc. 1662193323Sedstatic bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, 1663198090Srdivacky CallInst *CI, 1664226633Sdim Type *AllocTy, 1665234353Sdim AtomicOrdering Ordering, 1666198090Srdivacky Module::global_iterator &GVI, 1667243830Sdim DataLayout *TD, 1668234353Sdim TargetLibraryInfo *TLI) { 1669207618Srdivacky if (!TD) 1670207618Srdivacky return false; 1671218893Sdim 1672198090Srdivacky // If this is a malloc of an abstract type, don't touch it. 1673198090Srdivacky if (!AllocTy->isSized()) 1674198090Srdivacky return false; 1675198090Srdivacky 1676198090Srdivacky // We can't optimize this global unless all uses of it are *known* to be 1677198090Srdivacky // of the malloc value, not of the null initializer value (consider a use 1678198090Srdivacky // that compares the global's value against zero to see if the malloc has 1679198090Srdivacky // been reached). To do this, we check to see if all uses of the global 1680198090Srdivacky // would trap if the global were null: this proves that they must all 1681198090Srdivacky // happen after the malloc. 1682198090Srdivacky if (!AllUsesOfLoadedValueWillTrapIfNull(GV)) 1683198090Srdivacky return false; 1684198090Srdivacky 1685198090Srdivacky // We can't optimize this if the malloc itself is used in a complex way, 1686198090Srdivacky // for example, being stored into multiple globals. This allows the 1687234353Sdim // malloc to be stored into the specified global, loaded icmp'd, and 1688198090Srdivacky // GEP'd. These are all things we could transform to using the global 1689198090Srdivacky // for. 1690207618Srdivacky SmallPtrSet<const PHINode*, 8> PHIs; 1691207618Srdivacky if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV, PHIs)) 1692207618Srdivacky return false; 1693198090Srdivacky 1694198090Srdivacky // If we have a global that is only initialized with a fixed size malloc, 1695198090Srdivacky // transform the program to use global memory instead of malloc'd memory. 1696198090Srdivacky // This eliminates dynamic allocation, avoids an indirection accessing the 1697198090Srdivacky // data, and exposes the resultant global to further GlobalOpt. 1698198396Srdivacky // We cannot optimize the malloc if we cannot determine malloc array size. 1699243830Sdim Value *NElems = getMallocArraySize(CI, TD, TLI, true); 1700207618Srdivacky if (!NElems) 1701207618Srdivacky return false; 1702207618Srdivacky 1703207618Srdivacky if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems)) 1704207618Srdivacky // Restrict this transformation to only working on small allocations 1705207618Srdivacky // (2048 bytes currently), as we don't want to introduce a 16M global or 1706207618Srdivacky // something. 1707207618Srdivacky if (NElements->getZExtValue() * TD->getTypeAllocSize(AllocTy) < 2048) { 1708234353Sdim GVI = OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, TD, TLI); 1709207618Srdivacky return true; 1710207618Srdivacky } 1711218893Sdim 1712207618Srdivacky // If the allocation is an array of structures, consider transforming this 1713207618Srdivacky // into multiple malloc'd arrays, one for each field. This is basically 1714207618Srdivacky // SRoA for malloc'd memory. 1715198090Srdivacky 1716234353Sdim if (Ordering != NotAtomic) 1717234353Sdim return false; 1718234353Sdim 1719207618Srdivacky // If this is an allocation of a fixed size array of structs, analyze as a 1720207618Srdivacky // variable size array. malloc [100 x struct],1 -> malloc struct, 100 1721210299Sed if (NElems == ConstantInt::get(CI->getArgOperand(0)->getType(), 1)) 1722226633Sdim if (ArrayType *AT = dyn_cast<ArrayType>(AllocTy)) 1723207618Srdivacky AllocTy = AT->getElementType(); 1724210299Sed 1725226633Sdim StructType *AllocSTy = dyn_cast<StructType>(AllocTy); 1726207618Srdivacky if (!AllocSTy) 1727207618Srdivacky return false; 1728198090Srdivacky 1729207618Srdivacky // This the structure has an unreasonable number of fields, leave it 1730207618Srdivacky // alone. 1731207618Srdivacky if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 && 1732207618Srdivacky AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV, CI)) { 1733207618Srdivacky 1734207618Srdivacky // If this is a fixed size array, transform the Malloc to be an alloc of 1735207618Srdivacky // structs. malloc [100 x struct],1 -> malloc struct, 100 1736243830Sdim if (ArrayType *AT = dyn_cast<ArrayType>(getMallocAllocatedType(CI, TLI))) { 1737226633Sdim Type *IntPtrTy = TD->getIntPtrType(CI->getContext()); 1738207618Srdivacky unsigned TypeSize = TD->getStructLayout(AllocSTy)->getSizeInBytes(); 1739207618Srdivacky Value *AllocSize = ConstantInt::get(IntPtrTy, TypeSize); 1740207618Srdivacky Value *NumElements = ConstantInt::get(IntPtrTy, AT->getNumElements()); 1741207618Srdivacky Instruction *Malloc = CallInst::CreateMalloc(CI, IntPtrTy, AllocSTy, 1742207618Srdivacky AllocSize, NumElements, 1743210299Sed 0, CI->getName()); 1744207618Srdivacky Instruction *Cast = new BitCastInst(Malloc, CI->getType(), "tmp", CI); 1745207618Srdivacky CI->replaceAllUsesWith(Cast); 1746207618Srdivacky CI->eraseFromParent(); 1747239462Sdim if (BitCastInst *BCI = dyn_cast<BitCastInst>(Malloc)) 1748239462Sdim CI = cast<CallInst>(BCI->getOperand(0)); 1749239462Sdim else 1750239462Sdim CI = cast<CallInst>(Malloc); 1751207618Srdivacky } 1752218893Sdim 1753243830Sdim GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, TD, TLI, true), 1754243830Sdim TD, TLI); 1755207618Srdivacky return true; 1756198090Srdivacky } 1757218893Sdim 1758198090Srdivacky return false; 1759218893Sdim} 1760198090Srdivacky 1761193323Sed// OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge 1762193323Sed// that only one value (besides its initializer) is ever stored to the global. 1763193323Sedstatic bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, 1764234353Sdim AtomicOrdering Ordering, 1765193323Sed Module::global_iterator &GVI, 1766243830Sdim DataLayout *TD, TargetLibraryInfo *TLI) { 1767193323Sed // Ignore no-op GEPs and bitcasts. 1768193323Sed StoredOnceVal = StoredOnceVal->stripPointerCasts(); 1769193323Sed 1770193323Sed // If we are dealing with a pointer global that is initialized to null and 1771193323Sed // only has one (non-null) value stored into it, then we can optimize any 1772193323Sed // users of the loaded value (often calls and loads) that would trap if the 1773193323Sed // value was null. 1774204642Srdivacky if (GV->getInitializer()->getType()->isPointerTy() && 1775193323Sed GV->getInitializer()->isNullValue()) { 1776193323Sed if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) { 1777193323Sed if (GV->getInitializer()->getType() != SOVC->getType()) 1778223017Sdim SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); 1779193323Sed 1780193323Sed // Optimize away any trapping uses of the loaded value. 1781234353Sdim if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, TD, TLI)) 1782193323Sed return true; 1783243830Sdim } else if (CallInst *CI = extractMallocCall(StoredOnceVal, TLI)) { 1784243830Sdim Type *MallocType = getMallocAllocatedType(CI, TLI); 1785234353Sdim if (MallocType && 1786234353Sdim TryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType, Ordering, GVI, 1787234353Sdim TD, TLI)) 1788198953Srdivacky return true; 1789193323Sed } 1790193323Sed } 1791193323Sed 1792193323Sed return false; 1793193323Sed} 1794193323Sed 1795193323Sed/// TryToShrinkGlobalToBoolean - At this point, we have learned that the only 1796193323Sed/// two values ever stored into GV are its initializer and OtherVal. See if we 1797193323Sed/// can shrink the global into a boolean and select between the two values 1798193323Sed/// whenever it is used. This exposes the values to other scalar optimizations. 1799199481Srdivackystatic bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { 1800226633Sdim Type *GVElType = GV->getType()->getElementType(); 1801218893Sdim 1802193323Sed // If GVElType is already i1, it is already shrunk. If the type of the GV is 1803193323Sed // an FP value, pointer or vector, don't do this optimization because a select 1804193323Sed // between them is very expensive and unlikely to lead to later 1805193323Sed // simplification. In these cases, we typically end up with "cond ? v1 : v2" 1806193323Sed // where v1 and v2 both require constant pool loads, a big loss. 1807199481Srdivacky if (GVElType == Type::getInt1Ty(GV->getContext()) || 1808203954Srdivacky GVElType->isFloatingPointTy() || 1809204642Srdivacky GVElType->isPointerTy() || GVElType->isVectorTy()) 1810193323Sed return false; 1811210299Sed 1812193323Sed // Walk the use list of the global seeing if all the uses are load or store. 1813193323Sed // If there is anything else, bail out. 1814210299Sed for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I){ 1815210299Sed User *U = *I; 1816210299Sed if (!isa<LoadInst>(U) && !isa<StoreInst>(U)) 1817193323Sed return false; 1818210299Sed } 1819210299Sed 1820202375Srdivacky DEBUG(dbgs() << " *** SHRINKING TO BOOL: " << *GV); 1821218893Sdim 1822193323Sed // Create the new global, initializing it to false. 1823199481Srdivacky GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(GV->getContext()), 1824199481Srdivacky false, 1825218893Sdim GlobalValue::InternalLinkage, 1826199481Srdivacky ConstantInt::getFalse(GV->getContext()), 1827193323Sed GV->getName()+".b", 1828249423Sdim GV->getThreadLocalMode(), 1829249423Sdim GV->getType()->getAddressSpace()); 1830193323Sed GV->getParent()->getGlobalList().insert(GV, NewGV); 1831193323Sed 1832193323Sed Constant *InitVal = GV->getInitializer(); 1833199481Srdivacky assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) && 1834198090Srdivacky "No reason to shrink to bool!"); 1835193323Sed 1836193323Sed // If initialized to zero and storing one into the global, we can use a cast 1837193323Sed // instead of a select to synthesize the desired value. 1838193323Sed bool IsOneZero = false; 1839193323Sed if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) 1840193323Sed IsOneZero = InitVal->isNullValue() && CI->isOne(); 1841193323Sed 1842193323Sed while (!GV->use_empty()) { 1843193323Sed Instruction *UI = cast<Instruction>(GV->use_back()); 1844193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 1845193323Sed // Change the store into a boolean store. 1846193323Sed bool StoringOther = SI->getOperand(0) == OtherVal; 1847193323Sed // Only do this if we weren't storing a loaded value. 1848193323Sed Value *StoreVal; 1849249423Sdim if (StoringOther || SI->getOperand(0) == InitVal) { 1850199481Srdivacky StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()), 1851199481Srdivacky StoringOther); 1852249423Sdim } else { 1853193323Sed // Otherwise, we are storing a previously loaded copy. To do this, 1854193323Sed // change the copy from copying the original value to just copying the 1855193323Sed // bool. 1856193323Sed Instruction *StoredVal = cast<Instruction>(SI->getOperand(0)); 1857193323Sed 1858210299Sed // If we've already replaced the input, StoredVal will be a cast or 1859193323Sed // select instruction. If not, it will be a load of the original 1860193323Sed // global. 1861193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) { 1862193323Sed assert(LI->getOperand(0) == GV && "Not a copy!"); 1863193323Sed // Insert a new load, to preserve the saved value. 1864234353Sdim StoreVal = new LoadInst(NewGV, LI->getName()+".b", false, 0, 1865234353Sdim LI->getOrdering(), LI->getSynchScope(), LI); 1866193323Sed } else { 1867193323Sed assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && 1868193323Sed "This is not a form that we understand!"); 1869193323Sed StoreVal = StoredVal->getOperand(0); 1870193323Sed assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!"); 1871193323Sed } 1872193323Sed } 1873234353Sdim new StoreInst(StoreVal, NewGV, false, 0, 1874234353Sdim SI->getOrdering(), SI->getSynchScope(), SI); 1875193323Sed } else { 1876193323Sed // Change the load into a load of bool then a select. 1877193323Sed LoadInst *LI = cast<LoadInst>(UI); 1878234353Sdim LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", false, 0, 1879234353Sdim LI->getOrdering(), LI->getSynchScope(), LI); 1880193323Sed Value *NSI; 1881193323Sed if (IsOneZero) 1882193323Sed NSI = new ZExtInst(NLI, LI->getType(), "", LI); 1883193323Sed else 1884193323Sed NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI); 1885193323Sed NSI->takeName(LI); 1886193323Sed LI->replaceAllUsesWith(NSI); 1887193323Sed } 1888193323Sed UI->eraseFromParent(); 1889193323Sed } 1890193323Sed 1891249423Sdim // Retain the name of the old global variable. People who are debugging their 1892249423Sdim // programs may expect these variables to be named the same. 1893249423Sdim NewGV->takeName(GV); 1894193323Sed GV->eraseFromParent(); 1895193323Sed return true; 1896193323Sed} 1897193323Sed 1898193323Sed 1899234353Sdim/// ProcessGlobal - Analyze the specified global variable and optimize it if 1900234353Sdim/// possible. If we make a change, return true. 1901218893Sdimbool GlobalOpt::ProcessGlobal(GlobalVariable *GV, 1902218893Sdim Module::global_iterator &GVI) { 1903239462Sdim if (!GV->isDiscardableIfUnused()) 1904218893Sdim return false; 1905218893Sdim 1906218893Sdim // Do more involved optimizations if the global is internal. 1907193323Sed GV->removeDeadConstantUsers(); 1908193323Sed 1909193323Sed if (GV->use_empty()) { 1910202375Srdivacky DEBUG(dbgs() << "GLOBAL DEAD: " << *GV); 1911193323Sed GV->eraseFromParent(); 1912193323Sed ++NumDeleted; 1913193323Sed return true; 1914193323Sed } 1915193323Sed 1916239462Sdim if (!GV->hasLocalLinkage()) 1917239462Sdim return false; 1918239462Sdim 1919218893Sdim SmallPtrSet<const PHINode*, 16> PHIUsers; 1920218893Sdim GlobalStatus GS; 1921218893Sdim 1922218893Sdim if (AnalyzeGlobal(GV, GS, PHIUsers)) 1923218893Sdim return false; 1924218893Sdim 1925218893Sdim if (!GS.isCompared && !GV->hasUnnamedAddr()) { 1926218893Sdim GV->setUnnamedAddr(true); 1927218893Sdim NumUnnamed++; 1928218893Sdim } 1929218893Sdim 1930218893Sdim if (GV->isConstant() || !GV->hasInitializer()) 1931218893Sdim return false; 1932218893Sdim 1933218893Sdim return ProcessInternalGlobal(GV, GVI, PHIUsers, GS); 1934218893Sdim} 1935218893Sdim 1936218893Sdim/// ProcessInternalGlobal - Analyze the specified global variable and optimize 1937218893Sdim/// it if possible. If we make a change, return true. 1938218893Sdimbool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, 1939218893Sdim Module::global_iterator &GVI, 1940234353Sdim const SmallPtrSet<const PHINode*, 16> &PHIUsers, 1941218893Sdim const GlobalStatus &GS) { 1942218893Sdim // If this is a first class global and has only one accessing function 1943218893Sdim // and this function is main (which we know is not recursive we can make 1944218893Sdim // this global a local variable) we replace the global with a local alloca 1945218893Sdim // in this function. 1946218893Sdim // 1947218893Sdim // NOTE: It doesn't make sense to promote non single-value types since we 1948218893Sdim // are just replacing static memory to stack memory. 1949218893Sdim // 1950218893Sdim // If the global is in different address space, don't bring it to stack. 1951218893Sdim if (!GS.HasMultipleAccessingFunctions && 1952218893Sdim GS.AccessingFunction && !GS.HasNonInstructionUser && 1953218893Sdim GV->getType()->getElementType()->isSingleValueType() && 1954218893Sdim GS.AccessingFunction->getName() == "main" && 1955218893Sdim GS.AccessingFunction->hasExternalLinkage() && 1956218893Sdim GV->getType()->getAddressSpace() == 0) { 1957218893Sdim DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV); 1958234353Sdim Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction 1959218893Sdim ->getEntryBlock().begin()); 1960234353Sdim Type *ElemTy = GV->getType()->getElementType(); 1961218893Sdim // FIXME: Pass Global's alignment when globals have alignment 1962234353Sdim AllocaInst *Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), &FirstI); 1963218893Sdim if (!isa<UndefValue>(GV->getInitializer())) 1964218893Sdim new StoreInst(GV->getInitializer(), Alloca, &FirstI); 1965218893Sdim 1966218893Sdim GV->replaceAllUsesWith(Alloca); 1967218893Sdim GV->eraseFromParent(); 1968218893Sdim ++NumLocalized; 1969218893Sdim return true; 1970218893Sdim } 1971218893Sdim 1972218893Sdim // If the global is never loaded (but may be stored to), it is dead. 1973218893Sdim // Delete it now. 1974218893Sdim if (!GS.isLoaded) { 1975218893Sdim DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV); 1976218893Sdim 1977239462Sdim bool Changed; 1978239462Sdim if (isLeakCheckerRoot(GV)) { 1979239462Sdim // Delete any constant stores to the global. 1980243830Sdim Changed = CleanupPointerRootUsers(GV, TLI); 1981239462Sdim } else { 1982239462Sdim // Delete any stores we can find to the global. We may not be able to 1983239462Sdim // make it completely dead though. 1984239462Sdim Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); 1985239462Sdim } 1986218893Sdim 1987218893Sdim // If the global is dead now, delete it. 1988218893Sdim if (GV->use_empty()) { 1989218893Sdim GV->eraseFromParent(); 1990218893Sdim ++NumDeleted; 1991218893Sdim Changed = true; 1992193323Sed } 1993218893Sdim return Changed; 1994193323Sed 1995218893Sdim } else if (GS.StoredType <= GlobalStatus::isInitializerStored) { 1996249423Sdim DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n"); 1997218893Sdim GV->setConstant(true); 1998218893Sdim 1999218893Sdim // Clean up any obviously simplifiable users now. 2000234353Sdim CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); 2001218893Sdim 2002218893Sdim // If the global is dead now, just nuke it. 2003218893Sdim if (GV->use_empty()) { 2004218893Sdim DEBUG(dbgs() << " *** Marking constant allowed us to simplify " 2005218893Sdim << "all users and delete global!\n"); 2006193323Sed GV->eraseFromParent(); 2007218893Sdim ++NumDeleted; 2008193323Sed } 2009193323Sed 2010218893Sdim ++NumMarked; 2011218893Sdim return true; 2012218893Sdim } else if (!GV->getInitializer()->getType()->isSingleValueType()) { 2013243830Sdim if (DataLayout *TD = getAnalysisIfAvailable<DataLayout>()) 2014218893Sdim if (GlobalVariable *FirstNewGV = SRAGlobal(GV, *TD)) { 2015218893Sdim GVI = FirstNewGV; // Don't skip the newly produced globals! 2016218893Sdim return true; 2017193323Sed } 2018218893Sdim } else if (GS.StoredType == GlobalStatus::isStoredOnce) { 2019218893Sdim // If the initial value for the global was an undef value, and if only 2020218893Sdim // one other value was stored into it, we can just change the 2021218893Sdim // initializer to be the stored value, then delete all stores to the 2022218893Sdim // global. This allows us to mark it constant. 2023218893Sdim if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 2024218893Sdim if (isa<UndefValue>(GV->getInitializer())) { 2025218893Sdim // Change the initial value here. 2026218893Sdim GV->setInitializer(SOVConstant); 2027193323Sed 2028218893Sdim // Clean up any obviously simplifiable users now. 2029234353Sdim CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); 2030193323Sed 2031218893Sdim if (GV->use_empty()) { 2032218893Sdim DEBUG(dbgs() << " *** Substituting initializer allowed us to " 2033239462Sdim << "simplify all users and delete global!\n"); 2034218893Sdim GV->eraseFromParent(); 2035218893Sdim ++NumDeleted; 2036218893Sdim } else { 2037218893Sdim GVI = GV; 2038218893Sdim } 2039218893Sdim ++NumSubstitute; 2040218893Sdim return true; 2041193323Sed } 2042193323Sed 2043218893Sdim // Try to optimize globals based on the knowledge that only one value 2044218893Sdim // (besides its initializer) is ever stored to the global. 2045234353Sdim if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, GVI, 2046234353Sdim TD, TLI)) 2047193323Sed return true; 2048193323Sed 2049218893Sdim // Otherwise, if the global was not a boolean, we can shrink it to be a 2050218893Sdim // boolean. 2051218893Sdim if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 2052218893Sdim if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) { 2053218893Sdim ++NumShrunkToBool; 2054193323Sed return true; 2055218893Sdim } 2056218893Sdim } 2057193323Sed 2058193323Sed return false; 2059193323Sed} 2060193323Sed 2061193323Sed/// ChangeCalleesToFastCall - Walk all of the direct calls of the specified 2062193323Sed/// function, changing them to FastCC. 2063193323Sedstatic void ChangeCalleesToFastCall(Function *F) { 2064193323Sed for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 2065239462Sdim if (isa<BlockAddress>(*UI)) 2066239462Sdim continue; 2067193323Sed CallSite User(cast<Instruction>(*UI)); 2068193323Sed User.setCallingConv(CallingConv::Fast); 2069193323Sed } 2070193323Sed} 2071193323Sed 2072249423Sdimstatic AttributeSet StripNest(LLVMContext &C, const AttributeSet &Attrs) { 2073193323Sed for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) { 2074249423Sdim unsigned Index = Attrs.getSlotIndex(i); 2075249423Sdim if (!Attrs.getSlotAttributes(i).hasAttribute(Index, Attribute::Nest)) 2076193323Sed continue; 2077193323Sed 2078193323Sed // There can be only one. 2079249423Sdim return Attrs.removeAttribute(C, Index, Attribute::Nest); 2080193323Sed } 2081193323Sed 2082193323Sed return Attrs; 2083193323Sed} 2084193323Sed 2085193323Sedstatic void RemoveNestAttribute(Function *F) { 2086243830Sdim F->setAttributes(StripNest(F->getContext(), F->getAttributes())); 2087193323Sed for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 2088239462Sdim if (isa<BlockAddress>(*UI)) 2089239462Sdim continue; 2090193323Sed CallSite User(cast<Instruction>(*UI)); 2091243830Sdim User.setAttributes(StripNest(F->getContext(), User.getAttributes())); 2092193323Sed } 2093193323Sed} 2094193323Sed 2095193323Sedbool GlobalOpt::OptimizeFunctions(Module &M) { 2096193323Sed bool Changed = false; 2097193323Sed // Optimize functions. 2098193323Sed for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) { 2099193323Sed Function *F = FI++; 2100193323Sed // Functions without names cannot be referenced outside this module. 2101193323Sed if (!F->hasName() && !F->isDeclaration()) 2102193323Sed F->setLinkage(GlobalValue::InternalLinkage); 2103193323Sed F->removeDeadConstantUsers(); 2104234353Sdim if (F->isDefTriviallyDead()) { 2105198892Srdivacky F->eraseFromParent(); 2106193323Sed Changed = true; 2107193323Sed ++NumFnDeleted; 2108193323Sed } else if (F->hasLocalLinkage()) { 2109193323Sed if (F->getCallingConv() == CallingConv::C && !F->isVarArg() && 2110194178Sed !F->hasAddressTaken()) { 2111193323Sed // If this function has C calling conventions, is not a varargs 2112193323Sed // function, and is only called directly, promote it to use the Fast 2113193323Sed // calling convention. 2114193323Sed F->setCallingConv(CallingConv::Fast); 2115193323Sed ChangeCalleesToFastCall(F); 2116193323Sed ++NumFastCallFns; 2117193323Sed Changed = true; 2118193323Sed } 2119193323Sed 2120249423Sdim if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) && 2121194178Sed !F->hasAddressTaken()) { 2122193323Sed // The function is not used by a trampoline intrinsic, so it is safe 2123193323Sed // to remove the 'nest' attribute. 2124193323Sed RemoveNestAttribute(F); 2125193323Sed ++NumNestRemoved; 2126193323Sed Changed = true; 2127193323Sed } 2128193323Sed } 2129193323Sed } 2130193323Sed return Changed; 2131193323Sed} 2132193323Sed 2133193323Sedbool GlobalOpt::OptimizeGlobalVars(Module &M) { 2134193323Sed bool Changed = false; 2135193323Sed for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 2136193323Sed GVI != E; ) { 2137193323Sed GlobalVariable *GV = GVI++; 2138193323Sed // Global variables without names cannot be referenced outside this module. 2139193323Sed if (!GV->hasName() && !GV->isDeclaration()) 2140193323Sed GV->setLinkage(GlobalValue::InternalLinkage); 2141199989Srdivacky // Simplify the initializer. 2142199989Srdivacky if (GV->hasInitializer()) 2143199989Srdivacky if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GV->getInitializer())) { 2144234353Sdim Constant *New = ConstantFoldConstantExpression(CE, TD, TLI); 2145199989Srdivacky if (New && New != CE) 2146199989Srdivacky GV->setInitializer(New); 2147199989Srdivacky } 2148218893Sdim 2149218893Sdim Changed |= ProcessGlobal(GV, GVI); 2150193323Sed } 2151193323Sed return Changed; 2152193323Sed} 2153193323Sed 2154221345Sdim/// FindGlobalCtors - Find the llvm.global_ctors list, verifying that all 2155193323Sed/// initializers have an init priority of 65535. 2156193323SedGlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) { 2157218893Sdim GlobalVariable *GV = M.getGlobalVariable("llvm.global_ctors"); 2158218893Sdim if (GV == 0) return 0; 2159249423Sdim 2160218893Sdim // Verify that the initializer is simple enough for us to handle. We are 2161218893Sdim // only allowed to optimize the initializer if it is unique. 2162218893Sdim if (!GV->hasUniqueInitializer()) return 0; 2163221345Sdim 2164221345Sdim if (isa<ConstantAggregateZero>(GV->getInitializer())) 2165221345Sdim return GV; 2166221345Sdim ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); 2167221345Sdim 2168218893Sdim for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) { 2169221345Sdim if (isa<ConstantAggregateZero>(*i)) 2170221345Sdim continue; 2171221345Sdim ConstantStruct *CS = cast<ConstantStruct>(*i); 2172218893Sdim if (isa<ConstantPointerNull>(CS->getOperand(1))) 2173218893Sdim continue; 2174218893Sdim 2175218893Sdim // Must have a function or null ptr. 2176218893Sdim if (!isa<Function>(CS->getOperand(1))) 2177218893Sdim return 0; 2178218893Sdim 2179218893Sdim // Init priority must be standard. 2180221345Sdim ConstantInt *CI = cast<ConstantInt>(CS->getOperand(0)); 2181221345Sdim if (CI->getZExtValue() != 65535) 2182218893Sdim return 0; 2183218893Sdim } 2184218893Sdim 2185218893Sdim return GV; 2186193323Sed} 2187193323Sed 2188193323Sed/// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand, 2189193323Sed/// return a list of the functions and null terminator as a vector. 2190193323Sedstatic std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) { 2191221345Sdim if (GV->getInitializer()->isNullValue()) 2192221345Sdim return std::vector<Function*>(); 2193193323Sed ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); 2194193323Sed std::vector<Function*> Result; 2195193323Sed Result.reserve(CA->getNumOperands()); 2196193323Sed for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) { 2197193323Sed ConstantStruct *CS = cast<ConstantStruct>(*i); 2198193323Sed Result.push_back(dyn_cast<Function>(CS->getOperand(1))); 2199193323Sed } 2200193323Sed return Result; 2201193323Sed} 2202193323Sed 2203193323Sed/// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the 2204193323Sed/// specified array, returning the new global to use. 2205218893Sdimstatic GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, 2206199481Srdivacky const std::vector<Function*> &Ctors) { 2207193323Sed // If we made a change, reassemble the initializer list. 2208224145Sdim Constant *CSVals[2]; 2209224145Sdim CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()), 65535); 2210224145Sdim CSVals[1] = 0; 2211218893Sdim 2212226633Sdim StructType *StructTy = 2213224145Sdim cast <StructType>( 2214224145Sdim cast<ArrayType>(GCL->getType()->getElementType())->getElementType()); 2215224145Sdim 2216193323Sed // Create the new init list. 2217193323Sed std::vector<Constant*> CAList; 2218193323Sed for (unsigned i = 0, e = Ctors.size(); i != e; ++i) { 2219193323Sed if (Ctors[i]) { 2220193323Sed CSVals[1] = Ctors[i]; 2221193323Sed } else { 2222226633Sdim Type *FTy = FunctionType::get(Type::getVoidTy(GCL->getContext()), 2223199481Srdivacky false); 2224226633Sdim PointerType *PFTy = PointerType::getUnqual(FTy); 2225193323Sed CSVals[1] = Constant::getNullValue(PFTy); 2226199481Srdivacky CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()), 2227221345Sdim 0x7fffffff); 2228193323Sed } 2229224145Sdim CAList.push_back(ConstantStruct::get(StructTy, CSVals)); 2230193323Sed } 2231218893Sdim 2232193323Sed // Create the array initializer. 2233218893Sdim Constant *CA = ConstantArray::get(ArrayType::get(StructTy, 2234198090Srdivacky CAList.size()), CAList); 2235218893Sdim 2236193323Sed // If we didn't change the number of elements, don't create a new GV. 2237193323Sed if (CA->getType() == GCL->getInitializer()->getType()) { 2238193323Sed GCL->setInitializer(CA); 2239193323Sed return GCL; 2240193323Sed } 2241218893Sdim 2242193323Sed // Create the new global and insert it next to the existing list. 2243199481Srdivacky GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(), 2244193323Sed GCL->getLinkage(), CA, "", 2245239462Sdim GCL->getThreadLocalMode()); 2246193323Sed GCL->getParent()->getGlobalList().insert(GCL, NGV); 2247193323Sed NGV->takeName(GCL); 2248218893Sdim 2249193323Sed // Nuke the old list, replacing any uses with the new one. 2250193323Sed if (!GCL->use_empty()) { 2251193323Sed Constant *V = NGV; 2252193323Sed if (V->getType() != GCL->getType()) 2253193323Sed V = ConstantExpr::getBitCast(V, GCL->getType()); 2254193323Sed GCL->replaceAllUsesWith(V); 2255193323Sed } 2256193323Sed GCL->eraseFromParent(); 2257218893Sdim 2258193323Sed if (Ctors.size()) 2259193323Sed return NGV; 2260193323Sed else 2261193323Sed return 0; 2262193323Sed} 2263193323Sed 2264193323Sed 2265249423Sdimstatic inline bool 2266218893SdimisSimpleEnoughValueToCommit(Constant *C, 2267234353Sdim SmallPtrSet<Constant*, 8> &SimpleConstants, 2268243830Sdim const DataLayout *TD); 2269218893Sdim 2270218893Sdim 2271218893Sdim/// isSimpleEnoughValueToCommit - Return true if the specified constant can be 2272218893Sdim/// handled by the code generator. We don't want to generate something like: 2273218893Sdim/// void *X = &X/42; 2274218893Sdim/// because the code generator doesn't have a relocation that can handle that. 2275218893Sdim/// 2276218893Sdim/// This function should be called if C was not found (but just got inserted) 2277218893Sdim/// in SimpleConstants to avoid having to rescan the same constants all the 2278218893Sdim/// time. 2279218893Sdimstatic bool isSimpleEnoughValueToCommitHelper(Constant *C, 2280234353Sdim SmallPtrSet<Constant*, 8> &SimpleConstants, 2281243830Sdim const DataLayout *TD) { 2282218893Sdim // Simple integer, undef, constant aggregate zero, global addresses, etc are 2283218893Sdim // all supported. 2284218893Sdim if (C->getNumOperands() == 0 || isa<BlockAddress>(C) || 2285218893Sdim isa<GlobalValue>(C)) 2286218893Sdim return true; 2287249423Sdim 2288218893Sdim // Aggregate values are safe if all their elements are. 2289218893Sdim if (isa<ConstantArray>(C) || isa<ConstantStruct>(C) || 2290218893Sdim isa<ConstantVector>(C)) { 2291218893Sdim for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { 2292218893Sdim Constant *Op = cast<Constant>(C->getOperand(i)); 2293234353Sdim if (!isSimpleEnoughValueToCommit(Op, SimpleConstants, TD)) 2294218893Sdim return false; 2295218893Sdim } 2296218893Sdim return true; 2297218893Sdim } 2298249423Sdim 2299218893Sdim // We don't know exactly what relocations are allowed in constant expressions, 2300218893Sdim // so we allow &global+constantoffset, which is safe and uniformly supported 2301218893Sdim // across targets. 2302218893Sdim ConstantExpr *CE = cast<ConstantExpr>(C); 2303218893Sdim switch (CE->getOpcode()) { 2304218893Sdim case Instruction::BitCast: 2305234353Sdim // Bitcast is fine if the casted value is fine. 2306234353Sdim return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); 2307234353Sdim 2308218893Sdim case Instruction::IntToPtr: 2309218893Sdim case Instruction::PtrToInt: 2310234353Sdim // int <=> ptr is fine if the int type is the same size as the 2311234353Sdim // pointer type. 2312234353Sdim if (!TD || TD->getTypeSizeInBits(CE->getType()) != 2313234353Sdim TD->getTypeSizeInBits(CE->getOperand(0)->getType())) 2314234353Sdim return false; 2315234353Sdim return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); 2316249423Sdim 2317218893Sdim // GEP is fine if it is simple + constant offset. 2318218893Sdim case Instruction::GetElementPtr: 2319218893Sdim for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 2320218893Sdim if (!isa<ConstantInt>(CE->getOperand(i))) 2321218893Sdim return false; 2322234353Sdim return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); 2323249423Sdim 2324218893Sdim case Instruction::Add: 2325218893Sdim // We allow simple+cst. 2326218893Sdim if (!isa<ConstantInt>(CE->getOperand(1))) 2327218893Sdim return false; 2328234353Sdim return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); 2329218893Sdim } 2330218893Sdim return false; 2331218893Sdim} 2332218893Sdim 2333249423Sdimstatic inline bool 2334218893SdimisSimpleEnoughValueToCommit(Constant *C, 2335234353Sdim SmallPtrSet<Constant*, 8> &SimpleConstants, 2336243830Sdim const DataLayout *TD) { 2337218893Sdim // If we already checked this constant, we win. 2338218893Sdim if (!SimpleConstants.insert(C)) return true; 2339218893Sdim // Check the constant. 2340234353Sdim return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, TD); 2341218893Sdim} 2342218893Sdim 2343218893Sdim 2344193323Sed/// isSimpleEnoughPointerToCommit - Return true if this constant is simple 2345218893Sdim/// enough for us to understand. In particular, if it is a cast to anything 2346218893Sdim/// other than from one pointer type to another pointer type, we punt. 2347218893Sdim/// We basically just support direct accesses to globals and GEP's of 2348193323Sed/// globals. This should be kept up to date with CommitValueTo. 2349199481Srdivackystatic bool isSimpleEnoughPointerToCommit(Constant *C) { 2350198090Srdivacky // Conservatively, avoid aggregate types. This is because we don't 2351198090Srdivacky // want to worry about them partially overlapping other stores. 2352198090Srdivacky if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType()) 2353198090Srdivacky return false; 2354198090Srdivacky 2355198090Srdivacky if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) 2356218893Sdim // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or 2357198090Srdivacky // external globals. 2358218893Sdim return GV->hasUniqueInitializer(); 2359198090Srdivacky 2360218893Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 2361193323Sed // Handle a constantexpr gep. 2362193323Sed if (CE->getOpcode() == Instruction::GetElementPtr && 2363198090Srdivacky isa<GlobalVariable>(CE->getOperand(0)) && 2364198090Srdivacky cast<GEPOperator>(CE)->isInBounds()) { 2365193323Sed GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 2366218893Sdim // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or 2367198090Srdivacky // external globals. 2368218893Sdim if (!GV->hasUniqueInitializer()) 2369198090Srdivacky return false; 2370198090Srdivacky 2371198090Srdivacky // The first index must be zero. 2372212904Sdim ConstantInt *CI = dyn_cast<ConstantInt>(*llvm::next(CE->op_begin())); 2373198090Srdivacky if (!CI || !CI->isZero()) return false; 2374198090Srdivacky 2375198090Srdivacky // The remaining indices must be compile-time known integers within the 2376198090Srdivacky // notional bounds of the corresponding static array types. 2377198090Srdivacky if (!CE->isGEPWithNoNotionalOverIndexing()) 2378198090Srdivacky return false; 2379198090Srdivacky 2380198090Srdivacky return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); 2381249423Sdim 2382218893Sdim // A constantexpr bitcast from a pointer to another pointer is a no-op, 2383218893Sdim // and we know how to evaluate it by moving the bitcast from the pointer 2384218893Sdim // operand to the value operand. 2385218893Sdim } else if (CE->getOpcode() == Instruction::BitCast && 2386218893Sdim isa<GlobalVariable>(CE->getOperand(0))) { 2387218893Sdim // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or 2388218893Sdim // external globals. 2389218893Sdim return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer(); 2390193323Sed } 2391218893Sdim } 2392249423Sdim 2393193323Sed return false; 2394193323Sed} 2395193323Sed 2396193323Sed/// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global 2397193323Sed/// initializer. This returns 'Init' modified to reflect 'Val' stored into it. 2398193323Sed/// At this point, the GEP operands of Addr [0, OpNo) have been stepped into. 2399193323Sedstatic Constant *EvaluateStoreInto(Constant *Init, Constant *Val, 2400199481Srdivacky ConstantExpr *Addr, unsigned OpNo) { 2401193323Sed // Base case of the recursion. 2402193323Sed if (OpNo == Addr->getNumOperands()) { 2403193323Sed assert(Val->getType() == Init->getType() && "Type mismatch!"); 2404193323Sed return Val; 2405193323Sed } 2406218893Sdim 2407234353Sdim SmallVector<Constant*, 32> Elts; 2408226633Sdim if (StructType *STy = dyn_cast<StructType>(Init->getType())) { 2409193323Sed // Break up the constant into its elements. 2410234353Sdim for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 2411234353Sdim Elts.push_back(Init->getAggregateElement(i)); 2412218893Sdim 2413193323Sed // Replace the element that we are supposed to. 2414193323Sed ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo)); 2415193323Sed unsigned Idx = CU->getZExtValue(); 2416193323Sed assert(Idx < STy->getNumElements() && "Struct index out of range!"); 2417199481Srdivacky Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1); 2418218893Sdim 2419193323Sed // Return the modified struct. 2420224145Sdim return ConstantStruct::get(STy, Elts); 2421224145Sdim } 2422249423Sdim 2423224145Sdim ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo)); 2424226633Sdim SequentialType *InitTy = cast<SequentialType>(Init->getType()); 2425193323Sed 2426224145Sdim uint64_t NumElts; 2427226633Sdim if (ArrayType *ATy = dyn_cast<ArrayType>(InitTy)) 2428224145Sdim NumElts = ATy->getNumElements(); 2429224145Sdim else 2430234353Sdim NumElts = InitTy->getVectorNumElements(); 2431218893Sdim 2432224145Sdim // Break up the array into elements. 2433234353Sdim for (uint64_t i = 0, e = NumElts; i != e; ++i) 2434234353Sdim Elts.push_back(Init->getAggregateElement(i)); 2435218893Sdim 2436224145Sdim assert(CI->getZExtValue() < NumElts); 2437224145Sdim Elts[CI->getZExtValue()] = 2438224145Sdim EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1); 2439218893Sdim 2440224145Sdim if (Init->getType()->isArrayTy()) 2441224145Sdim return ConstantArray::get(cast<ArrayType>(InitTy), Elts); 2442224145Sdim return ConstantVector::get(Elts); 2443193323Sed} 2444193323Sed 2445193323Sed/// CommitValueTo - We have decided that Addr (which satisfies the predicate 2446193323Sed/// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen. 2447199481Srdivackystatic void CommitValueTo(Constant *Val, Constant *Addr) { 2448193323Sed if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) { 2449193323Sed assert(GV->hasInitializer()); 2450193323Sed GV->setInitializer(Val); 2451193323Sed return; 2452193323Sed } 2453202375Srdivacky 2454193323Sed ConstantExpr *CE = cast<ConstantExpr>(Addr); 2455193323Sed GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 2456202375Srdivacky GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2)); 2457193323Sed} 2458193323Sed 2459234353Sdimnamespace { 2460234353Sdim 2461234353Sdim/// Evaluator - This class evaluates LLVM IR, producing the Constant 2462234353Sdim/// representing each SSA instruction. Changes to global variables are stored 2463234353Sdim/// in a mapping that can be iterated over after the evaluation is complete. 2464234353Sdim/// Once an evaluation call fails, the evaluation object should not be reused. 2465234353Sdimclass Evaluator { 2466234353Sdimpublic: 2467243830Sdim Evaluator(const DataLayout *TD, const TargetLibraryInfo *TLI) 2468234353Sdim : TD(TD), TLI(TLI) { 2469234353Sdim ValueStack.push_back(new DenseMap<Value*, Constant*>); 2470234353Sdim } 2471234353Sdim 2472234353Sdim ~Evaluator() { 2473234353Sdim DeleteContainerPointers(ValueStack); 2474234353Sdim while (!AllocaTmps.empty()) { 2475234353Sdim GlobalVariable *Tmp = AllocaTmps.back(); 2476234353Sdim AllocaTmps.pop_back(); 2477234353Sdim 2478234353Sdim // If there are still users of the alloca, the program is doing something 2479234353Sdim // silly, e.g. storing the address of the alloca somewhere and using it 2480234353Sdim // later. Since this is undefined, we'll just make it be null. 2481234353Sdim if (!Tmp->use_empty()) 2482234353Sdim Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); 2483234353Sdim delete Tmp; 2484234353Sdim } 2485234353Sdim } 2486234353Sdim 2487234353Sdim /// EvaluateFunction - Evaluate a call to function F, returning true if 2488234353Sdim /// successful, false if we can't evaluate it. ActualArgs contains the formal 2489234353Sdim /// arguments for the function. 2490234353Sdim bool EvaluateFunction(Function *F, Constant *&RetVal, 2491234353Sdim const SmallVectorImpl<Constant*> &ActualArgs); 2492234353Sdim 2493234353Sdim /// EvaluateBlock - Evaluate all instructions in block BB, returning true if 2494234353Sdim /// successful, false if we can't evaluate it. NewBB returns the next BB that 2495234353Sdim /// control flows into, or null upon return. 2496234353Sdim bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB); 2497234353Sdim 2498234353Sdim Constant *getVal(Value *V) { 2499234353Sdim if (Constant *CV = dyn_cast<Constant>(V)) return CV; 2500234353Sdim Constant *R = ValueStack.back()->lookup(V); 2501234353Sdim assert(R && "Reference to an uncomputed value!"); 2502234353Sdim return R; 2503234353Sdim } 2504234353Sdim 2505234353Sdim void setVal(Value *V, Constant *C) { 2506234353Sdim ValueStack.back()->operator[](V) = C; 2507234353Sdim } 2508234353Sdim 2509234353Sdim const DenseMap<Constant*, Constant*> &getMutatedMemory() const { 2510234353Sdim return MutatedMemory; 2511234353Sdim } 2512234353Sdim 2513234353Sdim const SmallPtrSet<GlobalVariable*, 8> &getInvariants() const { 2514234353Sdim return Invariants; 2515234353Sdim } 2516234353Sdim 2517234353Sdimprivate: 2518234353Sdim Constant *ComputeLoadResult(Constant *P); 2519234353Sdim 2520234353Sdim /// ValueStack - As we compute SSA register values, we store their contents 2521234353Sdim /// here. The back of the vector contains the current function and the stack 2522234353Sdim /// contains the values in the calling frames. 2523234353Sdim SmallVector<DenseMap<Value*, Constant*>*, 4> ValueStack; 2524234353Sdim 2525234353Sdim /// CallStack - This is used to detect recursion. In pathological situations 2526234353Sdim /// we could hit exponential behavior, but at least there is nothing 2527234353Sdim /// unbounded. 2528234353Sdim SmallVector<Function*, 4> CallStack; 2529234353Sdim 2530234353Sdim /// MutatedMemory - For each store we execute, we update this map. Loads 2531234353Sdim /// check this to get the most up-to-date value. If evaluation is successful, 2532234353Sdim /// this state is committed to the process. 2533234353Sdim DenseMap<Constant*, Constant*> MutatedMemory; 2534234353Sdim 2535234353Sdim /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable 2536234353Sdim /// to represent its body. This vector is needed so we can delete the 2537234353Sdim /// temporary globals when we are done. 2538234353Sdim SmallVector<GlobalVariable*, 32> AllocaTmps; 2539234353Sdim 2540234353Sdim /// Invariants - These global variables have been marked invariant by the 2541234353Sdim /// static constructor. 2542234353Sdim SmallPtrSet<GlobalVariable*, 8> Invariants; 2543234353Sdim 2544234353Sdim /// SimpleConstants - These are constants we have checked and know to be 2545234353Sdim /// simple enough to live in a static initializer of a global. 2546234353Sdim SmallPtrSet<Constant*, 8> SimpleConstants; 2547234353Sdim 2548243830Sdim const DataLayout *TD; 2549234353Sdim const TargetLibraryInfo *TLI; 2550234353Sdim}; 2551234353Sdim 2552234353Sdim} // anonymous namespace 2553234353Sdim 2554193323Sed/// ComputeLoadResult - Return the value that would be computed by a load from 2555193323Sed/// P after the stores reflected by 'memory' have been performed. If we can't 2556193323Sed/// decide, return null. 2557234353SdimConstant *Evaluator::ComputeLoadResult(Constant *P) { 2558193323Sed // If this memory location has been recently stored, use the stored value: it 2559193323Sed // is the most up-to-date. 2560234353Sdim DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P); 2561234353Sdim if (I != MutatedMemory.end()) return I->second; 2562218893Sdim 2563193323Sed // Access it. 2564193323Sed if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { 2565198090Srdivacky if (GV->hasDefinitiveInitializer()) 2566193323Sed return GV->getInitializer(); 2567193323Sed return 0; 2568193323Sed } 2569218893Sdim 2570193323Sed // Handle a constantexpr getelementptr. 2571193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) 2572193323Sed if (CE->getOpcode() == Instruction::GetElementPtr && 2573193323Sed isa<GlobalVariable>(CE->getOperand(0))) { 2574193323Sed GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 2575198090Srdivacky if (GV->hasDefinitiveInitializer()) 2576193323Sed return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); 2577193323Sed } 2578193323Sed 2579193323Sed return 0; // don't know how to evaluate. 2580193323Sed} 2581193323Sed 2582234353Sdim/// EvaluateBlock - Evaluate all instructions in block BB, returning true if 2583234353Sdim/// successful, false if we can't evaluate it. NewBB returns the next BB that 2584234353Sdim/// control flows into, or null upon return. 2585234353Sdimbool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, 2586234353Sdim BasicBlock *&NextBB) { 2587193323Sed // This is the main evaluation loop. 2588193323Sed while (1) { 2589193323Sed Constant *InstResult = 0; 2590218893Sdim 2591249423Sdim DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n"); 2592249423Sdim 2593193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) { 2594249423Sdim if (!SI->isSimple()) { 2595249423Sdim DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n"); 2596249423Sdim return false; // no volatile/atomic accesses. 2597249423Sdim } 2598234353Sdim Constant *Ptr = getVal(SI->getOperand(1)); 2599249423Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { 2600249423Sdim DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr); 2601234353Sdim Ptr = ConstantFoldConstantExpression(CE, TD, TLI); 2602249423Sdim DEBUG(dbgs() << "; To: " << *Ptr << "\n"); 2603249423Sdim } 2604249423Sdim if (!isSimpleEnoughPointerToCommit(Ptr)) { 2605193323Sed // If this is too complex for us to commit, reject it. 2606249423Sdim DEBUG(dbgs() << "Pointer is too complex for us to evaluate store."); 2607193323Sed return false; 2608249423Sdim } 2609249423Sdim 2610234353Sdim Constant *Val = getVal(SI->getOperand(0)); 2611218893Sdim 2612218893Sdim // If this might be too difficult for the backend to handle (e.g. the addr 2613218893Sdim // of one global variable divided by another) then we can't commit it. 2614249423Sdim if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, TD)) { 2615249423Sdim DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val 2616249423Sdim << "\n"); 2617218893Sdim return false; 2618249423Sdim } 2619249423Sdim 2620249423Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { 2621218893Sdim if (CE->getOpcode() == Instruction::BitCast) { 2622249423Sdim DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n"); 2623218893Sdim // If we're evaluating a store through a bitcast, then we need 2624218893Sdim // to pull the bitcast off the pointer type and push it onto the 2625218893Sdim // stored value. 2626218893Sdim Ptr = CE->getOperand(0); 2627249423Sdim 2628234353Sdim Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType(); 2629249423Sdim 2630218893Sdim // In order to push the bitcast onto the stored value, a bitcast 2631218893Sdim // from NewTy to Val's type must be legal. If it's not, we can try 2632218893Sdim // introspecting NewTy to find a legal conversion. 2633218893Sdim while (!Val->getType()->canLosslesslyBitCastTo(NewTy)) { 2634218893Sdim // If NewTy is a struct, we can convert the pointer to the struct 2635218893Sdim // into a pointer to its first member. 2636218893Sdim // FIXME: This could be extended to support arrays as well. 2637226633Sdim if (StructType *STy = dyn_cast<StructType>(NewTy)) { 2638218893Sdim NewTy = STy->getTypeAtIndex(0U); 2639218893Sdim 2640234353Sdim IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32); 2641218893Sdim Constant *IdxZero = ConstantInt::get(IdxTy, 0, false); 2642218893Sdim Constant * const IdxList[] = {IdxZero, IdxZero}; 2643218893Sdim 2644226633Sdim Ptr = ConstantExpr::getGetElementPtr(Ptr, IdxList); 2645234353Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 2646234353Sdim Ptr = ConstantFoldConstantExpression(CE, TD, TLI); 2647234353Sdim 2648218893Sdim // If we can't improve the situation by introspecting NewTy, 2649218893Sdim // we have to give up. 2650218893Sdim } else { 2651249423Sdim DEBUG(dbgs() << "Failed to bitcast constant ptr, can not " 2652249423Sdim "evaluate.\n"); 2653234353Sdim return false; 2654218893Sdim } 2655218893Sdim } 2656249423Sdim 2657218893Sdim // If we found compatible types, go ahead and push the bitcast 2658218893Sdim // onto the stored value. 2659218893Sdim Val = ConstantExpr::getBitCast(Val, NewTy); 2660249423Sdim 2661249423Sdim DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n"); 2662218893Sdim } 2663249423Sdim } 2664249423Sdim 2665193323Sed MutatedMemory[Ptr] = Val; 2666193323Sed } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) { 2667193323Sed InstResult = ConstantExpr::get(BO->getOpcode(), 2668234353Sdim getVal(BO->getOperand(0)), 2669234353Sdim getVal(BO->getOperand(1))); 2670249423Sdim DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult 2671249423Sdim << "\n"); 2672193323Sed } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) { 2673193323Sed InstResult = ConstantExpr::getCompare(CI->getPredicate(), 2674234353Sdim getVal(CI->getOperand(0)), 2675234353Sdim getVal(CI->getOperand(1))); 2676249423Sdim DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult 2677249423Sdim << "\n"); 2678193323Sed } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) { 2679193323Sed InstResult = ConstantExpr::getCast(CI->getOpcode(), 2680234353Sdim getVal(CI->getOperand(0)), 2681193323Sed CI->getType()); 2682249423Sdim DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult 2683249423Sdim << "\n"); 2684193323Sed } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) { 2685234353Sdim InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)), 2686234353Sdim getVal(SI->getOperand(1)), 2687234353Sdim getVal(SI->getOperand(2))); 2688249423Sdim DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult 2689249423Sdim << "\n"); 2690193323Sed } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) { 2691234353Sdim Constant *P = getVal(GEP->getOperand(0)); 2692193323Sed SmallVector<Constant*, 8> GEPOps; 2693193323Sed for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); 2694193323Sed i != e; ++i) 2695234353Sdim GEPOps.push_back(getVal(*i)); 2696226633Sdim InstResult = 2697226633Sdim ConstantExpr::getGetElementPtr(P, GEPOps, 2698226633Sdim cast<GEPOperator>(GEP)->isInBounds()); 2699249423Sdim DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult 2700249423Sdim << "\n"); 2701193323Sed } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) { 2702249423Sdim 2703249423Sdim if (!LI->isSimple()) { 2704249423Sdim DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n"); 2705249423Sdim return false; // no volatile/atomic accesses. 2706249423Sdim } 2707249423Sdim 2708234353Sdim Constant *Ptr = getVal(LI->getOperand(0)); 2709249423Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { 2710234353Sdim Ptr = ConstantFoldConstantExpression(CE, TD, TLI); 2711249423Sdim DEBUG(dbgs() << "Found a constant pointer expression, constant " 2712249423Sdim "folding: " << *Ptr << "\n"); 2713249423Sdim } 2714234353Sdim InstResult = ComputeLoadResult(Ptr); 2715249423Sdim if (InstResult == 0) { 2716249423Sdim DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load." 2717249423Sdim "\n"); 2718249423Sdim return false; // Could not evaluate load. 2719249423Sdim } 2720249423Sdim 2721249423Sdim DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n"); 2722193323Sed } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) { 2723249423Sdim if (AI->isArrayAllocation()) { 2724249423Sdim DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n"); 2725249423Sdim return false; // Cannot handle array allocs. 2726249423Sdim } 2727226633Sdim Type *Ty = AI->getType()->getElementType(); 2728199481Srdivacky AllocaTmps.push_back(new GlobalVariable(Ty, false, 2729193323Sed GlobalValue::InternalLinkage, 2730193323Sed UndefValue::get(Ty), 2731193323Sed AI->getName())); 2732218893Sdim InstResult = AllocaTmps.back(); 2733249423Sdim DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n"); 2734234353Sdim } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) { 2735234353Sdim CallSite CS(CurInst); 2736193323Sed 2737193323Sed // Debug info can safely be ignored here. 2738234353Sdim if (isa<DbgInfoIntrinsic>(CS.getInstruction())) { 2739249423Sdim DEBUG(dbgs() << "Ignoring debug info.\n"); 2740193323Sed ++CurInst; 2741193323Sed continue; 2742193323Sed } 2743193323Sed 2744193323Sed // Cannot handle inline asm. 2745249423Sdim if (isa<InlineAsm>(CS.getCalledValue())) { 2746249423Sdim DEBUG(dbgs() << "Found inline asm, can not evaluate.\n"); 2747249423Sdim return false; 2748249423Sdim } 2749193323Sed 2750234353Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) { 2751234353Sdim if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) { 2752249423Sdim if (MSI->isVolatile()) { 2753249423Sdim DEBUG(dbgs() << "Can not optimize a volatile memset " << 2754249423Sdim "intrinsic.\n"); 2755249423Sdim return false; 2756249423Sdim } 2757234353Sdim Constant *Ptr = getVal(MSI->getDest()); 2758234353Sdim Constant *Val = getVal(MSI->getValue()); 2759234353Sdim Constant *DestVal = ComputeLoadResult(getVal(Ptr)); 2760234353Sdim if (Val->isNullValue() && DestVal && DestVal->isNullValue()) { 2761234353Sdim // This memset is a no-op. 2762249423Sdim DEBUG(dbgs() << "Ignoring no-op memset.\n"); 2763234353Sdim ++CurInst; 2764234353Sdim continue; 2765234353Sdim } 2766234353Sdim } 2767234353Sdim 2768234353Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start || 2769234353Sdim II->getIntrinsicID() == Intrinsic::lifetime_end) { 2770249423Sdim DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n"); 2771223017Sdim ++CurInst; 2772223017Sdim continue; 2773223017Sdim } 2774234353Sdim 2775234353Sdim if (II->getIntrinsicID() == Intrinsic::invariant_start) { 2776234353Sdim // We don't insert an entry into Values, as it doesn't have a 2777234353Sdim // meaningful return value. 2778249423Sdim if (!II->use_empty()) { 2779249423Sdim DEBUG(dbgs() << "Found unused invariant_start. Cant evaluate.\n"); 2780234353Sdim return false; 2781249423Sdim } 2782234353Sdim ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0)); 2783234353Sdim Value *PtrArg = getVal(II->getArgOperand(1)); 2784234353Sdim Value *Ptr = PtrArg->stripPointerCasts(); 2785234353Sdim if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { 2786234353Sdim Type *ElemTy = cast<PointerType>(GV->getType())->getElementType(); 2787234353Sdim if (!Size->isAllOnesValue() && 2788234353Sdim Size->getValue().getLimitedValue() >= 2789249423Sdim TD->getTypeStoreSize(ElemTy)) { 2790234353Sdim Invariants.insert(GV); 2791249423Sdim DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV 2792249423Sdim << "\n"); 2793249423Sdim } else { 2794249423Sdim DEBUG(dbgs() << "Found a global var, but can not treat it as an " 2795249423Sdim "invariant.\n"); 2796249423Sdim } 2797234353Sdim } 2798234353Sdim // Continue even if we do nothing. 2799234353Sdim ++CurInst; 2800234353Sdim continue; 2801234353Sdim } 2802249423Sdim 2803249423Sdim DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n"); 2804223017Sdim return false; 2805223017Sdim } 2806223017Sdim 2807193323Sed // Resolve function pointers. 2808234353Sdim Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue())); 2809249423Sdim if (!Callee || Callee->mayBeOverridden()) { 2810249423Sdim DEBUG(dbgs() << "Can not resolve function pointer.\n"); 2811234353Sdim return false; // Cannot resolve. 2812249423Sdim } 2813193323Sed 2814198090Srdivacky SmallVector<Constant*, 8> Formals; 2815234353Sdim for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); i != e; ++i) 2816234353Sdim Formals.push_back(getVal(*i)); 2817198090Srdivacky 2818193323Sed if (Callee->isDeclaration()) { 2819193323Sed // If this is a function we can constant fold, do it. 2820234353Sdim if (Constant *C = ConstantFoldCall(Callee, Formals, TLI)) { 2821193323Sed InstResult = C; 2822249423Sdim DEBUG(dbgs() << "Constant folded function call. Result: " << 2823249423Sdim *InstResult << "\n"); 2824193323Sed } else { 2825249423Sdim DEBUG(dbgs() << "Can not constant fold function call.\n"); 2826193323Sed return false; 2827193323Sed } 2828193323Sed } else { 2829249423Sdim if (Callee->getFunctionType()->isVarArg()) { 2830249423Sdim DEBUG(dbgs() << "Can not constant fold vararg function call.\n"); 2831193323Sed return false; 2832249423Sdim } 2833218893Sdim 2834249423Sdim Constant *RetVal = 0; 2835193323Sed // Execute the call, if successful, use the return value. 2836234353Sdim ValueStack.push_back(new DenseMap<Value*, Constant*>); 2837249423Sdim if (!EvaluateFunction(Callee, RetVal, Formals)) { 2838249423Sdim DEBUG(dbgs() << "Failed to evaluate function.\n"); 2839193323Sed return false; 2840249423Sdim } 2841234353Sdim delete ValueStack.pop_back_val(); 2842193323Sed InstResult = RetVal; 2843249423Sdim 2844249423Sdim if (InstResult != NULL) { 2845249423Sdim DEBUG(dbgs() << "Successfully evaluated function. Result: " << 2846249423Sdim InstResult << "\n\n"); 2847249423Sdim } else { 2848249423Sdim DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n"); 2849249423Sdim } 2850193323Sed } 2851193323Sed } else if (isa<TerminatorInst>(CurInst)) { 2852249423Sdim DEBUG(dbgs() << "Found a terminator instruction.\n"); 2853249423Sdim 2854193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) { 2855193323Sed if (BI->isUnconditional()) { 2856234353Sdim NextBB = BI->getSuccessor(0); 2857193323Sed } else { 2858193323Sed ConstantInt *Cond = 2859234353Sdim dyn_cast<ConstantInt>(getVal(BI->getCondition())); 2860193323Sed if (!Cond) return false; // Cannot determine. 2861193323Sed 2862234353Sdim NextBB = BI->getSuccessor(!Cond->getZExtValue()); 2863193323Sed } 2864193323Sed } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) { 2865193323Sed ConstantInt *Val = 2866234353Sdim dyn_cast<ConstantInt>(getVal(SI->getCondition())); 2867193323Sed if (!Val) return false; // Cannot determine. 2868234353Sdim NextBB = SI->findCaseValue(Val).getCaseSuccessor(); 2869198892Srdivacky } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) { 2870234353Sdim Value *Val = getVal(IBI->getAddress())->stripPointerCasts(); 2871198892Srdivacky if (BlockAddress *BA = dyn_cast<BlockAddress>(Val)) 2872234353Sdim NextBB = BA->getBasicBlock(); 2873198892Srdivacky else 2874198892Srdivacky return false; // Cannot determine. 2875234353Sdim } else if (isa<ReturnInst>(CurInst)) { 2876234353Sdim NextBB = 0; 2877193323Sed } else { 2878226633Sdim // invoke, unwind, resume, unreachable. 2879249423Sdim DEBUG(dbgs() << "Can not handle terminator."); 2880193323Sed return false; // Cannot handle this terminator. 2881193323Sed } 2882218893Sdim 2883234353Sdim // We succeeded at evaluating this block! 2884249423Sdim DEBUG(dbgs() << "Successfully evaluated block.\n"); 2885234353Sdim return true; 2886193323Sed } else { 2887193323Sed // Did not know how to evaluate this! 2888249423Sdim DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction." 2889249423Sdim "\n"); 2890193323Sed return false; 2891193323Sed } 2892218893Sdim 2893218893Sdim if (!CurInst->use_empty()) { 2894218893Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(InstResult)) 2895234353Sdim InstResult = ConstantFoldConstantExpression(CE, TD, TLI); 2896249423Sdim 2897234353Sdim setVal(CurInst, InstResult); 2898218893Sdim } 2899218893Sdim 2900234353Sdim // If we just processed an invoke, we finished evaluating the block. 2901234353Sdim if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) { 2902234353Sdim NextBB = II->getNormalDest(); 2903249423Sdim DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n"); 2904234353Sdim return true; 2905234353Sdim } 2906234353Sdim 2907193323Sed // Advance program counter. 2908193323Sed ++CurInst; 2909193323Sed } 2910193323Sed} 2911193323Sed 2912234353Sdim/// EvaluateFunction - Evaluate a call to function F, returning true if 2913234353Sdim/// successful, false if we can't evaluate it. ActualArgs contains the formal 2914234353Sdim/// arguments for the function. 2915234353Sdimbool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal, 2916234353Sdim const SmallVectorImpl<Constant*> &ActualArgs) { 2917234353Sdim // Check to see if this function is already executing (recursion). If so, 2918234353Sdim // bail out. TODO: we might want to accept limited recursion. 2919234353Sdim if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end()) 2920234353Sdim return false; 2921193323Sed 2922234353Sdim CallStack.push_back(F); 2923218893Sdim 2924234353Sdim // Initialize arguments to the incoming values specified. 2925234353Sdim unsigned ArgNo = 0; 2926234353Sdim for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; 2927234353Sdim ++AI, ++ArgNo) 2928234353Sdim setVal(AI, ActualArgs[ArgNo]); 2929193323Sed 2930234353Sdim // ExecutedBlocks - We only handle non-looping, non-recursive code. As such, 2931234353Sdim // we can only evaluate any one basic block at most once. This set keeps 2932234353Sdim // track of what we have executed so we can detect recursive cases etc. 2933234353Sdim SmallPtrSet<BasicBlock*, 32> ExecutedBlocks; 2934234353Sdim 2935234353Sdim // CurBB - The current basic block we're evaluating. 2936234353Sdim BasicBlock *CurBB = F->begin(); 2937234353Sdim 2938234353Sdim BasicBlock::iterator CurInst = CurBB->begin(); 2939234353Sdim 2940234353Sdim while (1) { 2941234353Sdim BasicBlock *NextBB = 0; // Initialized to avoid compiler warnings. 2942249423Sdim DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n"); 2943249423Sdim 2944234353Sdim if (!EvaluateBlock(CurInst, NextBB)) 2945234353Sdim return false; 2946234353Sdim 2947234353Sdim if (NextBB == 0) { 2948234353Sdim // Successfully running until there's no next block means that we found 2949234353Sdim // the return. Fill it the return value and pop the call stack. 2950234353Sdim ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator()); 2951234353Sdim if (RI->getNumOperands()) 2952234353Sdim RetVal = getVal(RI->getOperand(0)); 2953234353Sdim CallStack.pop_back(); 2954234353Sdim return true; 2955234353Sdim } 2956234353Sdim 2957234353Sdim // Okay, we succeeded in evaluating this control flow. See if we have 2958234353Sdim // executed the new block before. If so, we have a looping function, 2959234353Sdim // which we cannot evaluate in reasonable time. 2960234353Sdim if (!ExecutedBlocks.insert(NextBB)) 2961234353Sdim return false; // looped! 2962234353Sdim 2963234353Sdim // Okay, we have never been in this block before. Check to see if there 2964234353Sdim // are any PHI nodes. If so, evaluate them with information about where 2965234353Sdim // we came from. 2966234353Sdim PHINode *PN = 0; 2967234353Sdim for (CurInst = NextBB->begin(); 2968234353Sdim (PN = dyn_cast<PHINode>(CurInst)); ++CurInst) 2969234353Sdim setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB))); 2970234353Sdim 2971234353Sdim // Advance to the next block. 2972234353Sdim CurBB = NextBB; 2973234353Sdim } 2974234353Sdim} 2975234353Sdim 2976234353Sdim/// EvaluateStaticConstructor - Evaluate static constructors in the function, if 2977234353Sdim/// we can. Return true if we can, false otherwise. 2978243830Sdimstatic bool EvaluateStaticConstructor(Function *F, const DataLayout *TD, 2979234353Sdim const TargetLibraryInfo *TLI) { 2980193323Sed // Call the function. 2981234353Sdim Evaluator Eval(TD, TLI); 2982193323Sed Constant *RetValDummy; 2983234353Sdim bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy, 2984234353Sdim SmallVector<Constant*, 0>()); 2985249423Sdim 2986193323Sed if (EvalSuccess) { 2987193323Sed // We succeeded at evaluation: commit the result. 2988202375Srdivacky DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" 2989234353Sdim << F->getName() << "' to " << Eval.getMutatedMemory().size() 2990198090Srdivacky << " stores.\n"); 2991234353Sdim for (DenseMap<Constant*, Constant*>::const_iterator I = 2992234353Sdim Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end(); 2993239462Sdim I != E; ++I) 2994199481Srdivacky CommitValueTo(I->second, I->first); 2995234353Sdim for (SmallPtrSet<GlobalVariable*, 8>::const_iterator I = 2996234353Sdim Eval.getInvariants().begin(), E = Eval.getInvariants().end(); 2997234353Sdim I != E; ++I) 2998234353Sdim (*I)->setConstant(true); 2999193323Sed } 3000218893Sdim 3001193323Sed return EvalSuccess; 3002193323Sed} 3003193323Sed 3004193323Sed/// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible. 3005193323Sed/// Return true if anything changed. 3006193323Sedbool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) { 3007193323Sed std::vector<Function*> Ctors = ParseGlobalCtors(GCL); 3008193323Sed bool MadeChange = false; 3009193323Sed if (Ctors.empty()) return false; 3010218893Sdim 3011193323Sed // Loop over global ctors, optimizing them when we can. 3012193323Sed for (unsigned i = 0; i != Ctors.size(); ++i) { 3013193323Sed Function *F = Ctors[i]; 3014193323Sed // Found a null terminator in the middle of the list, prune off the rest of 3015193323Sed // the list. 3016193323Sed if (F == 0) { 3017193323Sed if (i != Ctors.size()-1) { 3018193323Sed Ctors.resize(i+1); 3019193323Sed MadeChange = true; 3020193323Sed } 3021193323Sed break; 3022193323Sed } 3023249423Sdim DEBUG(dbgs() << "Optimizing Global Constructor: " << *F << "\n"); 3024218893Sdim 3025193323Sed // We cannot simplify external ctor functions. 3026193323Sed if (F->empty()) continue; 3027218893Sdim 3028193323Sed // If we can evaluate the ctor at compile time, do. 3029234353Sdim if (EvaluateStaticConstructor(F, TD, TLI)) { 3030193323Sed Ctors.erase(Ctors.begin()+i); 3031193323Sed MadeChange = true; 3032193323Sed --i; 3033193323Sed ++NumCtorsEvaluated; 3034193323Sed continue; 3035193323Sed } 3036193323Sed } 3037218893Sdim 3038193323Sed if (!MadeChange) return false; 3039218893Sdim 3040199481Srdivacky GCL = InstallGlobalCtors(GCL, Ctors); 3041193323Sed return true; 3042193323Sed} 3043193323Sed 3044251662Sdimstatic Value::use_iterator getFirst(Value *V, SmallPtrSet<Use*, 8> &Tried) { 3045251662Sdim for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) { 3046251662Sdim Use *U = &I.getUse(); 3047251662Sdim if (Tried.count(U)) 3048251662Sdim continue; 3049251662Sdim 3050251662Sdim User *Usr = *I; 3051251662Sdim GlobalVariable *GV = dyn_cast<GlobalVariable>(Usr); 3052251662Sdim if (!GV || !GV->hasName()) { 3053251662Sdim Tried.insert(U); 3054251662Sdim return I; 3055251662Sdim } 3056251662Sdim 3057251662Sdim StringRef Name = GV->getName(); 3058251662Sdim if (Name != "llvm.used" && Name != "llvm.compiler_used") { 3059251662Sdim Tried.insert(U); 3060251662Sdim return I; 3061251662Sdim } 3062251662Sdim } 3063251662Sdim return V->use_end(); 3064251662Sdim} 3065251662Sdim 3066251662Sdimstatic bool replaceAllNonLLVMUsedUsesWith(Constant *Old, Constant *New); 3067251662Sdim 3068251662Sdimstatic bool replaceUsesOfWithOnConstant(ConstantArray *CA, Value *From, 3069251662Sdim Value *ToV, Use *U) { 3070251662Sdim Constant *To = cast<Constant>(ToV); 3071251662Sdim 3072251662Sdim SmallVector<Constant*, 8> NewOps; 3073251662Sdim for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) { 3074251662Sdim Constant *Op = CA->getOperand(i); 3075251662Sdim NewOps.push_back(Op == From ? To : Op); 3076251662Sdim } 3077251662Sdim 3078251662Sdim Constant *Replacement = ConstantArray::get(CA->getType(), NewOps); 3079251662Sdim assert(Replacement != CA && "CA didn't contain From!"); 3080251662Sdim 3081251662Sdim bool Ret = replaceAllNonLLVMUsedUsesWith(CA, Replacement); 3082251662Sdim if (Replacement->use_empty()) 3083251662Sdim Replacement->destroyConstant(); 3084251662Sdim if (CA->use_empty()) 3085251662Sdim CA->destroyConstant(); 3086251662Sdim return Ret; 3087251662Sdim} 3088251662Sdim 3089251662Sdimstatic bool replaceUsesOfWithOnConstant(ConstantExpr *CE, Value *From, 3090251662Sdim Value *ToV, Use *U) { 3091251662Sdim Constant *To = cast<Constant>(ToV); 3092251662Sdim SmallVector<Constant*, 8> NewOps; 3093251662Sdim for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) { 3094251662Sdim Constant *Op = CE->getOperand(i); 3095251662Sdim NewOps.push_back(Op == From ? To : Op); 3096251662Sdim } 3097251662Sdim 3098251662Sdim Constant *Replacement = CE->getWithOperands(NewOps); 3099251662Sdim assert(Replacement != CE && "CE didn't contain From!"); 3100251662Sdim 3101251662Sdim bool Ret = replaceAllNonLLVMUsedUsesWith(CE, Replacement); 3102251662Sdim if (Replacement->use_empty()) 3103251662Sdim Replacement->destroyConstant(); 3104251662Sdim if (CE->use_empty()) 3105251662Sdim CE->destroyConstant(); 3106251662Sdim return Ret; 3107251662Sdim} 3108251662Sdim 3109251662Sdimstatic bool replaceUsesOfWithOnConstant(Constant *C, Value *From, Value *To, 3110251662Sdim Use *U) { 3111251662Sdim if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) 3112251662Sdim return replaceUsesOfWithOnConstant(CA, From, To, U); 3113251662Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 3114251662Sdim return replaceUsesOfWithOnConstant(CE, From, To, U); 3115251662Sdim C->replaceUsesOfWithOnConstant(From, To, U); 3116251662Sdim return true; 3117251662Sdim} 3118251662Sdim 3119251662Sdimstatic bool replaceAllNonLLVMUsedUsesWith(Constant *Old, Constant *New) { 3120251662Sdim SmallPtrSet<Use*, 8> Tried; 3121251662Sdim bool Ret = false; 3122251662Sdim for (;;) { 3123251662Sdim Value::use_iterator I = getFirst(Old, Tried); 3124251662Sdim if (I == Old->use_end()) 3125251662Sdim break; 3126251662Sdim Use &U = I.getUse(); 3127251662Sdim 3128251662Sdim // Must handle Constants specially, we cannot call replaceUsesOfWith on a 3129251662Sdim // constant because they are uniqued. 3130251662Sdim if (Constant *C = dyn_cast<Constant>(U.getUser())) { 3131251662Sdim if (!isa<GlobalValue>(C)) { 3132251662Sdim Ret |= replaceUsesOfWithOnConstant(C, Old, New, &U); 3133251662Sdim continue; 3134251662Sdim } 3135251662Sdim } 3136251662Sdim 3137251662Sdim U.set(New); 3138251662Sdim Ret = true; 3139251662Sdim } 3140251662Sdim return Ret; 3141251662Sdim} 3142251662Sdim 3143193323Sedbool GlobalOpt::OptimizeGlobalAliases(Module &M) { 3144193323Sed bool Changed = false; 3145193323Sed 3146193323Sed for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); 3147193323Sed I != E;) { 3148193323Sed Module::alias_iterator J = I++; 3149193323Sed // Aliases without names cannot be referenced outside this module. 3150193323Sed if (!J->hasName() && !J->isDeclaration()) 3151193323Sed J->setLinkage(GlobalValue::InternalLinkage); 3152193323Sed // If the aliasee may change at link time, nothing can be done - bail out. 3153193323Sed if (J->mayBeOverridden()) 3154193323Sed continue; 3155193323Sed 3156193323Sed Constant *Aliasee = J->getAliasee(); 3157193323Sed GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts()); 3158193323Sed Target->removeDeadConstantUsers(); 3159193323Sed bool hasOneUse = Target->hasOneUse() && Aliasee->hasOneUse(); 3160193323Sed 3161193323Sed // Make all users of the alias use the aliasee instead. 3162251662Sdim if (replaceAllNonLLVMUsedUsesWith(J, Aliasee)) { 3163193323Sed ++NumAliasesResolved; 3164193323Sed Changed = true; 3165193323Sed } 3166251662Sdim if (!J->use_empty()) 3167251662Sdim continue; 3168193323Sed 3169200581Srdivacky // If the alias is externally visible, we may still be able to simplify it. 3170200581Srdivacky if (!J->hasLocalLinkage()) { 3171200581Srdivacky // If the aliasee has internal linkage, give it the name and linkage 3172200581Srdivacky // of the alias, and delete the alias. This turns: 3173200581Srdivacky // define internal ... @f(...) 3174200581Srdivacky // @a = alias ... @f 3175200581Srdivacky // into: 3176200581Srdivacky // define ... @a(...) 3177200581Srdivacky if (!Target->hasLocalLinkage()) 3178200581Srdivacky continue; 3179193323Sed 3180200581Srdivacky // Do not perform the transform if multiple aliases potentially target the 3181207618Srdivacky // aliasee. This check also ensures that it is safe to replace the section 3182200581Srdivacky // and other attributes of the aliasee with those of the alias. 3183200581Srdivacky if (!hasOneUse) 3184200581Srdivacky continue; 3185193323Sed 3186200581Srdivacky // Give the aliasee the name, linkage and other attributes of the alias. 3187200581Srdivacky Target->takeName(J); 3188200581Srdivacky Target->setLinkage(J->getLinkage()); 3189200581Srdivacky Target->GlobalValue::copyAttributesFrom(J); 3190200581Srdivacky } 3191193323Sed 3192193323Sed // Delete the alias. 3193193323Sed M.getAliasList().erase(J); 3194193323Sed ++NumAliasesRemoved; 3195193323Sed Changed = true; 3196193323Sed } 3197193323Sed 3198193323Sed return Changed; 3199193323Sed} 3200193323Sed 3201234353Sdimstatic Function *FindCXAAtExit(Module &M, TargetLibraryInfo *TLI) { 3202234353Sdim if (!TLI->has(LibFunc::cxa_atexit)) 3203234353Sdim return 0; 3204234353Sdim 3205234353Sdim Function *Fn = M.getFunction(TLI->getName(LibFunc::cxa_atexit)); 3206249423Sdim 3207221345Sdim if (!Fn) 3208221345Sdim return 0; 3209234353Sdim 3210226633Sdim FunctionType *FTy = Fn->getFunctionType(); 3211249423Sdim 3212249423Sdim // Checking that the function has the right return type, the right number of 3213221345Sdim // parameters and that they all have pointer types should be enough. 3214221345Sdim if (!FTy->getReturnType()->isIntegerTy() || 3215221345Sdim FTy->getNumParams() != 3 || 3216221345Sdim !FTy->getParamType(0)->isPointerTy() || 3217221345Sdim !FTy->getParamType(1)->isPointerTy() || 3218221345Sdim !FTy->getParamType(2)->isPointerTy()) 3219221345Sdim return 0; 3220221345Sdim 3221221345Sdim return Fn; 3222221345Sdim} 3223221345Sdim 3224221345Sdim/// cxxDtorIsEmpty - Returns whether the given function is an empty C++ 3225221345Sdim/// destructor and can therefore be eliminated. 3226221345Sdim/// Note that we assume that other optimization passes have already simplified 3227221345Sdim/// the code so we only look for a function with a single basic block, where 3228234353Sdim/// the only allowed instructions are 'ret', 'call' to an empty C++ dtor and 3229234353Sdim/// other side-effect free instructions. 3230221345Sdimstatic bool cxxDtorIsEmpty(const Function &Fn, 3231221345Sdim SmallPtrSet<const Function *, 8> &CalledFunctions) { 3232221345Sdim // FIXME: We could eliminate C++ destructors if they're readonly/readnone and 3233221345Sdim // nounwind, but that doesn't seem worth doing. 3234221345Sdim if (Fn.isDeclaration()) 3235221345Sdim return false; 3236221345Sdim 3237221345Sdim if (++Fn.begin() != Fn.end()) 3238221345Sdim return false; 3239221345Sdim 3240221345Sdim const BasicBlock &EntryBlock = Fn.getEntryBlock(); 3241221345Sdim for (BasicBlock::const_iterator I = EntryBlock.begin(), E = EntryBlock.end(); 3242221345Sdim I != E; ++I) { 3243221345Sdim if (const CallInst *CI = dyn_cast<CallInst>(I)) { 3244221345Sdim // Ignore debug intrinsics. 3245221345Sdim if (isa<DbgInfoIntrinsic>(CI)) 3246221345Sdim continue; 3247221345Sdim 3248221345Sdim const Function *CalledFn = CI->getCalledFunction(); 3249221345Sdim 3250221345Sdim if (!CalledFn) 3251221345Sdim return false; 3252221345Sdim 3253221345Sdim SmallPtrSet<const Function *, 8> NewCalledFunctions(CalledFunctions); 3254221345Sdim 3255221345Sdim // Don't treat recursive functions as empty. 3256221345Sdim if (!NewCalledFunctions.insert(CalledFn)) 3257221345Sdim return false; 3258221345Sdim 3259221345Sdim if (!cxxDtorIsEmpty(*CalledFn, NewCalledFunctions)) 3260221345Sdim return false; 3261221345Sdim } else if (isa<ReturnInst>(*I)) 3262234353Sdim return true; // We're done. 3263234353Sdim else if (I->mayHaveSideEffects()) 3264234353Sdim return false; // Destructor with side effects, bail. 3265221345Sdim } 3266221345Sdim 3267221345Sdim return false; 3268221345Sdim} 3269221345Sdim 3270221345Sdimbool GlobalOpt::OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) { 3271221345Sdim /// Itanium C++ ABI p3.3.5: 3272221345Sdim /// 3273221345Sdim /// After constructing a global (or local static) object, that will require 3274221345Sdim /// destruction on exit, a termination function is registered as follows: 3275221345Sdim /// 3276221345Sdim /// extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d ); 3277221345Sdim /// 3278221345Sdim /// This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the 3279221345Sdim /// call f(p) when DSO d is unloaded, before all such termination calls 3280221345Sdim /// registered before this one. It returns zero if registration is 3281221345Sdim /// successful, nonzero on failure. 3282221345Sdim 3283221345Sdim // This pass will look for calls to __cxa_atexit where the function is trivial 3284221345Sdim // and remove them. 3285221345Sdim bool Changed = false; 3286221345Sdim 3287249423Sdim for (Function::use_iterator I = CXAAtExitFn->use_begin(), 3288221345Sdim E = CXAAtExitFn->use_end(); I != E;) { 3289221345Sdim // We're only interested in calls. Theoretically, we could handle invoke 3290221345Sdim // instructions as well, but neither llvm-gcc nor clang generate invokes 3291221345Sdim // to __cxa_atexit. 3292221345Sdim CallInst *CI = dyn_cast<CallInst>(*I++); 3293221345Sdim if (!CI) 3294221345Sdim continue; 3295221345Sdim 3296249423Sdim Function *DtorFn = 3297221345Sdim dyn_cast<Function>(CI->getArgOperand(0)->stripPointerCasts()); 3298221345Sdim if (!DtorFn) 3299221345Sdim continue; 3300221345Sdim 3301221345Sdim SmallPtrSet<const Function *, 8> CalledFunctions; 3302221345Sdim if (!cxxDtorIsEmpty(*DtorFn, CalledFunctions)) 3303221345Sdim continue; 3304221345Sdim 3305221345Sdim // Just remove the call. 3306221345Sdim CI->replaceAllUsesWith(Constant::getNullValue(CI->getType())); 3307221345Sdim CI->eraseFromParent(); 3308221345Sdim 3309221345Sdim ++NumCXXDtorsRemoved; 3310221345Sdim 3311221345Sdim Changed |= true; 3312221345Sdim } 3313221345Sdim 3314221345Sdim return Changed; 3315221345Sdim} 3316221345Sdim 3317193323Sedbool GlobalOpt::runOnModule(Module &M) { 3318193323Sed bool Changed = false; 3319218893Sdim 3320243830Sdim TD = getAnalysisIfAvailable<DataLayout>(); 3321234353Sdim TLI = &getAnalysis<TargetLibraryInfo>(); 3322234353Sdim 3323193323Sed // Try to find the llvm.globalctors list. 3324193323Sed GlobalVariable *GlobalCtors = FindGlobalCtors(M); 3325193323Sed 3326234353Sdim Function *CXAAtExitFn = FindCXAAtExit(M, TLI); 3327221345Sdim 3328193323Sed bool LocalChange = true; 3329193323Sed while (LocalChange) { 3330193323Sed LocalChange = false; 3331218893Sdim 3332193323Sed // Delete functions that are trivially dead, ccc -> fastcc 3333193323Sed LocalChange |= OptimizeFunctions(M); 3334218893Sdim 3335193323Sed // Optimize global_ctors list. 3336193323Sed if (GlobalCtors) 3337193323Sed LocalChange |= OptimizeGlobalCtorsList(GlobalCtors); 3338218893Sdim 3339193323Sed // Optimize non-address-taken globals. 3340193323Sed LocalChange |= OptimizeGlobalVars(M); 3341193323Sed 3342193323Sed // Resolve aliases, when possible. 3343193323Sed LocalChange |= OptimizeGlobalAliases(M); 3344221345Sdim 3345221345Sdim // Try to remove trivial global destructors. 3346221345Sdim if (CXAAtExitFn) 3347221345Sdim LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn); 3348221345Sdim 3349193323Sed Changed |= LocalChange; 3350193323Sed } 3351218893Sdim 3352193323Sed // TODO: Move all global ctors functions to the end of the module for code 3353193323Sed // layout. 3354218893Sdim 3355193323Sed return Changed; 3356193323Sed} 3357