GlobalMerge.cpp revision 263508
11558Srgrimes//===-- GlobalMerge.cpp - Internal globals merging -----------------------===// 21558Srgrimes// 31558Srgrimes// The LLVM Compiler Infrastructure 41558Srgrimes// 51558Srgrimes// This file is distributed under the University of Illinois Open Source 61558Srgrimes// License. See LICENSE.TXT for details. 71558Srgrimes// 81558Srgrimes//===----------------------------------------------------------------------===// 91558Srgrimes// This pass merges globals with internal linkage into one. This way all the 101558Srgrimes// globals which were merged into a biggest one can be addressed using offsets 111558Srgrimes// from the same base pointer (no need for separate base pointer for each of the 121558Srgrimes// global). Such a transformation can significantly reduce the register pressure 131558Srgrimes// when many globals are involved. 141558Srgrimes// 151558Srgrimes// For example, consider the code which touches several global variables at 161558Srgrimes// once: 171558Srgrimes// 181558Srgrimes// static int foo[N], bar[N], baz[N]; 191558Srgrimes// 201558Srgrimes// for (i = 0; i < N; ++i) { 211558Srgrimes// foo[i] = bar[i] * baz[i]; 221558Srgrimes// } 231558Srgrimes// 241558Srgrimes// On ARM the addresses of 3 arrays should be kept in the registers, thus 251558Srgrimes// this code has quite large register pressure (loop body): 261558Srgrimes// 271558Srgrimes// ldr r1, [r5], #4 281558Srgrimes// ldr r2, [r6], #4 291558Srgrimes// mul r1, r2, r1 301558Srgrimes// str r1, [r0], #4 311558Srgrimes// 321558Srgrimes// Pass converts the code to something like: 33114589Sobrien// 341558Srgrimes// static struct { 3537427Scharnier// int foo[N]; 361558Srgrimes// int bar[N]; 371558Srgrimes// int baz[N]; 381558Srgrimes// } merged; 391558Srgrimes// 401558Srgrimes// for (i = 0; i < N; ++i) { 4123680Speter// merged.foo[i] = merged.bar[i] * merged.baz[i]; 42114589Sobrien// } 4337427Scharnier// 44114589Sobrien// and in ARM code this becomes: 45114589Sobrien// 461558Srgrimes// ldr r0, [r5, #40] 471558Srgrimes// ldr r1, [r5, #80] 48192930Srmacklem// mul r0, r1, r0 49192930Srmacklem// str r0, [r5], #4 501558Srgrimes// 5174462Salfred// note that we saved 2 registers here almostly "for free". 521558Srgrimes// ===---------------------------------------------------------------------===// 531558Srgrimes 54164457Srodrigc#define DEBUG_TYPE "global-merge" 551558Srgrimes#include "llvm/Transforms/Scalar.h" 561558Srgrimes#include "llvm/ADT/SmallPtrSet.h" 571558Srgrimes#include "llvm/ADT/Statistic.h" 581558Srgrimes#include "llvm/IR/Attributes.h" 59194880Sdfr#include "llvm/IR/Constants.h" 60194880Sdfr#include "llvm/IR/DataLayout.h" 611558Srgrimes#include "llvm/IR/DerivedTypes.h" 6283653Speter#include "llvm/IR/Function.h" 631558Srgrimes#include "llvm/IR/GlobalVariable.h" 641558Srgrimes#include "llvm/IR/Instructions.h" 651558Srgrimes#include "llvm/IR/Intrinsics.h" 661558Srgrimes#include "llvm/IR/Module.h" 671558Srgrimes#include "llvm/Pass.h" 681558Srgrimes#include "llvm/Support/CommandLine.h" 6974462Salfred#include "llvm/Target/TargetLowering.h" 701558Srgrimes#include "llvm/Target/TargetLoweringObjectFile.h" 711558Srgrimesusing namespace llvm; 721558Srgrimes 73112570Smdoddstatic cl::opt<bool> 741558SrgrimesEnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, 7515770Swollman cl::desc("Enable global merge pass on constants"), 761558Srgrimes cl::init(false)); 771558Srgrimes 781558SrgrimesSTATISTIC(NumMerged , "Number of globals merged"); 7953550Sdillonnamespace { 801558Srgrimes class GlobalMerge : public FunctionPass { 8176530Siedowse const TargetMachine *TM; 82275257Strasz 83183008Srodrigc bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 8476530Siedowse Module &M, bool isConst, unsigned AddrSpace) const; 8576530Siedowse 8676530Siedowse /// \brief Check if the given variable has been identified as must keep 8776530Siedowse /// \pre setMustKeepGlobalVariables must have been called on the Module that 8876530Siedowse /// contains GV 8976530Siedowse bool isMustKeepGlobalVariable(const GlobalVariable *GV) const { 9076530Siedowse return MustKeepGlobalVariables.count(GV); 91164458Srodrigc } 9276530Siedowse 9376530Siedowse /// Collect every variables marked as "used" or used in a landing pad 941558Srgrimes /// instruction for this Module. 959336Sdfr void setMustKeepGlobalVariables(Module &M); 969336Sdfr 979336Sdfr /// Collect every variables marked as "used" 989336Sdfr void collectUsedGlobalVariables(Module &M); 99194880Sdfr 1001558Srgrimes /// Keep track of the GlobalVariable that must not be merged away 1011558Srgrimes SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables; 1021558Srgrimes 103112580Smdodd public: 104112580Smdodd static char ID; // Pass identification, replacement for typeid. 105275257Strasz explicit GlobalMerge(const TargetMachine *TM = 0) 106275257Strasz : FunctionPass(ID), TM(TM) { 107275257Strasz initializeGlobalMergePass(*PassRegistry::getPassRegistry()); 108275257Strasz } 109275257Strasz 110275257Strasz virtual bool doInitialization(Module &M); 111275257Strasz virtual bool runOnFunction(Function &F); 112275257Strasz virtual bool doFinalization(Module &M); 113275257Strasz 114275257Strasz const char *getPassName() const { 115275257Strasz return "Merge internal globals"; 116275257Strasz } 117275257Strasz 118183008Srodrigc virtual void getAnalysisUsage(AnalysisUsage &AU) const { 119275257Strasz AU.setPreservesCFG(); 12025004Sdfr FunctionPass::getAnalysisUsage(AU); 12125004Sdfr } 122166183Srodrigc 123192930Srmacklem struct GlobalCmp { 12425004Sdfr const DataLayout *TD; 1251558Srgrimes 12675394Siedowse GlobalCmp(const DataLayout *td) : TD(td) { } 12775394Siedowse 12875394Siedowse bool operator()(const GlobalVariable *GV1, const GlobalVariable *GV2) { 12975394Siedowse Type *Ty1 = cast<PointerType>(GV1->getType())->getElementType(); 13075394Siedowse Type *Ty2 = cast<PointerType>(GV2->getType())->getElementType(); 13175394Siedowse 13275394Siedowse return (TD->getTypeAllocSize(Ty1) < TD->getTypeAllocSize(Ty2)); 13375394Siedowse } 134275257Strasz }; 135275257Strasz }; 136203461Sdelphij} // end anonymous namespace 13792882Simp 138203461Sdelphijchar GlobalMerge::ID = 0; 139203461SdelphijINITIALIZE_PASS(GlobalMerge, "global-merge", 140203461Sdelphij "Global Merge", false, false) 141203461Sdelphij 142203461Sdelphij 143203461Sdelphijbool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 144183008Srodrigc Module &M, bool isConst, unsigned AddrSpace) const { 145203461Sdelphij const TargetLowering *TLI = TM->getTargetLowering(); 1461558Srgrimes const DataLayout *TD = TLI->getDataLayout(); 1471558Srgrimes 148156925Simp // FIXME: Infer the maximum possible offset depending on the actual users 1491558Srgrimes // (these max offsets are different for the users inside Thumb or ARM 15092806Sobrien // functions) 151164457Srodrigc unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 152247856Sjkim 153275257Strasz // FIXME: Find better heuristics 154164733Srodrigc std::stable_sort(Globals.begin(), Globals.end(), GlobalCmp(TD)); 155275257Strasz 156275257Strasz Type *Int32Ty = Type::getInt32Ty(M.getContext()); 1571558Srgrimes 158164457Srodrigc for (size_t i = 0, e = Globals.size(); i != e; ) { 159164457Srodrigc size_t j = 0; 160164733Srodrigc uint64_t MergedSize = 0; 161192930Srmacklem std::vector<Type*> Tys; 162164457Srodrigc std::vector<Constant*> Inits; 163164732Srodrigc for (j = i; j != e; ++j) { 164164732Srodrigc Type *Ty = Globals[j]->getType()->getElementType(); 165164732Srodrigc MergedSize += TD->getTypeAllocSize(Ty); 166164732Srodrigc if (MergedSize > MaxOffset) { 167164732Srodrigc break; 168164732Srodrigc } 1691558Srgrimes Tys.push_back(Ty); 170192578Srwatson Inits.push_back(Globals[j]->getInitializer()); 1711558Srgrimes } 17225004Sdfr 17325004Sdfr StructType *MergedTy = StructType::get(M.getContext(), Tys); 17425004Sdfr Constant *MergedInit = ConstantStruct::get(MergedTy, Inits); 1759336Sdfr GlobalVariable *MergedGV = new GlobalVariable(M, MergedTy, isConst, 17625004Sdfr GlobalValue::InternalLinkage, 1779336Sdfr MergedInit, "_MergedGlobals", 1781558Srgrimes 0, GlobalVariable::NotThreadLocal, 179214419Sjh AddrSpace); 180183008Srodrigc for (size_t k = i; k < j; ++k) { 1811558Srgrimes Constant *Idx[2] = { 1821558Srgrimes ConstantInt::get(Int32Ty, 0), 1831558Srgrimes ConstantInt::get(Int32Ty, k-i) 1841558Srgrimes }; 1851558Srgrimes Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx); 186183008Srodrigc Globals[k]->replaceAllUsesWith(GEP); 187183008Srodrigc Globals[k]->eraseFromParent(); 188183008Srodrigc NumMerged++; 1891558Srgrimes } 1901558Srgrimes i = j; 191183008Srodrigc } 192183008Srodrigc 1931558Srgrimes return true; 1941558Srgrimes} 195183008Srodrigc 196183008Srodrigcvoid GlobalMerge::collectUsedGlobalVariables(Module &M) { 1971558Srgrimes // Extract global variables from llvm.used array 1981558Srgrimes const GlobalVariable *GV = M.getGlobalVariable("llvm.used"); 199183008Srodrigc if (!GV || !GV->hasInitializer()) return; 2001558Srgrimes 2011558Srgrimes // Should be an array of 'i8*'. 2021558Srgrimes const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer()); 203183008Srodrigc 204183008Srodrigc for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) 2051558Srgrimes if (const GlobalVariable *G = 2069336Sdfr dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts())) 207183008Srodrigc MustKeepGlobalVariables.insert(G); 208183008Srodrigc} 2099336Sdfr 2101558Srgrimesvoid GlobalMerge::setMustKeepGlobalVariables(Module &M) { 211183008Srodrigc collectUsedGlobalVariables(M); 212183008Srodrigc 2131558Srgrimes for (Module::iterator IFn = M.begin(), IEndFn = M.end(); IFn != IEndFn; 21486284Salfred ++IFn) { 215216725Ssimon for (Function::iterator IBB = IFn->begin(), IEndBB = IFn->end(); 216183008Srodrigc IBB != IEndBB; ++IBB) { 21786284Salfred // Follow the inwoke link to find the landing pad instruction 2181558Srgrimes const InvokeInst *II = dyn_cast<InvokeInst>(IBB->getTerminator()); 219183008Srodrigc if (!II) continue; 220183008Srodrigc 2211558Srgrimes const LandingPadInst *LPInst = II->getUnwindDest()->getLandingPadInst(); 22230580Sjoerg // Look for globals in the clauses of the landing pad instruction 223183008Srodrigc for (unsigned Idx = 0, NumClauses = LPInst->getNumClauses(); 22430580Sjoerg Idx != NumClauses; ++Idx) 225183008Srodrigc if (const GlobalVariable *GV = 226183008Srodrigc dyn_cast<GlobalVariable>(LPInst->getClause(Idx) 227183008Srodrigc ->stripPointerCasts())) 228183008Srodrigc MustKeepGlobalVariables.insert(GV); 229183008Srodrigc } 230183008Srodrigc } 231275257Strasz} 232183008Srodrigc 233198491Sjhbool GlobalMerge::doInitialization(Module &M) { 234198491Sjh DenseMap<unsigned, SmallVector<GlobalVariable*, 16> > Globals, ConstGlobals, 235198491Sjh BSSGlobals; 236198491Sjh const TargetLowering *TLI = TM->getTargetLowering(); 237198491Sjh const DataLayout *TD = TLI->getDataLayout(); 238183008Srodrigc unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 239183008Srodrigc bool Changed = false; 240183008Srodrigc setMustKeepGlobalVariables(M); 241183008Srodrigc 242183008Srodrigc // Grab all non-const globals. 243183008Srodrigc for (Module::global_iterator I = M.global_begin(), 244183008Srodrigc E = M.global_end(); I != E; ++I) { 245183008Srodrigc // Merge is safe for "normal" internal globals only 246183008Srodrigc if (!I->hasLocalLinkage() || I->isThreadLocal() || I->hasSection()) 247183008Srodrigc continue; 248183008Srodrigc 249192930Srmacklem PointerType *PT = dyn_cast<PointerType>(I->getType()); 250192930Srmacklem assert(PT && "Global variable is not a pointer!"); 251192930Srmacklem 252183008Srodrigc unsigned AddressSpace = PT->getAddressSpace(); 253183008Srodrigc 254183008Srodrigc // Ignore fancy-aligned globals for now. 255183008Srodrigc unsigned Alignment = TD->getPreferredAlignment(I); 256183008Srodrigc Type *Ty = I->getType()->getElementType(); 257183008Srodrigc if (Alignment > TD->getABITypeAlignment(Ty)) 258183008Srodrigc continue; 259183008Srodrigc 260183008Srodrigc // Ignore all 'special' globals. 261183008Srodrigc if (I->getName().startswith("llvm.") || 262183008Srodrigc I->getName().startswith(".llvm.")) 263183008Srodrigc continue; 264183008Srodrigc 265183008Srodrigc // Ignore all "required" globals: 266183008Srodrigc if (isMustKeepGlobalVariable(I)) 267183008Srodrigc continue; 268183008Srodrigc 269183008Srodrigc if (TD->getTypeAllocSize(Ty) < MaxOffset) { 270183008Srodrigc if (TargetLoweringObjectFile::getKindForGlobal(I, TLI->getTargetMachine()) 271183008Srodrigc .isBSSLocal()) 272192930Srmacklem BSSGlobals[AddressSpace].push_back(I); 273192930Srmacklem else if (I->isConstant()) 274192930Srmacklem ConstGlobals[AddressSpace].push_back(I); 275221124Srmacklem else 276192930Srmacklem Globals[AddressSpace].push_back(I); 277192930Srmacklem } 278192930Srmacklem } 279183008Srodrigc 280183008Srodrigc for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 281275257Strasz I = Globals.begin(), E = Globals.end(); I != E; ++I) 282275257Strasz if (I->second.size() > 1) 283103039Speter Changed |= doMerge(I->second, M, false, I->first); 284275257Strasz 285192930Srmacklem for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 286192930Srmacklem I = BSSGlobals.begin(), E = BSSGlobals.end(); I != E; ++I) 287275249Strasz if (I->second.size() > 1) 288275249Strasz Changed |= doMerge(I->second, M, false, I->first); 289275249Strasz 290275249Strasz if (EnableGlobalMergeOnConst) 291275249Strasz for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 292275249Strasz I = ConstGlobals.begin(), E = ConstGlobals.end(); I != E; ++I) 293275249Strasz if (I->second.size() > 1) 294275249Strasz Changed |= doMerge(I->second, M, true, I->first); 295275249Strasz 296275249Strasz return Changed; 297275249Strasz} 298275249Strasz 299275249Straszbool GlobalMerge::runOnFunction(Function &F) { 300275249Strasz return false; 301275249Strasz} 302275249Strasz 303275249Straszbool GlobalMerge::doFinalization(Module &M) { 304275249Strasz MustKeepGlobalVariables.clear(); 305275249Strasz return false; 306275249Strasz} 307275249Strasz 308275249StraszPass *llvm::createGlobalMergePass(const TargetMachine *TM) { 309275249Strasz return new GlobalMerge(TM); 310275249Strasz} 311275249Strasz