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