1//===-- GlobalMerge.cpp - Internal globals merging -----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// This pass merges globals with internal linkage into one. This way all the 10// globals which were merged into a biggest one can be addressed using offsets 11// from the same base pointer (no need for separate base pointer for each of the 12// global). Such a transformation can significantly reduce the register pressure 13// when many globals are involved. 14// 15// For example, consider the code which touches several global variables at 16// once: 17// 18// static int foo[N], bar[N], baz[N]; 19// 20// for (i = 0; i < N; ++i) { 21// foo[i] = bar[i] * baz[i]; 22// } 23// 24// On ARM the addresses of 3 arrays should be kept in the registers, thus 25// this code has quite large register pressure (loop body): 26// 27// ldr r1, [r5], #4 28// ldr r2, [r6], #4 29// mul r1, r2, r1 30// str r1, [r0], #4 31// 32// Pass converts the code to something like: 33// 34// static struct { 35// int foo[N]; 36// int bar[N]; 37// int baz[N]; 38// } merged; 39// 40// for (i = 0; i < N; ++i) { 41// merged.foo[i] = merged.bar[i] * merged.baz[i]; 42// } 43// 44// and in ARM code this becomes: 45// 46// ldr r0, [r5, #40] 47// ldr r1, [r5, #80] 48// mul r0, r1, r0 49// str r0, [r5], #4 50// 51// note that we saved 2 registers here almostly "for free". 52// ===---------------------------------------------------------------------===// 53 54#define DEBUG_TYPE "global-merge" 55#include "llvm/Transforms/Scalar.h" 56#include "llvm/ADT/SmallPtrSet.h" 57#include "llvm/ADT/Statistic.h" 58#include "llvm/IR/Attributes.h" 59#include "llvm/IR/Constants.h" 60#include "llvm/IR/DataLayout.h" 61#include "llvm/IR/DerivedTypes.h" 62#include "llvm/IR/Function.h" 63#include "llvm/IR/GlobalVariable.h" 64#include "llvm/IR/InlineAsm.h" 65#include "llvm/IR/Instructions.h" 66#include "llvm/IR/Intrinsics.h" 67#include "llvm/IR/IntrinsicInst.h" 68#include "llvm/IR/Module.h" 69#include "llvm/Pass.h" 70#include "llvm/Support/CommandLine.h" 71#include "llvm/Target/TargetLowering.h" 72#include "llvm/Target/TargetLoweringObjectFile.h" 73using namespace llvm; 74 75static cl::opt<bool> 76EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, 77 cl::desc("Enable global merge pass on constants"), 78 cl::init(false)); 79 80STATISTIC(NumMerged , "Number of globals merged"); 81namespace { 82 class GlobalMerge : public FunctionPass { 83 /// TLI - Keep a pointer of a TargetLowering to consult for determining 84 /// target type sizes. 85 const TargetLowering *TLI; 86 87 bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 88 Module &M, bool isConst, unsigned AddrSpace) const; 89 90 /// \brief Check if the given variable has been identified as must keep 91 /// \pre setMustKeepGlobalVariables must have been called on the Module that 92 /// contains GV 93 bool isMustKeepGlobalVariable(const GlobalVariable *GV) const { 94 return MustKeepGlobalVariables.count(GV); 95 } 96 97 /// Collect every variables marked as "used" or used in a landing pad 98 /// instruction for this Module. 99 void setMustKeepGlobalVariables(Module &M); 100 101 /// Collect every variables marked as "used" 102 void collectUsedGlobalVariables(Module &M); 103 104 /// Keep track of the GlobalVariable that are marked as "used" 105 SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables; 106 107 public: 108 static char ID; // Pass identification, replacement for typeid. 109 explicit GlobalMerge(const TargetLowering *tli = 0) 110 : FunctionPass(ID), TLI(tli) { 111 initializeGlobalMergePass(*PassRegistry::getPassRegistry()); 112 } 113 114 virtual bool doInitialization(Module &M); 115 virtual bool runOnFunction(Function &F); 116 117 const char *getPassName() const { 118 return "Merge internal globals"; 119 } 120 121 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 122 AU.setPreservesCFG(); 123 FunctionPass::getAnalysisUsage(AU); 124 } 125 126 struct GlobalCmp { 127 const DataLayout *TD; 128 129 GlobalCmp(const DataLayout *td) : TD(td) { } 130 131 bool operator()(const GlobalVariable *GV1, const GlobalVariable *GV2) { 132 Type *Ty1 = cast<PointerType>(GV1->getType())->getElementType(); 133 Type *Ty2 = cast<PointerType>(GV2->getType())->getElementType(); 134 135 return (TD->getTypeAllocSize(Ty1) < TD->getTypeAllocSize(Ty2)); 136 } 137 }; 138 }; 139} // end anonymous namespace 140 141char GlobalMerge::ID = 0; 142INITIALIZE_PASS(GlobalMerge, "global-merge", 143 "Global Merge", false, false) 144 145 146bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 147 Module &M, bool isConst, unsigned AddrSpace) const { 148 const DataLayout *TD = TLI->getDataLayout(); 149 150 // FIXME: Infer the maximum possible offset depending on the actual users 151 // (these max offsets are different for the users inside Thumb or ARM 152 // functions) 153 unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 154 155 // FIXME: Find better heuristics 156 std::stable_sort(Globals.begin(), Globals.end(), GlobalCmp(TD)); 157 158 Type *Int32Ty = Type::getInt32Ty(M.getContext()); 159 160 for (size_t i = 0, e = Globals.size(); i != e; ) { 161 size_t j = 0; 162 uint64_t MergedSize = 0; 163 std::vector<Type*> Tys; 164 std::vector<Constant*> Inits; 165 for (j = i; j != e; ++j) { 166 Type *Ty = Globals[j]->getType()->getElementType(); 167 MergedSize += TD->getTypeAllocSize(Ty); 168 if (MergedSize > MaxOffset) { 169 break; 170 } 171 Tys.push_back(Ty); 172 Inits.push_back(Globals[j]->getInitializer()); 173 } 174 175 StructType *MergedTy = StructType::get(M.getContext(), Tys); 176 Constant *MergedInit = ConstantStruct::get(MergedTy, Inits); 177 GlobalVariable *MergedGV = new GlobalVariable(M, MergedTy, isConst, 178 GlobalValue::InternalLinkage, 179 MergedInit, "_MergedGlobals", 180 0, GlobalVariable::NotThreadLocal, 181 AddrSpace); 182 for (size_t k = i; k < j; ++k) { 183 Constant *Idx[2] = { 184 ConstantInt::get(Int32Ty, 0), 185 ConstantInt::get(Int32Ty, k-i) 186 }; 187 Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx); 188 Globals[k]->replaceAllUsesWith(GEP); 189 Globals[k]->eraseFromParent(); 190 NumMerged++; 191 } 192 i = j; 193 } 194 195 return true; 196} 197 198void GlobalMerge::collectUsedGlobalVariables(Module &M) { 199 // Extract global variables from llvm.used array 200 const GlobalVariable *GV = M.getGlobalVariable("llvm.used"); 201 if (!GV || !GV->hasInitializer()) return; 202 203 // Should be an array of 'i8*'. 204 const ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); 205 if (InitList == 0) return; 206 207 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) 208 if (const GlobalVariable *G = 209 dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts())) 210 MustKeepGlobalVariables.insert(G); 211} 212 213void GlobalMerge::setMustKeepGlobalVariables(Module &M) { 214 // If we already processed a Module, UsedGlobalVariables may have been 215 // populated. Reset the information for this module. 216 MustKeepGlobalVariables.clear(); 217 collectUsedGlobalVariables(M); 218 219 for (Module::iterator IFn = M.begin(), IEndFn = M.end(); IFn != IEndFn; 220 ++IFn) { 221 for (Function::iterator IBB = IFn->begin(), IEndBB = IFn->end(); 222 IBB != IEndBB; ++IBB) { 223 // Follow the inwoke link to find the landing pad instruction 224 const InvokeInst *II = dyn_cast<InvokeInst>(IBB->getTerminator()); 225 if (!II) continue; 226 227 const LandingPadInst *LPInst = II->getUnwindDest()->getLandingPadInst(); 228 // Look for globals in the clauses of the landing pad instruction 229 for (unsigned Idx = 0, NumClauses = LPInst->getNumClauses(); 230 Idx != NumClauses; ++Idx) 231 if (const GlobalVariable *GV = 232 dyn_cast<GlobalVariable>(LPInst->getClause(Idx) 233 ->stripPointerCasts())) 234 MustKeepGlobalVariables.insert(GV); 235 } 236 } 237} 238 239bool GlobalMerge::doInitialization(Module &M) { 240 DenseMap<unsigned, SmallVector<GlobalVariable*, 16> > Globals, ConstGlobals, 241 BSSGlobals; 242 const DataLayout *TD = TLI->getDataLayout(); 243 unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 244 bool Changed = false; 245 setMustKeepGlobalVariables(M); 246 247 // Grab all non-const globals. 248 for (Module::global_iterator I = M.global_begin(), 249 E = M.global_end(); I != E; ++I) { 250 // Merge is safe for "normal" internal globals only 251 if (!I->hasLocalLinkage() || I->isThreadLocal() || I->hasSection()) 252 continue; 253 254 PointerType *PT = dyn_cast<PointerType>(I->getType()); 255 assert(PT && "Global variable is not a pointer!"); 256 257 unsigned AddressSpace = PT->getAddressSpace(); 258 259 // Ignore fancy-aligned globals for now. 260 unsigned Alignment = TD->getPreferredAlignment(I); 261 Type *Ty = I->getType()->getElementType(); 262 if (Alignment > TD->getABITypeAlignment(Ty)) 263 continue; 264 265 // Ignore all 'special' globals. 266 if (I->getName().startswith("llvm.") || 267 I->getName().startswith(".llvm.")) 268 continue; 269 270 // Ignore all "required" globals: 271 // - the ones used for EH 272 // - the ones marked with "used" attribute 273 if (isMustKeepGlobalVariable(I)) 274 continue; 275 276 if (TD->getTypeAllocSize(Ty) < MaxOffset) { 277 if (TargetLoweringObjectFile::getKindForGlobal(I, TLI->getTargetMachine()) 278 .isBSSLocal()) 279 BSSGlobals[AddressSpace].push_back(I); 280 else if (I->isConstant()) 281 ConstGlobals[AddressSpace].push_back(I); 282 else 283 Globals[AddressSpace].push_back(I); 284 } 285 } 286 287 for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 288 I = Globals.begin(), E = Globals.end(); I != E; ++I) 289 if (I->second.size() > 1) 290 Changed |= doMerge(I->second, M, false, I->first); 291 292 for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 293 I = BSSGlobals.begin(), E = BSSGlobals.end(); I != E; ++I) 294 if (I->second.size() > 1) 295 Changed |= doMerge(I->second, M, false, I->first); 296 297 if (EnableGlobalMergeOnConst) 298 for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 299 I = ConstGlobals.begin(), E = ConstGlobals.end(); I != E; ++I) 300 if (I->second.size() > 1) 301 Changed |= doMerge(I->second, M, true, I->first); 302 303 return Changed; 304} 305 306bool GlobalMerge::runOnFunction(Function &F) { 307 return false; 308} 309 310Pass *llvm::createGlobalMergePass(const TargetLowering *tli) { 311 return new GlobalMerge(tli); 312} 313