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/Attributes.h" 57 #include "llvm/Constants.h" 58 #include "llvm/DerivedTypes.h" 59 #include "llvm/Function.h" 60 #include "llvm/GlobalVariable.h" 61 #include "llvm/Instructions.h" 62 #include "llvm/Intrinsics.h" 63 #include "llvm/Module.h" 64 #include "llvm/Pass.h" 65 #include "llvm/Target/TargetData.h" 66 #include "llvm/Target/TargetLowering.h" 67 #include "llvm/Target/TargetLoweringObjectFile.h" 68 #include "llvm/ADT/Statistic.h" 69 using namespace llvm; 70 71 STATISTIC(NumMerged , "Number of globals merged"); 72 namespace { 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) 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 TargetData *TD; 102 103 GlobalCmp(const TargetData *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 115 char GlobalMerge::ID = 0; 116 INITIALIZE_PASS(GlobalMerge, "global-merge", 117 "Global Merge", false, false) 118 119 120 bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 121 Module &M, bool isConst) const { 122 const TargetData *TD = TLI->getTargetData(); 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 for (size_t k = i; k < j; ++k) { 155 Constant *Idx[2] = { 156 ConstantInt::get(Int32Ty, 0), 157 ConstantInt::get(Int32Ty, k-i) 158 }; 159 Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx); 160 Globals[k]->replaceAllUsesWith(GEP); 161 Globals[k]->eraseFromParent(); 162 NumMerged++; 163 } 164 i = j; 165 } 166 167 return true; 168 } 169 170 171 bool GlobalMerge::doInitialization(Module &M) { 172 SmallVector<GlobalVariable*, 16> Globals, ConstGlobals, BSSGlobals; 173 const TargetData *TD = TLI->getTargetData(); 174 unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 175 bool Changed = false; 176 177 // Grab all non-const globals. 178 for (Module::global_iterator I = M.global_begin(), 179 E = M.global_end(); I != E; ++I) { 180 // Merge is safe for "normal" internal globals only 181 if (!I->hasLocalLinkage() || I->isThreadLocal() || I->hasSection()) 182 continue; 183 184 // Ignore fancy-aligned globals for now. 185 unsigned Alignment = TD->getPreferredAlignment(I); 186 Type *Ty = I->getType()->getElementType(); 187 if (Alignment > TD->getABITypeAlignment(Ty)) 188 continue; 189 190 // Ignore all 'special' globals. 191 if (I->getName().startswith("llvm.") || 192 I->getName().startswith(".llvm.")) 193 continue; 194 195 if (TD->getTypeAllocSize(Ty) < MaxOffset) { 196 if (TargetLoweringObjectFile::getKindForGlobal(I, TLI->getTargetMachine()) 197 .isBSSLocal()) 198 BSSGlobals.push_back(I); 199 else if (I->isConstant()) 200 ConstGlobals.push_back(I); 201 else 202 Globals.push_back(I); 203 } 204 } 205 206 if (Globals.size() > 1) 207 Changed |= doMerge(Globals, M, false); 208 if (BSSGlobals.size() > 1) 209 Changed |= doMerge(BSSGlobals, M, false); 210 211 // FIXME: This currently breaks the EH processing due to way how the 212 // typeinfo detection works. We might want to detect the TIs and ignore 213 // them in the future. 214 // if (ConstGlobals.size() > 1) 215 // Changed |= doMerge(ConstGlobals, M, true); 216 217 return Changed; 218 } 219 220 bool GlobalMerge::runOnFunction(Function &F) { 221 return false; 222 } 223 224 Pass *llvm::createGlobalMergePass(const TargetLowering *tli) { 225 return new GlobalMerge(tli); 226 } 227
