Home | History | Annotate | Download | only in Scalar
      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/Instructions.h"
     65 #include "llvm/IR/Intrinsics.h"
     66 #include "llvm/IR/Module.h"
     67 #include "llvm/Pass.h"
     68 #include "llvm/Support/CommandLine.h"
     69 #include "llvm/Target/TargetLowering.h"
     70 #include "llvm/Target/TargetLoweringObjectFile.h"
     71 using namespace llvm;
     72 
     73 static cl::opt<bool>
     74 EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden,
     75                          cl::desc("Enable global merge pass on constants"),
     76                          cl::init(false));
     77 
     78 STATISTIC(NumMerged      , "Number of globals merged");
     79 namespace {
     80   class GlobalMerge : public FunctionPass {
     81     const TargetMachine *TM;
     82 
     83     bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
     84                  Module &M, bool isConst, unsigned AddrSpace) const;
     85 
     86     /// \brief Check if the given variable has been identified as must keep
     87     /// \pre setMustKeepGlobalVariables must have been called on the Module that
     88     ///      contains GV
     89     bool isMustKeepGlobalVariable(const GlobalVariable *GV) const {
     90       return MustKeepGlobalVariables.count(GV);
     91     }
     92 
     93     /// Collect every variables marked as "used" or used in a landing pad
     94     /// instruction for this Module.
     95     void setMustKeepGlobalVariables(Module &M);
     96 
     97     /// Collect every variables marked as "used"
     98     void collectUsedGlobalVariables(Module &M);
     99 
    100     /// Keep track of the GlobalVariable that must not be merged away
    101     SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables;
    102 
    103   public:
    104     static char ID;             // Pass identification, replacement for typeid.
    105     explicit GlobalMerge(const TargetMachine *TM = 0)
    106       : FunctionPass(ID), TM(TM) {
    107       initializeGlobalMergePass(*PassRegistry::getPassRegistry());
    108     }
    109 
    110     virtual bool doInitialization(Module &M);
    111     virtual bool runOnFunction(Function &F);
    112     virtual bool doFinalization(Module &M);
    113 
    114     const char *getPassName() const {
    115       return "Merge internal globals";
    116     }
    117 
    118     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
    119       AU.setPreservesCFG();
    120       FunctionPass::getAnalysisUsage(AU);
    121     }
    122 
    123     struct GlobalCmp {
    124       const DataLayout *TD;
    125 
    126       GlobalCmp(const DataLayout *td) : TD(td) { }
    127 
    128       bool operator()(const GlobalVariable *GV1, const GlobalVariable *GV2) {
    129         Type *Ty1 = cast<PointerType>(GV1->getType())->getElementType();
    130         Type *Ty2 = cast<PointerType>(GV2->getType())->getElementType();
    131 
    132         return (TD->getTypeAllocSize(Ty1) < TD->getTypeAllocSize(Ty2));
    133       }
    134     };
    135   };
    136 } // end anonymous namespace
    137 
    138 char GlobalMerge::ID = 0;
    139 INITIALIZE_PASS(GlobalMerge, "global-merge",
    140                 "Global Merge", false, false)
    141 
    142 
    143 bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
    144                           Module &M, bool isConst, unsigned AddrSpace) const {
    145   const TargetLowering *TLI = TM->getTargetLowering();
    146   const DataLayout *TD = TLI->getDataLayout();
    147 
    148   // FIXME: Infer the maximum possible offset depending on the actual users
    149   // (these max offsets are different for the users inside Thumb or ARM
    150   // functions)
    151   unsigned MaxOffset = TLI->getMaximalGlobalOffset();
    152 
    153   // FIXME: Find better heuristics
    154   std::stable_sort(Globals.begin(), Globals.end(), GlobalCmp(TD));
    155 
    156   Type *Int32Ty = Type::getInt32Ty(M.getContext());
    157 
    158   for (size_t i = 0, e = Globals.size(); i != e; ) {
    159     size_t j = 0;
    160     uint64_t MergedSize = 0;
    161     std::vector<Type*> Tys;
    162     std::vector<Constant*> Inits;
    163     for (j = i; j != e; ++j) {
    164       Type *Ty = Globals[j]->getType()->getElementType();
    165       MergedSize += TD->getTypeAllocSize(Ty);
    166       if (MergedSize > MaxOffset) {
    167         break;
    168       }
    169       Tys.push_back(Ty);
    170       Inits.push_back(Globals[j]->getInitializer());
    171     }
    172 
    173     StructType *MergedTy = StructType::get(M.getContext(), Tys);
    174     Constant *MergedInit = ConstantStruct::get(MergedTy, Inits);
    175     GlobalVariable *MergedGV = new GlobalVariable(M, MergedTy, isConst,
    176                                                   GlobalValue::InternalLinkage,
    177                                                   MergedInit, "_MergedGlobals",
    178                                                   0, GlobalVariable::NotThreadLocal,
    179                                                   AddrSpace);
    180     for (size_t k = i; k < j; ++k) {
    181       Constant *Idx[2] = {
    182         ConstantInt::get(Int32Ty, 0),
    183         ConstantInt::get(Int32Ty, k-i)
    184       };
    185       Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx);
    186       Globals[k]->replaceAllUsesWith(GEP);
    187       Globals[k]->eraseFromParent();
    188       NumMerged++;
    189     }
    190     i = j;
    191   }
    192 
    193   return true;
    194 }
    195 
    196 void GlobalMerge::collectUsedGlobalVariables(Module &M) {
    197   // Extract global variables from llvm.used array
    198   const GlobalVariable *GV = M.getGlobalVariable("llvm.used");
    199   if (!GV || !GV->hasInitializer()) return;
    200 
    201   // Should be an array of 'i8*'.
    202   const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer());
    203 
    204   for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i)
    205     if (const GlobalVariable *G =
    206         dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts()))
    207       MustKeepGlobalVariables.insert(G);
    208 }
    209 
    210 void GlobalMerge::setMustKeepGlobalVariables(Module &M) {
    211   collectUsedGlobalVariables(M);
    212 
    213   for (Module::iterator IFn = M.begin(), IEndFn = M.end(); IFn != IEndFn;
    214        ++IFn) {
    215     for (Function::iterator IBB = IFn->begin(), IEndBB = IFn->end();
    216          IBB != IEndBB; ++IBB) {
    217       // Follow the inwoke link to find the landing pad instruction
    218       const InvokeInst *II = dyn_cast<InvokeInst>(IBB->getTerminator());
    219       if (!II) continue;
    220 
    221       const LandingPadInst *LPInst = II->getUnwindDest()->getLandingPadInst();
    222       // Look for globals in the clauses of the landing pad instruction
    223       for (unsigned Idx = 0, NumClauses = LPInst->getNumClauses();
    224            Idx != NumClauses; ++Idx)
    225         if (const GlobalVariable *GV =
    226             dyn_cast<GlobalVariable>(LPInst->getClause(Idx)
    227                                      ->stripPointerCasts()))
    228           MustKeepGlobalVariables.insert(GV);
    229     }
    230   }
    231 }
    232 
    233 bool GlobalMerge::doInitialization(Module &M) {
    234   DenseMap<unsigned, SmallVector<GlobalVariable*, 16> > Globals, ConstGlobals,
    235                                                         BSSGlobals;
    236   const TargetLowering *TLI = TM->getTargetLowering();
    237   const DataLayout *TD = TLI->getDataLayout();
    238   unsigned MaxOffset = TLI->getMaximalGlobalOffset();
    239   bool Changed = false;
    240   setMustKeepGlobalVariables(M);
    241 
    242   // Grab all non-const globals.
    243   for (Module::global_iterator I = M.global_begin(),
    244          E = M.global_end(); I != E; ++I) {
    245     // Merge is safe for "normal" internal globals only
    246     if (!I->hasLocalLinkage() || I->isThreadLocal() || I->hasSection())
    247       continue;
    248 
    249     PointerType *PT = dyn_cast<PointerType>(I->getType());
    250     assert(PT && "Global variable is not a pointer!");
    251 
    252     unsigned AddressSpace = PT->getAddressSpace();
    253 
    254     // Ignore fancy-aligned globals for now.
    255     unsigned Alignment = TD->getPreferredAlignment(I);
    256     Type *Ty = I->getType()->getElementType();
    257     if (Alignment > TD->getABITypeAlignment(Ty))
    258       continue;
    259 
    260     // Ignore all 'special' globals.
    261     if (I->getName().startswith("llvm.") ||
    262         I->getName().startswith(".llvm."))
    263       continue;
    264 
    265     // Ignore all "required" globals:
    266     if (isMustKeepGlobalVariable(I))
    267       continue;
    268 
    269     if (TD->getTypeAllocSize(Ty) < MaxOffset) {
    270       if (TargetLoweringObjectFile::getKindForGlobal(I, TLI->getTargetMachine())
    271           .isBSSLocal())
    272         BSSGlobals[AddressSpace].push_back(I);
    273       else if (I->isConstant())
    274         ConstGlobals[AddressSpace].push_back(I);
    275       else
    276         Globals[AddressSpace].push_back(I);
    277     }
    278   }
    279 
    280   for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator
    281        I = Globals.begin(), E = Globals.end(); I != E; ++I)
    282     if (I->second.size() > 1)
    283       Changed |= doMerge(I->second, M, false, I->first);
    284 
    285   for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator
    286        I = BSSGlobals.begin(), E = BSSGlobals.end(); I != E; ++I)
    287     if (I->second.size() > 1)
    288       Changed |= doMerge(I->second, M, false, I->first);
    289 
    290   if (EnableGlobalMergeOnConst)
    291     for (DenseMap<unsigned, SmallVector<GlobalVariable*, 16> >::iterator
    292          I = ConstGlobals.begin(), E = ConstGlobals.end(); I != E; ++I)
    293       if (I->second.size() > 1)
    294         Changed |= doMerge(I->second, M, true, I->first);
    295 
    296   return Changed;
    297 }
    298 
    299 bool GlobalMerge::runOnFunction(Function &F) {
    300   return false;
    301 }
    302 
    303 bool GlobalMerge::doFinalization(Module &M) {
    304   MustKeepGlobalVariables.clear();
    305   return false;
    306 }
    307 
    308 Pass *llvm::createGlobalMergePass(const TargetMachine *TM) {
    309   return new GlobalMerge(TM);
    310 }
    311