GlobalMerge.cpp revision 274955
1254721Semaste//===-- GlobalMerge.cpp - Internal globals merging -----------------------===// 2254721Semaste// 3254721Semaste// The LLVM Compiler Infrastructure 4254721Semaste// 5254721Semaste// This file is distributed under the University of Illinois Open Source 6254721Semaste// License. See LICENSE.TXT for details. 7254721Semaste// 8254721Semaste//===----------------------------------------------------------------------===// 9254721Semaste// This pass merges globals with internal linkage into one. This way all the 10254721Semaste// globals which were merged into a biggest one can be addressed using offsets 11254721Semaste// from the same base pointer (no need for separate base pointer for each of the 12254721Semaste// global). Such a transformation can significantly reduce the register pressure 13254721Semaste// when many globals are involved. 14254721Semaste// 15254721Semaste// For example, consider the code which touches several global variables at 16254721Semaste// once: 17254721Semaste// 18254721Semaste// static int foo[N], bar[N], baz[N]; 19254721Semaste// 20254721Semaste// for (i = 0; i < N; ++i) { 21254721Semaste// foo[i] = bar[i] * baz[i]; 22254721Semaste// } 23254721Semaste// 24254721Semaste// On ARM the addresses of 3 arrays should be kept in the registers, thus 25254721Semaste// this code has quite large register pressure (loop body): 26254721Semaste// 27254721Semaste// ldr r1, [r5], #4 28254721Semaste// ldr r2, [r6], #4 29254721Semaste// mul r1, r2, r1 30254721Semaste// str r1, [r0], #4 31254721Semaste// 32254721Semaste// Pass converts the code to something like: 33254721Semaste// 34254721Semaste// static struct { 35254721Semaste// int foo[N]; 36254721Semaste// int bar[N]; 37254721Semaste// int baz[N]; 38254721Semaste// } merged; 39254721Semaste// 40254721Semaste// for (i = 0; i < N; ++i) { 41254721Semaste// merged.foo[i] = merged.bar[i] * merged.baz[i]; 42254721Semaste// } 43254721Semaste// 44254721Semaste// and in ARM code this becomes: 45254721Semaste// 46254721Semaste// ldr r0, [r5, #40] 47254721Semaste// ldr r1, [r5, #80] 48254721Semaste// mul r0, r1, r0 49254721Semaste// str r0, [r5], #4 50254721Semaste// 51254721Semaste// note that we saved 2 registers here almostly "for free". 52254721Semaste// ===---------------------------------------------------------------------===// 53254721Semaste 54254721Semaste#include "llvm/Transforms/Scalar.h" 55254721Semaste#include "llvm/ADT/SmallPtrSet.h" 56254721Semaste#include "llvm/ADT/Statistic.h" 57254721Semaste#include "llvm/IR/Attributes.h" 58254721Semaste#include "llvm/IR/Constants.h" 59254721Semaste#include "llvm/IR/DataLayout.h" 60254721Semaste#include "llvm/IR/DerivedTypes.h" 61254721Semaste#include "llvm/IR/Function.h" 62254721Semaste#include "llvm/IR/GlobalVariable.h" 63254721Semaste#include "llvm/IR/Instructions.h" 64254721Semaste#include "llvm/IR/Intrinsics.h" 65254721Semaste#include "llvm/IR/Module.h" 66254721Semaste#include "llvm/Pass.h" 67254721Semaste#include "llvm/CodeGen/Passes.h" 68254721Semaste#include "llvm/Support/CommandLine.h" 69254721Semaste#include "llvm/Target/TargetLowering.h" 70254721Semaste#include "llvm/Target/TargetLoweringObjectFile.h" 71254721Semasteusing namespace llvm; 72254721Semaste 73254721Semaste#define DEBUG_TYPE "global-merge" 74254721Semaste 75254721Semastestatic cl::opt<bool> 76254721SemasteEnableGlobalMerge("enable-global-merge", cl::Hidden, 77254721Semaste cl::desc("Enable global merge pass"), 78254721Semaste cl::init(true)); 79254721Semaste 80254721Semastestatic cl::opt<bool> 81254721SemasteEnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, 82254721Semaste cl::desc("Enable global merge pass on constants"), 83254721Semaste cl::init(false)); 84254721Semaste 85254721Semaste// FIXME: this could be a transitional option, and we probably need to remove 86254721Semaste// it if only we are sure this optimization could always benefit all targets. 87254721Semastestatic cl::opt<bool> 88254721SemasteEnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden, 89254721Semaste cl::desc("Enable global merge pass on external linkage"), 90254721Semaste cl::init(false)); 91254721Semaste 92254721SemasteSTATISTIC(NumMerged , "Number of globals merged"); 93254721Semastenamespace { 94254721Semaste class GlobalMerge : public FunctionPass { 95254721Semaste const TargetMachine *TM; 96254721Semaste 97254721Semaste bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 98254721Semaste Module &M, bool isConst, unsigned AddrSpace) const; 99254721Semaste 100254721Semaste /// \brief Check if the given variable has been identified as must keep 101254721Semaste /// \pre setMustKeepGlobalVariables must have been called on the Module that 102254721Semaste /// contains GV 103254721Semaste bool isMustKeepGlobalVariable(const GlobalVariable *GV) const { 104254721Semaste return MustKeepGlobalVariables.count(GV); 105254721Semaste } 106254721Semaste 107254721Semaste /// Collect every variables marked as "used" or used in a landing pad 108254721Semaste /// instruction for this Module. 109254721Semaste void setMustKeepGlobalVariables(Module &M); 110254721Semaste 111254721Semaste /// Collect every variables marked as "used" 112254721Semaste void collectUsedGlobalVariables(Module &M); 113254721Semaste 114254721Semaste /// Keep track of the GlobalVariable that must not be merged away 115254721Semaste SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables; 116254721Semaste 117254721Semaste public: 118254721Semaste static char ID; // Pass identification, replacement for typeid. 119254721Semaste explicit GlobalMerge(const TargetMachine *TM = nullptr) 120254721Semaste : FunctionPass(ID), TM(TM) { 121254721Semaste initializeGlobalMergePass(*PassRegistry::getPassRegistry()); 122254721Semaste } 123254721Semaste 124254721Semaste bool doInitialization(Module &M) override; 125254721Semaste bool runOnFunction(Function &F) override; 126254721Semaste bool doFinalization(Module &M) override; 127254721Semaste 128254721Semaste const char *getPassName() const override { 129254721Semaste return "Merge internal globals"; 130254721Semaste } 131254721Semaste 132254721Semaste void getAnalysisUsage(AnalysisUsage &AU) const override { 133254721Semaste AU.setPreservesCFG(); 134254721Semaste FunctionPass::getAnalysisUsage(AU); 135254721Semaste } 136254721Semaste }; 137254721Semaste} // end anonymous namespace 138254721Semaste 139254721Semastechar GlobalMerge::ID = 0; 140254721SemasteINITIALIZE_TM_PASS(GlobalMerge, "global-merge", "Merge global variables", 141254721Semaste false, false) 142254721Semaste 143254721Semastebool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 144254721Semaste Module &M, bool isConst, unsigned AddrSpace) const { 145254721Semaste const TargetLowering *TLI = TM->getTargetLowering(); 146254721Semaste const DataLayout *DL = TLI->getDataLayout(); 147254721Semaste 148254721Semaste // FIXME: Infer the maximum possible offset depending on the actual users 149254721Semaste // (these max offsets are different for the users inside Thumb or ARM 150254721Semaste // functions) 151254721Semaste unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 152254721Semaste 153254721Semaste // FIXME: Find better heuristics 154254721Semaste std::stable_sort(Globals.begin(), Globals.end(), 155254721Semaste [DL](const GlobalVariable *GV1, const GlobalVariable *GV2) { 156254721Semaste Type *Ty1 = cast<PointerType>(GV1->getType())->getElementType(); 157254721Semaste Type *Ty2 = cast<PointerType>(GV2->getType())->getElementType(); 158254721Semaste 159254721Semaste return (DL->getTypeAllocSize(Ty1) < DL->getTypeAllocSize(Ty2)); 160254721Semaste }); 161254721Semaste 162254721Semaste Type *Int32Ty = Type::getInt32Ty(M.getContext()); 163254721Semaste 164254721Semaste assert(Globals.size() > 1); 165254721Semaste 166254721Semaste // FIXME: This simple solution merges globals all together as maximum as 167254721Semaste // possible. However, with this solution it would be hard to remove dead 168254721Semaste // global symbols at link-time. An alternative solution could be checking 169254721Semaste // global symbols references function by function, and make the symbols 170254721Semaste // being referred in the same function merged and we would probably need 171254721Semaste // to introduce heuristic algorithm to solve the merge conflict from 172254721Semaste // different functions. 173254721Semaste for (size_t i = 0, e = Globals.size(); i != e; ) { 174254721Semaste size_t j = 0; 175254721Semaste uint64_t MergedSize = 0; 176254721Semaste std::vector<Type*> Tys; 177254721Semaste std::vector<Constant*> Inits; 178254721Semaste 179254721Semaste bool HasExternal = false; 180254721Semaste GlobalVariable *TheFirstExternal = 0; 181254721Semaste for (j = i; j != e; ++j) { 182254721Semaste Type *Ty = Globals[j]->getType()->getElementType(); 183254721Semaste MergedSize += DL->getTypeAllocSize(Ty); 184254721Semaste if (MergedSize > MaxOffset) { 185254721Semaste break; 186254721Semaste } 187254721Semaste Tys.push_back(Ty); 188254721Semaste Inits.push_back(Globals[j]->getInitializer()); 189254721Semaste 190254721Semaste if (Globals[j]->hasExternalLinkage() && !HasExternal) { 191254721Semaste HasExternal = true; 192254721Semaste TheFirstExternal = Globals[j]; 193254721Semaste } 194254721Semaste } 195254721Semaste 196254721Semaste // If merged variables doesn't have external linkage, we needn't to expose 197254721Semaste // the symbol after merging. 198254721Semaste GlobalValue::LinkageTypes Linkage = HasExternal 199254721Semaste ? GlobalValue::ExternalLinkage 200254721Semaste : GlobalValue::InternalLinkage; 201254721Semaste 202254721Semaste StructType *MergedTy = StructType::get(M.getContext(), Tys); 203254721Semaste Constant *MergedInit = ConstantStruct::get(MergedTy, Inits); 204254721Semaste 205254721Semaste // If merged variables have external linkage, we use symbol name of the 206254721Semaste // first variable merged as the suffix of global symbol name. This would 207254721Semaste // be able to avoid the link-time naming conflict for globalm symbols. 208254721Semaste GlobalVariable *MergedGV = new GlobalVariable( 209254721Semaste M, MergedTy, isConst, Linkage, MergedInit, 210254721Semaste HasExternal ? "_MergedGlobals_" + TheFirstExternal->getName() 211254721Semaste : "_MergedGlobals", 212254721Semaste nullptr, GlobalVariable::NotThreadLocal, AddrSpace); 213254721Semaste 214254721Semaste for (size_t k = i; k < j; ++k) { 215254721Semaste GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage(); 216254721Semaste std::string Name = Globals[k]->getName(); 217254721Semaste 218254721Semaste Constant *Idx[2] = { 219254721Semaste ConstantInt::get(Int32Ty, 0), 220254721Semaste ConstantInt::get(Int32Ty, k-i) 221254721Semaste }; 222254721Semaste Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx); 223254721Semaste Globals[k]->replaceAllUsesWith(GEP); 224254721Semaste Globals[k]->eraseFromParent(); 225254721Semaste 226254721Semaste if (Linkage != GlobalValue::InternalLinkage) { 227254721Semaste // Generate a new alias... 228254721Semaste auto *PTy = cast<PointerType>(GEP->getType()); 229254721Semaste GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(), 230254721Semaste Linkage, Name, GEP, &M); 231254721Semaste } 232254721Semaste 233254721Semaste NumMerged++; 234254721Semaste } 235254721Semaste i = j; 236254721Semaste } 237254721Semaste 238254721Semaste return true; 239254721Semaste} 240254721Semaste 241254721Semastevoid GlobalMerge::collectUsedGlobalVariables(Module &M) { 242254721Semaste // Extract global variables from llvm.used array 243254721Semaste const GlobalVariable *GV = M.getGlobalVariable("llvm.used"); 244254721Semaste if (!GV || !GV->hasInitializer()) return; 245254721Semaste 246254721Semaste // Should be an array of 'i8*'. 247254721Semaste const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer()); 248254721Semaste 249254721Semaste for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) 250254721Semaste if (const GlobalVariable *G = 251254721Semaste dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts())) 252254721Semaste MustKeepGlobalVariables.insert(G); 253254721Semaste} 254254721Semaste 255254721Semastevoid GlobalMerge::setMustKeepGlobalVariables(Module &M) { 256254721Semaste collectUsedGlobalVariables(M); 257254721Semaste 258254721Semaste for (Module::iterator IFn = M.begin(), IEndFn = M.end(); IFn != IEndFn; 259254721Semaste ++IFn) { 260254721Semaste for (Function::iterator IBB = IFn->begin(), IEndBB = IFn->end(); 261254721Semaste IBB != IEndBB; ++IBB) { 262254721Semaste // Follow the invoke link to find the landing pad instruction 263254721Semaste const InvokeInst *II = dyn_cast<InvokeInst>(IBB->getTerminator()); 264254721Semaste if (!II) continue; 265254721Semaste 266254721Semaste const LandingPadInst *LPInst = II->getUnwindDest()->getLandingPadInst(); 267254721Semaste // Look for globals in the clauses of the landing pad instruction 268254721Semaste for (unsigned Idx = 0, NumClauses = LPInst->getNumClauses(); 269254721Semaste Idx != NumClauses; ++Idx) 270254721Semaste if (const GlobalVariable *GV = 271254721Semaste dyn_cast<GlobalVariable>(LPInst->getClause(Idx) 272254721Semaste ->stripPointerCasts())) 273254721Semaste MustKeepGlobalVariables.insert(GV); 274254721Semaste } 275254721Semaste } 276254721Semaste} 277254721Semaste 278254721Semastebool GlobalMerge::doInitialization(Module &M) { 279254721Semaste if (!EnableGlobalMerge) 280254721Semaste return false; 281254721Semaste 282254721Semaste DenseMap<unsigned, SmallVector<GlobalVariable*, 16> > Globals, ConstGlobals, 283254721Semaste BSSGlobals; 284254721Semaste const TargetLowering *TLI = TM->getTargetLowering(); 285254721Semaste const DataLayout *DL = TLI->getDataLayout(); 286254721Semaste unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 287254721Semaste bool Changed = false; 288254721Semaste setMustKeepGlobalVariables(M); 289254721Semaste 290254721Semaste // Grab all non-const globals. 291254721Semaste for (Module::global_iterator I = M.global_begin(), 292254721Semaste E = M.global_end(); I != E; ++I) { 293254721Semaste // Merge is safe for "normal" internal or external globals only 294254721Semaste if (I->isDeclaration() || I->isThreadLocal() || I->hasSection()) 295254721Semaste continue; 296254721Semaste 297254721Semaste if (!(EnableGlobalMergeOnExternal && I->hasExternalLinkage()) && 298254721Semaste !I->hasInternalLinkage()) 299254721Semaste continue; 300254721Semaste 301254721Semaste PointerType *PT = dyn_cast<PointerType>(I->getType()); 302254721Semaste assert(PT && "Global variable is not a pointer!"); 303254721Semaste 304254721Semaste unsigned AddressSpace = PT->getAddressSpace(); 305254721Semaste 306254721Semaste // Ignore fancy-aligned globals for now. 307254721Semaste unsigned Alignment = DL->getPreferredAlignment(I); 308254721Semaste Type *Ty = I->getType()->getElementType(); 309254721Semaste if (Alignment > DL->getABITypeAlignment(Ty)) 310254721Semaste continue; 311254721Semaste 312254721Semaste // Ignore all 'special' globals. 313254721Semaste if (I->getName().startswith("llvm.") || 314254721Semaste I->getName().startswith(".llvm.")) 315254721Semaste continue; 316254721Semaste 317254721Semaste // Ignore all "required" globals: 318254721Semaste if (isMustKeepGlobalVariable(I)) 319254721Semaste continue; 320254721Semaste 321254721Semaste if (DL->getTypeAllocSize(Ty) < MaxOffset) { 322254721Semaste if (TargetLoweringObjectFile::getKindForGlobal(I, *TM).isBSSLocal()) 323254721Semaste BSSGlobals[AddressSpace].push_back(I); 324254721Semaste else if (I->isConstant()) 325254721Semaste ConstGlobals[AddressSpace].push_back(I); 326254721Semaste else 327254721Semaste Globals[AddressSpace].push_back(I); 328254721Semaste } 329254721Semaste } 330254721Semaste 331254721Semaste for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 332254721Semaste I = Globals.begin(), E = Globals.end(); I != E; ++I) 333254721Semaste if (I->second.size() > 1) 334254721Semaste Changed |= doMerge(I->second, M, false, I->first); 335254721Semaste 336254721Semaste for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 337254721Semaste I = BSSGlobals.begin(), E = BSSGlobals.end(); I != E; ++I) 338254721Semaste if (I->second.size() > 1) 339254721Semaste Changed |= doMerge(I->second, M, false, I->first); 340254721Semaste 341254721Semaste if (EnableGlobalMergeOnConst) 342254721Semaste for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 343254721Semaste I = ConstGlobals.begin(), E = ConstGlobals.end(); I != E; ++I) 344254721Semaste if (I->second.size() > 1) 345254721Semaste Changed |= doMerge(I->second, M, true, I->first); 346254721Semaste 347254721Semaste return Changed; 348254721Semaste} 349254721Semaste 350254721Semastebool GlobalMerge::runOnFunction(Function &F) { 351254721Semaste return false; 352254721Semaste} 353254721Semaste 354254721Semastebool GlobalMerge::doFinalization(Module &M) { 355254721Semaste MustKeepGlobalVariables.clear(); 356254721Semaste return false; 357254721Semaste} 358254721Semaste 359254721SemastePass *llvm::createGlobalMergePass(const TargetMachine *TM) { 360254721Semaste return new GlobalMerge(TM); 361254721Semaste} 362254721Semaste