GlobalMerge.cpp revision e97165901ee51216b22b808041b10febbb4afa5e
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/Statistic.h" 57#include "llvm/IR/Attributes.h" 58#include "llvm/IR/Constants.h" 59#include "llvm/IR/DataLayout.h" 60#include "llvm/IR/DerivedTypes.h" 61#include "llvm/IR/Function.h" 62#include "llvm/IR/GlobalVariable.h" 63#include "llvm/IR/Instructions.h" 64#include "llvm/IR/Intrinsics.h" 65#include "llvm/IR/Module.h" 66#include "llvm/Pass.h" 67#include "llvm/Target/TargetLowering.h" 68#include "llvm/Target/TargetLoweringObjectFile.h" 69using namespace llvm; 70 71STATISTIC(NumMerged , "Number of globals merged"); 72namespace { 73 class GlobalMerge : public FunctionPass { 74 /// TLI - Keep a pointer of a TargetLowering to consult for determining 75 /// target type sizes. 76 const TargetLowering *TLI; 77 78 bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 79 Module &M, bool isConst, unsigned AddrSpace) const; 80 81 public: 82 static char ID; // Pass identification, replacement for typeid. 83 explicit GlobalMerge(const TargetLowering *tli = 0) 84 : FunctionPass(ID), TLI(tli) { 85 initializeGlobalMergePass(*PassRegistry::getPassRegistry()); 86 } 87 88 virtual bool doInitialization(Module &M); 89 virtual bool runOnFunction(Function &F); 90 91 const char *getPassName() const { 92 return "Merge internal globals"; 93 } 94 95 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 96 AU.setPreservesCFG(); 97 FunctionPass::getAnalysisUsage(AU); 98 } 99 100 struct GlobalCmp { 101 const DataLayout *TD; 102 103 GlobalCmp(const DataLayout *td) : TD(td) { } 104 105 bool operator()(const GlobalVariable *GV1, const GlobalVariable *GV2) { 106 Type *Ty1 = cast<PointerType>(GV1->getType())->getElementType(); 107 Type *Ty2 = cast<PointerType>(GV2->getType())->getElementType(); 108 109 return (TD->getTypeAllocSize(Ty1) < TD->getTypeAllocSize(Ty2)); 110 } 111 }; 112 }; 113} // end anonymous namespace 114 115char GlobalMerge::ID = 0; 116INITIALIZE_PASS(GlobalMerge, "global-merge", 117 "Global Merge", false, false) 118 119 120bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 121 Module &M, bool isConst, unsigned AddrSpace) const { 122 const DataLayout *TD = TLI->getDataLayout(); 123 124 // FIXME: Infer the maximum possible offset depending on the actual users 125 // (these max offsets are different for the users inside Thumb or ARM 126 // functions) 127 unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 128 129 // FIXME: Find better heuristics 130 std::stable_sort(Globals.begin(), Globals.end(), GlobalCmp(TD)); 131 132 Type *Int32Ty = Type::getInt32Ty(M.getContext()); 133 134 for (size_t i = 0, e = Globals.size(); i != e; ) { 135 size_t j = 0; 136 uint64_t MergedSize = 0; 137 std::vector<Type*> Tys; 138 std::vector<Constant*> Inits; 139 for (j = i; j != e; ++j) { 140 Type *Ty = Globals[j]->getType()->getElementType(); 141 MergedSize += TD->getTypeAllocSize(Ty); 142 if (MergedSize > MaxOffset) { 143 break; 144 } 145 Tys.push_back(Ty); 146 Inits.push_back(Globals[j]->getInitializer()); 147 } 148 149 StructType *MergedTy = StructType::get(M.getContext(), Tys); 150 Constant *MergedInit = ConstantStruct::get(MergedTy, Inits); 151 GlobalVariable *MergedGV = new GlobalVariable(M, MergedTy, isConst, 152 GlobalValue::InternalLinkage, 153 MergedInit, "_MergedGlobals", 154 0, GlobalVariable::NotThreadLocal, 155 AddrSpace); 156 for (size_t k = i; k < j; ++k) { 157 Constant *Idx[2] = { 158 ConstantInt::get(Int32Ty, 0), 159 ConstantInt::get(Int32Ty, k-i) 160 }; 161 Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx); 162 Globals[k]->replaceAllUsesWith(GEP); 163 Globals[k]->eraseFromParent(); 164 NumMerged++; 165 } 166 i = j; 167 } 168 169 return true; 170} 171 172 173bool GlobalMerge::doInitialization(Module &M) { 174 DenseMap<unsigned, SmallVector<GlobalVariable*, 16> > Globals, ConstGlobals, 175 BSSGlobals; 176 const DataLayout *TD = TLI->getDataLayout(); 177 unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 178 bool Changed = false; 179 180 // Grab all non-const globals. 181 for (Module::global_iterator I = M.global_begin(), 182 E = M.global_end(); I != E; ++I) { 183 // Merge is safe for "normal" internal globals only 184 if (!I->hasLocalLinkage() || I->isThreadLocal() || I->hasSection()) 185 continue; 186 187 PointerType *PT = dyn_cast<PointerType>(I->getType()); 188 assert(PT && "Global variable is not a pointer!"); 189 190 unsigned AddressSpace = PT->getAddressSpace(); 191 192 // Ignore fancy-aligned globals for now. 193 unsigned Alignment = TD->getPreferredAlignment(I); 194 Type *Ty = I->getType()->getElementType(); 195 if (Alignment > TD->getABITypeAlignment(Ty)) 196 continue; 197 198 // Ignore all 'special' globals. 199 if (I->getName().startswith("llvm.") || 200 I->getName().startswith(".llvm.")) 201 continue; 202 203 if (TD->getTypeAllocSize(Ty) < MaxOffset) { 204 if (TargetLoweringObjectFile::getKindForGlobal(I, TLI->getTargetMachine()) 205 .isBSSLocal()) 206 BSSGlobals[AddressSpace].push_back(I); 207 else if (I->isConstant()) 208 ConstGlobals[AddressSpace].push_back(I); 209 else 210 Globals[AddressSpace].push_back(I); 211 } 212 } 213 214 for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 215 I = Globals.begin(), E = Globals.end(); I != E; ++I) 216 if (I->second.size() > 1) 217 Changed |= doMerge(I->second, M, false, I->first); 218 219 for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 220 I = BSSGlobals.begin(), E = BSSGlobals.end(); I != E; ++I) 221 if (I->second.size() > 1) 222 Changed |= doMerge(I->second, M, false, I->first); 223 224 // FIXME: This currently breaks the EH processing due to way how the 225 // typeinfo detection works. We might want to detect the TIs and ignore 226 // them in the future. 227 // if (ConstGlobals.size() > 1) 228 // Changed |= doMerge(ConstGlobals, M, true); 229 230 return Changed; 231} 232 233bool GlobalMerge::runOnFunction(Function &F) { 234 return false; 235} 236 237Pass *llvm::createGlobalMergePass(const TargetLowering *tli) { 238 return new GlobalMerge(tli); 239} 240