1827454e6e28cfed93db990b03b720ef7c23e6917Devang Patel//===-- GlobalMerge.cpp - Internal globals merging -----------------------===// 2cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 3cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// The LLVM Compiler Infrastructure 4cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 5cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// This file is distributed under the University of Illinois Open Source 6cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// License. See LICENSE.TXT for details. 7cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 8cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov//===----------------------------------------------------------------------===// 9cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// This pass merges globals with internal linkage into one. This way all the 10cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// globals which were merged into a biggest one can be addressed using offsets 11cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// from the same base pointer (no need for separate base pointer for each of the 12cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// global). Such a transformation can significantly reduce the register pressure 13cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// when many globals are involved. 14cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 15a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem// For example, consider the code which touches several global variables at 16a99c3e9acd95f5fbfb611e3f807240cd74001142Eric Christopher// once: 17cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 18cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// static int foo[N], bar[N], baz[N]; 19cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 20cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// for (i = 0; i < N; ++i) { 21cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// foo[i] = bar[i] * baz[i]; 22cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// } 23cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 24cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// On ARM the addresses of 3 arrays should be kept in the registers, thus 25cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// this code has quite large register pressure (loop body): 26cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 27cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// ldr r1, [r5], #4 28cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// ldr r2, [r6], #4 29cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// mul r1, r2, r1 30cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// str r1, [r0], #4 31cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 32cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// Pass converts the code to something like: 33cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 34cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// static struct { 35cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// int foo[N]; 36cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// int bar[N]; 37cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// int baz[N]; 38cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// } merged; 39cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 40cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// for (i = 0; i < N; ++i) { 41cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// merged.foo[i] = merged.bar[i] * merged.baz[i]; 42cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// } 43cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 44cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// and in ARM code this becomes: 45cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 46cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// ldr r0, [r5, #40] 47cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// ldr r1, [r5, #80] 48cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// mul r0, r1, r0 49cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// str r0, [r5], #4 50cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// 51cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov// note that we saved 2 registers here almostly "for free". 52a99c3e9acd95f5fbfb611e3f807240cd74001142Eric Christopher// ===---------------------------------------------------------------------===// 53cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 54827454e6e28cfed93db990b03b720ef7c23e6917Devang Patel#include "llvm/Transforms/Scalar.h" 55e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet#include "llvm/ADT/SmallPtrSet.h" 56d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 570b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Attributes.h" 580b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 590b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 600b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 610b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 620b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 630b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 640b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Intrinsics.h" 650b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 66cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov#include "llvm/Pass.h" 67cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/CodeGen/Passes.h" 68e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet#include "llvm/Support/CommandLine.h" 69cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov#include "llvm/Target/TargetLowering.h" 7005646099a0b7ebd97571354d658a142e4e4c94c7Bob Wilson#include "llvm/Target/TargetLoweringObjectFile.h" 71cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikovusing namespace llvm; 72cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "global-merge" 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinescl::opt<bool> 76cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesEnableGlobalMerge("enable-global-merge", cl::Hidden, 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::desc("Enable global merge pass"), 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::init(true)); 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 80e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombetstatic cl::opt<bool> 81e572809aa153f37a7a17726f9aac26598d60e57cQuentin ColombetEnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, 82dca13e0b3fd9d0f3ba371485cc51a015a60f837fJakub Staszak cl::desc("Enable global merge pass on constants"), 83dca13e0b3fd9d0f3ba371485cc51a015a60f837fJakub Staszak cl::init(false)); 84e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 85cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// FIXME: this could be a transitional option, and we probably need to remove 86cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// it if only we are sure this optimization could always benefit all targets. 87cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesstatic cl::opt<bool> 88cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesEnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden, 89cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines cl::desc("Enable global merge pass on external linkage"), 90cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines cl::init(false)); 91cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 92827454e6e28cfed93db990b03b720ef7c23e6917Devang PatelSTATISTIC(NumMerged , "Number of globals merged"); 93cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikovnamespace { 94827454e6e28cfed93db990b03b720ef7c23e6917Devang Patel class GlobalMerge : public FunctionPass { 95f9fd58a44bbc7d9371ce39eb20eec16b0f1f7395Bill Wendling const TargetMachine *TM; 96cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 97cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 98e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga Module &M, bool isConst, unsigned AddrSpace) const; 99cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 100e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet /// \brief Check if the given variable has been identified as must keep 101e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet /// \pre setMustKeepGlobalVariables must have been called on the Module that 102e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet /// contains GV 103e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet bool isMustKeepGlobalVariable(const GlobalVariable *GV) const { 104e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet return MustKeepGlobalVariables.count(GV); 105e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet } 106e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 107e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet /// Collect every variables marked as "used" or used in a landing pad 108e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet /// instruction for this Module. 109e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet void setMustKeepGlobalVariables(Module &M); 110e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 111e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet /// Collect every variables marked as "used" 112e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet void collectUsedGlobalVariables(Module &M); 113e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 1149deb91722cc4a7e0aa220b0a210c56ac95c62d73Quentin Colombet /// Keep track of the GlobalVariable that must not be merged away 115e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables; 116e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 117cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov public: 118cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov static char ID; // Pass identification, replacement for typeid. 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines explicit GlobalMerge(const TargetMachine *TM = nullptr) 120f9fd58a44bbc7d9371ce39eb20eec16b0f1f7395Bill Wendling : FunctionPass(ID), TM(TM) { 121827454e6e28cfed93db990b03b720ef7c23e6917Devang Patel initializeGlobalMergePass(*PassRegistry::getPassRegistry()); 122827454e6e28cfed93db990b03b720ef7c23e6917Devang Patel } 123cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool doInitialization(Module &M) override; 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool doFinalization(Module &M) override; 127cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const char *getPassName() const override { 129cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov return "Merge internal globals"; 130cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov } 131cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 133cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov AU.setPreservesCFG(); 134cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov FunctionPass::getAnalysisUsage(AU); 135cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov } 136cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov }; 137cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov} // end anonymous namespace 138cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 139827454e6e28cfed93db990b03b720ef7c23e6917Devang Patelchar GlobalMerge::ID = 0; 140cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesINITIALIZE_TM_PASS(GlobalMerge, "global-merge", "Merge global variables", 141cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines false, false) 142cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 143827454e6e28cfed93db990b03b720ef7c23e6917Devang Patelbool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals, 144e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga Module &M, bool isConst, unsigned AddrSpace) const { 145f9fd58a44bbc7d9371ce39eb20eec16b0f1f7395Bill Wendling const TargetLowering *TLI = TM->getTargetLowering(); 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL = TLI->getDataLayout(); 147cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 148cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov // FIXME: Infer the maximum possible offset depending on the actual users 149cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov // (these max offsets are different for the users inside Thumb or ARM 150cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov // functions) 151cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 152cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 153cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov // FIXME: Find better heuristics 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::stable_sort(Globals.begin(), Globals.end(), 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines [DL](const GlobalVariable *GV1, const GlobalVariable *GV2) { 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *Ty1 = cast<PointerType>(GV1->getType())->getElementType(); 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type *Ty2 = cast<PointerType>(GV2->getType())->getElementType(); 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return (DL->getTypeAllocSize(Ty1) < DL->getTypeAllocSize(Ty2)); 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }); 161cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 162db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Int32Ty = Type::getInt32Ty(M.getContext()); 163cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 164cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert(Globals.size() > 1); 165cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 166cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // FIXME: This simple solution merges globals all together as maximum as 167cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // possible. However, with this solution it would be hard to remove dead 168cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // global symbols at link-time. An alternative solution could be checking 169cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // global symbols references function by function, and make the symbols 170cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // being referred in the same function merged and we would probably need 171cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // to introduce heuristic algorithm to solve the merge conflict from 172cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // different functions. 173cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov for (size_t i = 0, e = Globals.size(); i != e; ) { 174cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov size_t j = 0; 175cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov uint64_t MergedSize = 0; 1765fdd6c8793462549e3593890ec61573da06e3346Jay Foad std::vector<Type*> Tys; 177cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov std::vector<Constant*> Inits; 178cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 179cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool HasExternal = false; 180cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GlobalVariable *TheFirstExternal = 0; 181619a3726177c63a14e2822a80e6bc897be2e5a91Bob Wilson for (j = i; j != e; ++j) { 1825fdd6c8793462549e3593890ec61573da06e3346Jay Foad Type *Ty = Globals[j]->getType()->getElementType(); 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MergedSize += DL->getTypeAllocSize(Ty); 184619a3726177c63a14e2822a80e6bc897be2e5a91Bob Wilson if (MergedSize > MaxOffset) { 185619a3726177c63a14e2822a80e6bc897be2e5a91Bob Wilson break; 186619a3726177c63a14e2822a80e6bc897be2e5a91Bob Wilson } 187cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov Tys.push_back(Ty); 188cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov Inits.push_back(Globals[j]->getInitializer()); 189cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 190cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Globals[j]->hasExternalLinkage() && !HasExternal) { 191cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines HasExternal = true; 192cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines TheFirstExternal = Globals[j]; 193cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 194cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov } 195cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 196cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If merged variables doesn't have external linkage, we needn't to expose 197cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // the symbol after merging. 198cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GlobalValue::LinkageTypes Linkage = HasExternal 199cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ? GlobalValue::ExternalLinkage 200cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : GlobalValue::InternalLinkage; 201cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 202252b491875c544335406fb461be0fed8649e3814Chris Lattner StructType *MergedTy = StructType::get(M.getContext(), Tys); 203252b491875c544335406fb461be0fed8649e3814Chris Lattner Constant *MergedInit = ConstantStruct::get(MergedTy, Inits); 204cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 205cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If merged variables have external linkage, we use symbol name of the 206cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // first variable merged as the suffix of global symbol name. This would 207cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // be able to avoid the link-time naming conflict for globalm symbols. 208cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GlobalVariable *MergedGV = new GlobalVariable( 209cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines M, MergedTy, isConst, Linkage, MergedInit, 210cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines HasExternal ? "_MergedGlobals_" + TheFirstExternal->getName() 211cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : "_MergedGlobals", 212cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines nullptr, GlobalVariable::NotThreadLocal, AddrSpace); 213cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 214cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov for (size_t k = i; k < j; ++k) { 215cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage(); 216cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::string Name = Globals[k]->getName(); 217cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 218252b491875c544335406fb461be0fed8649e3814Chris Lattner Constant *Idx[2] = { 219252b491875c544335406fb461be0fed8649e3814Chris Lattner ConstantInt::get(Int32Ty, 0), 220252b491875c544335406fb461be0fed8649e3814Chris Lattner ConstantInt::get(Int32Ty, k-i) 221252b491875c544335406fb461be0fed8649e3814Chris Lattner }; 222dab3d29605a5c83db41b28176273ef55961120c1Jay Foad Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx); 223cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov Globals[k]->replaceAllUsesWith(GEP); 224cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov Globals[k]->eraseFromParent(); 225cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 226cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Linkage != GlobalValue::InternalLinkage) { 227cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Generate a new alias... 228cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines auto *PTy = cast<PointerType>(GEP->getType()); 229cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines GlobalAlias::create(PTy->getElementType(), PTy->getAddressSpace(), 230cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Linkage, Name, GEP, &M); 231cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 232cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 233827454e6e28cfed93db990b03b720ef7c23e6917Devang Patel NumMerged++; 234cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov } 235cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov i = j; 236cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov } 237cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 238cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov return true; 239cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov} 240cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 241e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombetvoid GlobalMerge::collectUsedGlobalVariables(Module &M) { 242e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet // Extract global variables from llvm.used array 243e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet const GlobalVariable *GV = M.getGlobalVariable("llvm.used"); 244e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet if (!GV || !GV->hasInitializer()) return; 245e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 246e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet // Should be an array of 'i8*'. 247cde25b435a907e7741da0c0d18953850936277c4Rafael Espindola const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer()); 248cde25b435a907e7741da0c0d18953850936277c4Rafael Espindola 249e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) 250e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet if (const GlobalVariable *G = 251e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts())) 252e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet MustKeepGlobalVariables.insert(G); 253e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet} 254e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 255e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombetvoid GlobalMerge::setMustKeepGlobalVariables(Module &M) { 256e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet collectUsedGlobalVariables(M); 257e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 258e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet for (Module::iterator IFn = M.begin(), IEndFn = M.end(); IFn != IEndFn; 259e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet ++IFn) { 260e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet for (Function::iterator IBB = IFn->begin(), IEndBB = IFn->end(); 261e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet IBB != IEndBB; ++IBB) { 26236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Follow the invoke link to find the landing pad instruction 263e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet const InvokeInst *II = dyn_cast<InvokeInst>(IBB->getTerminator()); 264e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet if (!II) continue; 265e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 266e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet const LandingPadInst *LPInst = II->getUnwindDest()->getLandingPadInst(); 267e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet // Look for globals in the clauses of the landing pad instruction 268e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet for (unsigned Idx = 0, NumClauses = LPInst->getNumClauses(); 269e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet Idx != NumClauses; ++Idx) 270e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet if (const GlobalVariable *GV = 271e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet dyn_cast<GlobalVariable>(LPInst->getClause(Idx) 272e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet ->stripPointerCasts())) 273e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet MustKeepGlobalVariables.insert(GV); 274e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet } 275e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet } 276e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet} 277cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 278827454e6e28cfed93db990b03b720ef7c23e6917Devang Patelbool GlobalMerge::doInitialization(Module &M) { 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!EnableGlobalMerge) 28036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 282e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga DenseMap<unsigned, SmallVector<GlobalVariable*, 16> > Globals, ConstGlobals, 283e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga BSSGlobals; 284f9fd58a44bbc7d9371ce39eb20eec16b0f1f7395Bill Wendling const TargetLowering *TLI = TM->getTargetLowering(); 28536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL = TLI->getDataLayout(); 286cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov unsigned MaxOffset = TLI->getMaximalGlobalOffset(); 287cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov bool Changed = false; 288e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet setMustKeepGlobalVariables(M); 289cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 290cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov // Grab all non-const globals. 291cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov for (Module::global_iterator I = M.global_begin(), 292cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov E = M.global_end(); I != E; ++I) { 293cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Merge is safe for "normal" internal or external globals only 294cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (I->isDeclaration() || I->isThreadLocal() || I->hasSection()) 295cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines continue; 296cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 297cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!(EnableGlobalMergeOnExternal && I->hasExternalLinkage()) && 298cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines !I->hasInternalLinkage()) 299cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov continue; 300cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 301e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga PointerType *PT = dyn_cast<PointerType>(I->getType()); 302e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga assert(PT && "Global variable is not a pointer!"); 303e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga 304e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga unsigned AddressSpace = PT->getAddressSpace(); 305e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga 306cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov // Ignore fancy-aligned globals for now. 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned Alignment = DL->getPreferredAlignment(I); 308db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Ty = I->getType()->getElementType(); 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Alignment > DL->getABITypeAlignment(Ty)) 310cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov continue; 311cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 312b5a0ef99f8e2bd48f2fb2a3221d296d48f1d5940Anton Korobeynikov // Ignore all 'special' globals. 313b5a0ef99f8e2bd48f2fb2a3221d296d48f1d5940Anton Korobeynikov if (I->getName().startswith("llvm.") || 314b5a0ef99f8e2bd48f2fb2a3221d296d48f1d5940Anton Korobeynikov I->getName().startswith(".llvm.")) 315b5a0ef99f8e2bd48f2fb2a3221d296d48f1d5940Anton Korobeynikov continue; 316b5a0ef99f8e2bd48f2fb2a3221d296d48f1d5940Anton Korobeynikov 317e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet // Ignore all "required" globals: 318e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet if (isMustKeepGlobalVariable(I)) 319e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet continue; 320e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet 32136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DL->getTypeAllocSize(Ty) < MaxOffset) { 322cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (TargetLoweringObjectFile::getKindForGlobal(I, *TM).isBSSLocal()) 323e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga BSSGlobals[AddressSpace].push_back(I); 32405646099a0b7ebd97571354d658a142e4e4c94c7Bob Wilson else if (I->isConstant()) 325e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga ConstGlobals[AddressSpace].push_back(I); 326cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov else 327e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga Globals[AddressSpace].push_back(I); 328cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov } 329cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov } 330cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 331e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 332e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga I = Globals.begin(), E = Globals.end(); I != E; ++I) 333e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga if (I->second.size() > 1) 334e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga Changed |= doMerge(I->second, M, false, I->first); 335e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga 336e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 337e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga I = BSSGlobals.begin(), E = BSSGlobals.end(); I != E; ++I) 338e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga if (I->second.size() > 1) 339e97165901ee51216b22b808041b10febbb4afa5eSilviu Baranga Changed |= doMerge(I->second, M, false, I->first); 34005646099a0b7ebd97571354d658a142e4e4c94c7Bob Wilson 341e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet if (EnableGlobalMergeOnConst) 342e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator 343e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet I = ConstGlobals.begin(), E = ConstGlobals.end(); I != E; ++I) 344e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet if (I->second.size() > 1) 345e572809aa153f37a7a17726f9aac26598d60e57cQuentin Colombet Changed |= doMerge(I->second, M, true, I->first); 346cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 347cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov return Changed; 348cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov} 349cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 350827454e6e28cfed93db990b03b720ef7c23e6917Devang Patelbool GlobalMerge::runOnFunction(Function &F) { 351cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov return false; 352cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov} 353cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov 3549deb91722cc4a7e0aa220b0a210c56ac95c62d73Quentin Colombetbool GlobalMerge::doFinalization(Module &M) { 3559deb91722cc4a7e0aa220b0a210c56ac95c62d73Quentin Colombet MustKeepGlobalVariables.clear(); 3569deb91722cc4a7e0aa220b0a210c56ac95c62d73Quentin Colombet return false; 3579deb91722cc4a7e0aa220b0a210c56ac95c62d73Quentin Colombet} 3589deb91722cc4a7e0aa220b0a210c56ac95c62d73Quentin Colombet 359f9fd58a44bbc7d9371ce39eb20eec16b0f1f7395Bill WendlingPass *llvm::createGlobalMergePass(const TargetMachine *TM) { 360f9fd58a44bbc7d9371ce39eb20eec16b0f1f7395Bill Wendling return new GlobalMerge(TM); 361cec36f4c1118dc8388910d4753fe7cbf88d2d793Anton Korobeynikov} 362