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" 40263508Sdim#include "llvm/Support/ValueHandle.h" 41249423Sdim#include "llvm/Target/TargetLibraryInfo.h" 42263508Sdim#include "llvm/Transforms/Utils/GlobalStatus.h" 43263508Sdim#include "llvm/Transforms/Utils/ModuleUtils.h" 44193323Sed#include <algorithm> 45193323Sedusing namespace llvm; 46193323Sed 47193323SedSTATISTIC(NumMarked , "Number of globals marked constant"); 48218893SdimSTATISTIC(NumUnnamed , "Number of globals marked unnamed_addr"); 49193323SedSTATISTIC(NumSRA , "Number of aggregate globals broken into scalars"); 50193323SedSTATISTIC(NumHeapSRA , "Number of heap objects SRA'd"); 51193323SedSTATISTIC(NumSubstitute,"Number of globals with initializers stored into them"); 52193323SedSTATISTIC(NumDeleted , "Number of globals deleted"); 53193323SedSTATISTIC(NumFnDeleted , "Number of functions deleted"); 54193323SedSTATISTIC(NumGlobUses , "Number of global uses devirtualized"); 55193323SedSTATISTIC(NumLocalized , "Number of globals localized"); 56193323SedSTATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans"); 57193323SedSTATISTIC(NumFastCallFns , "Number of functions converted to fastcc"); 58193323SedSTATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated"); 59193323SedSTATISTIC(NumNestRemoved , "Number of nest attributes removed"); 60193323SedSTATISTIC(NumAliasesResolved, "Number of global aliases resolved"); 61193323SedSTATISTIC(NumAliasesRemoved, "Number of global aliases eliminated"); 62221345SdimSTATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed"); 63193323Sed 64193323Sednamespace { 65198892Srdivacky struct GlobalOpt : public ModulePass { 66193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 67234353Sdim AU.addRequired<TargetLibraryInfo>(); 68193323Sed } 69193323Sed static char ID; // Pass identification, replacement for typeid 70218893Sdim GlobalOpt() : ModulePass(ID) { 71218893Sdim initializeGlobalOptPass(*PassRegistry::getPassRegistry()); 72218893Sdim } 73193323Sed 74193323Sed bool runOnModule(Module &M); 75193323Sed 76193323Sed private: 77193323Sed GlobalVariable *FindGlobalCtors(Module &M); 78193323Sed bool OptimizeFunctions(Module &M); 79193323Sed bool OptimizeGlobalVars(Module &M); 80193323Sed bool OptimizeGlobalAliases(Module &M); 81193323Sed bool OptimizeGlobalCtorsList(GlobalVariable *&GCL); 82218893Sdim bool ProcessGlobal(GlobalVariable *GV,Module::global_iterator &GVI); 83218893Sdim bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI, 84218893Sdim const GlobalStatus &GS); 85221345Sdim bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn); 86234353Sdim 87243830Sdim DataLayout *TD; 88234353Sdim TargetLibraryInfo *TLI; 89193323Sed }; 90193323Sed} 91193323Sed 92193323Sedchar GlobalOpt::ID = 0; 93234353SdimINITIALIZE_PASS_BEGIN(GlobalOpt, "globalopt", 94218893Sdim "Global Variable Optimizer", false, false) 95234353SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 96234353SdimINITIALIZE_PASS_END(GlobalOpt, "globalopt", 97234353Sdim "Global Variable Optimizer", false, false) 98193323Sed 99193323SedModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); } 100193323Sed 101239462Sdim/// isLeakCheckerRoot - Is this global variable possibly used by a leak checker 102239462Sdim/// as a root? If so, we might not really want to eliminate the stores to it. 103239462Sdimstatic bool isLeakCheckerRoot(GlobalVariable *GV) { 104239462Sdim // A global variable is a root if it is a pointer, or could plausibly contain 105239462Sdim // a pointer. There are two challenges; one is that we could have a struct 106239462Sdim // the has an inner member which is a pointer. We recurse through the type to 107239462Sdim // detect these (up to a point). The other is that we may actually be a union 108239462Sdim // of a pointer and another type, and so our LLVM type is an integer which 109239462Sdim // gets converted into a pointer, or our type is an [i8 x #] with a pointer 110239462Sdim // potentially contained here. 111239462Sdim 112239462Sdim if (GV->hasPrivateLinkage()) 113239462Sdim return false; 114239462Sdim 115239462Sdim SmallVector<Type *, 4> Types; 116239462Sdim Types.push_back(cast<PointerType>(GV->getType())->getElementType()); 117239462Sdim 118239462Sdim unsigned Limit = 20; 119239462Sdim do { 120239462Sdim Type *Ty = Types.pop_back_val(); 121239462Sdim switch (Ty->getTypeID()) { 122239462Sdim default: break; 123239462Sdim case Type::PointerTyID: return true; 124239462Sdim case Type::ArrayTyID: 125239462Sdim case Type::VectorTyID: { 126239462Sdim SequentialType *STy = cast<SequentialType>(Ty); 127239462Sdim Types.push_back(STy->getElementType()); 128239462Sdim break; 129239462Sdim } 130239462Sdim case Type::StructTyID: { 131239462Sdim StructType *STy = cast<StructType>(Ty); 132239462Sdim if (STy->isOpaque()) return true; 133239462Sdim for (StructType::element_iterator I = STy->element_begin(), 134239462Sdim E = STy->element_end(); I != E; ++I) { 135239462Sdim Type *InnerTy = *I; 136239462Sdim if (isa<PointerType>(InnerTy)) return true; 137239462Sdim if (isa<CompositeType>(InnerTy)) 138239462Sdim Types.push_back(InnerTy); 139239462Sdim } 140239462Sdim break; 141239462Sdim } 142239462Sdim } 143239462Sdim if (--Limit == 0) return true; 144239462Sdim } while (!Types.empty()); 145239462Sdim return false; 146239462Sdim} 147239462Sdim 148239462Sdim/// Given a value that is stored to a global but never read, determine whether 149239462Sdim/// it's safe to remove the store and the chain of computation that feeds the 150239462Sdim/// store. 151243830Sdimstatic bool IsSafeComputationToRemove(Value *V, const TargetLibraryInfo *TLI) { 152239462Sdim do { 153239462Sdim if (isa<Constant>(V)) 154239462Sdim return true; 155239462Sdim if (!V->hasOneUse()) 156239462Sdim return false; 157239462Sdim if (isa<LoadInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V) || 158239462Sdim isa<GlobalValue>(V)) 159239462Sdim return false; 160243830Sdim if (isAllocationFn(V, TLI)) 161239462Sdim return true; 162239462Sdim 163239462Sdim Instruction *I = cast<Instruction>(V); 164239462Sdim if (I->mayHaveSideEffects()) 165239462Sdim return false; 166239462Sdim if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) { 167239462Sdim if (!GEP->hasAllConstantIndices()) 168239462Sdim return false; 169239462Sdim } else if (I->getNumOperands() != 1) { 170239462Sdim return false; 171239462Sdim } 172239462Sdim 173239462Sdim V = I->getOperand(0); 174239462Sdim } while (1); 175239462Sdim} 176239462Sdim 177239462Sdim/// CleanupPointerRootUsers - This GV is a pointer root. Loop over all users 178239462Sdim/// of the global and clean up any that obviously don't assign the global a 179239462Sdim/// value that isn't dynamically allocated. 180239462Sdim/// 181243830Sdimstatic bool CleanupPointerRootUsers(GlobalVariable *GV, 182243830Sdim const TargetLibraryInfo *TLI) { 183239462Sdim // A brief explanation of leak checkers. The goal is to find bugs where 184239462Sdim // pointers are forgotten, causing an accumulating growth in memory 185239462Sdim // usage over time. The common strategy for leak checkers is to whitelist the 186239462Sdim // memory pointed to by globals at exit. This is popular because it also 187239462Sdim // solves another problem where the main thread of a C++ program may shut down 188239462Sdim // before other threads that are still expecting to use those globals. To 189239462Sdim // handle that case, we expect the program may create a singleton and never 190239462Sdim // destroy it. 191239462Sdim 192239462Sdim bool Changed = false; 193239462Sdim 194239462Sdim // If Dead[n].first is the only use of a malloc result, we can delete its 195239462Sdim // chain of computation and the store to the global in Dead[n].second. 196239462Sdim SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead; 197239462Sdim 198239462Sdim // Constants can't be pointers to dynamically allocated memory. 199239462Sdim for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 200239462Sdim UI != E;) { 201239462Sdim User *U = *UI++; 202239462Sdim if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 203239462Sdim Value *V = SI->getValueOperand(); 204239462Sdim if (isa<Constant>(V)) { 205239462Sdim Changed = true; 206239462Sdim SI->eraseFromParent(); 207239462Sdim } else if (Instruction *I = dyn_cast<Instruction>(V)) { 208239462Sdim if (I->hasOneUse()) 209239462Sdim Dead.push_back(std::make_pair(I, SI)); 210239462Sdim } 211239462Sdim } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) { 212239462Sdim if (isa<Constant>(MSI->getValue())) { 213239462Sdim Changed = true; 214239462Sdim MSI->eraseFromParent(); 215239462Sdim } else if (Instruction *I = dyn_cast<Instruction>(MSI->getValue())) { 216239462Sdim if (I->hasOneUse()) 217239462Sdim Dead.push_back(std::make_pair(I, MSI)); 218239462Sdim } 219239462Sdim } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) { 220239462Sdim GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(MTI->getSource()); 221239462Sdim if (MemSrc && MemSrc->isConstant()) { 222239462Sdim Changed = true; 223239462Sdim MTI->eraseFromParent(); 224239462Sdim } else if (Instruction *I = dyn_cast<Instruction>(MemSrc)) { 225239462Sdim if (I->hasOneUse()) 226239462Sdim Dead.push_back(std::make_pair(I, MTI)); 227239462Sdim } 228239462Sdim } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 229239462Sdim if (CE->use_empty()) { 230239462Sdim CE->destroyConstant(); 231239462Sdim Changed = true; 232239462Sdim } 233239462Sdim } else if (Constant *C = dyn_cast<Constant>(U)) { 234263508Sdim if (isSafeToDestroyConstant(C)) { 235239462Sdim C->destroyConstant(); 236239462Sdim // This could have invalidated UI, start over from scratch. 237239462Sdim Dead.clear(); 238243830Sdim CleanupPointerRootUsers(GV, TLI); 239239462Sdim return true; 240239462Sdim } 241239462Sdim } 242239462Sdim } 243239462Sdim 244239462Sdim for (int i = 0, e = Dead.size(); i != e; ++i) { 245243830Sdim if (IsSafeComputationToRemove(Dead[i].first, TLI)) { 246239462Sdim Dead[i].second->eraseFromParent(); 247239462Sdim Instruction *I = Dead[i].first; 248239462Sdim do { 249249423Sdim if (isAllocationFn(I, TLI)) 250249423Sdim break; 251239462Sdim Instruction *J = dyn_cast<Instruction>(I->getOperand(0)); 252239462Sdim if (!J) 253239462Sdim break; 254239462Sdim I->eraseFromParent(); 255239462Sdim I = J; 256239462Sdim } while (1); 257239462Sdim I->eraseFromParent(); 258239462Sdim } 259239462Sdim } 260239462Sdim 261239462Sdim return Changed; 262239462Sdim} 263239462Sdim 264193323Sed/// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all 265193323Sed/// users of the global, cleaning up the obvious ones. This is largely just a 266193323Sed/// quick scan over the use list to clean up the easy and obvious cruft. This 267193323Sed/// returns true if it made a change. 268234353Sdimstatic bool CleanupConstantGlobalUsers(Value *V, Constant *Init, 269243830Sdim DataLayout *TD, TargetLibraryInfo *TLI) { 270193323Sed bool Changed = false; 271263508Sdim // Note that we need to use a weak value handle for the worklist items. When 272263508Sdim // we delete a constant array, we may also be holding pointer to one of its 273263508Sdim // elements (or an element of one of its elements if we're dealing with an 274263508Sdim // array of arrays) in the worklist. 275263508Sdim SmallVector<WeakVH, 8> WorkList(V->use_begin(), V->use_end()); 276249423Sdim while (!WorkList.empty()) { 277263508Sdim Value *UV = WorkList.pop_back_val(); 278263508Sdim if (!UV) 279263508Sdim continue; 280193323Sed 281263508Sdim User *U = cast<User>(UV); 282263508Sdim 283193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 284193323Sed if (Init) { 285193323Sed // Replace the load with the initializer. 286193323Sed LI->replaceAllUsesWith(Init); 287193323Sed LI->eraseFromParent(); 288193323Sed Changed = true; 289193323Sed } 290193323Sed } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 291193323Sed // Store must be unreachable or storing Init into the global. 292193323Sed SI->eraseFromParent(); 293193323Sed Changed = true; 294193323Sed } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 295193323Sed if (CE->getOpcode() == Instruction::GetElementPtr) { 296193323Sed Constant *SubInit = 0; 297193323Sed if (Init) 298193323Sed SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); 299234353Sdim Changed |= CleanupConstantGlobalUsers(CE, SubInit, TD, TLI); 300218893Sdim } else if (CE->getOpcode() == Instruction::BitCast && 301204642Srdivacky CE->getType()->isPointerTy()) { 302193323Sed // Pointer cast, delete any stores and memsets to the global. 303234353Sdim Changed |= CleanupConstantGlobalUsers(CE, 0, TD, TLI); 304193323Sed } 305193323Sed 306193323Sed if (CE->use_empty()) { 307193323Sed CE->destroyConstant(); 308193323Sed Changed = true; 309193323Sed } 310193323Sed } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 311193323Sed // Do not transform "gepinst (gep constexpr (GV))" here, because forming 312193323Sed // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold 313193323Sed // and will invalidate our notion of what Init is. 314193323Sed Constant *SubInit = 0; 315193323Sed if (!isa<ConstantExpr>(GEP->getOperand(0))) { 316218893Sdim ConstantExpr *CE = 317234353Sdim dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP, TD, TLI)); 318193323Sed if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr) 319193323Sed SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); 320234353Sdim 321234353Sdim // If the initializer is an all-null value and we have an inbounds GEP, 322234353Sdim // we already know what the result of any load from that GEP is. 323234353Sdim // TODO: Handle splats. 324234353Sdim if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds()) 325234353Sdim SubInit = Constant::getNullValue(GEP->getType()->getElementType()); 326193323Sed } 327234353Sdim Changed |= CleanupConstantGlobalUsers(GEP, SubInit, TD, TLI); 328193323Sed 329193323Sed if (GEP->use_empty()) { 330193323Sed GEP->eraseFromParent(); 331193323Sed Changed = true; 332193323Sed } 333193323Sed } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv 334193323Sed if (MI->getRawDest() == V) { 335193323Sed MI->eraseFromParent(); 336193323Sed Changed = true; 337193323Sed } 338193323Sed 339193323Sed } else if (Constant *C = dyn_cast<Constant>(U)) { 340193323Sed // If we have a chain of dead constantexprs or other things dangling from 341193323Sed // us, and if they are all dead, nuke them without remorse. 342263508Sdim if (isSafeToDestroyConstant(C)) { 343193323Sed C->destroyConstant(); 344234353Sdim CleanupConstantGlobalUsers(V, Init, TD, TLI); 345193323Sed return true; 346193323Sed } 347193323Sed } 348193323Sed } 349193323Sed return Changed; 350193323Sed} 351193323Sed 352193323Sed/// isSafeSROAElementUse - Return true if the specified instruction is a safe 353193323Sed/// user of a derived expression from a global that we want to SROA. 354193323Sedstatic bool isSafeSROAElementUse(Value *V) { 355193323Sed // We might have a dead and dangling constant hanging off of here. 356193323Sed if (Constant *C = dyn_cast<Constant>(V)) 357263508Sdim return isSafeToDestroyConstant(C); 358218893Sdim 359193323Sed Instruction *I = dyn_cast<Instruction>(V); 360193323Sed if (!I) return false; 361193323Sed 362193323Sed // Loads are ok. 363193323Sed if (isa<LoadInst>(I)) return true; 364193323Sed 365193323Sed // Stores *to* the pointer are ok. 366193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(I)) 367193323Sed return SI->getOperand(0) != V; 368218893Sdim 369193323Sed // Otherwise, it must be a GEP. 370193323Sed GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I); 371193323Sed if (GEPI == 0) return false; 372218893Sdim 373193323Sed if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) || 374193323Sed !cast<Constant>(GEPI->getOperand(1))->isNullValue()) 375193323Sed return false; 376218893Sdim 377193323Sed for (Value::use_iterator I = GEPI->use_begin(), E = GEPI->use_end(); 378193323Sed I != E; ++I) 379193323Sed if (!isSafeSROAElementUse(*I)) 380193323Sed return false; 381193323Sed return true; 382193323Sed} 383193323Sed 384193323Sed 385193323Sed/// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value. 386193323Sed/// Look at it and its uses and decide whether it is safe to SROA this global. 387193323Sed/// 388193323Sedstatic bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) { 389193323Sed // The user of the global must be a GEP Inst or a ConstantExpr GEP. 390218893Sdim if (!isa<GetElementPtrInst>(U) && 391218893Sdim (!isa<ConstantExpr>(U) || 392193323Sed cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr)) 393193323Sed return false; 394218893Sdim 395193323Sed // Check to see if this ConstantExpr GEP is SRA'able. In particular, we 396193323Sed // don't like < 3 operand CE's, and we don't like non-constant integer 397193323Sed // indices. This enforces that all uses are 'gep GV, 0, C, ...' for some 398193323Sed // value of C. 399193323Sed if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) || 400193323Sed !cast<Constant>(U->getOperand(1))->isNullValue() || 401193323Sed !isa<ConstantInt>(U->getOperand(2))) 402193323Sed return false; 403193323Sed 404193323Sed gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U); 405193323Sed ++GEPI; // Skip over the pointer index. 406218893Sdim 407193323Sed // If this is a use of an array allocation, do a bit more checking for sanity. 408226633Sdim if (ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) { 409193323Sed uint64_t NumElements = AT->getNumElements(); 410193323Sed ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2)); 411218893Sdim 412193323Sed // Check to make sure that index falls within the array. If not, 413193323Sed // something funny is going on, so we won't do the optimization. 414193323Sed // 415193323Sed if (Idx->getZExtValue() >= NumElements) 416193323Sed return false; 417218893Sdim 418193323Sed // We cannot scalar repl this level of the array unless any array 419193323Sed // sub-indices are in-range constants. In particular, consider: 420193323Sed // A[0][i]. We cannot know that the user isn't doing invalid things like 421193323Sed // allowing i to index an out-of-range subscript that accesses A[1]. 422193323Sed // 423193323Sed // Scalar replacing *just* the outer index of the array is probably not 424193323Sed // going to be a win anyway, so just give up. 425193323Sed for (++GEPI; // Skip array index. 426198090Srdivacky GEPI != E; 427193323Sed ++GEPI) { 428193323Sed uint64_t NumElements; 429226633Sdim if (ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI)) 430193323Sed NumElements = SubArrayTy->getNumElements(); 431226633Sdim else if (VectorType *SubVectorTy = dyn_cast<VectorType>(*GEPI)) 432198090Srdivacky NumElements = SubVectorTy->getNumElements(); 433198090Srdivacky else { 434204642Srdivacky assert((*GEPI)->isStructTy() && 435198090Srdivacky "Indexed GEP type is not array, vector, or struct!"); 436198090Srdivacky continue; 437198090Srdivacky } 438218893Sdim 439193323Sed ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand()); 440193323Sed if (!IdxVal || IdxVal->getZExtValue() >= NumElements) 441193323Sed return false; 442193323Sed } 443193323Sed } 444193323Sed 445193323Sed for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I) 446193323Sed if (!isSafeSROAElementUse(*I)) 447193323Sed return false; 448193323Sed return true; 449193323Sed} 450193323Sed 451193323Sed/// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it 452193323Sed/// is safe for us to perform this transformation. 453193323Sed/// 454193323Sedstatic bool GlobalUsersSafeToSRA(GlobalValue *GV) { 455193323Sed for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); 456193323Sed UI != E; ++UI) { 457193323Sed if (!IsUserOfGlobalSafeForSRA(*UI, GV)) 458193323Sed return false; 459193323Sed } 460193323Sed return true; 461193323Sed} 462193323Sed 463218893Sdim 464193323Sed/// SRAGlobal - Perform scalar replacement of aggregates on the specified global 465193323Sed/// variable. This opens the door for other optimizations by exposing the 466193323Sed/// behavior of the program in a more fine-grained way. We have determined that 467193323Sed/// this transformation is safe already. We return the first global variable we 468193323Sed/// insert so that the caller can reprocess it. 469243830Sdimstatic GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &TD) { 470193323Sed // Make sure this global only has simple uses that we can SRA. 471193323Sed if (!GlobalUsersSafeToSRA(GV)) 472193323Sed return 0; 473218893Sdim 474193323Sed assert(GV->hasLocalLinkage() && !GV->isConstant()); 475193323Sed Constant *Init = GV->getInitializer(); 476226633Sdim Type *Ty = Init->getType(); 477193323Sed 478193323Sed std::vector<GlobalVariable*> NewGlobals; 479193323Sed Module::GlobalListType &Globals = GV->getParent()->getGlobalList(); 480193323Sed 481193323Sed // Get the alignment of the global, either explicit or target-specific. 482193323Sed unsigned StartAlignment = GV->getAlignment(); 483193323Sed if (StartAlignment == 0) 484193323Sed StartAlignment = TD.getABITypeAlignment(GV->getType()); 485218893Sdim 486226633Sdim if (StructType *STy = dyn_cast<StructType>(Ty)) { 487193323Sed NewGlobals.reserve(STy->getNumElements()); 488193323Sed const StructLayout &Layout = *TD.getStructLayout(STy); 489193323Sed for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 490234353Sdim Constant *In = Init->getAggregateElement(i); 491193323Sed assert(In && "Couldn't get element of initializer?"); 492199481Srdivacky GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false, 493193323Sed GlobalVariable::InternalLinkage, 494198090Srdivacky In, GV->getName()+"."+Twine(i), 495239462Sdim GV->getThreadLocalMode(), 496198090Srdivacky GV->getType()->getAddressSpace()); 497193323Sed Globals.insert(GV, NGV); 498193323Sed NewGlobals.push_back(NGV); 499218893Sdim 500193323Sed // Calculate the known alignment of the field. If the original aggregate 501193323Sed // had 256 byte alignment for example, something might depend on that: 502193323Sed // propagate info to each field. 503193323Sed uint64_t FieldOffset = Layout.getElementOffset(i); 504193323Sed unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset); 505193323Sed if (NewAlign > TD.getABITypeAlignment(STy->getElementType(i))) 506193323Sed NGV->setAlignment(NewAlign); 507193323Sed } 508226633Sdim } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) { 509193323Sed unsigned NumElements = 0; 510226633Sdim if (ArrayType *ATy = dyn_cast<ArrayType>(STy)) 511193323Sed NumElements = ATy->getNumElements(); 512193323Sed else 513193323Sed NumElements = cast<VectorType>(STy)->getNumElements(); 514193323Sed 515193323Sed if (NumElements > 16 && GV->hasNUsesOrMore(16)) 516193323Sed return 0; // It's not worth it. 517193323Sed NewGlobals.reserve(NumElements); 518218893Sdim 519193323Sed uint64_t EltSize = TD.getTypeAllocSize(STy->getElementType()); 520193323Sed unsigned EltAlign = TD.getABITypeAlignment(STy->getElementType()); 521193323Sed for (unsigned i = 0, e = NumElements; i != e; ++i) { 522234353Sdim Constant *In = Init->getAggregateElement(i); 523193323Sed assert(In && "Couldn't get element of initializer?"); 524193323Sed 525199481Srdivacky GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false, 526193323Sed GlobalVariable::InternalLinkage, 527198090Srdivacky In, GV->getName()+"."+Twine(i), 528239462Sdim GV->getThreadLocalMode(), 529198090Srdivacky GV->getType()->getAddressSpace()); 530193323Sed Globals.insert(GV, NGV); 531193323Sed NewGlobals.push_back(NGV); 532218893Sdim 533193323Sed // Calculate the known alignment of the field. If the original aggregate 534193323Sed // had 256 byte alignment for example, something might depend on that: 535193323Sed // propagate info to each field. 536193323Sed unsigned NewAlign = (unsigned)MinAlign(StartAlignment, EltSize*i); 537193323Sed if (NewAlign > EltAlign) 538193323Sed NGV->setAlignment(NewAlign); 539193323Sed } 540193323Sed } 541193323Sed 542193323Sed if (NewGlobals.empty()) 543193323Sed return 0; 544218893Sdim 545202375Srdivacky DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV); 546193323Sed 547199481Srdivacky Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext())); 548193323Sed 549193323Sed // Loop over all of the uses of the global, replacing the constantexpr geps, 550193323Sed // with smaller constantexpr geps or direct references. 551193323Sed while (!GV->use_empty()) { 552193323Sed User *GEP = GV->use_back(); 553193323Sed assert(((isa<ConstantExpr>(GEP) && 554193323Sed cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| 555193323Sed isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!"); 556193323Sed 557193323Sed // Ignore the 1th operand, which has to be zero or else the program is quite 558193323Sed // broken (undefined). Get the 2nd operand, which is the structure or array 559193323Sed // index. 560193323Sed unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue(); 561193323Sed if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access. 562193323Sed 563193323Sed Value *NewPtr = NewGlobals[Val]; 564193323Sed 565193323Sed // Form a shorter GEP if needed. 566193323Sed if (GEP->getNumOperands() > 3) { 567193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) { 568193323Sed SmallVector<Constant*, 8> Idxs; 569193323Sed Idxs.push_back(NullInt); 570193323Sed for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i) 571193323Sed Idxs.push_back(CE->getOperand(i)); 572226633Sdim NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), Idxs); 573193323Sed } else { 574193323Sed GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP); 575193323Sed SmallVector<Value*, 8> Idxs; 576193323Sed Idxs.push_back(NullInt); 577193323Sed for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i) 578193323Sed Idxs.push_back(GEPI->getOperand(i)); 579226633Sdim NewPtr = GetElementPtrInst::Create(NewPtr, Idxs, 580198090Srdivacky GEPI->getName()+"."+Twine(Val),GEPI); 581193323Sed } 582193323Sed } 583193323Sed GEP->replaceAllUsesWith(NewPtr); 584193323Sed 585193323Sed if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP)) 586193323Sed GEPI->eraseFromParent(); 587193323Sed else 588193323Sed cast<ConstantExpr>(GEP)->destroyConstant(); 589193323Sed } 590193323Sed 591193323Sed // Delete the old global, now that it is dead. 592193323Sed Globals.erase(GV); 593193323Sed ++NumSRA; 594193323Sed 595193323Sed // Loop over the new globals array deleting any globals that are obviously 596193323Sed // dead. This can arise due to scalarization of a structure or an array that 597193323Sed // has elements that are dead. 598193323Sed unsigned FirstGlobal = 0; 599193323Sed for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i) 600193323Sed if (NewGlobals[i]->use_empty()) { 601193323Sed Globals.erase(NewGlobals[i]); 602193323Sed if (FirstGlobal == i) ++FirstGlobal; 603193323Sed } 604193323Sed 605193323Sed return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0; 606193323Sed} 607193323Sed 608193323Sed/// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified 609218893Sdim/// value will trap if the value is dynamically null. PHIs keeps track of any 610193323Sed/// phi nodes we've seen to avoid reprocessing them. 611207618Srdivackystatic bool AllUsesOfValueWillTrapIfNull(const Value *V, 612207618Srdivacky SmallPtrSet<const PHINode*, 8> &PHIs) { 613207618Srdivacky for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; 614207618Srdivacky ++UI) { 615207618Srdivacky const User *U = *UI; 616207618Srdivacky 617207618Srdivacky if (isa<LoadInst>(U)) { 618193323Sed // Will trap. 619207618Srdivacky } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 620193323Sed if (SI->getOperand(0) == V) { 621207618Srdivacky //cerr << "NONTRAPPING USE: " << *U; 622193323Sed return false; // Storing the value. 623193323Sed } 624207618Srdivacky } else if (const CallInst *CI = dyn_cast<CallInst>(U)) { 625205407Srdivacky if (CI->getCalledValue() != V) { 626207618Srdivacky //cerr << "NONTRAPPING USE: " << *U; 627193323Sed return false; // Not calling the ptr 628193323Sed } 629207618Srdivacky } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) { 630205407Srdivacky if (II->getCalledValue() != V) { 631207618Srdivacky //cerr << "NONTRAPPING USE: " << *U; 632193323Sed return false; // Not calling the ptr 633193323Sed } 634207618Srdivacky } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) { 635193323Sed if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false; 636207618Srdivacky } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 637193323Sed if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false; 638207618Srdivacky } else if (const PHINode *PN = dyn_cast<PHINode>(U)) { 639193323Sed // If we've already seen this phi node, ignore it, it has already been 640193323Sed // checked. 641203954Srdivacky if (PHIs.insert(PN) && !AllUsesOfValueWillTrapIfNull(PN, PHIs)) 642203954Srdivacky return false; 643207618Srdivacky } else if (isa<ICmpInst>(U) && 644193323Sed isa<ConstantPointerNull>(UI->getOperand(1))) { 645204642Srdivacky // Ignore icmp X, null 646193323Sed } else { 647207618Srdivacky //cerr << "NONTRAPPING USE: " << *U; 648193323Sed return false; 649193323Sed } 650207618Srdivacky } 651193323Sed return true; 652193323Sed} 653193323Sed 654193323Sed/// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads 655193323Sed/// from GV will trap if the loaded value is null. Note that this also permits 656193323Sed/// comparisons of the loaded value against null, as a special case. 657207618Srdivackystatic bool AllUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) { 658207618Srdivacky for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); 659207618Srdivacky UI != E; ++UI) { 660207618Srdivacky const User *U = *UI; 661207618Srdivacky 662207618Srdivacky if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { 663207618Srdivacky SmallPtrSet<const PHINode*, 8> PHIs; 664193323Sed if (!AllUsesOfValueWillTrapIfNull(LI, PHIs)) 665193323Sed return false; 666207618Srdivacky } else if (isa<StoreInst>(U)) { 667193323Sed // Ignore stores to the global. 668193323Sed } else { 669193323Sed // We don't know or understand this user, bail out. 670207618Srdivacky //cerr << "UNKNOWN USER OF GLOBAL!: " << *U; 671193323Sed return false; 672193323Sed } 673207618Srdivacky } 674193323Sed return true; 675193323Sed} 676193323Sed 677199481Srdivackystatic bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { 678193323Sed bool Changed = false; 679193323Sed for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) { 680193323Sed Instruction *I = cast<Instruction>(*UI++); 681193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 682193323Sed LI->setOperand(0, NewV); 683193323Sed Changed = true; 684193323Sed } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 685193323Sed if (SI->getOperand(1) == V) { 686193323Sed SI->setOperand(1, NewV); 687193323Sed Changed = true; 688193323Sed } 689193323Sed } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 690207618Srdivacky CallSite CS(I); 691207618Srdivacky if (CS.getCalledValue() == V) { 692193323Sed // Calling through the pointer! Turn into a direct call, but be careful 693193323Sed // that the pointer is not also being passed as an argument. 694207618Srdivacky CS.setCalledFunction(NewV); 695193323Sed Changed = true; 696193323Sed bool PassedAsArg = false; 697207618Srdivacky for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) 698207618Srdivacky if (CS.getArgument(i) == V) { 699193323Sed PassedAsArg = true; 700207618Srdivacky CS.setArgument(i, NewV); 701193323Sed } 702193323Sed 703193323Sed if (PassedAsArg) { 704193323Sed // Being passed as an argument also. Be careful to not invalidate UI! 705193323Sed UI = V->use_begin(); 706193323Sed } 707193323Sed } 708193323Sed } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 709193323Sed Changed |= OptimizeAwayTrappingUsesOfValue(CI, 710193323Sed ConstantExpr::getCast(CI->getOpcode(), 711199481Srdivacky NewV, CI->getType())); 712193323Sed if (CI->use_empty()) { 713193323Sed Changed = true; 714193323Sed CI->eraseFromParent(); 715193323Sed } 716193323Sed } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 717193323Sed // Should handle GEP here. 718193323Sed SmallVector<Constant*, 8> Idxs; 719193323Sed Idxs.reserve(GEPI->getNumOperands()-1); 720193323Sed for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end(); 721193323Sed i != e; ++i) 722193323Sed if (Constant *C = dyn_cast<Constant>(*i)) 723193323Sed Idxs.push_back(C); 724193323Sed else 725193323Sed break; 726193323Sed if (Idxs.size() == GEPI->getNumOperands()-1) 727193323Sed Changed |= OptimizeAwayTrappingUsesOfValue(GEPI, 728226633Sdim ConstantExpr::getGetElementPtr(NewV, Idxs)); 729193323Sed if (GEPI->use_empty()) { 730193323Sed Changed = true; 731193323Sed GEPI->eraseFromParent(); 732193323Sed } 733193323Sed } 734193323Sed } 735193323Sed 736193323Sed return Changed; 737193323Sed} 738193323Sed 739193323Sed 740193323Sed/// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null 741193323Sed/// value stored into it. If there are uses of the loaded value that would trap 742193323Sed/// if the loaded value is dynamically null, then we know that they cannot be 743193323Sed/// reachable with a null optimize away the load. 744234353Sdimstatic bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV, 745243830Sdim DataLayout *TD, 746234353Sdim TargetLibraryInfo *TLI) { 747193323Sed bool Changed = false; 748193323Sed 749193323Sed // Keep track of whether we are able to remove all the uses of the global 750193323Sed // other than the store that defines it. 751193323Sed bool AllNonStoreUsesGone = true; 752218893Sdim 753193323Sed // Replace all uses of loads with uses of uses of the stored value. 754193323Sed for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); GUI != E;){ 755193323Sed User *GlobalUser = *GUI++; 756193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) { 757199481Srdivacky Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV); 758193323Sed // If we were able to delete all uses of the loads 759193323Sed if (LI->use_empty()) { 760193323Sed LI->eraseFromParent(); 761193323Sed Changed = true; 762193323Sed } else { 763193323Sed AllNonStoreUsesGone = false; 764193323Sed } 765193323Sed } else if (isa<StoreInst>(GlobalUser)) { 766193323Sed // Ignore the store that stores "LV" to the global. 767193323Sed assert(GlobalUser->getOperand(1) == GV && 768193323Sed "Must be storing *to* the global"); 769193323Sed } else { 770193323Sed AllNonStoreUsesGone = false; 771193323Sed 772193323Sed // If we get here we could have other crazy uses that are transitively 773193323Sed // loaded. 774193323Sed assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || 775243830Sdim isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || 776243830Sdim isa<BitCastInst>(GlobalUser) || 777243830Sdim isa<GetElementPtrInst>(GlobalUser)) && 778223017Sdim "Only expect load and stores!"); 779193323Sed } 780193323Sed } 781193323Sed 782193323Sed if (Changed) { 783202375Srdivacky DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV); 784193323Sed ++NumGlobUses; 785193323Sed } 786193323Sed 787193323Sed // If we nuked all of the loads, then none of the stores are needed either, 788193323Sed // nor is the global. 789193323Sed if (AllNonStoreUsesGone) { 790239462Sdim if (isLeakCheckerRoot(GV)) { 791243830Sdim Changed |= CleanupPointerRootUsers(GV, TLI); 792239462Sdim } else { 793239462Sdim Changed = true; 794239462Sdim CleanupConstantGlobalUsers(GV, 0, TD, TLI); 795239462Sdim } 796193323Sed if (GV->use_empty()) { 797239462Sdim DEBUG(dbgs() << " *** GLOBAL NOW DEAD!\n"); 798239462Sdim Changed = true; 799193323Sed GV->eraseFromParent(); 800193323Sed ++NumDeleted; 801193323Sed } 802193323Sed } 803193323Sed return Changed; 804193323Sed} 805193323Sed 806193323Sed/// ConstantPropUsersOf - Walk the use list of V, constant folding all of the 807193323Sed/// instructions that are foldable. 808234353Sdimstatic void ConstantPropUsersOf(Value *V, 809243830Sdim DataLayout *TD, TargetLibraryInfo *TLI) { 810193323Sed for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) 811193323Sed if (Instruction *I = dyn_cast<Instruction>(*UI++)) 812234353Sdim if (Constant *NewC = ConstantFoldInstruction(I, TD, TLI)) { 813193323Sed I->replaceAllUsesWith(NewC); 814193323Sed 815193323Sed // Advance UI to the next non-I use to avoid invalidating it! 816193323Sed // Instructions could multiply use V. 817193323Sed while (UI != E && *UI == I) 818193323Sed ++UI; 819193323Sed I->eraseFromParent(); 820193323Sed } 821193323Sed} 822193323Sed 823193323Sed/// OptimizeGlobalAddressOfMalloc - This function takes the specified global 824193323Sed/// variable, and transforms the program as if it always contained the result of 825193323Sed/// the specified malloc. Because it is always the result of the specified 826193323Sed/// malloc, there is no reason to actually DO the malloc. Instead, turn the 827193323Sed/// malloc into a global, and any loads of GV as uses of the new global. 828193323Sedstatic GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, 829198090Srdivacky CallInst *CI, 830226633Sdim Type *AllocTy, 831204642Srdivacky ConstantInt *NElements, 832243830Sdim DataLayout *TD, 833234353Sdim TargetLibraryInfo *TLI) { 834204642Srdivacky DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << " CALL = " << *CI << '\n'); 835218893Sdim 836226633Sdim Type *GlobalType; 837204642Srdivacky if (NElements->getZExtValue() == 1) 838204642Srdivacky GlobalType = AllocTy; 839204642Srdivacky else 840204642Srdivacky // If we have an array allocation, the global variable is of an array. 841204642Srdivacky GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue()); 842198953Srdivacky 843198090Srdivacky // Create the new global variable. The contents of the malloc'd memory is 844198090Srdivacky // undefined, so initialize with an undef value. 845218893Sdim GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(), 846204642Srdivacky GlobalType, false, 847204642Srdivacky GlobalValue::InternalLinkage, 848204642Srdivacky UndefValue::get(GlobalType), 849198090Srdivacky GV->getName()+".body", 850198090Srdivacky GV, 851239462Sdim GV->getThreadLocalMode()); 852218893Sdim 853204642Srdivacky // If there are bitcast users of the malloc (which is typical, usually we have 854204642Srdivacky // a malloc + bitcast) then replace them with uses of the new global. Update 855204642Srdivacky // other users to use the global as well. 856204642Srdivacky BitCastInst *TheBC = 0; 857204642Srdivacky while (!CI->use_empty()) { 858204642Srdivacky Instruction *User = cast<Instruction>(CI->use_back()); 859204642Srdivacky if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { 860204642Srdivacky if (BCI->getType() == NewGV->getType()) { 861204642Srdivacky BCI->replaceAllUsesWith(NewGV); 862204642Srdivacky BCI->eraseFromParent(); 863204642Srdivacky } else { 864204642Srdivacky BCI->setOperand(0, NewGV); 865204642Srdivacky } 866204642Srdivacky } else { 867204642Srdivacky if (TheBC == 0) 868204642Srdivacky TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI); 869204642Srdivacky User->replaceUsesOfWith(CI, TheBC); 870204642Srdivacky } 871204642Srdivacky } 872218893Sdim 873198090Srdivacky Constant *RepValue = NewGV; 874198090Srdivacky if (NewGV->getType() != GV->getType()->getElementType()) 875218893Sdim RepValue = ConstantExpr::getBitCast(RepValue, 876198090Srdivacky GV->getType()->getElementType()); 877198090Srdivacky 878198090Srdivacky // If there is a comparison against null, we will insert a global bool to 879198090Srdivacky // keep track of whether the global was initialized yet or not. 880198090Srdivacky GlobalVariable *InitBool = 881199481Srdivacky new GlobalVariable(Type::getInt1Ty(GV->getContext()), false, 882198090Srdivacky GlobalValue::InternalLinkage, 883199481Srdivacky ConstantInt::getFalse(GV->getContext()), 884239462Sdim GV->getName()+".init", GV->getThreadLocalMode()); 885198090Srdivacky bool InitBoolUsed = false; 886198090Srdivacky 887198090Srdivacky // Loop over all uses of GV, processing them in turn. 888204642Srdivacky while (!GV->use_empty()) { 889204642Srdivacky if (StoreInst *SI = dyn_cast<StoreInst>(GV->use_back())) { 890198090Srdivacky // The global is initialized when the store to it occurs. 891234353Sdim new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, false, 0, 892234353Sdim SI->getOrdering(), SI->getSynchScope(), SI); 893198090Srdivacky SI->eraseFromParent(); 894204642Srdivacky continue; 895198090Srdivacky } 896218893Sdim 897204642Srdivacky LoadInst *LI = cast<LoadInst>(GV->use_back()); 898204642Srdivacky while (!LI->use_empty()) { 899204642Srdivacky Use &LoadUse = LI->use_begin().getUse(); 900204642Srdivacky if (!isa<ICmpInst>(LoadUse.getUser())) { 901204642Srdivacky LoadUse = RepValue; 902204642Srdivacky continue; 903204642Srdivacky } 904218893Sdim 905204642Srdivacky ICmpInst *ICI = cast<ICmpInst>(LoadUse.getUser()); 906204642Srdivacky // Replace the cmp X, 0 with a use of the bool value. 907234353Sdim // Sink the load to where the compare was, if atomic rules allow us to. 908234353Sdim Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", false, 0, 909234353Sdim LI->getOrdering(), LI->getSynchScope(), 910234353Sdim LI->isUnordered() ? (Instruction*)ICI : LI); 911204642Srdivacky InitBoolUsed = true; 912204642Srdivacky switch (ICI->getPredicate()) { 913204642Srdivacky default: llvm_unreachable("Unknown ICmp Predicate!"); 914204642Srdivacky case ICmpInst::ICMP_ULT: 915204642Srdivacky case ICmpInst::ICMP_SLT: // X < null -> always false 916204642Srdivacky LV = ConstantInt::getFalse(GV->getContext()); 917204642Srdivacky break; 918204642Srdivacky case ICmpInst::ICMP_ULE: 919204642Srdivacky case ICmpInst::ICMP_SLE: 920204642Srdivacky case ICmpInst::ICMP_EQ: 921204642Srdivacky LV = BinaryOperator::CreateNot(LV, "notinit", ICI); 922204642Srdivacky break; 923204642Srdivacky case ICmpInst::ICMP_NE: 924204642Srdivacky case ICmpInst::ICMP_UGE: 925204642Srdivacky case ICmpInst::ICMP_SGE: 926204642Srdivacky case ICmpInst::ICMP_UGT: 927204642Srdivacky case ICmpInst::ICMP_SGT: 928204642Srdivacky break; // no change. 929204642Srdivacky } 930204642Srdivacky ICI->replaceAllUsesWith(LV); 931204642Srdivacky ICI->eraseFromParent(); 932204642Srdivacky } 933204642Srdivacky LI->eraseFromParent(); 934204642Srdivacky } 935198090Srdivacky 936198090Srdivacky // If the initialization boolean was used, insert it, otherwise delete it. 937198090Srdivacky if (!InitBoolUsed) { 938198090Srdivacky while (!InitBool->use_empty()) // Delete initializations 939204642Srdivacky cast<StoreInst>(InitBool->use_back())->eraseFromParent(); 940198090Srdivacky delete InitBool; 941198090Srdivacky } else 942198090Srdivacky GV->getParent()->getGlobalList().insert(GV, InitBool); 943198090Srdivacky 944204642Srdivacky // Now the GV is dead, nuke it and the malloc.. 945198090Srdivacky GV->eraseFromParent(); 946198090Srdivacky CI->eraseFromParent(); 947198090Srdivacky 948198090Srdivacky // To further other optimizations, loop over all users of NewGV and try to 949198090Srdivacky // constant prop them. This will promote GEP instructions with constant 950198090Srdivacky // indices into GEP constant-exprs, which will allow global-opt to hack on it. 951234353Sdim ConstantPropUsersOf(NewGV, TD, TLI); 952198090Srdivacky if (RepValue != NewGV) 953234353Sdim ConstantPropUsersOf(RepValue, TD, TLI); 954198090Srdivacky 955198090Srdivacky return NewGV; 956198090Srdivacky} 957198090Srdivacky 958193323Sed/// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking 959193323Sed/// to make sure that there are no complex uses of V. We permit simple things 960193323Sed/// like dereferencing the pointer, but not storing through the address, unless 961193323Sed/// it is to the specified global. 962207618Srdivackystatic bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction *V, 963207618Srdivacky const GlobalVariable *GV, 964207618Srdivacky SmallPtrSet<const PHINode*, 8> &PHIs) { 965207618Srdivacky for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); 966207618Srdivacky UI != E; ++UI) { 967207618Srdivacky const Instruction *Inst = cast<Instruction>(*UI); 968207618Srdivacky 969193323Sed if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) { 970193323Sed continue; // Fine, ignore. 971193323Sed } 972218893Sdim 973207618Srdivacky if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 974193323Sed if (SI->getOperand(0) == V && SI->getOperand(1) != GV) 975193323Sed return false; // Storing the pointer itself... bad. 976193323Sed continue; // Otherwise, storing through it, or storing into GV... fine. 977193323Sed } 978218893Sdim 979207618Srdivacky // Must index into the array and into the struct. 980207618Srdivacky if (isa<GetElementPtrInst>(Inst) && Inst->getNumOperands() >= 3) { 981193323Sed if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs)) 982193323Sed return false; 983193323Sed continue; 984193323Sed } 985218893Sdim 986207618Srdivacky if (const PHINode *PN = dyn_cast<PHINode>(Inst)) { 987193323Sed // PHIs are ok if all uses are ok. Don't infinitely recurse through PHI 988193323Sed // cycles. 989193323Sed if (PHIs.insert(PN)) 990193323Sed if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs)) 991193323Sed return false; 992193323Sed continue; 993193323Sed } 994218893Sdim 995207618Srdivacky if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) { 996193323Sed if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs)) 997193323Sed return false; 998193323Sed continue; 999193323Sed } 1000218893Sdim 1001193323Sed return false; 1002193323Sed } 1003193323Sed return true; 1004193323Sed} 1005193323Sed 1006193323Sed/// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV 1007193323Sed/// somewhere. Transform all uses of the allocation into loads from the 1008193323Sed/// global and uses of the resultant pointer. Further, delete the store into 1009218893Sdim/// GV. This assumes that these value pass the 1010193323Sed/// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate. 1011218893Sdimstatic void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc, 1012193323Sed GlobalVariable *GV) { 1013193323Sed while (!Alloc->use_empty()) { 1014193323Sed Instruction *U = cast<Instruction>(*Alloc->use_begin()); 1015193323Sed Instruction *InsertPt = U; 1016193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 1017193323Sed // If this is the store of the allocation into the global, remove it. 1018193323Sed if (SI->getOperand(1) == GV) { 1019193323Sed SI->eraseFromParent(); 1020193323Sed continue; 1021193323Sed } 1022193323Sed } else if (PHINode *PN = dyn_cast<PHINode>(U)) { 1023193323Sed // Insert the load in the corresponding predecessor, not right before the 1024193323Sed // PHI. 1025193323Sed InsertPt = PN->getIncomingBlock(Alloc->use_begin())->getTerminator(); 1026193323Sed } else if (isa<BitCastInst>(U)) { 1027193323Sed // Must be bitcast between the malloc and store to initialize the global. 1028193323Sed ReplaceUsesOfMallocWithGlobal(U, GV); 1029193323Sed U->eraseFromParent(); 1030193323Sed continue; 1031193323Sed } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 1032193323Sed // If this is a "GEP bitcast" and the user is a store to the global, then 1033193323Sed // just process it as a bitcast. 1034193323Sed if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse()) 1035193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->use_back())) 1036193323Sed if (SI->getOperand(1) == GV) { 1037193323Sed // Must be bitcast GEP between the malloc and store to initialize 1038193323Sed // the global. 1039193323Sed ReplaceUsesOfMallocWithGlobal(GEPI, GV); 1040193323Sed GEPI->eraseFromParent(); 1041193323Sed continue; 1042193323Sed } 1043193323Sed } 1044218893Sdim 1045193323Sed // Insert a load from the global, and use it instead of the malloc. 1046193323Sed Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt); 1047193323Sed U->replaceUsesOfWith(Alloc, NL); 1048193323Sed } 1049193323Sed} 1050193323Sed 1051193323Sed/// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi 1052193323Sed/// of a load) are simple enough to perform heap SRA on. This permits GEP's 1053193323Sed/// that index through the array and struct field, icmps of null, and PHIs. 1054206083Srdivackystatic bool LoadUsesSimpleEnoughForHeapSRA(const Value *V, 1055207618Srdivacky SmallPtrSet<const PHINode*, 32> &LoadUsingPHIs, 1056207618Srdivacky SmallPtrSet<const PHINode*, 32> &LoadUsingPHIsPerLoad) { 1057193323Sed // We permit two users of the load: setcc comparing against the null 1058193323Sed // pointer, and a getelementptr of a specific form. 1059207618Srdivacky for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; 1060207618Srdivacky ++UI) { 1061206083Srdivacky const Instruction *User = cast<Instruction>(*UI); 1062218893Sdim 1063193323Sed // Comparison against null is ok. 1064206083Srdivacky if (const ICmpInst *ICI = dyn_cast<ICmpInst>(User)) { 1065193323Sed if (!isa<ConstantPointerNull>(ICI->getOperand(1))) 1066193323Sed return false; 1067193323Sed continue; 1068193323Sed } 1069218893Sdim 1070193323Sed // getelementptr is also ok, but only a simple form. 1071206083Srdivacky if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { 1072193323Sed // Must index into the array and into the struct. 1073193323Sed if (GEPI->getNumOperands() < 3) 1074193323Sed return false; 1075218893Sdim 1076193323Sed // Otherwise the GEP is ok. 1077193323Sed continue; 1078193323Sed } 1079218893Sdim 1080206083Srdivacky if (const PHINode *PN = dyn_cast<PHINode>(User)) { 1081193323Sed if (!LoadUsingPHIsPerLoad.insert(PN)) 1082193323Sed // This means some phi nodes are dependent on each other. 1083193323Sed // Avoid infinite looping! 1084193323Sed return false; 1085193323Sed if (!LoadUsingPHIs.insert(PN)) 1086193323Sed // If we have already analyzed this PHI, then it is safe. 1087193323Sed continue; 1088218893Sdim 1089193323Sed // Make sure all uses of the PHI are simple enough to transform. 1090193323Sed if (!LoadUsesSimpleEnoughForHeapSRA(PN, 1091193323Sed LoadUsingPHIs, LoadUsingPHIsPerLoad)) 1092193323Sed return false; 1093218893Sdim 1094193323Sed continue; 1095193323Sed } 1096218893Sdim 1097193323Sed // Otherwise we don't know what this is, not ok. 1098193323Sed return false; 1099193323Sed } 1100218893Sdim 1101193323Sed return true; 1102193323Sed} 1103193323Sed 1104193323Sed 1105193323Sed/// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from 1106193323Sed/// GV are simple enough to perform HeapSRA, return true. 1107206083Srdivackystatic bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable *GV, 1108198090Srdivacky Instruction *StoredVal) { 1109206083Srdivacky SmallPtrSet<const PHINode*, 32> LoadUsingPHIs; 1110206083Srdivacky SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad; 1111207618Srdivacky for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); 1112207618Srdivacky UI != E; ++UI) 1113206083Srdivacky if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 1114193323Sed if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs, 1115193323Sed LoadUsingPHIsPerLoad)) 1116193323Sed return false; 1117193323Sed LoadUsingPHIsPerLoad.clear(); 1118193323Sed } 1119218893Sdim 1120193323Sed // If we reach here, we know that all uses of the loads and transitive uses 1121193323Sed // (through PHI nodes) are simple enough to transform. However, we don't know 1122218893Sdim // that all inputs the to the PHI nodes are in the same equivalence sets. 1123193323Sed // Check to verify that all operands of the PHIs are either PHIS that can be 1124193323Sed // transformed, loads from GV, or MI itself. 1125207618Srdivacky for (SmallPtrSet<const PHINode*, 32>::const_iterator I = LoadUsingPHIs.begin() 1126207618Srdivacky , E = LoadUsingPHIs.end(); I != E; ++I) { 1127206083Srdivacky const PHINode *PN = *I; 1128193323Sed for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) { 1129193323Sed Value *InVal = PN->getIncomingValue(op); 1130218893Sdim 1131193323Sed // PHI of the stored value itself is ok. 1132198090Srdivacky if (InVal == StoredVal) continue; 1133218893Sdim 1134206083Srdivacky if (const PHINode *InPN = dyn_cast<PHINode>(InVal)) { 1135193323Sed // One of the PHIs in our set is (optimistically) ok. 1136193323Sed if (LoadUsingPHIs.count(InPN)) 1137193323Sed continue; 1138193323Sed return false; 1139193323Sed } 1140218893Sdim 1141193323Sed // Load from GV is ok. 1142206083Srdivacky if (const LoadInst *LI = dyn_cast<LoadInst>(InVal)) 1143193323Sed if (LI->getOperand(0) == GV) 1144193323Sed continue; 1145218893Sdim 1146193323Sed // UNDEF? NULL? 1147218893Sdim 1148193323Sed // Anything else is rejected. 1149193323Sed return false; 1150193323Sed } 1151193323Sed } 1152218893Sdim 1153193323Sed return true; 1154193323Sed} 1155193323Sed 1156193323Sedstatic Value *GetHeapSROAValue(Value *V, unsigned FieldNo, 1157193323Sed DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 1158199481Srdivacky std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { 1159193323Sed std::vector<Value*> &FieldVals = InsertedScalarizedValues[V]; 1160218893Sdim 1161193323Sed if (FieldNo >= FieldVals.size()) 1162193323Sed FieldVals.resize(FieldNo+1); 1163218893Sdim 1164193323Sed // If we already have this value, just reuse the previously scalarized 1165193323Sed // version. 1166193323Sed if (Value *FieldVal = FieldVals[FieldNo]) 1167193323Sed return FieldVal; 1168218893Sdim 1169193323Sed // Depending on what instruction this is, we have several cases. 1170193323Sed Value *Result; 1171193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(V)) { 1172193323Sed // This is a scalarized version of the load from the global. Just create 1173193323Sed // a new Load of the scalarized global. 1174193323Sed Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo, 1175193323Sed InsertedScalarizedValues, 1176199481Srdivacky PHIsToRewrite), 1177198090Srdivacky LI->getName()+".f"+Twine(FieldNo), LI); 1178193323Sed } else if (PHINode *PN = dyn_cast<PHINode>(V)) { 1179193323Sed // PN's type is pointer to struct. Make a new PHI of pointer to struct 1180193323Sed // field. 1181263508Sdim StructType *ST = cast<StructType>(PN->getType()->getPointerElementType()); 1182218893Sdim 1183221345Sdim PHINode *NewPN = 1184198090Srdivacky PHINode::Create(PointerType::getUnqual(ST->getElementType(FieldNo)), 1185221345Sdim PN->getNumIncomingValues(), 1186198090Srdivacky PN->getName()+".f"+Twine(FieldNo), PN); 1187221345Sdim Result = NewPN; 1188193323Sed PHIsToRewrite.push_back(std::make_pair(PN, FieldNo)); 1189193323Sed } else { 1190198090Srdivacky llvm_unreachable("Unknown usable value"); 1191193323Sed } 1192218893Sdim 1193193323Sed return FieldVals[FieldNo] = Result; 1194193323Sed} 1195193323Sed 1196193323Sed/// RewriteHeapSROALoadUser - Given a load instruction and a value derived from 1197193323Sed/// the load, rewrite the derived value to use the HeapSRoA'd load. 1198218893Sdimstatic void RewriteHeapSROALoadUser(Instruction *LoadUser, 1199193323Sed DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 1200199481Srdivacky std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { 1201193323Sed // If this is a comparison against null, handle it. 1202193323Sed if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) { 1203193323Sed assert(isa<ConstantPointerNull>(SCI->getOperand(1))); 1204193323Sed // If we have a setcc of the loaded pointer, we can use a setcc of any 1205193323Sed // field. 1206193323Sed Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0, 1207199481Srdivacky InsertedScalarizedValues, PHIsToRewrite); 1208218893Sdim 1209198090Srdivacky Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr, 1210218893Sdim Constant::getNullValue(NPtr->getType()), 1211198090Srdivacky SCI->getName()); 1212193323Sed SCI->replaceAllUsesWith(New); 1213193323Sed SCI->eraseFromParent(); 1214193323Sed return; 1215193323Sed } 1216218893Sdim 1217193323Sed // Handle 'getelementptr Ptr, Idx, i32 FieldNo ...' 1218193323Sed if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) { 1219193323Sed assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2)) 1220193323Sed && "Unexpected GEPI!"); 1221218893Sdim 1222193323Sed // Load the pointer for this field. 1223193323Sed unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue(); 1224193323Sed Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo, 1225199481Srdivacky InsertedScalarizedValues, PHIsToRewrite); 1226218893Sdim 1227193323Sed // Create the new GEP idx vector. 1228193323Sed SmallVector<Value*, 8> GEPIdx; 1229193323Sed GEPIdx.push_back(GEPI->getOperand(1)); 1230193323Sed GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end()); 1231218893Sdim 1232226633Sdim Value *NGEPI = GetElementPtrInst::Create(NewPtr, GEPIdx, 1233193323Sed GEPI->getName(), GEPI); 1234193323Sed GEPI->replaceAllUsesWith(NGEPI); 1235193323Sed GEPI->eraseFromParent(); 1236193323Sed return; 1237193323Sed } 1238193323Sed 1239193323Sed // Recursively transform the users of PHI nodes. This will lazily create the 1240193323Sed // PHIs that are needed for individual elements. Keep track of what PHIs we 1241193323Sed // see in InsertedScalarizedValues so that we don't get infinite loops (very 1242193323Sed // antisocial). If the PHI is already in InsertedScalarizedValues, it has 1243193323Sed // already been seen first by another load, so its uses have already been 1244193323Sed // processed. 1245193323Sed PHINode *PN = cast<PHINode>(LoadUser); 1246226633Sdim if (!InsertedScalarizedValues.insert(std::make_pair(PN, 1247226633Sdim std::vector<Value*>())).second) 1248226633Sdim return; 1249218893Sdim 1250193323Sed // If this is the first time we've seen this PHI, recursively process all 1251193323Sed // users. 1252193323Sed for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; ) { 1253193323Sed Instruction *User = cast<Instruction>(*UI++); 1254199481Srdivacky RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite); 1255193323Sed } 1256193323Sed} 1257193323Sed 1258193323Sed/// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global. Ptr 1259193323Sed/// is a value loaded from the global. Eliminate all uses of Ptr, making them 1260193323Sed/// use FieldGlobals instead. All uses of loaded values satisfy 1261193323Sed/// AllGlobalLoadUsesSimpleEnoughForHeapSRA. 1262218893Sdimstatic void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load, 1263193323Sed DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, 1264199481Srdivacky std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { 1265193323Sed for (Value::use_iterator UI = Load->use_begin(), E = Load->use_end(); 1266193323Sed UI != E; ) { 1267193323Sed Instruction *User = cast<Instruction>(*UI++); 1268199481Srdivacky RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite); 1269193323Sed } 1270218893Sdim 1271193323Sed if (Load->use_empty()) { 1272193323Sed Load->eraseFromParent(); 1273193323Sed InsertedScalarizedValues.erase(Load); 1274193323Sed } 1275193323Sed} 1276193323Sed 1277198090Srdivacky/// PerformHeapAllocSRoA - CI is an allocation of an array of structures. Break 1278198090Srdivacky/// it up into multiple allocations of arrays of the fields. 1279198953Srdivackystatic GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI, 1280243830Sdim Value *NElems, DataLayout *TD, 1281243830Sdim const TargetLibraryInfo *TLI) { 1282202375Srdivacky DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *CI << '\n'); 1283243830Sdim Type *MAT = getMallocAllocatedType(CI, TLI); 1284226633Sdim StructType *STy = cast<StructType>(MAT); 1285198090Srdivacky 1286198090Srdivacky // There is guaranteed to be at least one use of the malloc (storing 1287198090Srdivacky // it into GV). If there are other uses, change them to be uses of 1288198090Srdivacky // the global to simplify later code. This also deletes the store 1289198090Srdivacky // into GV. 1290198953Srdivacky ReplaceUsesOfMallocWithGlobal(CI, GV); 1291198953Srdivacky 1292198090Srdivacky // Okay, at this point, there are no users of the malloc. Insert N 1293198090Srdivacky // new mallocs at the same place as CI, and N globals. 1294198090Srdivacky std::vector<Value*> FieldGlobals; 1295198090Srdivacky std::vector<Value*> FieldMallocs; 1296218893Sdim 1297198090Srdivacky for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){ 1298226633Sdim Type *FieldTy = STy->getElementType(FieldNo); 1299226633Sdim PointerType *PFieldTy = PointerType::getUnqual(FieldTy); 1300218893Sdim 1301198090Srdivacky GlobalVariable *NGV = 1302198090Srdivacky new GlobalVariable(*GV->getParent(), 1303198090Srdivacky PFieldTy, false, GlobalValue::InternalLinkage, 1304198090Srdivacky Constant::getNullValue(PFieldTy), 1305198090Srdivacky GV->getName() + ".f" + Twine(FieldNo), GV, 1306239462Sdim GV->getThreadLocalMode()); 1307198090Srdivacky FieldGlobals.push_back(NGV); 1308218893Sdim 1309198953Srdivacky unsigned TypeSize = TD->getTypeAllocSize(FieldTy); 1310226633Sdim if (StructType *ST = dyn_cast<StructType>(FieldTy)) 1311198953Srdivacky TypeSize = TD->getStructLayout(ST)->getSizeInBytes(); 1312263508Sdim Type *IntPtrTy = TD->getIntPtrType(CI->getType()); 1313198953Srdivacky Value *NMI = CallInst::CreateMalloc(CI, IntPtrTy, FieldTy, 1314198953Srdivacky ConstantInt::get(IntPtrTy, TypeSize), 1315210299Sed NElems, 0, 1316198953Srdivacky CI->getName() + ".f" + Twine(FieldNo)); 1317204642Srdivacky FieldMallocs.push_back(NMI); 1318198953Srdivacky new StoreInst(NMI, NGV, CI); 1319198090Srdivacky } 1320218893Sdim 1321198090Srdivacky // The tricky aspect of this transformation is handling the case when malloc 1322198090Srdivacky // fails. In the original code, malloc failing would set the result pointer 1323198090Srdivacky // of malloc to null. In this case, some mallocs could succeed and others 1324198090Srdivacky // could fail. As such, we emit code that looks like this: 1325198090Srdivacky // F0 = malloc(field0) 1326198090Srdivacky // F1 = malloc(field1) 1327198090Srdivacky // F2 = malloc(field2) 1328198090Srdivacky // if (F0 == 0 || F1 == 0 || F2 == 0) { 1329198090Srdivacky // if (F0) { free(F0); F0 = 0; } 1330198090Srdivacky // if (F1) { free(F1); F1 = 0; } 1331198090Srdivacky // if (F2) { free(F2); F2 = 0; } 1332198090Srdivacky // } 1333199481Srdivacky // The malloc can also fail if its argument is too large. 1334210299Sed Constant *ConstantZero = ConstantInt::get(CI->getArgOperand(0)->getType(), 0); 1335210299Sed Value *RunningOr = new ICmpInst(CI, ICmpInst::ICMP_SLT, CI->getArgOperand(0), 1336199481Srdivacky ConstantZero, "isneg"); 1337198090Srdivacky for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) { 1338198953Srdivacky Value *Cond = new ICmpInst(CI, ICmpInst::ICMP_EQ, FieldMallocs[i], 1339198953Srdivacky Constant::getNullValue(FieldMallocs[i]->getType()), 1340198953Srdivacky "isnull"); 1341199481Srdivacky RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI); 1342198090Srdivacky } 1343198090Srdivacky 1344198090Srdivacky // Split the basic block at the old malloc. 1345198953Srdivacky BasicBlock *OrigBB = CI->getParent(); 1346198953Srdivacky BasicBlock *ContBB = OrigBB->splitBasicBlock(CI, "malloc_cont"); 1347218893Sdim 1348198090Srdivacky // Create the block to check the first condition. Put all these blocks at the 1349198090Srdivacky // end of the function as they are unlikely to be executed. 1350199481Srdivacky BasicBlock *NullPtrBlock = BasicBlock::Create(OrigBB->getContext(), 1351199481Srdivacky "malloc_ret_null", 1352198090Srdivacky OrigBB->getParent()); 1353218893Sdim 1354198090Srdivacky // Remove the uncond branch from OrigBB to ContBB, turning it into a cond 1355198090Srdivacky // branch on RunningOr. 1356198090Srdivacky OrigBB->getTerminator()->eraseFromParent(); 1357198090Srdivacky BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB); 1358218893Sdim 1359198090Srdivacky // Within the NullPtrBlock, we need to emit a comparison and branch for each 1360198090Srdivacky // pointer, because some may be null while others are not. 1361198090Srdivacky for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 1362198090Srdivacky Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock); 1363218893Sdim Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal, 1364226633Sdim Constant::getNullValue(GVVal->getType())); 1365199481Srdivacky BasicBlock *FreeBlock = BasicBlock::Create(Cmp->getContext(), "free_it", 1366198090Srdivacky OrigBB->getParent()); 1367199481Srdivacky BasicBlock *NextBlock = BasicBlock::Create(Cmp->getContext(), "next", 1368198090Srdivacky OrigBB->getParent()); 1369198892Srdivacky Instruction *BI = BranchInst::Create(FreeBlock, NextBlock, 1370198892Srdivacky Cmp, NullPtrBlock); 1371198090Srdivacky 1372198090Srdivacky // Fill in FreeBlock. 1373198892Srdivacky CallInst::CreateFree(GVVal, BI); 1374198090Srdivacky new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i], 1375198090Srdivacky FreeBlock); 1376198090Srdivacky BranchInst::Create(NextBlock, FreeBlock); 1377218893Sdim 1378198090Srdivacky NullPtrBlock = NextBlock; 1379198090Srdivacky } 1380218893Sdim 1381198090Srdivacky BranchInst::Create(ContBB, NullPtrBlock); 1382198953Srdivacky 1383198953Srdivacky // CI is no longer needed, remove it. 1384198090Srdivacky CI->eraseFromParent(); 1385198090Srdivacky 1386198090Srdivacky /// InsertedScalarizedLoads - As we process loads, if we can't immediately 1387198090Srdivacky /// update all uses of the load, keep track of what scalarized loads are 1388198090Srdivacky /// inserted for a given load. 1389198090Srdivacky DenseMap<Value*, std::vector<Value*> > InsertedScalarizedValues; 1390198090Srdivacky InsertedScalarizedValues[GV] = FieldGlobals; 1391218893Sdim 1392198090Srdivacky std::vector<std::pair<PHINode*, unsigned> > PHIsToRewrite; 1393218893Sdim 1394198090Srdivacky // Okay, the malloc site is completely handled. All of the uses of GV are now 1395198090Srdivacky // loads, and all uses of those loads are simple. Rewrite them to use loads 1396198090Srdivacky // of the per-field globals instead. 1397198090Srdivacky for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;) { 1398198090Srdivacky Instruction *User = cast<Instruction>(*UI++); 1399218893Sdim 1400198090Srdivacky if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 1401199481Srdivacky RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite); 1402198090Srdivacky continue; 1403198090Srdivacky } 1404218893Sdim 1405198090Srdivacky // Must be a store of null. 1406198090Srdivacky StoreInst *SI = cast<StoreInst>(User); 1407198090Srdivacky assert(isa<ConstantPointerNull>(SI->getOperand(0)) && 1408198090Srdivacky "Unexpected heap-sra user!"); 1409218893Sdim 1410198090Srdivacky // Insert a store of null into each global. 1411198090Srdivacky for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) { 1412226633Sdim PointerType *PT = cast<PointerType>(FieldGlobals[i]->getType()); 1413198090Srdivacky Constant *Null = Constant::getNullValue(PT->getElementType()); 1414198090Srdivacky new StoreInst(Null, FieldGlobals[i], SI); 1415198090Srdivacky } 1416198090Srdivacky // Erase the original store. 1417198090Srdivacky SI->eraseFromParent(); 1418198090Srdivacky } 1419198090Srdivacky 1420198090Srdivacky // While we have PHIs that are interesting to rewrite, do it. 1421198090Srdivacky while (!PHIsToRewrite.empty()) { 1422198090Srdivacky PHINode *PN = PHIsToRewrite.back().first; 1423198090Srdivacky unsigned FieldNo = PHIsToRewrite.back().second; 1424198090Srdivacky PHIsToRewrite.pop_back(); 1425198090Srdivacky PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]); 1426198090Srdivacky assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi"); 1427198090Srdivacky 1428198090Srdivacky // Add all the incoming values. This can materialize more phis. 1429198090Srdivacky for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1430198090Srdivacky Value *InVal = PN->getIncomingValue(i); 1431198090Srdivacky InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues, 1432199481Srdivacky PHIsToRewrite); 1433198090Srdivacky FieldPN->addIncoming(InVal, PN->getIncomingBlock(i)); 1434198090Srdivacky } 1435198090Srdivacky } 1436218893Sdim 1437198090Srdivacky // Drop all inter-phi links and any loads that made it this far. 1438198090Srdivacky for (DenseMap<Value*, std::vector<Value*> >::iterator 1439198090Srdivacky I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end(); 1440198090Srdivacky I != E; ++I) { 1441198090Srdivacky if (PHINode *PN = dyn_cast<PHINode>(I->first)) 1442198090Srdivacky PN->dropAllReferences(); 1443198090Srdivacky else if (LoadInst *LI = dyn_cast<LoadInst>(I->first)) 1444198090Srdivacky LI->dropAllReferences(); 1445198090Srdivacky } 1446218893Sdim 1447198090Srdivacky // Delete all the phis and loads now that inter-references are dead. 1448198090Srdivacky for (DenseMap<Value*, std::vector<Value*> >::iterator 1449198090Srdivacky I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end(); 1450198090Srdivacky I != E; ++I) { 1451198090Srdivacky if (PHINode *PN = dyn_cast<PHINode>(I->first)) 1452198090Srdivacky PN->eraseFromParent(); 1453198090Srdivacky else if (LoadInst *LI = dyn_cast<LoadInst>(I->first)) 1454198090Srdivacky LI->eraseFromParent(); 1455198090Srdivacky } 1456218893Sdim 1457198090Srdivacky // The old global is now dead, remove it. 1458198090Srdivacky GV->eraseFromParent(); 1459198090Srdivacky 1460198090Srdivacky ++NumHeapSRA; 1461198090Srdivacky return cast<GlobalVariable>(FieldGlobals[0]); 1462198090Srdivacky} 1463198090Srdivacky 1464193323Sed/// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a 1465193323Sed/// pointer global variable with a single value stored it that is a malloc or 1466193323Sed/// cast of malloc. 1467193323Sedstatic bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, 1468198090Srdivacky CallInst *CI, 1469226633Sdim Type *AllocTy, 1470234353Sdim AtomicOrdering Ordering, 1471198090Srdivacky Module::global_iterator &GVI, 1472243830Sdim DataLayout *TD, 1473234353Sdim TargetLibraryInfo *TLI) { 1474207618Srdivacky if (!TD) 1475207618Srdivacky return false; 1476218893Sdim 1477198090Srdivacky // If this is a malloc of an abstract type, don't touch it. 1478198090Srdivacky if (!AllocTy->isSized()) 1479198090Srdivacky return false; 1480198090Srdivacky 1481198090Srdivacky // We can't optimize this global unless all uses of it are *known* to be 1482198090Srdivacky // of the malloc value, not of the null initializer value (consider a use 1483198090Srdivacky // that compares the global's value against zero to see if the malloc has 1484198090Srdivacky // been reached). To do this, we check to see if all uses of the global 1485198090Srdivacky // would trap if the global were null: this proves that they must all 1486198090Srdivacky // happen after the malloc. 1487198090Srdivacky if (!AllUsesOfLoadedValueWillTrapIfNull(GV)) 1488198090Srdivacky return false; 1489198090Srdivacky 1490198090Srdivacky // We can't optimize this if the malloc itself is used in a complex way, 1491198090Srdivacky // for example, being stored into multiple globals. This allows the 1492234353Sdim // malloc to be stored into the specified global, loaded icmp'd, and 1493198090Srdivacky // GEP'd. These are all things we could transform to using the global 1494198090Srdivacky // for. 1495207618Srdivacky SmallPtrSet<const PHINode*, 8> PHIs; 1496207618Srdivacky if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV, PHIs)) 1497207618Srdivacky return false; 1498198090Srdivacky 1499198090Srdivacky // If we have a global that is only initialized with a fixed size malloc, 1500198090Srdivacky // transform the program to use global memory instead of malloc'd memory. 1501198090Srdivacky // This eliminates dynamic allocation, avoids an indirection accessing the 1502198090Srdivacky // data, and exposes the resultant global to further GlobalOpt. 1503198396Srdivacky // We cannot optimize the malloc if we cannot determine malloc array size. 1504243830Sdim Value *NElems = getMallocArraySize(CI, TD, TLI, true); 1505207618Srdivacky if (!NElems) 1506207618Srdivacky return false; 1507207618Srdivacky 1508207618Srdivacky if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems)) 1509207618Srdivacky // Restrict this transformation to only working on small allocations 1510207618Srdivacky // (2048 bytes currently), as we don't want to introduce a 16M global or 1511207618Srdivacky // something. 1512207618Srdivacky if (NElements->getZExtValue() * TD->getTypeAllocSize(AllocTy) < 2048) { 1513234353Sdim GVI = OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, TD, TLI); 1514207618Srdivacky return true; 1515207618Srdivacky } 1516218893Sdim 1517207618Srdivacky // If the allocation is an array of structures, consider transforming this 1518207618Srdivacky // into multiple malloc'd arrays, one for each field. This is basically 1519207618Srdivacky // SRoA for malloc'd memory. 1520198090Srdivacky 1521234353Sdim if (Ordering != NotAtomic) 1522234353Sdim return false; 1523234353Sdim 1524207618Srdivacky // If this is an allocation of a fixed size array of structs, analyze as a 1525207618Srdivacky // variable size array. malloc [100 x struct],1 -> malloc struct, 100 1526210299Sed if (NElems == ConstantInt::get(CI->getArgOperand(0)->getType(), 1)) 1527226633Sdim if (ArrayType *AT = dyn_cast<ArrayType>(AllocTy)) 1528207618Srdivacky AllocTy = AT->getElementType(); 1529210299Sed 1530226633Sdim StructType *AllocSTy = dyn_cast<StructType>(AllocTy); 1531207618Srdivacky if (!AllocSTy) 1532207618Srdivacky return false; 1533198090Srdivacky 1534207618Srdivacky // This the structure has an unreasonable number of fields, leave it 1535207618Srdivacky // alone. 1536207618Srdivacky if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 && 1537207618Srdivacky AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV, CI)) { 1538207618Srdivacky 1539207618Srdivacky // If this is a fixed size array, transform the Malloc to be an alloc of 1540207618Srdivacky // structs. malloc [100 x struct],1 -> malloc struct, 100 1541243830Sdim if (ArrayType *AT = dyn_cast<ArrayType>(getMallocAllocatedType(CI, TLI))) { 1542263508Sdim Type *IntPtrTy = TD->getIntPtrType(CI->getType()); 1543207618Srdivacky unsigned TypeSize = TD->getStructLayout(AllocSTy)->getSizeInBytes(); 1544207618Srdivacky Value *AllocSize = ConstantInt::get(IntPtrTy, TypeSize); 1545207618Srdivacky Value *NumElements = ConstantInt::get(IntPtrTy, AT->getNumElements()); 1546207618Srdivacky Instruction *Malloc = CallInst::CreateMalloc(CI, IntPtrTy, AllocSTy, 1547207618Srdivacky AllocSize, NumElements, 1548210299Sed 0, CI->getName()); 1549207618Srdivacky Instruction *Cast = new BitCastInst(Malloc, CI->getType(), "tmp", CI); 1550207618Srdivacky CI->replaceAllUsesWith(Cast); 1551207618Srdivacky CI->eraseFromParent(); 1552239462Sdim if (BitCastInst *BCI = dyn_cast<BitCastInst>(Malloc)) 1553239462Sdim CI = cast<CallInst>(BCI->getOperand(0)); 1554239462Sdim else 1555239462Sdim CI = cast<CallInst>(Malloc); 1556207618Srdivacky } 1557218893Sdim 1558243830Sdim GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, TD, TLI, true), 1559243830Sdim TD, TLI); 1560207618Srdivacky return true; 1561198090Srdivacky } 1562218893Sdim 1563198090Srdivacky return false; 1564218893Sdim} 1565198090Srdivacky 1566193323Sed// OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge 1567193323Sed// that only one value (besides its initializer) is ever stored to the global. 1568193323Sedstatic bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, 1569234353Sdim AtomicOrdering Ordering, 1570193323Sed Module::global_iterator &GVI, 1571243830Sdim DataLayout *TD, TargetLibraryInfo *TLI) { 1572193323Sed // Ignore no-op GEPs and bitcasts. 1573193323Sed StoredOnceVal = StoredOnceVal->stripPointerCasts(); 1574193323Sed 1575193323Sed // If we are dealing with a pointer global that is initialized to null and 1576193323Sed // only has one (non-null) value stored into it, then we can optimize any 1577193323Sed // users of the loaded value (often calls and loads) that would trap if the 1578193323Sed // value was null. 1579204642Srdivacky if (GV->getInitializer()->getType()->isPointerTy() && 1580193323Sed GV->getInitializer()->isNullValue()) { 1581193323Sed if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) { 1582193323Sed if (GV->getInitializer()->getType() != SOVC->getType()) 1583223017Sdim SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); 1584193323Sed 1585193323Sed // Optimize away any trapping uses of the loaded value. 1586234353Sdim if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, TD, TLI)) 1587193323Sed return true; 1588243830Sdim } else if (CallInst *CI = extractMallocCall(StoredOnceVal, TLI)) { 1589243830Sdim Type *MallocType = getMallocAllocatedType(CI, TLI); 1590234353Sdim if (MallocType && 1591234353Sdim TryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType, Ordering, GVI, 1592234353Sdim TD, TLI)) 1593198953Srdivacky return true; 1594193323Sed } 1595193323Sed } 1596193323Sed 1597193323Sed return false; 1598193323Sed} 1599193323Sed 1600193323Sed/// TryToShrinkGlobalToBoolean - At this point, we have learned that the only 1601193323Sed/// two values ever stored into GV are its initializer and OtherVal. See if we 1602193323Sed/// can shrink the global into a boolean and select between the two values 1603193323Sed/// whenever it is used. This exposes the values to other scalar optimizations. 1604199481Srdivackystatic bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { 1605226633Sdim Type *GVElType = GV->getType()->getElementType(); 1606218893Sdim 1607193323Sed // If GVElType is already i1, it is already shrunk. If the type of the GV is 1608193323Sed // an FP value, pointer or vector, don't do this optimization because a select 1609193323Sed // between them is very expensive and unlikely to lead to later 1610193323Sed // simplification. In these cases, we typically end up with "cond ? v1 : v2" 1611193323Sed // where v1 and v2 both require constant pool loads, a big loss. 1612199481Srdivacky if (GVElType == Type::getInt1Ty(GV->getContext()) || 1613203954Srdivacky GVElType->isFloatingPointTy() || 1614204642Srdivacky GVElType->isPointerTy() || GVElType->isVectorTy()) 1615193323Sed return false; 1616210299Sed 1617193323Sed // Walk the use list of the global seeing if all the uses are load or store. 1618193323Sed // If there is anything else, bail out. 1619210299Sed for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I){ 1620210299Sed User *U = *I; 1621210299Sed if (!isa<LoadInst>(U) && !isa<StoreInst>(U)) 1622193323Sed return false; 1623210299Sed } 1624210299Sed 1625202375Srdivacky DEBUG(dbgs() << " *** SHRINKING TO BOOL: " << *GV); 1626218893Sdim 1627193323Sed // Create the new global, initializing it to false. 1628199481Srdivacky GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(GV->getContext()), 1629199481Srdivacky false, 1630218893Sdim GlobalValue::InternalLinkage, 1631199481Srdivacky ConstantInt::getFalse(GV->getContext()), 1632193323Sed GV->getName()+".b", 1633249423Sdim GV->getThreadLocalMode(), 1634249423Sdim GV->getType()->getAddressSpace()); 1635193323Sed GV->getParent()->getGlobalList().insert(GV, NewGV); 1636193323Sed 1637193323Sed Constant *InitVal = GV->getInitializer(); 1638199481Srdivacky assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) && 1639198090Srdivacky "No reason to shrink to bool!"); 1640193323Sed 1641193323Sed // If initialized to zero and storing one into the global, we can use a cast 1642193323Sed // instead of a select to synthesize the desired value. 1643193323Sed bool IsOneZero = false; 1644193323Sed if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)) 1645193323Sed IsOneZero = InitVal->isNullValue() && CI->isOne(); 1646193323Sed 1647193323Sed while (!GV->use_empty()) { 1648193323Sed Instruction *UI = cast<Instruction>(GV->use_back()); 1649193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { 1650193323Sed // Change the store into a boolean store. 1651193323Sed bool StoringOther = SI->getOperand(0) == OtherVal; 1652193323Sed // Only do this if we weren't storing a loaded value. 1653193323Sed Value *StoreVal; 1654249423Sdim if (StoringOther || SI->getOperand(0) == InitVal) { 1655199481Srdivacky StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()), 1656199481Srdivacky StoringOther); 1657249423Sdim } else { 1658193323Sed // Otherwise, we are storing a previously loaded copy. To do this, 1659193323Sed // change the copy from copying the original value to just copying the 1660193323Sed // bool. 1661193323Sed Instruction *StoredVal = cast<Instruction>(SI->getOperand(0)); 1662193323Sed 1663210299Sed // If we've already replaced the input, StoredVal will be a cast or 1664193323Sed // select instruction. If not, it will be a load of the original 1665193323Sed // global. 1666193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) { 1667193323Sed assert(LI->getOperand(0) == GV && "Not a copy!"); 1668193323Sed // Insert a new load, to preserve the saved value. 1669234353Sdim StoreVal = new LoadInst(NewGV, LI->getName()+".b", false, 0, 1670234353Sdim LI->getOrdering(), LI->getSynchScope(), LI); 1671193323Sed } else { 1672193323Sed assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && 1673193323Sed "This is not a form that we understand!"); 1674193323Sed StoreVal = StoredVal->getOperand(0); 1675193323Sed assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!"); 1676193323Sed } 1677193323Sed } 1678234353Sdim new StoreInst(StoreVal, NewGV, false, 0, 1679234353Sdim SI->getOrdering(), SI->getSynchScope(), SI); 1680193323Sed } else { 1681193323Sed // Change the load into a load of bool then a select. 1682193323Sed LoadInst *LI = cast<LoadInst>(UI); 1683234353Sdim LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", false, 0, 1684234353Sdim LI->getOrdering(), LI->getSynchScope(), LI); 1685193323Sed Value *NSI; 1686193323Sed if (IsOneZero) 1687193323Sed NSI = new ZExtInst(NLI, LI->getType(), "", LI); 1688193323Sed else 1689193323Sed NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI); 1690193323Sed NSI->takeName(LI); 1691193323Sed LI->replaceAllUsesWith(NSI); 1692193323Sed } 1693193323Sed UI->eraseFromParent(); 1694193323Sed } 1695193323Sed 1696249423Sdim // Retain the name of the old global variable. People who are debugging their 1697249423Sdim // programs may expect these variables to be named the same. 1698249423Sdim NewGV->takeName(GV); 1699193323Sed GV->eraseFromParent(); 1700193323Sed return true; 1701193323Sed} 1702193323Sed 1703193323Sed 1704234353Sdim/// ProcessGlobal - Analyze the specified global variable and optimize it if 1705234353Sdim/// possible. If we make a change, return true. 1706218893Sdimbool GlobalOpt::ProcessGlobal(GlobalVariable *GV, 1707218893Sdim Module::global_iterator &GVI) { 1708239462Sdim if (!GV->isDiscardableIfUnused()) 1709218893Sdim return false; 1710218893Sdim 1711218893Sdim // Do more involved optimizations if the global is internal. 1712193323Sed GV->removeDeadConstantUsers(); 1713193323Sed 1714193323Sed if (GV->use_empty()) { 1715202375Srdivacky DEBUG(dbgs() << "GLOBAL DEAD: " << *GV); 1716193323Sed GV->eraseFromParent(); 1717193323Sed ++NumDeleted; 1718193323Sed return true; 1719193323Sed } 1720193323Sed 1721239462Sdim if (!GV->hasLocalLinkage()) 1722239462Sdim return false; 1723239462Sdim 1724218893Sdim GlobalStatus GS; 1725218893Sdim 1726263508Sdim if (GlobalStatus::analyzeGlobal(GV, GS)) 1727218893Sdim return false; 1728218893Sdim 1729263508Sdim if (!GS.IsCompared && !GV->hasUnnamedAddr()) { 1730218893Sdim GV->setUnnamedAddr(true); 1731218893Sdim NumUnnamed++; 1732218893Sdim } 1733218893Sdim 1734218893Sdim if (GV->isConstant() || !GV->hasInitializer()) 1735218893Sdim return false; 1736218893Sdim 1737263508Sdim return ProcessInternalGlobal(GV, GVI, GS); 1738218893Sdim} 1739218893Sdim 1740218893Sdim/// ProcessInternalGlobal - Analyze the specified global variable and optimize 1741218893Sdim/// it if possible. If we make a change, return true. 1742218893Sdimbool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV, 1743218893Sdim Module::global_iterator &GVI, 1744218893Sdim const GlobalStatus &GS) { 1745218893Sdim // If this is a first class global and has only one accessing function 1746263508Sdim // and this function is main (which we know is not recursive), we replace 1747263508Sdim // the global with a local alloca in this function. 1748218893Sdim // 1749218893Sdim // NOTE: It doesn't make sense to promote non single-value types since we 1750218893Sdim // are just replacing static memory to stack memory. 1751218893Sdim // 1752218893Sdim // If the global is in different address space, don't bring it to stack. 1753218893Sdim if (!GS.HasMultipleAccessingFunctions && 1754218893Sdim GS.AccessingFunction && !GS.HasNonInstructionUser && 1755218893Sdim GV->getType()->getElementType()->isSingleValueType() && 1756218893Sdim GS.AccessingFunction->getName() == "main" && 1757218893Sdim GS.AccessingFunction->hasExternalLinkage() && 1758218893Sdim GV->getType()->getAddressSpace() == 0) { 1759218893Sdim DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV); 1760234353Sdim Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction 1761218893Sdim ->getEntryBlock().begin()); 1762234353Sdim Type *ElemTy = GV->getType()->getElementType(); 1763218893Sdim // FIXME: Pass Global's alignment when globals have alignment 1764234353Sdim AllocaInst *Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), &FirstI); 1765218893Sdim if (!isa<UndefValue>(GV->getInitializer())) 1766218893Sdim new StoreInst(GV->getInitializer(), Alloca, &FirstI); 1767218893Sdim 1768218893Sdim GV->replaceAllUsesWith(Alloca); 1769218893Sdim GV->eraseFromParent(); 1770218893Sdim ++NumLocalized; 1771218893Sdim return true; 1772218893Sdim } 1773218893Sdim 1774218893Sdim // If the global is never loaded (but may be stored to), it is dead. 1775218893Sdim // Delete it now. 1776263508Sdim if (!GS.IsLoaded) { 1777218893Sdim DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV); 1778218893Sdim 1779239462Sdim bool Changed; 1780239462Sdim if (isLeakCheckerRoot(GV)) { 1781239462Sdim // Delete any constant stores to the global. 1782243830Sdim Changed = CleanupPointerRootUsers(GV, TLI); 1783239462Sdim } else { 1784239462Sdim // Delete any stores we can find to the global. We may not be able to 1785239462Sdim // make it completely dead though. 1786239462Sdim Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); 1787239462Sdim } 1788218893Sdim 1789218893Sdim // If the global is dead now, delete it. 1790218893Sdim if (GV->use_empty()) { 1791218893Sdim GV->eraseFromParent(); 1792218893Sdim ++NumDeleted; 1793218893Sdim Changed = true; 1794193323Sed } 1795218893Sdim return Changed; 1796193323Sed 1797263508Sdim } else if (GS.StoredType <= GlobalStatus::InitializerStored) { 1798249423Sdim DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n"); 1799218893Sdim GV->setConstant(true); 1800218893Sdim 1801218893Sdim // Clean up any obviously simplifiable users now. 1802234353Sdim CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); 1803218893Sdim 1804218893Sdim // If the global is dead now, just nuke it. 1805218893Sdim if (GV->use_empty()) { 1806218893Sdim DEBUG(dbgs() << " *** Marking constant allowed us to simplify " 1807218893Sdim << "all users and delete global!\n"); 1808193323Sed GV->eraseFromParent(); 1809218893Sdim ++NumDeleted; 1810193323Sed } 1811193323Sed 1812218893Sdim ++NumMarked; 1813218893Sdim return true; 1814218893Sdim } else if (!GV->getInitializer()->getType()->isSingleValueType()) { 1815243830Sdim if (DataLayout *TD = getAnalysisIfAvailable<DataLayout>()) 1816218893Sdim if (GlobalVariable *FirstNewGV = SRAGlobal(GV, *TD)) { 1817218893Sdim GVI = FirstNewGV; // Don't skip the newly produced globals! 1818218893Sdim return true; 1819193323Sed } 1820263508Sdim } else if (GS.StoredType == GlobalStatus::StoredOnce) { 1821218893Sdim // If the initial value for the global was an undef value, and if only 1822218893Sdim // one other value was stored into it, we can just change the 1823218893Sdim // initializer to be the stored value, then delete all stores to the 1824218893Sdim // global. This allows us to mark it constant. 1825218893Sdim if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) 1826218893Sdim if (isa<UndefValue>(GV->getInitializer())) { 1827218893Sdim // Change the initial value here. 1828218893Sdim GV->setInitializer(SOVConstant); 1829193323Sed 1830218893Sdim // Clean up any obviously simplifiable users now. 1831234353Sdim CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); 1832193323Sed 1833218893Sdim if (GV->use_empty()) { 1834218893Sdim DEBUG(dbgs() << " *** Substituting initializer allowed us to " 1835239462Sdim << "simplify all users and delete global!\n"); 1836218893Sdim GV->eraseFromParent(); 1837218893Sdim ++NumDeleted; 1838218893Sdim } else { 1839218893Sdim GVI = GV; 1840218893Sdim } 1841218893Sdim ++NumSubstitute; 1842218893Sdim return true; 1843193323Sed } 1844193323Sed 1845218893Sdim // Try to optimize globals based on the knowledge that only one value 1846218893Sdim // (besides its initializer) is ever stored to the global. 1847234353Sdim if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, GVI, 1848234353Sdim TD, TLI)) 1849193323Sed return true; 1850193323Sed 1851218893Sdim // Otherwise, if the global was not a boolean, we can shrink it to be a 1852218893Sdim // boolean. 1853263508Sdim if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) { 1854263508Sdim if (GS.Ordering == NotAtomic) { 1855263508Sdim if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) { 1856263508Sdim ++NumShrunkToBool; 1857263508Sdim return true; 1858263508Sdim } 1859218893Sdim } 1860263508Sdim } 1861218893Sdim } 1862193323Sed 1863193323Sed return false; 1864193323Sed} 1865193323Sed 1866193323Sed/// ChangeCalleesToFastCall - Walk all of the direct calls of the specified 1867193323Sed/// function, changing them to FastCC. 1868193323Sedstatic void ChangeCalleesToFastCall(Function *F) { 1869193323Sed for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 1870239462Sdim if (isa<BlockAddress>(*UI)) 1871239462Sdim continue; 1872193323Sed CallSite User(cast<Instruction>(*UI)); 1873193323Sed User.setCallingConv(CallingConv::Fast); 1874193323Sed } 1875193323Sed} 1876193323Sed 1877249423Sdimstatic AttributeSet StripNest(LLVMContext &C, const AttributeSet &Attrs) { 1878193323Sed for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) { 1879249423Sdim unsigned Index = Attrs.getSlotIndex(i); 1880249423Sdim if (!Attrs.getSlotAttributes(i).hasAttribute(Index, Attribute::Nest)) 1881193323Sed continue; 1882193323Sed 1883193323Sed // There can be only one. 1884249423Sdim return Attrs.removeAttribute(C, Index, Attribute::Nest); 1885193323Sed } 1886193323Sed 1887193323Sed return Attrs; 1888193323Sed} 1889193323Sed 1890193323Sedstatic void RemoveNestAttribute(Function *F) { 1891243830Sdim F->setAttributes(StripNest(F->getContext(), F->getAttributes())); 1892193323Sed for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ 1893239462Sdim if (isa<BlockAddress>(*UI)) 1894239462Sdim continue; 1895193323Sed CallSite User(cast<Instruction>(*UI)); 1896243830Sdim User.setAttributes(StripNest(F->getContext(), User.getAttributes())); 1897193323Sed } 1898193323Sed} 1899193323Sed 1900193323Sedbool GlobalOpt::OptimizeFunctions(Module &M) { 1901193323Sed bool Changed = false; 1902193323Sed // Optimize functions. 1903193323Sed for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) { 1904193323Sed Function *F = FI++; 1905193323Sed // Functions without names cannot be referenced outside this module. 1906193323Sed if (!F->hasName() && !F->isDeclaration()) 1907193323Sed F->setLinkage(GlobalValue::InternalLinkage); 1908193323Sed F->removeDeadConstantUsers(); 1909234353Sdim if (F->isDefTriviallyDead()) { 1910198892Srdivacky F->eraseFromParent(); 1911193323Sed Changed = true; 1912193323Sed ++NumFnDeleted; 1913193323Sed } else if (F->hasLocalLinkage()) { 1914193323Sed if (F->getCallingConv() == CallingConv::C && !F->isVarArg() && 1915194178Sed !F->hasAddressTaken()) { 1916193323Sed // If this function has C calling conventions, is not a varargs 1917193323Sed // function, and is only called directly, promote it to use the Fast 1918193323Sed // calling convention. 1919193323Sed F->setCallingConv(CallingConv::Fast); 1920193323Sed ChangeCalleesToFastCall(F); 1921193323Sed ++NumFastCallFns; 1922193323Sed Changed = true; 1923193323Sed } 1924193323Sed 1925249423Sdim if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) && 1926194178Sed !F->hasAddressTaken()) { 1927193323Sed // The function is not used by a trampoline intrinsic, so it is safe 1928193323Sed // to remove the 'nest' attribute. 1929193323Sed RemoveNestAttribute(F); 1930193323Sed ++NumNestRemoved; 1931193323Sed Changed = true; 1932193323Sed } 1933193323Sed } 1934193323Sed } 1935193323Sed return Changed; 1936193323Sed} 1937193323Sed 1938193323Sedbool GlobalOpt::OptimizeGlobalVars(Module &M) { 1939193323Sed bool Changed = false; 1940193323Sed for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); 1941193323Sed GVI != E; ) { 1942193323Sed GlobalVariable *GV = GVI++; 1943193323Sed // Global variables without names cannot be referenced outside this module. 1944193323Sed if (!GV->hasName() && !GV->isDeclaration()) 1945193323Sed GV->setLinkage(GlobalValue::InternalLinkage); 1946199989Srdivacky // Simplify the initializer. 1947199989Srdivacky if (GV->hasInitializer()) 1948199989Srdivacky if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GV->getInitializer())) { 1949234353Sdim Constant *New = ConstantFoldConstantExpression(CE, TD, TLI); 1950199989Srdivacky if (New && New != CE) 1951199989Srdivacky GV->setInitializer(New); 1952199989Srdivacky } 1953218893Sdim 1954218893Sdim Changed |= ProcessGlobal(GV, GVI); 1955193323Sed } 1956193323Sed return Changed; 1957193323Sed} 1958193323Sed 1959221345Sdim/// FindGlobalCtors - Find the llvm.global_ctors list, verifying that all 1960193323Sed/// initializers have an init priority of 65535. 1961193323SedGlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) { 1962218893Sdim GlobalVariable *GV = M.getGlobalVariable("llvm.global_ctors"); 1963218893Sdim if (GV == 0) return 0; 1964249423Sdim 1965218893Sdim // Verify that the initializer is simple enough for us to handle. We are 1966218893Sdim // only allowed to optimize the initializer if it is unique. 1967218893Sdim if (!GV->hasUniqueInitializer()) return 0; 1968221345Sdim 1969221345Sdim if (isa<ConstantAggregateZero>(GV->getInitializer())) 1970221345Sdim return GV; 1971221345Sdim ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); 1972221345Sdim 1973218893Sdim for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) { 1974221345Sdim if (isa<ConstantAggregateZero>(*i)) 1975221345Sdim continue; 1976221345Sdim ConstantStruct *CS = cast<ConstantStruct>(*i); 1977218893Sdim if (isa<ConstantPointerNull>(CS->getOperand(1))) 1978218893Sdim continue; 1979218893Sdim 1980218893Sdim // Must have a function or null ptr. 1981218893Sdim if (!isa<Function>(CS->getOperand(1))) 1982218893Sdim return 0; 1983218893Sdim 1984218893Sdim // Init priority must be standard. 1985221345Sdim ConstantInt *CI = cast<ConstantInt>(CS->getOperand(0)); 1986221345Sdim if (CI->getZExtValue() != 65535) 1987218893Sdim return 0; 1988218893Sdim } 1989218893Sdim 1990218893Sdim return GV; 1991193323Sed} 1992193323Sed 1993193323Sed/// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand, 1994193323Sed/// return a list of the functions and null terminator as a vector. 1995193323Sedstatic std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) { 1996221345Sdim if (GV->getInitializer()->isNullValue()) 1997221345Sdim return std::vector<Function*>(); 1998193323Sed ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); 1999193323Sed std::vector<Function*> Result; 2000193323Sed Result.reserve(CA->getNumOperands()); 2001193323Sed for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) { 2002193323Sed ConstantStruct *CS = cast<ConstantStruct>(*i); 2003193323Sed Result.push_back(dyn_cast<Function>(CS->getOperand(1))); 2004193323Sed } 2005193323Sed return Result; 2006193323Sed} 2007193323Sed 2008193323Sed/// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the 2009193323Sed/// specified array, returning the new global to use. 2010218893Sdimstatic GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, 2011199481Srdivacky const std::vector<Function*> &Ctors) { 2012193323Sed // If we made a change, reassemble the initializer list. 2013224145Sdim Constant *CSVals[2]; 2014224145Sdim CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()), 65535); 2015224145Sdim CSVals[1] = 0; 2016218893Sdim 2017226633Sdim StructType *StructTy = 2018263508Sdim cast<StructType>(GCL->getType()->getElementType()->getArrayElementType()); 2019224145Sdim 2020193323Sed // Create the new init list. 2021193323Sed std::vector<Constant*> CAList; 2022193323Sed for (unsigned i = 0, e = Ctors.size(); i != e; ++i) { 2023193323Sed if (Ctors[i]) { 2024193323Sed CSVals[1] = Ctors[i]; 2025193323Sed } else { 2026226633Sdim Type *FTy = FunctionType::get(Type::getVoidTy(GCL->getContext()), 2027199481Srdivacky false); 2028226633Sdim PointerType *PFTy = PointerType::getUnqual(FTy); 2029193323Sed CSVals[1] = Constant::getNullValue(PFTy); 2030199481Srdivacky CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()), 2031221345Sdim 0x7fffffff); 2032193323Sed } 2033224145Sdim CAList.push_back(ConstantStruct::get(StructTy, CSVals)); 2034193323Sed } 2035218893Sdim 2036193323Sed // Create the array initializer. 2037218893Sdim Constant *CA = ConstantArray::get(ArrayType::get(StructTy, 2038198090Srdivacky CAList.size()), CAList); 2039218893Sdim 2040193323Sed // If we didn't change the number of elements, don't create a new GV. 2041193323Sed if (CA->getType() == GCL->getInitializer()->getType()) { 2042193323Sed GCL->setInitializer(CA); 2043193323Sed return GCL; 2044193323Sed } 2045218893Sdim 2046193323Sed // Create the new global and insert it next to the existing list. 2047199481Srdivacky GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(), 2048193323Sed GCL->getLinkage(), CA, "", 2049239462Sdim GCL->getThreadLocalMode()); 2050193323Sed GCL->getParent()->getGlobalList().insert(GCL, NGV); 2051193323Sed NGV->takeName(GCL); 2052218893Sdim 2053193323Sed // Nuke the old list, replacing any uses with the new one. 2054193323Sed if (!GCL->use_empty()) { 2055193323Sed Constant *V = NGV; 2056193323Sed if (V->getType() != GCL->getType()) 2057193323Sed V = ConstantExpr::getBitCast(V, GCL->getType()); 2058193323Sed GCL->replaceAllUsesWith(V); 2059193323Sed } 2060193323Sed GCL->eraseFromParent(); 2061218893Sdim 2062193323Sed if (Ctors.size()) 2063193323Sed return NGV; 2064193323Sed else 2065193323Sed return 0; 2066193323Sed} 2067193323Sed 2068193323Sed 2069249423Sdimstatic inline bool 2070218893SdimisSimpleEnoughValueToCommit(Constant *C, 2071234353Sdim SmallPtrSet<Constant*, 8> &SimpleConstants, 2072243830Sdim const DataLayout *TD); 2073218893Sdim 2074218893Sdim 2075218893Sdim/// isSimpleEnoughValueToCommit - Return true if the specified constant can be 2076218893Sdim/// handled by the code generator. We don't want to generate something like: 2077218893Sdim/// void *X = &X/42; 2078218893Sdim/// because the code generator doesn't have a relocation that can handle that. 2079218893Sdim/// 2080218893Sdim/// This function should be called if C was not found (but just got inserted) 2081218893Sdim/// in SimpleConstants to avoid having to rescan the same constants all the 2082218893Sdim/// time. 2083218893Sdimstatic bool isSimpleEnoughValueToCommitHelper(Constant *C, 2084234353Sdim SmallPtrSet<Constant*, 8> &SimpleConstants, 2085243830Sdim const DataLayout *TD) { 2086218893Sdim // Simple integer, undef, constant aggregate zero, global addresses, etc are 2087218893Sdim // all supported. 2088218893Sdim if (C->getNumOperands() == 0 || isa<BlockAddress>(C) || 2089218893Sdim isa<GlobalValue>(C)) 2090218893Sdim return true; 2091249423Sdim 2092218893Sdim // Aggregate values are safe if all their elements are. 2093218893Sdim if (isa<ConstantArray>(C) || isa<ConstantStruct>(C) || 2094218893Sdim isa<ConstantVector>(C)) { 2095218893Sdim for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { 2096218893Sdim Constant *Op = cast<Constant>(C->getOperand(i)); 2097234353Sdim if (!isSimpleEnoughValueToCommit(Op, SimpleConstants, TD)) 2098218893Sdim return false; 2099218893Sdim } 2100218893Sdim return true; 2101218893Sdim } 2102249423Sdim 2103218893Sdim // We don't know exactly what relocations are allowed in constant expressions, 2104218893Sdim // so we allow &global+constantoffset, which is safe and uniformly supported 2105218893Sdim // across targets. 2106218893Sdim ConstantExpr *CE = cast<ConstantExpr>(C); 2107218893Sdim switch (CE->getOpcode()) { 2108218893Sdim case Instruction::BitCast: 2109234353Sdim // Bitcast is fine if the casted value is fine. 2110234353Sdim return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); 2111234353Sdim 2112218893Sdim case Instruction::IntToPtr: 2113218893Sdim case Instruction::PtrToInt: 2114234353Sdim // int <=> ptr is fine if the int type is the same size as the 2115234353Sdim // pointer type. 2116234353Sdim if (!TD || TD->getTypeSizeInBits(CE->getType()) != 2117234353Sdim TD->getTypeSizeInBits(CE->getOperand(0)->getType())) 2118234353Sdim return false; 2119234353Sdim return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); 2120249423Sdim 2121218893Sdim // GEP is fine if it is simple + constant offset. 2122218893Sdim case Instruction::GetElementPtr: 2123218893Sdim for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 2124218893Sdim if (!isa<ConstantInt>(CE->getOperand(i))) 2125218893Sdim return false; 2126234353Sdim return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); 2127249423Sdim 2128218893Sdim case Instruction::Add: 2129218893Sdim // We allow simple+cst. 2130218893Sdim if (!isa<ConstantInt>(CE->getOperand(1))) 2131218893Sdim return false; 2132234353Sdim return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); 2133218893Sdim } 2134218893Sdim return false; 2135218893Sdim} 2136218893Sdim 2137249423Sdimstatic inline bool 2138218893SdimisSimpleEnoughValueToCommit(Constant *C, 2139234353Sdim SmallPtrSet<Constant*, 8> &SimpleConstants, 2140243830Sdim const DataLayout *TD) { 2141218893Sdim // If we already checked this constant, we win. 2142218893Sdim if (!SimpleConstants.insert(C)) return true; 2143218893Sdim // Check the constant. 2144234353Sdim return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, TD); 2145218893Sdim} 2146218893Sdim 2147218893Sdim 2148193323Sed/// isSimpleEnoughPointerToCommit - Return true if this constant is simple 2149218893Sdim/// enough for us to understand. In particular, if it is a cast to anything 2150218893Sdim/// other than from one pointer type to another pointer type, we punt. 2151218893Sdim/// We basically just support direct accesses to globals and GEP's of 2152193323Sed/// globals. This should be kept up to date with CommitValueTo. 2153199481Srdivackystatic bool isSimpleEnoughPointerToCommit(Constant *C) { 2154198090Srdivacky // Conservatively, avoid aggregate types. This is because we don't 2155198090Srdivacky // want to worry about them partially overlapping other stores. 2156198090Srdivacky if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType()) 2157198090Srdivacky return false; 2158198090Srdivacky 2159198090Srdivacky if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) 2160218893Sdim // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or 2161198090Srdivacky // external globals. 2162218893Sdim return GV->hasUniqueInitializer(); 2163198090Srdivacky 2164218893Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 2165193323Sed // Handle a constantexpr gep. 2166193323Sed if (CE->getOpcode() == Instruction::GetElementPtr && 2167198090Srdivacky isa<GlobalVariable>(CE->getOperand(0)) && 2168198090Srdivacky cast<GEPOperator>(CE)->isInBounds()) { 2169193323Sed GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 2170218893Sdim // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or 2171198090Srdivacky // external globals. 2172218893Sdim if (!GV->hasUniqueInitializer()) 2173198090Srdivacky return false; 2174198090Srdivacky 2175198090Srdivacky // The first index must be zero. 2176212904Sdim ConstantInt *CI = dyn_cast<ConstantInt>(*llvm::next(CE->op_begin())); 2177198090Srdivacky if (!CI || !CI->isZero()) return false; 2178198090Srdivacky 2179198090Srdivacky // The remaining indices must be compile-time known integers within the 2180198090Srdivacky // notional bounds of the corresponding static array types. 2181198090Srdivacky if (!CE->isGEPWithNoNotionalOverIndexing()) 2182198090Srdivacky return false; 2183198090Srdivacky 2184198090Srdivacky return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); 2185249423Sdim 2186218893Sdim // A constantexpr bitcast from a pointer to another pointer is a no-op, 2187218893Sdim // and we know how to evaluate it by moving the bitcast from the pointer 2188218893Sdim // operand to the value operand. 2189218893Sdim } else if (CE->getOpcode() == Instruction::BitCast && 2190218893Sdim isa<GlobalVariable>(CE->getOperand(0))) { 2191218893Sdim // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or 2192218893Sdim // external globals. 2193218893Sdim return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer(); 2194193323Sed } 2195218893Sdim } 2196249423Sdim 2197193323Sed return false; 2198193323Sed} 2199193323Sed 2200193323Sed/// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global 2201193323Sed/// initializer. This returns 'Init' modified to reflect 'Val' stored into it. 2202193323Sed/// At this point, the GEP operands of Addr [0, OpNo) have been stepped into. 2203193323Sedstatic Constant *EvaluateStoreInto(Constant *Init, Constant *Val, 2204199481Srdivacky ConstantExpr *Addr, unsigned OpNo) { 2205193323Sed // Base case of the recursion. 2206193323Sed if (OpNo == Addr->getNumOperands()) { 2207193323Sed assert(Val->getType() == Init->getType() && "Type mismatch!"); 2208193323Sed return Val; 2209193323Sed } 2210218893Sdim 2211234353Sdim SmallVector<Constant*, 32> Elts; 2212226633Sdim if (StructType *STy = dyn_cast<StructType>(Init->getType())) { 2213193323Sed // Break up the constant into its elements. 2214234353Sdim for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 2215234353Sdim Elts.push_back(Init->getAggregateElement(i)); 2216218893Sdim 2217193323Sed // Replace the element that we are supposed to. 2218193323Sed ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo)); 2219193323Sed unsigned Idx = CU->getZExtValue(); 2220193323Sed assert(Idx < STy->getNumElements() && "Struct index out of range!"); 2221199481Srdivacky Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1); 2222218893Sdim 2223193323Sed // Return the modified struct. 2224224145Sdim return ConstantStruct::get(STy, Elts); 2225224145Sdim } 2226249423Sdim 2227224145Sdim ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo)); 2228226633Sdim SequentialType *InitTy = cast<SequentialType>(Init->getType()); 2229193323Sed 2230224145Sdim uint64_t NumElts; 2231226633Sdim if (ArrayType *ATy = dyn_cast<ArrayType>(InitTy)) 2232224145Sdim NumElts = ATy->getNumElements(); 2233224145Sdim else 2234234353Sdim NumElts = InitTy->getVectorNumElements(); 2235218893Sdim 2236224145Sdim // Break up the array into elements. 2237234353Sdim for (uint64_t i = 0, e = NumElts; i != e; ++i) 2238234353Sdim Elts.push_back(Init->getAggregateElement(i)); 2239218893Sdim 2240224145Sdim assert(CI->getZExtValue() < NumElts); 2241224145Sdim Elts[CI->getZExtValue()] = 2242224145Sdim EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1); 2243218893Sdim 2244224145Sdim if (Init->getType()->isArrayTy()) 2245224145Sdim return ConstantArray::get(cast<ArrayType>(InitTy), Elts); 2246224145Sdim return ConstantVector::get(Elts); 2247193323Sed} 2248193323Sed 2249193323Sed/// CommitValueTo - We have decided that Addr (which satisfies the predicate 2250193323Sed/// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen. 2251199481Srdivackystatic void CommitValueTo(Constant *Val, Constant *Addr) { 2252193323Sed if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) { 2253193323Sed assert(GV->hasInitializer()); 2254193323Sed GV->setInitializer(Val); 2255193323Sed return; 2256193323Sed } 2257202375Srdivacky 2258193323Sed ConstantExpr *CE = cast<ConstantExpr>(Addr); 2259193323Sed GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 2260202375Srdivacky GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2)); 2261193323Sed} 2262193323Sed 2263234353Sdimnamespace { 2264234353Sdim 2265234353Sdim/// Evaluator - This class evaluates LLVM IR, producing the Constant 2266234353Sdim/// representing each SSA instruction. Changes to global variables are stored 2267234353Sdim/// in a mapping that can be iterated over after the evaluation is complete. 2268234353Sdim/// Once an evaluation call fails, the evaluation object should not be reused. 2269234353Sdimclass Evaluator { 2270234353Sdimpublic: 2271243830Sdim Evaluator(const DataLayout *TD, const TargetLibraryInfo *TLI) 2272234353Sdim : TD(TD), TLI(TLI) { 2273234353Sdim ValueStack.push_back(new DenseMap<Value*, Constant*>); 2274234353Sdim } 2275234353Sdim 2276234353Sdim ~Evaluator() { 2277234353Sdim DeleteContainerPointers(ValueStack); 2278234353Sdim while (!AllocaTmps.empty()) { 2279234353Sdim GlobalVariable *Tmp = AllocaTmps.back(); 2280234353Sdim AllocaTmps.pop_back(); 2281234353Sdim 2282234353Sdim // If there are still users of the alloca, the program is doing something 2283234353Sdim // silly, e.g. storing the address of the alloca somewhere and using it 2284234353Sdim // later. Since this is undefined, we'll just make it be null. 2285234353Sdim if (!Tmp->use_empty()) 2286234353Sdim Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); 2287234353Sdim delete Tmp; 2288234353Sdim } 2289234353Sdim } 2290234353Sdim 2291234353Sdim /// EvaluateFunction - Evaluate a call to function F, returning true if 2292234353Sdim /// successful, false if we can't evaluate it. ActualArgs contains the formal 2293234353Sdim /// arguments for the function. 2294234353Sdim bool EvaluateFunction(Function *F, Constant *&RetVal, 2295234353Sdim const SmallVectorImpl<Constant*> &ActualArgs); 2296234353Sdim 2297234353Sdim /// EvaluateBlock - Evaluate all instructions in block BB, returning true if 2298234353Sdim /// successful, false if we can't evaluate it. NewBB returns the next BB that 2299234353Sdim /// control flows into, or null upon return. 2300234353Sdim bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB); 2301234353Sdim 2302234353Sdim Constant *getVal(Value *V) { 2303234353Sdim if (Constant *CV = dyn_cast<Constant>(V)) return CV; 2304234353Sdim Constant *R = ValueStack.back()->lookup(V); 2305234353Sdim assert(R && "Reference to an uncomputed value!"); 2306234353Sdim return R; 2307234353Sdim } 2308234353Sdim 2309234353Sdim void setVal(Value *V, Constant *C) { 2310234353Sdim ValueStack.back()->operator[](V) = C; 2311234353Sdim } 2312234353Sdim 2313234353Sdim const DenseMap<Constant*, Constant*> &getMutatedMemory() const { 2314234353Sdim return MutatedMemory; 2315234353Sdim } 2316234353Sdim 2317234353Sdim const SmallPtrSet<GlobalVariable*, 8> &getInvariants() const { 2318234353Sdim return Invariants; 2319234353Sdim } 2320234353Sdim 2321234353Sdimprivate: 2322234353Sdim Constant *ComputeLoadResult(Constant *P); 2323234353Sdim 2324234353Sdim /// ValueStack - As we compute SSA register values, we store their contents 2325234353Sdim /// here. The back of the vector contains the current function and the stack 2326234353Sdim /// contains the values in the calling frames. 2327234353Sdim SmallVector<DenseMap<Value*, Constant*>*, 4> ValueStack; 2328234353Sdim 2329234353Sdim /// CallStack - This is used to detect recursion. In pathological situations 2330234353Sdim /// we could hit exponential behavior, but at least there is nothing 2331234353Sdim /// unbounded. 2332234353Sdim SmallVector<Function*, 4> CallStack; 2333234353Sdim 2334234353Sdim /// MutatedMemory - For each store we execute, we update this map. Loads 2335234353Sdim /// check this to get the most up-to-date value. If evaluation is successful, 2336234353Sdim /// this state is committed to the process. 2337234353Sdim DenseMap<Constant*, Constant*> MutatedMemory; 2338234353Sdim 2339234353Sdim /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable 2340234353Sdim /// to represent its body. This vector is needed so we can delete the 2341234353Sdim /// temporary globals when we are done. 2342234353Sdim SmallVector<GlobalVariable*, 32> AllocaTmps; 2343234353Sdim 2344234353Sdim /// Invariants - These global variables have been marked invariant by the 2345234353Sdim /// static constructor. 2346234353Sdim SmallPtrSet<GlobalVariable*, 8> Invariants; 2347234353Sdim 2348234353Sdim /// SimpleConstants - These are constants we have checked and know to be 2349234353Sdim /// simple enough to live in a static initializer of a global. 2350234353Sdim SmallPtrSet<Constant*, 8> SimpleConstants; 2351234353Sdim 2352243830Sdim const DataLayout *TD; 2353234353Sdim const TargetLibraryInfo *TLI; 2354234353Sdim}; 2355234353Sdim 2356234353Sdim} // anonymous namespace 2357234353Sdim 2358193323Sed/// ComputeLoadResult - Return the value that would be computed by a load from 2359193323Sed/// P after the stores reflected by 'memory' have been performed. If we can't 2360193323Sed/// decide, return null. 2361234353SdimConstant *Evaluator::ComputeLoadResult(Constant *P) { 2362193323Sed // If this memory location has been recently stored, use the stored value: it 2363193323Sed // is the most up-to-date. 2364234353Sdim DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P); 2365234353Sdim if (I != MutatedMemory.end()) return I->second; 2366218893Sdim 2367193323Sed // Access it. 2368193323Sed if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { 2369198090Srdivacky if (GV->hasDefinitiveInitializer()) 2370193323Sed return GV->getInitializer(); 2371193323Sed return 0; 2372193323Sed } 2373218893Sdim 2374193323Sed // Handle a constantexpr getelementptr. 2375193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) 2376193323Sed if (CE->getOpcode() == Instruction::GetElementPtr && 2377193323Sed isa<GlobalVariable>(CE->getOperand(0))) { 2378193323Sed GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); 2379198090Srdivacky if (GV->hasDefinitiveInitializer()) 2380193323Sed return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); 2381193323Sed } 2382193323Sed 2383193323Sed return 0; // don't know how to evaluate. 2384193323Sed} 2385193323Sed 2386234353Sdim/// EvaluateBlock - Evaluate all instructions in block BB, returning true if 2387234353Sdim/// successful, false if we can't evaluate it. NewBB returns the next BB that 2388234353Sdim/// control flows into, or null upon return. 2389234353Sdimbool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, 2390234353Sdim BasicBlock *&NextBB) { 2391193323Sed // This is the main evaluation loop. 2392193323Sed while (1) { 2393193323Sed Constant *InstResult = 0; 2394218893Sdim 2395249423Sdim DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n"); 2396249423Sdim 2397193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) { 2398249423Sdim if (!SI->isSimple()) { 2399249423Sdim DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n"); 2400249423Sdim return false; // no volatile/atomic accesses. 2401249423Sdim } 2402234353Sdim Constant *Ptr = getVal(SI->getOperand(1)); 2403249423Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { 2404249423Sdim DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr); 2405234353Sdim Ptr = ConstantFoldConstantExpression(CE, TD, TLI); 2406249423Sdim DEBUG(dbgs() << "; To: " << *Ptr << "\n"); 2407249423Sdim } 2408249423Sdim if (!isSimpleEnoughPointerToCommit(Ptr)) { 2409193323Sed // If this is too complex for us to commit, reject it. 2410249423Sdim DEBUG(dbgs() << "Pointer is too complex for us to evaluate store."); 2411193323Sed return false; 2412249423Sdim } 2413249423Sdim 2414234353Sdim Constant *Val = getVal(SI->getOperand(0)); 2415218893Sdim 2416218893Sdim // If this might be too difficult for the backend to handle (e.g. the addr 2417218893Sdim // of one global variable divided by another) then we can't commit it. 2418249423Sdim if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, TD)) { 2419249423Sdim DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val 2420249423Sdim << "\n"); 2421218893Sdim return false; 2422249423Sdim } 2423249423Sdim 2424249423Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { 2425218893Sdim if (CE->getOpcode() == Instruction::BitCast) { 2426249423Sdim DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n"); 2427218893Sdim // If we're evaluating a store through a bitcast, then we need 2428218893Sdim // to pull the bitcast off the pointer type and push it onto the 2429218893Sdim // stored value. 2430218893Sdim Ptr = CE->getOperand(0); 2431249423Sdim 2432234353Sdim Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType(); 2433249423Sdim 2434218893Sdim // In order to push the bitcast onto the stored value, a bitcast 2435218893Sdim // from NewTy to Val's type must be legal. If it's not, we can try 2436218893Sdim // introspecting NewTy to find a legal conversion. 2437218893Sdim while (!Val->getType()->canLosslesslyBitCastTo(NewTy)) { 2438218893Sdim // If NewTy is a struct, we can convert the pointer to the struct 2439218893Sdim // into a pointer to its first member. 2440218893Sdim // FIXME: This could be extended to support arrays as well. 2441226633Sdim if (StructType *STy = dyn_cast<StructType>(NewTy)) { 2442218893Sdim NewTy = STy->getTypeAtIndex(0U); 2443218893Sdim 2444234353Sdim IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32); 2445218893Sdim Constant *IdxZero = ConstantInt::get(IdxTy, 0, false); 2446218893Sdim Constant * const IdxList[] = {IdxZero, IdxZero}; 2447218893Sdim 2448226633Sdim Ptr = ConstantExpr::getGetElementPtr(Ptr, IdxList); 2449234353Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) 2450234353Sdim Ptr = ConstantFoldConstantExpression(CE, TD, TLI); 2451234353Sdim 2452218893Sdim // If we can't improve the situation by introspecting NewTy, 2453218893Sdim // we have to give up. 2454218893Sdim } else { 2455249423Sdim DEBUG(dbgs() << "Failed to bitcast constant ptr, can not " 2456249423Sdim "evaluate.\n"); 2457234353Sdim return false; 2458218893Sdim } 2459218893Sdim } 2460249423Sdim 2461218893Sdim // If we found compatible types, go ahead and push the bitcast 2462218893Sdim // onto the stored value. 2463218893Sdim Val = ConstantExpr::getBitCast(Val, NewTy); 2464249423Sdim 2465249423Sdim DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n"); 2466218893Sdim } 2467249423Sdim } 2468249423Sdim 2469193323Sed MutatedMemory[Ptr] = Val; 2470193323Sed } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) { 2471193323Sed InstResult = ConstantExpr::get(BO->getOpcode(), 2472234353Sdim getVal(BO->getOperand(0)), 2473234353Sdim getVal(BO->getOperand(1))); 2474249423Sdim DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult 2475249423Sdim << "\n"); 2476193323Sed } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) { 2477193323Sed InstResult = ConstantExpr::getCompare(CI->getPredicate(), 2478234353Sdim getVal(CI->getOperand(0)), 2479234353Sdim getVal(CI->getOperand(1))); 2480249423Sdim DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult 2481249423Sdim << "\n"); 2482193323Sed } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) { 2483193323Sed InstResult = ConstantExpr::getCast(CI->getOpcode(), 2484234353Sdim getVal(CI->getOperand(0)), 2485193323Sed CI->getType()); 2486249423Sdim DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult 2487249423Sdim << "\n"); 2488193323Sed } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) { 2489234353Sdim InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)), 2490234353Sdim getVal(SI->getOperand(1)), 2491234353Sdim getVal(SI->getOperand(2))); 2492249423Sdim DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult 2493249423Sdim << "\n"); 2494193323Sed } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) { 2495234353Sdim Constant *P = getVal(GEP->getOperand(0)); 2496193323Sed SmallVector<Constant*, 8> GEPOps; 2497193323Sed for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); 2498193323Sed i != e; ++i) 2499234353Sdim GEPOps.push_back(getVal(*i)); 2500226633Sdim InstResult = 2501226633Sdim ConstantExpr::getGetElementPtr(P, GEPOps, 2502226633Sdim cast<GEPOperator>(GEP)->isInBounds()); 2503249423Sdim DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult 2504249423Sdim << "\n"); 2505193323Sed } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) { 2506249423Sdim 2507249423Sdim if (!LI->isSimple()) { 2508249423Sdim DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n"); 2509249423Sdim return false; // no volatile/atomic accesses. 2510249423Sdim } 2511249423Sdim 2512234353Sdim Constant *Ptr = getVal(LI->getOperand(0)); 2513249423Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { 2514234353Sdim Ptr = ConstantFoldConstantExpression(CE, TD, TLI); 2515249423Sdim DEBUG(dbgs() << "Found a constant pointer expression, constant " 2516249423Sdim "folding: " << *Ptr << "\n"); 2517249423Sdim } 2518234353Sdim InstResult = ComputeLoadResult(Ptr); 2519249423Sdim if (InstResult == 0) { 2520249423Sdim DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load." 2521249423Sdim "\n"); 2522249423Sdim return false; // Could not evaluate load. 2523249423Sdim } 2524249423Sdim 2525249423Sdim DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n"); 2526193323Sed } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) { 2527249423Sdim if (AI->isArrayAllocation()) { 2528249423Sdim DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n"); 2529249423Sdim return false; // Cannot handle array allocs. 2530249423Sdim } 2531226633Sdim Type *Ty = AI->getType()->getElementType(); 2532199481Srdivacky AllocaTmps.push_back(new GlobalVariable(Ty, false, 2533193323Sed GlobalValue::InternalLinkage, 2534193323Sed UndefValue::get(Ty), 2535193323Sed AI->getName())); 2536218893Sdim InstResult = AllocaTmps.back(); 2537249423Sdim DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n"); 2538234353Sdim } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) { 2539234353Sdim CallSite CS(CurInst); 2540193323Sed 2541193323Sed // Debug info can safely be ignored here. 2542234353Sdim if (isa<DbgInfoIntrinsic>(CS.getInstruction())) { 2543249423Sdim DEBUG(dbgs() << "Ignoring debug info.\n"); 2544193323Sed ++CurInst; 2545193323Sed continue; 2546193323Sed } 2547193323Sed 2548193323Sed // Cannot handle inline asm. 2549249423Sdim if (isa<InlineAsm>(CS.getCalledValue())) { 2550249423Sdim DEBUG(dbgs() << "Found inline asm, can not evaluate.\n"); 2551249423Sdim return false; 2552249423Sdim } 2553193323Sed 2554234353Sdim if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) { 2555234353Sdim if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) { 2556249423Sdim if (MSI->isVolatile()) { 2557249423Sdim DEBUG(dbgs() << "Can not optimize a volatile memset " << 2558249423Sdim "intrinsic.\n"); 2559249423Sdim return false; 2560249423Sdim } 2561234353Sdim Constant *Ptr = getVal(MSI->getDest()); 2562234353Sdim Constant *Val = getVal(MSI->getValue()); 2563234353Sdim Constant *DestVal = ComputeLoadResult(getVal(Ptr)); 2564234353Sdim if (Val->isNullValue() && DestVal && DestVal->isNullValue()) { 2565234353Sdim // This memset is a no-op. 2566249423Sdim DEBUG(dbgs() << "Ignoring no-op memset.\n"); 2567234353Sdim ++CurInst; 2568234353Sdim continue; 2569234353Sdim } 2570234353Sdim } 2571234353Sdim 2572234353Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start || 2573234353Sdim II->getIntrinsicID() == Intrinsic::lifetime_end) { 2574249423Sdim DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n"); 2575223017Sdim ++CurInst; 2576223017Sdim continue; 2577223017Sdim } 2578234353Sdim 2579234353Sdim if (II->getIntrinsicID() == Intrinsic::invariant_start) { 2580234353Sdim // We don't insert an entry into Values, as it doesn't have a 2581234353Sdim // meaningful return value. 2582249423Sdim if (!II->use_empty()) { 2583249423Sdim DEBUG(dbgs() << "Found unused invariant_start. Cant evaluate.\n"); 2584234353Sdim return false; 2585249423Sdim } 2586234353Sdim ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0)); 2587234353Sdim Value *PtrArg = getVal(II->getArgOperand(1)); 2588234353Sdim Value *Ptr = PtrArg->stripPointerCasts(); 2589234353Sdim if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { 2590234353Sdim Type *ElemTy = cast<PointerType>(GV->getType())->getElementType(); 2591263508Sdim if (TD && !Size->isAllOnesValue() && 2592234353Sdim Size->getValue().getLimitedValue() >= 2593249423Sdim TD->getTypeStoreSize(ElemTy)) { 2594234353Sdim Invariants.insert(GV); 2595249423Sdim DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV 2596249423Sdim << "\n"); 2597249423Sdim } else { 2598249423Sdim DEBUG(dbgs() << "Found a global var, but can not treat it as an " 2599249423Sdim "invariant.\n"); 2600249423Sdim } 2601234353Sdim } 2602234353Sdim // Continue even if we do nothing. 2603234353Sdim ++CurInst; 2604234353Sdim continue; 2605234353Sdim } 2606249423Sdim 2607249423Sdim DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n"); 2608223017Sdim return false; 2609223017Sdim } 2610223017Sdim 2611193323Sed // Resolve function pointers. 2612234353Sdim Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue())); 2613249423Sdim if (!Callee || Callee->mayBeOverridden()) { 2614249423Sdim DEBUG(dbgs() << "Can not resolve function pointer.\n"); 2615234353Sdim return false; // Cannot resolve. 2616249423Sdim } 2617193323Sed 2618198090Srdivacky SmallVector<Constant*, 8> Formals; 2619234353Sdim for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); i != e; ++i) 2620234353Sdim Formals.push_back(getVal(*i)); 2621198090Srdivacky 2622193323Sed if (Callee->isDeclaration()) { 2623193323Sed // If this is a function we can constant fold, do it. 2624234353Sdim if (Constant *C = ConstantFoldCall(Callee, Formals, TLI)) { 2625193323Sed InstResult = C; 2626249423Sdim DEBUG(dbgs() << "Constant folded function call. Result: " << 2627249423Sdim *InstResult << "\n"); 2628193323Sed } else { 2629249423Sdim DEBUG(dbgs() << "Can not constant fold function call.\n"); 2630193323Sed return false; 2631193323Sed } 2632193323Sed } else { 2633249423Sdim if (Callee->getFunctionType()->isVarArg()) { 2634249423Sdim DEBUG(dbgs() << "Can not constant fold vararg function call.\n"); 2635193323Sed return false; 2636249423Sdim } 2637218893Sdim 2638249423Sdim Constant *RetVal = 0; 2639193323Sed // Execute the call, if successful, use the return value. 2640234353Sdim ValueStack.push_back(new DenseMap<Value*, Constant*>); 2641249423Sdim if (!EvaluateFunction(Callee, RetVal, Formals)) { 2642249423Sdim DEBUG(dbgs() << "Failed to evaluate function.\n"); 2643193323Sed return false; 2644249423Sdim } 2645234353Sdim delete ValueStack.pop_back_val(); 2646193323Sed InstResult = RetVal; 2647249423Sdim 2648249423Sdim if (InstResult != NULL) { 2649249423Sdim DEBUG(dbgs() << "Successfully evaluated function. Result: " << 2650249423Sdim InstResult << "\n\n"); 2651249423Sdim } else { 2652249423Sdim DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n"); 2653249423Sdim } 2654193323Sed } 2655193323Sed } else if (isa<TerminatorInst>(CurInst)) { 2656249423Sdim DEBUG(dbgs() << "Found a terminator instruction.\n"); 2657249423Sdim 2658193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) { 2659193323Sed if (BI->isUnconditional()) { 2660234353Sdim NextBB = BI->getSuccessor(0); 2661193323Sed } else { 2662193323Sed ConstantInt *Cond = 2663234353Sdim dyn_cast<ConstantInt>(getVal(BI->getCondition())); 2664193323Sed if (!Cond) return false; // Cannot determine. 2665193323Sed 2666234353Sdim NextBB = BI->getSuccessor(!Cond->getZExtValue()); 2667193323Sed } 2668193323Sed } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) { 2669193323Sed ConstantInt *Val = 2670234353Sdim dyn_cast<ConstantInt>(getVal(SI->getCondition())); 2671193323Sed if (!Val) return false; // Cannot determine. 2672234353Sdim NextBB = SI->findCaseValue(Val).getCaseSuccessor(); 2673198892Srdivacky } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) { 2674234353Sdim Value *Val = getVal(IBI->getAddress())->stripPointerCasts(); 2675198892Srdivacky if (BlockAddress *BA = dyn_cast<BlockAddress>(Val)) 2676234353Sdim NextBB = BA->getBasicBlock(); 2677198892Srdivacky else 2678198892Srdivacky return false; // Cannot determine. 2679234353Sdim } else if (isa<ReturnInst>(CurInst)) { 2680234353Sdim NextBB = 0; 2681193323Sed } else { 2682226633Sdim // invoke, unwind, resume, unreachable. 2683249423Sdim DEBUG(dbgs() << "Can not handle terminator."); 2684193323Sed return false; // Cannot handle this terminator. 2685193323Sed } 2686218893Sdim 2687234353Sdim // We succeeded at evaluating this block! 2688249423Sdim DEBUG(dbgs() << "Successfully evaluated block.\n"); 2689234353Sdim return true; 2690193323Sed } else { 2691193323Sed // Did not know how to evaluate this! 2692249423Sdim DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction." 2693249423Sdim "\n"); 2694193323Sed return false; 2695193323Sed } 2696218893Sdim 2697218893Sdim if (!CurInst->use_empty()) { 2698218893Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(InstResult)) 2699234353Sdim InstResult = ConstantFoldConstantExpression(CE, TD, TLI); 2700249423Sdim 2701234353Sdim setVal(CurInst, InstResult); 2702218893Sdim } 2703218893Sdim 2704234353Sdim // If we just processed an invoke, we finished evaluating the block. 2705234353Sdim if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) { 2706234353Sdim NextBB = II->getNormalDest(); 2707249423Sdim DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n"); 2708234353Sdim return true; 2709234353Sdim } 2710234353Sdim 2711193323Sed // Advance program counter. 2712193323Sed ++CurInst; 2713193323Sed } 2714193323Sed} 2715193323Sed 2716234353Sdim/// EvaluateFunction - Evaluate a call to function F, returning true if 2717234353Sdim/// successful, false if we can't evaluate it. ActualArgs contains the formal 2718234353Sdim/// arguments for the function. 2719234353Sdimbool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal, 2720234353Sdim const SmallVectorImpl<Constant*> &ActualArgs) { 2721234353Sdim // Check to see if this function is already executing (recursion). If so, 2722234353Sdim // bail out. TODO: we might want to accept limited recursion. 2723234353Sdim if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end()) 2724234353Sdim return false; 2725193323Sed 2726234353Sdim CallStack.push_back(F); 2727218893Sdim 2728234353Sdim // Initialize arguments to the incoming values specified. 2729234353Sdim unsigned ArgNo = 0; 2730234353Sdim for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; 2731234353Sdim ++AI, ++ArgNo) 2732234353Sdim setVal(AI, ActualArgs[ArgNo]); 2733193323Sed 2734234353Sdim // ExecutedBlocks - We only handle non-looping, non-recursive code. As such, 2735234353Sdim // we can only evaluate any one basic block at most once. This set keeps 2736234353Sdim // track of what we have executed so we can detect recursive cases etc. 2737234353Sdim SmallPtrSet<BasicBlock*, 32> ExecutedBlocks; 2738234353Sdim 2739234353Sdim // CurBB - The current basic block we're evaluating. 2740234353Sdim BasicBlock *CurBB = F->begin(); 2741234353Sdim 2742234353Sdim BasicBlock::iterator CurInst = CurBB->begin(); 2743234353Sdim 2744234353Sdim while (1) { 2745234353Sdim BasicBlock *NextBB = 0; // Initialized to avoid compiler warnings. 2746249423Sdim DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n"); 2747249423Sdim 2748234353Sdim if (!EvaluateBlock(CurInst, NextBB)) 2749234353Sdim return false; 2750234353Sdim 2751234353Sdim if (NextBB == 0) { 2752234353Sdim // Successfully running until there's no next block means that we found 2753234353Sdim // the return. Fill it the return value and pop the call stack. 2754234353Sdim ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator()); 2755234353Sdim if (RI->getNumOperands()) 2756234353Sdim RetVal = getVal(RI->getOperand(0)); 2757234353Sdim CallStack.pop_back(); 2758234353Sdim return true; 2759234353Sdim } 2760234353Sdim 2761234353Sdim // Okay, we succeeded in evaluating this control flow. See if we have 2762234353Sdim // executed the new block before. If so, we have a looping function, 2763234353Sdim // which we cannot evaluate in reasonable time. 2764234353Sdim if (!ExecutedBlocks.insert(NextBB)) 2765234353Sdim return false; // looped! 2766234353Sdim 2767234353Sdim // Okay, we have never been in this block before. Check to see if there 2768234353Sdim // are any PHI nodes. If so, evaluate them with information about where 2769234353Sdim // we came from. 2770234353Sdim PHINode *PN = 0; 2771234353Sdim for (CurInst = NextBB->begin(); 2772234353Sdim (PN = dyn_cast<PHINode>(CurInst)); ++CurInst) 2773234353Sdim setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB))); 2774234353Sdim 2775234353Sdim // Advance to the next block. 2776234353Sdim CurBB = NextBB; 2777234353Sdim } 2778234353Sdim} 2779234353Sdim 2780234353Sdim/// EvaluateStaticConstructor - Evaluate static constructors in the function, if 2781234353Sdim/// we can. Return true if we can, false otherwise. 2782243830Sdimstatic bool EvaluateStaticConstructor(Function *F, const DataLayout *TD, 2783234353Sdim const TargetLibraryInfo *TLI) { 2784193323Sed // Call the function. 2785234353Sdim Evaluator Eval(TD, TLI); 2786193323Sed Constant *RetValDummy; 2787234353Sdim bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy, 2788234353Sdim SmallVector<Constant*, 0>()); 2789249423Sdim 2790193323Sed if (EvalSuccess) { 2791193323Sed // We succeeded at evaluation: commit the result. 2792202375Srdivacky DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" 2793234353Sdim << F->getName() << "' to " << Eval.getMutatedMemory().size() 2794198090Srdivacky << " stores.\n"); 2795234353Sdim for (DenseMap<Constant*, Constant*>::const_iterator I = 2796234353Sdim Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end(); 2797239462Sdim I != E; ++I) 2798199481Srdivacky CommitValueTo(I->second, I->first); 2799234353Sdim for (SmallPtrSet<GlobalVariable*, 8>::const_iterator I = 2800234353Sdim Eval.getInvariants().begin(), E = Eval.getInvariants().end(); 2801234353Sdim I != E; ++I) 2802234353Sdim (*I)->setConstant(true); 2803193323Sed } 2804218893Sdim 2805193323Sed return EvalSuccess; 2806193323Sed} 2807193323Sed 2808193323Sed/// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible. 2809193323Sed/// Return true if anything changed. 2810193323Sedbool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) { 2811193323Sed std::vector<Function*> Ctors = ParseGlobalCtors(GCL); 2812193323Sed bool MadeChange = false; 2813193323Sed if (Ctors.empty()) return false; 2814218893Sdim 2815193323Sed // Loop over global ctors, optimizing them when we can. 2816193323Sed for (unsigned i = 0; i != Ctors.size(); ++i) { 2817193323Sed Function *F = Ctors[i]; 2818193323Sed // Found a null terminator in the middle of the list, prune off the rest of 2819193323Sed // the list. 2820193323Sed if (F == 0) { 2821193323Sed if (i != Ctors.size()-1) { 2822193323Sed Ctors.resize(i+1); 2823193323Sed MadeChange = true; 2824193323Sed } 2825193323Sed break; 2826193323Sed } 2827249423Sdim DEBUG(dbgs() << "Optimizing Global Constructor: " << *F << "\n"); 2828218893Sdim 2829193323Sed // We cannot simplify external ctor functions. 2830193323Sed if (F->empty()) continue; 2831218893Sdim 2832193323Sed // If we can evaluate the ctor at compile time, do. 2833234353Sdim if (EvaluateStaticConstructor(F, TD, TLI)) { 2834193323Sed Ctors.erase(Ctors.begin()+i); 2835193323Sed MadeChange = true; 2836193323Sed --i; 2837193323Sed ++NumCtorsEvaluated; 2838193323Sed continue; 2839193323Sed } 2840193323Sed } 2841218893Sdim 2842193323Sed if (!MadeChange) return false; 2843218893Sdim 2844199481Srdivacky GCL = InstallGlobalCtors(GCL, Ctors); 2845193323Sed return true; 2846193323Sed} 2847193323Sed 2848263508Sdimstatic int compareNames(Constant *const *A, Constant *const *B) { 2849263508Sdim return (*A)->getName().compare((*B)->getName()); 2850263508Sdim} 2851251662Sdim 2852263508Sdimstatic void setUsedInitializer(GlobalVariable &V, 2853263508Sdim SmallPtrSet<GlobalValue *, 8> Init) { 2854263508Sdim if (Init.empty()) { 2855263508Sdim V.eraseFromParent(); 2856263508Sdim return; 2857263508Sdim } 2858251662Sdim 2859263508Sdim SmallVector<llvm::Constant *, 8> UsedArray; 2860263508Sdim PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext()); 2861263508Sdim 2862263508Sdim for (SmallPtrSet<GlobalValue *, 8>::iterator I = Init.begin(), E = Init.end(); 2863263508Sdim I != E; ++I) { 2864263508Sdim Constant *Cast = llvm::ConstantExpr::getBitCast(*I, Int8PtrTy); 2865263508Sdim UsedArray.push_back(Cast); 2866251662Sdim } 2867263508Sdim // Sort to get deterministic order. 2868263508Sdim array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames); 2869263508Sdim ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size()); 2870263508Sdim 2871263508Sdim Module *M = V.getParent(); 2872263508Sdim V.removeFromParent(); 2873263508Sdim GlobalVariable *NV = 2874263508Sdim new GlobalVariable(*M, ATy, false, llvm::GlobalValue::AppendingLinkage, 2875263508Sdim llvm::ConstantArray::get(ATy, UsedArray), ""); 2876263508Sdim NV->takeName(&V); 2877263508Sdim NV->setSection("llvm.metadata"); 2878263508Sdim delete &V; 2879251662Sdim} 2880251662Sdim 2881263508Sdimnamespace { 2882263508Sdim/// \brief An easy to access representation of llvm.used and llvm.compiler.used. 2883263508Sdimclass LLVMUsed { 2884263508Sdim SmallPtrSet<GlobalValue *, 8> Used; 2885263508Sdim SmallPtrSet<GlobalValue *, 8> CompilerUsed; 2886263508Sdim GlobalVariable *UsedV; 2887263508Sdim GlobalVariable *CompilerUsedV; 2888251662Sdim 2889263508Sdimpublic: 2890263508Sdim LLVMUsed(Module &M) { 2891263508Sdim UsedV = collectUsedGlobalVariables(M, Used, false); 2892263508Sdim CompilerUsedV = collectUsedGlobalVariables(M, CompilerUsed, true); 2893263508Sdim } 2894263508Sdim typedef SmallPtrSet<GlobalValue *, 8>::iterator iterator; 2895263508Sdim iterator usedBegin() { return Used.begin(); } 2896263508Sdim iterator usedEnd() { return Used.end(); } 2897263508Sdim iterator compilerUsedBegin() { return CompilerUsed.begin(); } 2898263508Sdim iterator compilerUsedEnd() { return CompilerUsed.end(); } 2899263508Sdim bool usedCount(GlobalValue *GV) const { return Used.count(GV); } 2900263508Sdim bool compilerUsedCount(GlobalValue *GV) const { 2901263508Sdim return CompilerUsed.count(GV); 2902263508Sdim } 2903263508Sdim bool usedErase(GlobalValue *GV) { return Used.erase(GV); } 2904263508Sdim bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); } 2905263508Sdim bool usedInsert(GlobalValue *GV) { return Used.insert(GV); } 2906263508Sdim bool compilerUsedInsert(GlobalValue *GV) { return CompilerUsed.insert(GV); } 2907251662Sdim 2908263508Sdim void syncVariablesAndSets() { 2909263508Sdim if (UsedV) 2910263508Sdim setUsedInitializer(*UsedV, Used); 2911263508Sdim if (CompilerUsedV) 2912263508Sdim setUsedInitializer(*CompilerUsedV, CompilerUsed); 2913251662Sdim } 2914263508Sdim}; 2915263508Sdim} 2916251662Sdim 2917263508Sdimstatic bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) { 2918263508Sdim if (GA.use_empty()) // No use at all. 2919263508Sdim return false; 2920251662Sdim 2921263508Sdim assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) && 2922263508Sdim "We should have removed the duplicated " 2923263508Sdim "element from llvm.compiler.used"); 2924263508Sdim if (!GA.hasOneUse()) 2925263508Sdim // Strictly more than one use. So at least one is not in llvm.used and 2926263508Sdim // llvm.compiler.used. 2927263508Sdim return true; 2928263508Sdim 2929263508Sdim // Exactly one use. Check if it is in llvm.used or llvm.compiler.used. 2930263508Sdim return !U.usedCount(&GA) && !U.compilerUsedCount(&GA); 2931251662Sdim} 2932251662Sdim 2933263508Sdimstatic bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue &V, 2934263508Sdim const LLVMUsed &U) { 2935263508Sdim unsigned N = 2; 2936263508Sdim assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) && 2937263508Sdim "We should have removed the duplicated " 2938263508Sdim "element from llvm.compiler.used"); 2939263508Sdim if (U.usedCount(&V) || U.compilerUsedCount(&V)) 2940263508Sdim ++N; 2941263508Sdim return V.hasNUsesOrMore(N); 2942263508Sdim} 2943251662Sdim 2944263508Sdimstatic bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) { 2945263508Sdim if (!GA.hasLocalLinkage()) 2946263508Sdim return true; 2947251662Sdim 2948263508Sdim return U.usedCount(&GA) || U.compilerUsedCount(&GA); 2949251662Sdim} 2950251662Sdim 2951263508Sdimstatic bool hasUsesToReplace(GlobalAlias &GA, LLVMUsed &U, bool &RenameTarget) { 2952263508Sdim RenameTarget = false; 2953251662Sdim bool Ret = false; 2954263508Sdim if (hasUseOtherThanLLVMUsed(GA, U)) 2955263508Sdim Ret = true; 2956251662Sdim 2957263508Sdim // If the alias is externally visible, we may still be able to simplify it. 2958263508Sdim if (!mayHaveOtherReferences(GA, U)) 2959263508Sdim return Ret; 2960251662Sdim 2961263508Sdim // If the aliasee has internal linkage, give it the name and linkage 2962263508Sdim // of the alias, and delete the alias. This turns: 2963263508Sdim // define internal ... @f(...) 2964263508Sdim // @a = alias ... @f 2965263508Sdim // into: 2966263508Sdim // define ... @a(...) 2967263508Sdim Constant *Aliasee = GA.getAliasee(); 2968263508Sdim GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts()); 2969263508Sdim if (!Target->hasLocalLinkage()) 2970263508Sdim return Ret; 2971263508Sdim 2972263508Sdim // Do not perform the transform if multiple aliases potentially target the 2973263508Sdim // aliasee. This check also ensures that it is safe to replace the section 2974263508Sdim // and other attributes of the aliasee with those of the alias. 2975263508Sdim if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U)) 2976263508Sdim return Ret; 2977263508Sdim 2978263508Sdim RenameTarget = true; 2979263508Sdim return true; 2980251662Sdim} 2981251662Sdim 2982193323Sedbool GlobalOpt::OptimizeGlobalAliases(Module &M) { 2983193323Sed bool Changed = false; 2984263508Sdim LLVMUsed Used(M); 2985193323Sed 2986263508Sdim for (SmallPtrSet<GlobalValue *, 8>::iterator I = Used.usedBegin(), 2987263508Sdim E = Used.usedEnd(); 2988263508Sdim I != E; ++I) 2989263508Sdim Used.compilerUsedErase(*I); 2990263508Sdim 2991193323Sed for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); 2992193323Sed I != E;) { 2993193323Sed Module::alias_iterator J = I++; 2994193323Sed // Aliases without names cannot be referenced outside this module. 2995193323Sed if (!J->hasName() && !J->isDeclaration()) 2996193323Sed J->setLinkage(GlobalValue::InternalLinkage); 2997193323Sed // If the aliasee may change at link time, nothing can be done - bail out. 2998193323Sed if (J->mayBeOverridden()) 2999193323Sed continue; 3000193323Sed 3001193323Sed Constant *Aliasee = J->getAliasee(); 3002193323Sed GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts()); 3003193323Sed Target->removeDeadConstantUsers(); 3004193323Sed 3005193323Sed // Make all users of the alias use the aliasee instead. 3006263508Sdim bool RenameTarget; 3007263508Sdim if (!hasUsesToReplace(*J, Used, RenameTarget)) 3008251662Sdim continue; 3009193323Sed 3010263508Sdim J->replaceAllUsesWith(Aliasee); 3011263508Sdim ++NumAliasesResolved; 3012263508Sdim Changed = true; 3013193323Sed 3014263508Sdim if (RenameTarget) { 3015200581Srdivacky // Give the aliasee the name, linkage and other attributes of the alias. 3016200581Srdivacky Target->takeName(J); 3017200581Srdivacky Target->setLinkage(J->getLinkage()); 3018200581Srdivacky Target->GlobalValue::copyAttributesFrom(J); 3019193323Sed 3020263508Sdim if (Used.usedErase(J)) 3021263508Sdim Used.usedInsert(Target); 3022263508Sdim 3023263508Sdim if (Used.compilerUsedErase(J)) 3024263508Sdim Used.compilerUsedInsert(Target); 3025263508Sdim } else if (mayHaveOtherReferences(*J, Used)) 3026263508Sdim continue; 3027263508Sdim 3028193323Sed // Delete the alias. 3029193323Sed M.getAliasList().erase(J); 3030193323Sed ++NumAliasesRemoved; 3031193323Sed Changed = true; 3032193323Sed } 3033193323Sed 3034263508Sdim Used.syncVariablesAndSets(); 3035263508Sdim 3036193323Sed return Changed; 3037193323Sed} 3038193323Sed 3039234353Sdimstatic Function *FindCXAAtExit(Module &M, TargetLibraryInfo *TLI) { 3040234353Sdim if (!TLI->has(LibFunc::cxa_atexit)) 3041234353Sdim return 0; 3042234353Sdim 3043234353Sdim Function *Fn = M.getFunction(TLI->getName(LibFunc::cxa_atexit)); 3044249423Sdim 3045221345Sdim if (!Fn) 3046221345Sdim return 0; 3047234353Sdim 3048226633Sdim FunctionType *FTy = Fn->getFunctionType(); 3049249423Sdim 3050249423Sdim // Checking that the function has the right return type, the right number of 3051221345Sdim // parameters and that they all have pointer types should be enough. 3052221345Sdim if (!FTy->getReturnType()->isIntegerTy() || 3053221345Sdim FTy->getNumParams() != 3 || 3054221345Sdim !FTy->getParamType(0)->isPointerTy() || 3055221345Sdim !FTy->getParamType(1)->isPointerTy() || 3056221345Sdim !FTy->getParamType(2)->isPointerTy()) 3057221345Sdim return 0; 3058221345Sdim 3059221345Sdim return Fn; 3060221345Sdim} 3061221345Sdim 3062221345Sdim/// cxxDtorIsEmpty - Returns whether the given function is an empty C++ 3063221345Sdim/// destructor and can therefore be eliminated. 3064221345Sdim/// Note that we assume that other optimization passes have already simplified 3065221345Sdim/// the code so we only look for a function with a single basic block, where 3066234353Sdim/// the only allowed instructions are 'ret', 'call' to an empty C++ dtor and 3067234353Sdim/// other side-effect free instructions. 3068221345Sdimstatic bool cxxDtorIsEmpty(const Function &Fn, 3069221345Sdim SmallPtrSet<const Function *, 8> &CalledFunctions) { 3070221345Sdim // FIXME: We could eliminate C++ destructors if they're readonly/readnone and 3071221345Sdim // nounwind, but that doesn't seem worth doing. 3072221345Sdim if (Fn.isDeclaration()) 3073221345Sdim return false; 3074221345Sdim 3075221345Sdim if (++Fn.begin() != Fn.end()) 3076221345Sdim return false; 3077221345Sdim 3078221345Sdim const BasicBlock &EntryBlock = Fn.getEntryBlock(); 3079221345Sdim for (BasicBlock::const_iterator I = EntryBlock.begin(), E = EntryBlock.end(); 3080221345Sdim I != E; ++I) { 3081221345Sdim if (const CallInst *CI = dyn_cast<CallInst>(I)) { 3082221345Sdim // Ignore debug intrinsics. 3083221345Sdim if (isa<DbgInfoIntrinsic>(CI)) 3084221345Sdim continue; 3085221345Sdim 3086221345Sdim const Function *CalledFn = CI->getCalledFunction(); 3087221345Sdim 3088221345Sdim if (!CalledFn) 3089221345Sdim return false; 3090221345Sdim 3091221345Sdim SmallPtrSet<const Function *, 8> NewCalledFunctions(CalledFunctions); 3092221345Sdim 3093221345Sdim // Don't treat recursive functions as empty. 3094221345Sdim if (!NewCalledFunctions.insert(CalledFn)) 3095221345Sdim return false; 3096221345Sdim 3097221345Sdim if (!cxxDtorIsEmpty(*CalledFn, NewCalledFunctions)) 3098221345Sdim return false; 3099221345Sdim } else if (isa<ReturnInst>(*I)) 3100234353Sdim return true; // We're done. 3101234353Sdim else if (I->mayHaveSideEffects()) 3102234353Sdim return false; // Destructor with side effects, bail. 3103221345Sdim } 3104221345Sdim 3105221345Sdim return false; 3106221345Sdim} 3107221345Sdim 3108221345Sdimbool GlobalOpt::OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) { 3109221345Sdim /// Itanium C++ ABI p3.3.5: 3110221345Sdim /// 3111221345Sdim /// After constructing a global (or local static) object, that will require 3112221345Sdim /// destruction on exit, a termination function is registered as follows: 3113221345Sdim /// 3114221345Sdim /// extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d ); 3115221345Sdim /// 3116221345Sdim /// This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the 3117221345Sdim /// call f(p) when DSO d is unloaded, before all such termination calls 3118221345Sdim /// registered before this one. It returns zero if registration is 3119221345Sdim /// successful, nonzero on failure. 3120221345Sdim 3121221345Sdim // This pass will look for calls to __cxa_atexit where the function is trivial 3122221345Sdim // and remove them. 3123221345Sdim bool Changed = false; 3124221345Sdim 3125249423Sdim for (Function::use_iterator I = CXAAtExitFn->use_begin(), 3126221345Sdim E = CXAAtExitFn->use_end(); I != E;) { 3127221345Sdim // We're only interested in calls. Theoretically, we could handle invoke 3128221345Sdim // instructions as well, but neither llvm-gcc nor clang generate invokes 3129221345Sdim // to __cxa_atexit. 3130221345Sdim CallInst *CI = dyn_cast<CallInst>(*I++); 3131221345Sdim if (!CI) 3132221345Sdim continue; 3133221345Sdim 3134249423Sdim Function *DtorFn = 3135221345Sdim dyn_cast<Function>(CI->getArgOperand(0)->stripPointerCasts()); 3136221345Sdim if (!DtorFn) 3137221345Sdim continue; 3138221345Sdim 3139221345Sdim SmallPtrSet<const Function *, 8> CalledFunctions; 3140221345Sdim if (!cxxDtorIsEmpty(*DtorFn, CalledFunctions)) 3141221345Sdim continue; 3142221345Sdim 3143221345Sdim // Just remove the call. 3144221345Sdim CI->replaceAllUsesWith(Constant::getNullValue(CI->getType())); 3145221345Sdim CI->eraseFromParent(); 3146221345Sdim 3147221345Sdim ++NumCXXDtorsRemoved; 3148221345Sdim 3149221345Sdim Changed |= true; 3150221345Sdim } 3151221345Sdim 3152221345Sdim return Changed; 3153221345Sdim} 3154221345Sdim 3155193323Sedbool GlobalOpt::runOnModule(Module &M) { 3156193323Sed bool Changed = false; 3157218893Sdim 3158243830Sdim TD = getAnalysisIfAvailable<DataLayout>(); 3159234353Sdim TLI = &getAnalysis<TargetLibraryInfo>(); 3160234353Sdim 3161193323Sed // Try to find the llvm.globalctors list. 3162193323Sed GlobalVariable *GlobalCtors = FindGlobalCtors(M); 3163193323Sed 3164193323Sed bool LocalChange = true; 3165193323Sed while (LocalChange) { 3166193323Sed LocalChange = false; 3167218893Sdim 3168193323Sed // Delete functions that are trivially dead, ccc -> fastcc 3169193323Sed LocalChange |= OptimizeFunctions(M); 3170218893Sdim 3171193323Sed // Optimize global_ctors list. 3172193323Sed if (GlobalCtors) 3173193323Sed LocalChange |= OptimizeGlobalCtorsList(GlobalCtors); 3174218893Sdim 3175193323Sed // Optimize non-address-taken globals. 3176193323Sed LocalChange |= OptimizeGlobalVars(M); 3177193323Sed 3178193323Sed // Resolve aliases, when possible. 3179193323Sed LocalChange |= OptimizeGlobalAliases(M); 3180221345Sdim 3181263508Sdim // Try to remove trivial global destructors if they are not removed 3182263508Sdim // already. 3183263508Sdim Function *CXAAtExitFn = FindCXAAtExit(M, TLI); 3184221345Sdim if (CXAAtExitFn) 3185221345Sdim LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn); 3186221345Sdim 3187193323Sed Changed |= LocalChange; 3188193323Sed } 3189218893Sdim 3190193323Sed // TODO: Move all global ctors functions to the end of the module for code 3191193323Sed // layout. 3192218893Sdim 3193193323Sed return Changed; 3194193323Sed} 3195