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