1 | //===- GlobalMerge.cpp - Internal globals merging -------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
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 | // However, merging globals can have tradeoffs: |
54 | // - it confuses debuggers, tools, and users |
55 | // - it makes linker optimizations less useful (order files, LOHs, ...) |
56 | // - it forces usage of indexed addressing (which isn't necessarily "free") |
57 | // - it can increase register pressure when the uses are disparate enough. |
58 | // |
59 | // We use heuristics to discover the best global grouping we can (cf cl::opts). |
60 | // |
61 | // ===---------------------------------------------------------------------===// |
62 | |
63 | #include "llvm/CodeGen/GlobalMerge.h" |
64 | #include "llvm/ADT/BitVector.h" |
65 | #include "llvm/ADT/DenseMap.h" |
66 | #include "llvm/ADT/SetVector.h" |
67 | #include "llvm/ADT/SmallVector.h" |
68 | #include "llvm/ADT/Statistic.h" |
69 | #include "llvm/ADT/StringRef.h" |
70 | #include "llvm/ADT/Twine.h" |
71 | #include "llvm/CodeGen/Passes.h" |
72 | #include "llvm/IR/BasicBlock.h" |
73 | #include "llvm/IR/Constants.h" |
74 | #include "llvm/IR/DataLayout.h" |
75 | #include "llvm/IR/DerivedTypes.h" |
76 | #include "llvm/IR/Function.h" |
77 | #include "llvm/IR/GlobalAlias.h" |
78 | #include "llvm/IR/GlobalValue.h" |
79 | #include "llvm/IR/GlobalVariable.h" |
80 | #include "llvm/IR/Instruction.h" |
81 | #include "llvm/IR/Module.h" |
82 | #include "llvm/IR/Type.h" |
83 | #include "llvm/IR/Use.h" |
84 | #include "llvm/IR/User.h" |
85 | #include "llvm/InitializePasses.h" |
86 | #include "llvm/MC/SectionKind.h" |
87 | #include "llvm/Pass.h" |
88 | #include "llvm/Support/Casting.h" |
89 | #include "llvm/Support/CommandLine.h" |
90 | #include "llvm/Support/Debug.h" |
91 | #include "llvm/Support/raw_ostream.h" |
92 | #include "llvm/Target/TargetLoweringObjectFile.h" |
93 | #include "llvm/Target/TargetMachine.h" |
94 | #include "llvm/TargetParser/Triple.h" |
95 | #include <algorithm> |
96 | #include <cassert> |
97 | #include <cstddef> |
98 | #include <cstdint> |
99 | #include <string> |
100 | #include <vector> |
101 | |
102 | using namespace llvm; |
103 | |
104 | #define DEBUG_TYPE "global-merge" |
105 | |
106 | // FIXME: This is only useful as a last-resort way to disable the pass. |
107 | static cl::opt<bool> |
108 | EnableGlobalMerge("enable-global-merge" , cl::Hidden, |
109 | cl::desc("Enable the global merge pass" ), |
110 | cl::init(Val: true)); |
111 | |
112 | static cl::opt<unsigned> |
113 | GlobalMergeMaxOffset("global-merge-max-offset" , cl::Hidden, |
114 | cl::desc("Set maximum offset for global merge pass" ), |
115 | cl::init(Val: 0)); |
116 | |
117 | static cl::opt<bool> GlobalMergeGroupByUse( |
118 | "global-merge-group-by-use" , cl::Hidden, |
119 | cl::desc("Improve global merge pass to look at uses" ), cl::init(Val: true)); |
120 | |
121 | static cl::opt<bool> GlobalMergeIgnoreSingleUse( |
122 | "global-merge-ignore-single-use" , cl::Hidden, |
123 | cl::desc("Improve global merge pass to ignore globals only used alone" ), |
124 | cl::init(Val: true)); |
125 | |
126 | static cl::opt<bool> |
127 | EnableGlobalMergeOnConst("global-merge-on-const" , cl::Hidden, |
128 | cl::desc("Enable global merge pass on constants" ), |
129 | cl::init(Val: false)); |
130 | |
131 | // FIXME: this could be a transitional option, and we probably need to remove |
132 | // it if only we are sure this optimization could always benefit all targets. |
133 | static cl::opt<cl::boolOrDefault> |
134 | EnableGlobalMergeOnExternal("global-merge-on-external" , cl::Hidden, |
135 | cl::desc("Enable global merge pass on external linkage" )); |
136 | |
137 | STATISTIC(NumMerged, "Number of globals merged" ); |
138 | |
139 | namespace { |
140 | |
141 | class GlobalMergeImpl { |
142 | const TargetMachine *TM = nullptr; |
143 | GlobalMergeOptions Opt; |
144 | bool IsMachO = false; |
145 | |
146 | private: |
147 | bool doMerge(SmallVectorImpl<GlobalVariable *> &Globals, Module &M, |
148 | bool isConst, unsigned AddrSpace) const; |
149 | |
150 | /// Merge everything in \p Globals for which the corresponding bit |
151 | /// in \p GlobalSet is set. |
152 | bool doMerge(const SmallVectorImpl<GlobalVariable *> &Globals, |
153 | const BitVector &GlobalSet, Module &M, bool isConst, |
154 | unsigned AddrSpace) const; |
155 | |
156 | /// Check if the given variable has been identified as must keep |
157 | /// \pre setMustKeepGlobalVariables must have been called on the Module that |
158 | /// contains GV |
159 | bool isMustKeepGlobalVariable(const GlobalVariable *GV) const { |
160 | return MustKeepGlobalVariables.count(key: GV); |
161 | } |
162 | |
163 | /// Collect every variables marked as "used" or used in a landing pad |
164 | /// instruction for this Module. |
165 | void setMustKeepGlobalVariables(Module &M); |
166 | |
167 | /// Collect every variables marked as "used" |
168 | void collectUsedGlobalVariables(Module &M, StringRef Name); |
169 | |
170 | /// Keep track of the GlobalVariable that must not be merged away |
171 | SmallSetVector<const GlobalVariable *, 16> MustKeepGlobalVariables; |
172 | |
173 | public: |
174 | GlobalMergeImpl(const TargetMachine *TM, GlobalMergeOptions Opt) |
175 | : TM(TM), Opt(Opt) {} |
176 | bool run(Module &M); |
177 | }; |
178 | |
179 | class GlobalMerge : public FunctionPass { |
180 | const TargetMachine *TM = nullptr; |
181 | GlobalMergeOptions Opt; |
182 | |
183 | public: |
184 | static char ID; // Pass identification, replacement for typeid. |
185 | |
186 | explicit GlobalMerge() : FunctionPass(ID) { |
187 | Opt.MaxOffset = GlobalMergeMaxOffset; |
188 | initializeGlobalMergePass(*PassRegistry::getPassRegistry()); |
189 | } |
190 | |
191 | explicit GlobalMerge(const TargetMachine *TM, unsigned MaximalOffset, |
192 | bool OnlyOptimizeForSize, bool MergeExternalGlobals) |
193 | : FunctionPass(ID), TM(TM) { |
194 | Opt.MaxOffset = MaximalOffset; |
195 | Opt.SizeOnly = OnlyOptimizeForSize; |
196 | Opt.MergeExternal = MergeExternalGlobals; |
197 | initializeGlobalMergePass(*PassRegistry::getPassRegistry()); |
198 | } |
199 | |
200 | bool doInitialization(Module &M) override { |
201 | GlobalMergeImpl P(TM, Opt); |
202 | return P.run(M); |
203 | } |
204 | bool runOnFunction(Function &F) override { return false; } |
205 | |
206 | StringRef getPassName() const override { return "Merge internal globals" ; } |
207 | |
208 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
209 | AU.setPreservesCFG(); |
210 | FunctionPass::getAnalysisUsage(AU); |
211 | } |
212 | }; |
213 | |
214 | } // end anonymous namespace |
215 | |
216 | PreservedAnalyses GlobalMergePass::run(Module &M, ModuleAnalysisManager &) { |
217 | GlobalMergeImpl P(TM, Options); |
218 | bool Changed = P.run(M); |
219 | if (!Changed) |
220 | return PreservedAnalyses::all(); |
221 | |
222 | PreservedAnalyses PA; |
223 | PA.preserveSet<CFGAnalyses>(); |
224 | return PA; |
225 | } |
226 | |
227 | char GlobalMerge::ID = 0; |
228 | |
229 | INITIALIZE_PASS(GlobalMerge, DEBUG_TYPE, "Merge global variables" , false, false) |
230 | |
231 | bool GlobalMergeImpl::doMerge(SmallVectorImpl<GlobalVariable *> &Globals, |
232 | Module &M, bool isConst, |
233 | unsigned AddrSpace) const { |
234 | auto &DL = M.getDataLayout(); |
235 | // FIXME: Find better heuristics |
236 | llvm::stable_sort( |
237 | Range&: Globals, C: [&DL](const GlobalVariable *GV1, const GlobalVariable *GV2) { |
238 | // We don't support scalable global variables. |
239 | return DL.getTypeAllocSize(Ty: GV1->getValueType()).getFixedValue() < |
240 | DL.getTypeAllocSize(Ty: GV2->getValueType()).getFixedValue(); |
241 | }); |
242 | |
243 | // If we want to just blindly group all globals together, do so. |
244 | if (!GlobalMergeGroupByUse) { |
245 | BitVector AllGlobals(Globals.size()); |
246 | AllGlobals.set(); |
247 | return doMerge(Globals, GlobalSet: AllGlobals, M, isConst, AddrSpace); |
248 | } |
249 | |
250 | // If we want to be smarter, look at all uses of each global, to try to |
251 | // discover all sets of globals used together, and how many times each of |
252 | // these sets occurred. |
253 | // |
254 | // Keep this reasonably efficient, by having an append-only list of all sets |
255 | // discovered so far (UsedGlobalSet), and mapping each "together-ness" unit of |
256 | // code (currently, a Function) to the set of globals seen so far that are |
257 | // used together in that unit (GlobalUsesByFunction). |
258 | // |
259 | // When we look at the Nth global, we know that any new set is either: |
260 | // - the singleton set {N}, containing this global only, or |
261 | // - the union of {N} and a previously-discovered set, containing some |
262 | // combination of the previous N-1 globals. |
263 | // Using that knowledge, when looking at the Nth global, we can keep: |
264 | // - a reference to the singleton set {N} (CurGVOnlySetIdx) |
265 | // - a list mapping each previous set to its union with {N} (EncounteredUGS), |
266 | // if it actually occurs. |
267 | |
268 | // We keep track of the sets of globals used together "close enough". |
269 | struct UsedGlobalSet { |
270 | BitVector Globals; |
271 | unsigned UsageCount = 1; |
272 | |
273 | UsedGlobalSet(size_t Size) : Globals(Size) {} |
274 | }; |
275 | |
276 | // Each set is unique in UsedGlobalSets. |
277 | std::vector<UsedGlobalSet> UsedGlobalSets; |
278 | |
279 | // Avoid repeating the create-global-set pattern. |
280 | auto CreateGlobalSet = [&]() -> UsedGlobalSet & { |
281 | UsedGlobalSets.emplace_back(args: Globals.size()); |
282 | return UsedGlobalSets.back(); |
283 | }; |
284 | |
285 | // The first set is the empty set. |
286 | CreateGlobalSet().UsageCount = 0; |
287 | |
288 | // We define "close enough" to be "in the same function". |
289 | // FIXME: Grouping uses by function is way too aggressive, so we should have |
290 | // a better metric for distance between uses. |
291 | // The obvious alternative would be to group by BasicBlock, but that's in |
292 | // turn too conservative.. |
293 | // Anything in between wouldn't be trivial to compute, so just stick with |
294 | // per-function grouping. |
295 | |
296 | // The value type is an index into UsedGlobalSets. |
297 | // The default (0) conveniently points to the empty set. |
298 | DenseMap<Function *, size_t /*UsedGlobalSetIdx*/> GlobalUsesByFunction; |
299 | |
300 | // Now, look at each merge-eligible global in turn. |
301 | |
302 | // Keep track of the sets we already encountered to which we added the |
303 | // current global. |
304 | // Each element matches the same-index element in UsedGlobalSets. |
305 | // This lets us efficiently tell whether a set has already been expanded to |
306 | // include the current global. |
307 | std::vector<size_t> EncounteredUGS; |
308 | |
309 | for (size_t GI = 0, GE = Globals.size(); GI != GE; ++GI) { |
310 | GlobalVariable *GV = Globals[GI]; |
311 | |
312 | // Reset the encountered sets for this global... |
313 | std::fill(first: EncounteredUGS.begin(), last: EncounteredUGS.end(), value: 0); |
314 | // ...and grow it in case we created new sets for the previous global. |
315 | EncounteredUGS.resize(new_size: UsedGlobalSets.size()); |
316 | |
317 | // We might need to create a set that only consists of the current global. |
318 | // Keep track of its index into UsedGlobalSets. |
319 | size_t CurGVOnlySetIdx = 0; |
320 | |
321 | // For each global, look at all its Uses. |
322 | for (auto &U : GV->uses()) { |
323 | // This Use might be a ConstantExpr. We're interested in Instruction |
324 | // users, so look through ConstantExpr... |
325 | Use *UI, *UE; |
326 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: U.getUser())) { |
327 | if (CE->use_empty()) |
328 | continue; |
329 | UI = &*CE->use_begin(); |
330 | UE = nullptr; |
331 | } else if (isa<Instruction>(Val: U.getUser())) { |
332 | UI = &U; |
333 | UE = UI->getNext(); |
334 | } else { |
335 | continue; |
336 | } |
337 | |
338 | // ...to iterate on all the instruction users of the global. |
339 | // Note that we iterate on Uses and not on Users to be able to getNext(). |
340 | for (; UI != UE; UI = UI->getNext()) { |
341 | Instruction *I = dyn_cast<Instruction>(Val: UI->getUser()); |
342 | if (!I) |
343 | continue; |
344 | |
345 | Function *ParentFn = I->getParent()->getParent(); |
346 | |
347 | // If we're only optimizing for size, ignore non-minsize functions. |
348 | if (Opt.SizeOnly && !ParentFn->hasMinSize()) |
349 | continue; |
350 | |
351 | size_t UGSIdx = GlobalUsesByFunction[ParentFn]; |
352 | |
353 | // If this is the first global the basic block uses, map it to the set |
354 | // consisting of this global only. |
355 | if (!UGSIdx) { |
356 | // If that set doesn't exist yet, create it. |
357 | if (!CurGVOnlySetIdx) { |
358 | CurGVOnlySetIdx = UsedGlobalSets.size(); |
359 | CreateGlobalSet().Globals.set(GI); |
360 | } else { |
361 | ++UsedGlobalSets[CurGVOnlySetIdx].UsageCount; |
362 | } |
363 | |
364 | GlobalUsesByFunction[ParentFn] = CurGVOnlySetIdx; |
365 | continue; |
366 | } |
367 | |
368 | // If we already encountered this BB, just increment the counter. |
369 | if (UsedGlobalSets[UGSIdx].Globals.test(Idx: GI)) { |
370 | ++UsedGlobalSets[UGSIdx].UsageCount; |
371 | continue; |
372 | } |
373 | |
374 | // If not, the previous set wasn't actually used in this function. |
375 | --UsedGlobalSets[UGSIdx].UsageCount; |
376 | |
377 | // If we already expanded the previous set to include this global, just |
378 | // reuse that expanded set. |
379 | if (size_t ExpandedIdx = EncounteredUGS[UGSIdx]) { |
380 | ++UsedGlobalSets[ExpandedIdx].UsageCount; |
381 | GlobalUsesByFunction[ParentFn] = ExpandedIdx; |
382 | continue; |
383 | } |
384 | |
385 | // If not, create a new set consisting of the union of the previous set |
386 | // and this global. Mark it as encountered, so we can reuse it later. |
387 | GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] = |
388 | UsedGlobalSets.size(); |
389 | |
390 | UsedGlobalSet &NewUGS = CreateGlobalSet(); |
391 | NewUGS.Globals.set(GI); |
392 | NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals; |
393 | } |
394 | } |
395 | } |
396 | |
397 | // Now we found a bunch of sets of globals used together. We accumulated |
398 | // the number of times we encountered the sets (i.e., the number of blocks |
399 | // that use that exact set of globals). |
400 | // |
401 | // Multiply that by the size of the set to give us a crude profitability |
402 | // metric. |
403 | llvm::stable_sort(Range&: UsedGlobalSets, |
404 | C: [](const UsedGlobalSet &UGS1, const UsedGlobalSet &UGS2) { |
405 | return UGS1.Globals.count() * UGS1.UsageCount < |
406 | UGS2.Globals.count() * UGS2.UsageCount; |
407 | }); |
408 | |
409 | // We can choose to merge all globals together, but ignore globals never used |
410 | // with another global. This catches the obviously non-profitable cases of |
411 | // having a single global, but is aggressive enough for any other case. |
412 | if (GlobalMergeIgnoreSingleUse) { |
413 | BitVector AllGlobals(Globals.size()); |
414 | for (const UsedGlobalSet &UGS : llvm::reverse(C&: UsedGlobalSets)) { |
415 | if (UGS.UsageCount == 0) |
416 | continue; |
417 | if (UGS.Globals.count() > 1) |
418 | AllGlobals |= UGS.Globals; |
419 | } |
420 | return doMerge(Globals, GlobalSet: AllGlobals, M, isConst, AddrSpace); |
421 | } |
422 | |
423 | // Starting from the sets with the best (=biggest) profitability, find a |
424 | // good combination. |
425 | // The ideal (and expensive) solution can only be found by trying all |
426 | // combinations, looking for the one with the best profitability. |
427 | // Don't be smart about it, and just pick the first compatible combination, |
428 | // starting with the sets with the best profitability. |
429 | BitVector PickedGlobals(Globals.size()); |
430 | bool Changed = false; |
431 | |
432 | for (const UsedGlobalSet &UGS : llvm::reverse(C&: UsedGlobalSets)) { |
433 | if (UGS.UsageCount == 0) |
434 | continue; |
435 | if (PickedGlobals.anyCommon(RHS: UGS.Globals)) |
436 | continue; |
437 | PickedGlobals |= UGS.Globals; |
438 | // If the set only contains one global, there's no point in merging. |
439 | // Ignore the global for inclusion in other sets though, so keep it in |
440 | // PickedGlobals. |
441 | if (UGS.Globals.count() < 2) |
442 | continue; |
443 | Changed |= doMerge(Globals, GlobalSet: UGS.Globals, M, isConst, AddrSpace); |
444 | } |
445 | |
446 | return Changed; |
447 | } |
448 | |
449 | bool GlobalMergeImpl::doMerge(const SmallVectorImpl<GlobalVariable *> &Globals, |
450 | const BitVector &GlobalSet, Module &M, |
451 | bool isConst, unsigned AddrSpace) const { |
452 | assert(Globals.size() > 1); |
453 | |
454 | Type *Int32Ty = Type::getInt32Ty(C&: M.getContext()); |
455 | Type *Int8Ty = Type::getInt8Ty(C&: M.getContext()); |
456 | auto &DL = M.getDataLayout(); |
457 | |
458 | LLVM_DEBUG(dbgs() << " Trying to merge set, starts with #" |
459 | << GlobalSet.find_first() << "\n" ); |
460 | |
461 | bool Changed = false; |
462 | ssize_t i = GlobalSet.find_first(); |
463 | while (i != -1) { |
464 | ssize_t j = 0; |
465 | uint64_t MergedSize = 0; |
466 | std::vector<Type*> Tys; |
467 | std::vector<Constant*> Inits; |
468 | std::vector<unsigned> StructIdxs; |
469 | |
470 | bool HasExternal = false; |
471 | StringRef FirstExternalName; |
472 | Align MaxAlign; |
473 | unsigned CurIdx = 0; |
474 | for (j = i; j != -1; j = GlobalSet.find_next(Prev: j)) { |
475 | Type *Ty = Globals[j]->getValueType(); |
476 | |
477 | // Make sure we use the same alignment AsmPrinter would use. |
478 | Align Alignment = DL.getPreferredAlign(GV: Globals[j]); |
479 | unsigned Padding = alignTo(Size: MergedSize, A: Alignment) - MergedSize; |
480 | MergedSize += Padding; |
481 | MergedSize += DL.getTypeAllocSize(Ty); |
482 | if (MergedSize > Opt.MaxOffset) { |
483 | break; |
484 | } |
485 | if (Padding) { |
486 | Tys.push_back(x: ArrayType::get(ElementType: Int8Ty, NumElements: Padding)); |
487 | Inits.push_back(x: ConstantAggregateZero::get(Ty: Tys.back())); |
488 | ++CurIdx; |
489 | } |
490 | Tys.push_back(x: Ty); |
491 | Inits.push_back(x: Globals[j]->getInitializer()); |
492 | StructIdxs.push_back(x: CurIdx++); |
493 | |
494 | MaxAlign = std::max(a: MaxAlign, b: Alignment); |
495 | |
496 | if (Globals[j]->hasExternalLinkage() && !HasExternal) { |
497 | HasExternal = true; |
498 | FirstExternalName = Globals[j]->getName(); |
499 | } |
500 | } |
501 | |
502 | // Exit early if there is only one global to merge. |
503 | if (Tys.size() < 2) { |
504 | i = j; |
505 | continue; |
506 | } |
507 | |
508 | // If merged variables doesn't have external linkage, we needn't to expose |
509 | // the symbol after merging. |
510 | GlobalValue::LinkageTypes Linkage = HasExternal |
511 | ? GlobalValue::ExternalLinkage |
512 | : GlobalValue::InternalLinkage; |
513 | // Use a packed struct so we can control alignment. |
514 | StructType *MergedTy = StructType::get(Context&: M.getContext(), Elements: Tys, isPacked: true); |
515 | Constant *MergedInit = ConstantStruct::get(T: MergedTy, V: Inits); |
516 | |
517 | // On Darwin external linkage needs to be preserved, otherwise |
518 | // dsymutil cannot preserve the debug info for the merged |
519 | // variables. If they have external linkage, use the symbol name |
520 | // of the first variable merged as the suffix of global symbol |
521 | // name. This avoids a link-time naming conflict for the |
522 | // _MergedGlobals symbols. |
523 | Twine MergedName = |
524 | (IsMachO && HasExternal) |
525 | ? "_MergedGlobals_" + FirstExternalName |
526 | : "_MergedGlobals" ; |
527 | auto MergedLinkage = IsMachO ? Linkage : GlobalValue::PrivateLinkage; |
528 | auto *MergedGV = new GlobalVariable( |
529 | M, MergedTy, isConst, MergedLinkage, MergedInit, MergedName, nullptr, |
530 | GlobalVariable::NotThreadLocal, AddrSpace); |
531 | |
532 | MergedGV->setAlignment(MaxAlign); |
533 | MergedGV->setSection(Globals[i]->getSection()); |
534 | |
535 | const StructLayout *MergedLayout = DL.getStructLayout(Ty: MergedTy); |
536 | for (ssize_t k = i, idx = 0; k != j; k = GlobalSet.find_next(Prev: k), ++idx) { |
537 | GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage(); |
538 | std::string Name(Globals[k]->getName()); |
539 | GlobalValue::VisibilityTypes Visibility = Globals[k]->getVisibility(); |
540 | GlobalValue::DLLStorageClassTypes DLLStorage = |
541 | Globals[k]->getDLLStorageClass(); |
542 | |
543 | // Copy metadata while adjusting any debug info metadata by the original |
544 | // global's offset within the merged global. |
545 | MergedGV->copyMetadata(Src: Globals[k], |
546 | Offset: MergedLayout->getElementOffset(Idx: StructIdxs[idx])); |
547 | |
548 | Constant *Idx[2] = { |
549 | ConstantInt::get(Ty: Int32Ty, V: 0), |
550 | ConstantInt::get(Ty: Int32Ty, V: StructIdxs[idx]), |
551 | }; |
552 | Constant *GEP = |
553 | ConstantExpr::getInBoundsGetElementPtr(Ty: MergedTy, C: MergedGV, IdxList: Idx); |
554 | Globals[k]->replaceAllUsesWith(V: GEP); |
555 | Globals[k]->eraseFromParent(); |
556 | |
557 | // When the linkage is not internal we must emit an alias for the original |
558 | // variable name as it may be accessed from another object. On non-Mach-O |
559 | // we can also emit an alias for internal linkage as it's safe to do so. |
560 | // It's not safe on Mach-O as the alias (and thus the portion of the |
561 | // MergedGlobals variable) may be dead stripped at link time. |
562 | if (Linkage != GlobalValue::InternalLinkage || !IsMachO) { |
563 | GlobalAlias *GA = GlobalAlias::create(Ty: Tys[StructIdxs[idx]], AddressSpace: AddrSpace, |
564 | Linkage, Name, Aliasee: GEP, Parent: &M); |
565 | GA->setVisibility(Visibility); |
566 | GA->setDLLStorageClass(DLLStorage); |
567 | } |
568 | |
569 | NumMerged++; |
570 | } |
571 | Changed = true; |
572 | i = j; |
573 | } |
574 | |
575 | return Changed; |
576 | } |
577 | |
578 | void GlobalMergeImpl::collectUsedGlobalVariables(Module &M, StringRef Name) { |
579 | // Extract global variables from llvm.used array |
580 | const GlobalVariable *GV = M.getGlobalVariable(Name); |
581 | if (!GV || !GV->hasInitializer()) return; |
582 | |
583 | // Should be an array of 'i8*'. |
584 | const ConstantArray *InitList = cast<ConstantArray>(Val: GV->getInitializer()); |
585 | |
586 | for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) |
587 | if (const GlobalVariable *G = |
588 | dyn_cast<GlobalVariable>(Val: InitList->getOperand(i_nocapture: i)->stripPointerCasts())) |
589 | MustKeepGlobalVariables.insert(X: G); |
590 | } |
591 | |
592 | void GlobalMergeImpl::setMustKeepGlobalVariables(Module &M) { |
593 | collectUsedGlobalVariables(M, Name: "llvm.used" ); |
594 | collectUsedGlobalVariables(M, Name: "llvm.compiler.used" ); |
595 | |
596 | for (Function &F : M) { |
597 | for (BasicBlock &BB : F) { |
598 | Instruction *Pad = BB.getFirstNonPHI(); |
599 | if (!Pad->isEHPad()) |
600 | continue; |
601 | |
602 | // Keep globals used by landingpads and catchpads. |
603 | for (const Use &U : Pad->operands()) { |
604 | if (const GlobalVariable *GV = |
605 | dyn_cast<GlobalVariable>(Val: U->stripPointerCasts())) |
606 | MustKeepGlobalVariables.insert(X: GV); |
607 | else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Val: U->stripPointerCasts())) { |
608 | for (const Use &Elt : CA->operands()) { |
609 | if (const GlobalVariable *GV = |
610 | dyn_cast<GlobalVariable>(Val: Elt->stripPointerCasts())) |
611 | MustKeepGlobalVariables.insert(X: GV); |
612 | } |
613 | } |
614 | } |
615 | } |
616 | } |
617 | } |
618 | |
619 | bool GlobalMergeImpl::run(Module &M) { |
620 | if (!EnableGlobalMerge) |
621 | return false; |
622 | |
623 | IsMachO = Triple(M.getTargetTriple()).isOSBinFormatMachO(); |
624 | |
625 | auto &DL = M.getDataLayout(); |
626 | DenseMap<std::pair<unsigned, StringRef>, SmallVector<GlobalVariable *, 16>> |
627 | Globals, ConstGlobals, BSSGlobals; |
628 | bool Changed = false; |
629 | setMustKeepGlobalVariables(M); |
630 | |
631 | LLVM_DEBUG({ |
632 | dbgs() << "Number of GV that must be kept: " << |
633 | MustKeepGlobalVariables.size() << "\n" ; |
634 | for (const GlobalVariable *KeptGV : MustKeepGlobalVariables) |
635 | dbgs() << "Kept: " << *KeptGV << "\n" ; |
636 | }); |
637 | // Grab all non-const globals. |
638 | for (auto &GV : M.globals()) { |
639 | // Merge is safe for "normal" internal or external globals only |
640 | if (GV.isDeclaration() || GV.isThreadLocal() || GV.hasImplicitSection()) |
641 | continue; |
642 | |
643 | // It's not safe to merge globals that may be preempted |
644 | if (TM && !TM->shouldAssumeDSOLocal(M, GV: &GV)) |
645 | continue; |
646 | |
647 | if (!(Opt.MergeExternal && GV.hasExternalLinkage()) && |
648 | !GV.hasInternalLinkage()) |
649 | continue; |
650 | |
651 | PointerType *PT = dyn_cast<PointerType>(Val: GV.getType()); |
652 | assert(PT && "Global variable is not a pointer!" ); |
653 | |
654 | unsigned AddressSpace = PT->getAddressSpace(); |
655 | StringRef Section = GV.getSection(); |
656 | |
657 | // Ignore all 'special' globals. |
658 | if (GV.getName().starts_with(Prefix: "llvm." ) || GV.getName().starts_with(Prefix: ".llvm." )) |
659 | continue; |
660 | |
661 | // Ignore all "required" globals: |
662 | if (isMustKeepGlobalVariable(GV: &GV)) |
663 | continue; |
664 | |
665 | // Don't merge tagged globals, as each global should have its own unique |
666 | // memory tag at runtime. TODO(hctim): This can be relaxed: constant globals |
667 | // with compatible alignment and the same contents may be merged as long as |
668 | // the globals occupy the same number of tag granules (i.e. `size_a / 16 == |
669 | // size_b / 16`). |
670 | if (GV.isTagged()) |
671 | continue; |
672 | |
673 | Type *Ty = GV.getValueType(); |
674 | if (DL.getTypeAllocSize(Ty) < Opt.MaxOffset) { |
675 | if (TM && |
676 | TargetLoweringObjectFile::getKindForGlobal(GO: &GV, TM: *TM).isBSS()) |
677 | BSSGlobals[{AddressSpace, Section}].push_back(Elt: &GV); |
678 | else if (GV.isConstant()) |
679 | ConstGlobals[{AddressSpace, Section}].push_back(Elt: &GV); |
680 | else |
681 | Globals[{AddressSpace, Section}].push_back(Elt: &GV); |
682 | } |
683 | } |
684 | |
685 | for (auto &P : Globals) |
686 | if (P.second.size() > 1) |
687 | Changed |= doMerge(Globals&: P.second, M, isConst: false, AddrSpace: P.first.first); |
688 | |
689 | for (auto &P : BSSGlobals) |
690 | if (P.second.size() > 1) |
691 | Changed |= doMerge(Globals&: P.second, M, isConst: false, AddrSpace: P.first.first); |
692 | |
693 | if (EnableGlobalMergeOnConst) |
694 | for (auto &P : ConstGlobals) |
695 | if (P.second.size() > 1) |
696 | Changed |= doMerge(Globals&: P.second, M, isConst: true, AddrSpace: P.first.first); |
697 | |
698 | return Changed; |
699 | } |
700 | |
701 | Pass *llvm::createGlobalMergePass(const TargetMachine *TM, unsigned Offset, |
702 | bool OnlyOptimizeForSize, |
703 | bool MergeExternalByDefault) { |
704 | bool MergeExternal = (EnableGlobalMergeOnExternal == cl::BOU_UNSET) ? |
705 | MergeExternalByDefault : (EnableGlobalMergeOnExternal == cl::BOU_TRUE); |
706 | return new GlobalMerge(TM, Offset, OnlyOptimizeForSize, MergeExternal); |
707 | } |
708 | |