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/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