]> CyberLeo.Net >> Repos - FreeBSD/releng/10.0.git/blob - contrib/llvm/lib/Transforms/Scalar/GlobalMerge.cpp
- Copy stable/10 (r259064) to releng/10.0 as part of the
[FreeBSD/releng/10.0.git] / contrib / llvm / lib / Transforms / Scalar / GlobalMerge.cpp
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     /// TLI - Keep a pointer of a TargetLowering to consult for determining
82     /// target type sizes.
83     const TargetLowering *TLI;
84
85     bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
86                  Module &M, bool isConst, unsigned AddrSpace) const;
87
88     /// \brief Check if the given variable has been identified as must keep
89     /// \pre setMustKeepGlobalVariables must have been called on the Module that
90     ///      contains GV
91     bool isMustKeepGlobalVariable(const GlobalVariable *GV) const {
92       return MustKeepGlobalVariables.count(GV);
93     }
94
95     /// Collect every variables marked as "used" or used in a landing pad
96     /// instruction for this Module.
97     void setMustKeepGlobalVariables(Module &M);
98
99     /// Collect every variables marked as "used"
100     void collectUsedGlobalVariables(Module &M);
101
102     /// Keep track of the GlobalVariable that must not be merged away
103     SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables;
104
105   public:
106     static char ID;             // Pass identification, replacement for typeid.
107     explicit GlobalMerge(const TargetLowering *tli = 0)
108       : FunctionPass(ID), TLI(tli) {
109       initializeGlobalMergePass(*PassRegistry::getPassRegistry());
110     }
111
112     virtual bool doInitialization(Module &M);
113     virtual bool runOnFunction(Function &F);
114     virtual bool doFinalization(Module &M);
115
116     const char *getPassName() const {
117       return "Merge internal globals";
118     }
119
120     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
121       AU.setPreservesCFG();
122       FunctionPass::getAnalysisUsage(AU);
123     }
124
125     struct GlobalCmp {
126       const DataLayout *TD;
127
128       GlobalCmp(const DataLayout *td) : TD(td) { }
129
130       bool operator()(const GlobalVariable *GV1, const GlobalVariable *GV2) {
131         Type *Ty1 = cast<PointerType>(GV1->getType())->getElementType();
132         Type *Ty2 = cast<PointerType>(GV2->getType())->getElementType();
133
134         return (TD->getTypeAllocSize(Ty1) < TD->getTypeAllocSize(Ty2));
135       }
136     };
137   };
138 } // end anonymous namespace
139
140 char GlobalMerge::ID = 0;
141 INITIALIZE_PASS(GlobalMerge, "global-merge",
142                 "Global Merge", false, false)
143
144
145 bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
146                           Module &M, bool isConst, unsigned AddrSpace) const {
147   const DataLayout *TD = TLI->getDataLayout();
148
149   // FIXME: Infer the maximum possible offset depending on the actual users
150   // (these max offsets are different for the users inside Thumb or ARM
151   // functions)
152   unsigned MaxOffset = TLI->getMaximalGlobalOffset();
153
154   // FIXME: Find better heuristics
155   std::stable_sort(Globals.begin(), Globals.end(), GlobalCmp(TD));
156
157   Type *Int32Ty = Type::getInt32Ty(M.getContext());
158
159   for (size_t i = 0, e = Globals.size(); i != e; ) {
160     size_t j = 0;
161     uint64_t MergedSize = 0;
162     std::vector<Type*> Tys;
163     std::vector<Constant*> Inits;
164     for (j = i; j != e; ++j) {
165       Type *Ty = Globals[j]->getType()->getElementType();
166       MergedSize += TD->getTypeAllocSize(Ty);
167       if (MergedSize > MaxOffset) {
168         break;
169       }
170       Tys.push_back(Ty);
171       Inits.push_back(Globals[j]->getInitializer());
172     }
173
174     StructType *MergedTy = StructType::get(M.getContext(), Tys);
175     Constant *MergedInit = ConstantStruct::get(MergedTy, Inits);
176     GlobalVariable *MergedGV = new GlobalVariable(M, MergedTy, isConst,
177                                                   GlobalValue::InternalLinkage,
178                                                   MergedInit, "_MergedGlobals",
179                                                   0, GlobalVariable::NotThreadLocal,
180                                                   AddrSpace);
181     for (size_t k = i; k < j; ++k) {
182       Constant *Idx[2] = {
183         ConstantInt::get(Int32Ty, 0),
184         ConstantInt::get(Int32Ty, k-i)
185       };
186       Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx);
187       Globals[k]->replaceAllUsesWith(GEP);
188       Globals[k]->eraseFromParent();
189       NumMerged++;
190     }
191     i = j;
192   }
193
194   return true;
195 }
196
197 void GlobalMerge::collectUsedGlobalVariables(Module &M) {
198   // Extract global variables from llvm.used array
199   const GlobalVariable *GV = M.getGlobalVariable("llvm.used");
200   if (!GV || !GV->hasInitializer()) return;
201
202   // Should be an array of 'i8*'.
203   const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer());
204
205   for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i)
206     if (const GlobalVariable *G =
207         dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts()))
208       MustKeepGlobalVariables.insert(G);
209 }
210
211 void GlobalMerge::setMustKeepGlobalVariables(Module &M) {
212   collectUsedGlobalVariables(M);
213
214   for (Module::iterator IFn = M.begin(), IEndFn = M.end(); IFn != IEndFn;
215        ++IFn) {
216     for (Function::iterator IBB = IFn->begin(), IEndBB = IFn->end();
217          IBB != IEndBB; ++IBB) {
218       // Follow the inwoke link to find the landing pad instruction
219       const InvokeInst *II = dyn_cast<InvokeInst>(IBB->getTerminator());
220       if (!II) continue;
221
222       const LandingPadInst *LPInst = II->getUnwindDest()->getLandingPadInst();
223       // Look for globals in the clauses of the landing pad instruction
224       for (unsigned Idx = 0, NumClauses = LPInst->getNumClauses();
225            Idx != NumClauses; ++Idx)
226         if (const GlobalVariable *GV =
227             dyn_cast<GlobalVariable>(LPInst->getClause(Idx)
228                                      ->stripPointerCasts()))
229           MustKeepGlobalVariables.insert(GV);
230     }
231   }
232 }
233
234 bool GlobalMerge::doInitialization(Module &M) {
235   DenseMap<unsigned, SmallVector<GlobalVariable*, 16> > Globals, ConstGlobals,
236                                                         BSSGlobals;
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 TargetLowering *tli) {
309   return new GlobalMerge(tli);
310 }