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/Module.h" 83 #include "llvm/IR/Type.h" 84 #include "llvm/IR/Use.h" 85 #include "llvm/IR/User.h" 86 #include "llvm/InitializePasses.h" 87 #include "llvm/MC/SectionKind.h" 88 #include "llvm/Pass.h" 89 #include "llvm/Support/Casting.h" 90 #include "llvm/Support/CommandLine.h" 91 #include "llvm/Support/Debug.h" 92 #include "llvm/Support/raw_ostream.h" 93 #include "llvm/Target/TargetLoweringObjectFile.h" 94 #include "llvm/Target/TargetMachine.h" 95 #include "llvm/TargetParser/Triple.h" 96 #include <algorithm> 97 #include <cassert> 98 #include <cstddef> 99 #include <cstdint> 100 #include <string> 101 #include <vector> 102 103 using namespace llvm; 104 105 #define DEBUG_TYPE "global-merge" 106 107 // FIXME: This is only useful as a last-resort way to disable the pass. 108 static cl::opt<bool> 109 EnableGlobalMerge("enable-global-merge", cl::Hidden, 110 cl::desc("Enable the global merge pass"), 111 cl::init(true)); 112 113 static cl::opt<unsigned> 114 GlobalMergeMaxOffset("global-merge-max-offset", cl::Hidden, 115 cl::desc("Set maximum offset for global merge pass"), 116 cl::init(0)); 117 118 static cl::opt<bool> GlobalMergeGroupByUse( 119 "global-merge-group-by-use", cl::Hidden, 120 cl::desc("Improve global merge pass to look at uses"), cl::init(true)); 121 122 static cl::opt<bool> GlobalMergeAllConst( 123 "global-merge-all-const", cl::Hidden, 124 cl::desc("Merge all const globals without looking at uses"), 125 cl::init(false)); 126 127 static cl::opt<bool> GlobalMergeIgnoreSingleUse( 128 "global-merge-ignore-single-use", cl::Hidden, 129 cl::desc("Improve global merge pass to ignore globals only used alone"), 130 cl::init(true)); 131 132 static cl::opt<bool> 133 EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, 134 cl::desc("Enable global merge pass on constants"), 135 cl::init(false)); 136 137 // FIXME: this could be a transitional option, and we probably need to remove 138 // it if only we are sure this optimization could always benefit all targets. 139 static cl::opt<cl::boolOrDefault> 140 EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden, 141 cl::desc("Enable global merge pass on external linkage")); 142 143 static cl::opt<unsigned> 144 GlobalMergeMinDataSize("global-merge-min-data-size", 145 cl::desc("The minimum size in bytes of each global " 146 "that should considered in merging."), 147 cl::init(0), cl::Hidden); 148 149 STATISTIC(NumMerged, "Number of globals merged"); 150 151 namespace { 152 153 class GlobalMergeImpl { 154 const TargetMachine *TM = nullptr; 155 GlobalMergeOptions Opt; 156 bool IsMachO = false; 157 158 private: 159 bool doMerge(SmallVectorImpl<GlobalVariable *> &Globals, Module &M, 160 bool isConst, unsigned AddrSpace) const; 161 162 /// Merge everything in \p Globals for which the corresponding bit 163 /// in \p GlobalSet is set. 164 bool doMerge(const SmallVectorImpl<GlobalVariable *> &Globals, 165 const BitVector &GlobalSet, Module &M, bool isConst, 166 unsigned AddrSpace) const; 167 168 /// Check if the given variable has been identified as must keep 169 /// \pre setMustKeepGlobalVariables must have been called on the Module that 170 /// contains GV 171 bool isMustKeepGlobalVariable(const GlobalVariable *GV) const { 172 return MustKeepGlobalVariables.count(GV); 173 } 174 175 /// Collect every variables marked as "used" or used in a landing pad 176 /// instruction for this Module. 177 void setMustKeepGlobalVariables(Module &M); 178 179 /// Collect every variables marked as "used" 180 void collectUsedGlobalVariables(Module &M, StringRef Name); 181 182 /// Keep track of the GlobalVariable that must not be merged away 183 SmallSetVector<const GlobalVariable *, 16> MustKeepGlobalVariables; 184 185 public: 186 GlobalMergeImpl(const TargetMachine *TM, GlobalMergeOptions Opt) 187 : TM(TM), Opt(Opt) {} 188 bool run(Module &M); 189 }; 190 191 class GlobalMerge : public FunctionPass { 192 const TargetMachine *TM = nullptr; 193 GlobalMergeOptions Opt; 194 195 public: 196 static char ID; // Pass identification, replacement for typeid. 197 198 explicit GlobalMerge() : FunctionPass(ID) { 199 Opt.MaxOffset = GlobalMergeMaxOffset; 200 initializeGlobalMergePass(*PassRegistry::getPassRegistry()); 201 } 202 203 explicit GlobalMerge(const TargetMachine *TM, unsigned MaximalOffset, 204 bool OnlyOptimizeForSize, bool MergeExternalGlobals, 205 bool MergeConstantGlobals) 206 : FunctionPass(ID), TM(TM) { 207 Opt.MaxOffset = MaximalOffset; 208 Opt.SizeOnly = OnlyOptimizeForSize; 209 Opt.MergeExternal = MergeExternalGlobals; 210 Opt.MergeConstantGlobals = MergeConstantGlobals; 211 initializeGlobalMergePass(*PassRegistry::getPassRegistry()); 212 } 213 214 bool doInitialization(Module &M) override { 215 auto GetSmallDataLimit = [](Module &M) -> std::optional<uint64_t> { 216 Metadata *SDL = M.getModuleFlag("SmallDataLimit"); 217 if (!SDL) 218 return std::nullopt; 219 return mdconst::extract<ConstantInt>(SDL)->getZExtValue(); 220 }; 221 if (GlobalMergeMinDataSize.getNumOccurrences()) 222 Opt.MinSize = GlobalMergeMinDataSize; 223 else if (auto SDL = GetSmallDataLimit(M); SDL && *SDL > 0) 224 Opt.MinSize = *SDL + 1; 225 else 226 Opt.MinSize = 0; 227 228 GlobalMergeImpl P(TM, Opt); 229 return P.run(M); 230 } 231 bool runOnFunction(Function &F) override { return false; } 232 233 StringRef getPassName() const override { return "Merge internal globals"; } 234 235 void getAnalysisUsage(AnalysisUsage &AU) const override { 236 AU.setPreservesCFG(); 237 FunctionPass::getAnalysisUsage(AU); 238 } 239 }; 240 241 } // end anonymous namespace 242 243 PreservedAnalyses GlobalMergePass::run(Module &M, ModuleAnalysisManager &) { 244 GlobalMergeImpl P(TM, Options); 245 bool Changed = P.run(M); 246 if (!Changed) 247 return PreservedAnalyses::all(); 248 249 PreservedAnalyses PA; 250 PA.preserveSet<CFGAnalyses>(); 251 return PA; 252 } 253 254 char GlobalMerge::ID = 0; 255 256 INITIALIZE_PASS(GlobalMerge, DEBUG_TYPE, "Merge global variables", false, false) 257 258 bool GlobalMergeImpl::doMerge(SmallVectorImpl<GlobalVariable *> &Globals, 259 Module &M, bool isConst, 260 unsigned AddrSpace) const { 261 auto &DL = M.getDataLayout(); 262 // FIXME: Find better heuristics 263 llvm::stable_sort( 264 Globals, [&DL](const GlobalVariable *GV1, const GlobalVariable *GV2) { 265 // We don't support scalable global variables. 266 return DL.getTypeAllocSize(GV1->getValueType()).getFixedValue() < 267 DL.getTypeAllocSize(GV2->getValueType()).getFixedValue(); 268 }); 269 270 // If we want to just blindly group all globals together, do so. 271 if (!GlobalMergeGroupByUse || (GlobalMergeAllConst && isConst)) { 272 BitVector AllGlobals(Globals.size()); 273 AllGlobals.set(); 274 return doMerge(Globals, 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(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(UsedGlobalSets.size(), 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>(U.getUser())) { 353 if (CE->use_empty()) 354 continue; 355 UI = &*CE->use_begin(); 356 UE = nullptr; 357 } else if (isa<Instruction>(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>(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 basic block 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 this BB, just increment the counter. 395 if (UsedGlobalSets[UGSIdx].Globals.test(GI)) { 396 ++UsedGlobalSets[UGSIdx].UsageCount; 397 continue; 398 } 399 400 // If not, the previous set wasn't actually used in this function. 401 --UsedGlobalSets[UGSIdx].UsageCount; 402 403 // If we already expanded the previous set to include this global, just 404 // reuse that expanded set. 405 if (size_t ExpandedIdx = EncounteredUGS[UGSIdx]) { 406 ++UsedGlobalSets[ExpandedIdx].UsageCount; 407 GlobalUsesByFunction[ParentFn] = ExpandedIdx; 408 continue; 409 } 410 411 // If not, create a new set consisting of the union of the previous set 412 // and this global. Mark it as encountered, so we can reuse it later. 413 GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] = 414 UsedGlobalSets.size(); 415 416 UsedGlobalSet &NewUGS = CreateGlobalSet(); 417 NewUGS.Globals.set(GI); 418 NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals; 419 } 420 } 421 } 422 423 // Now we found a bunch of sets of globals used together. We accumulated 424 // the number of times we encountered the sets (i.e., the number of blocks 425 // that use that exact set of globals). 426 // 427 // Multiply that by the size of the set to give us a crude profitability 428 // metric. 429 llvm::stable_sort(UsedGlobalSets, 430 [](const UsedGlobalSet &UGS1, const UsedGlobalSet &UGS2) { 431 return UGS1.Globals.count() * UGS1.UsageCount < 432 UGS2.Globals.count() * UGS2.UsageCount; 433 }); 434 435 // We can choose to merge all globals together, but ignore globals never used 436 // with another global. This catches the obviously non-profitable cases of 437 // having a single global, but is aggressive enough for any other case. 438 if (GlobalMergeIgnoreSingleUse) { 439 BitVector AllGlobals(Globals.size()); 440 for (const UsedGlobalSet &UGS : llvm::reverse(UsedGlobalSets)) { 441 if (UGS.UsageCount == 0) 442 continue; 443 if (UGS.Globals.count() > 1) 444 AllGlobals |= UGS.Globals; 445 } 446 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace); 447 } 448 449 // Starting from the sets with the best (=biggest) profitability, find a 450 // good combination. 451 // The ideal (and expensive) solution can only be found by trying all 452 // combinations, looking for the one with the best profitability. 453 // Don't be smart about it, and just pick the first compatible combination, 454 // starting with the sets with the best profitability. 455 BitVector PickedGlobals(Globals.size()); 456 bool Changed = false; 457 458 for (const UsedGlobalSet &UGS : llvm::reverse(UsedGlobalSets)) { 459 if (UGS.UsageCount == 0) 460 continue; 461 if (PickedGlobals.anyCommon(UGS.Globals)) 462 continue; 463 PickedGlobals |= UGS.Globals; 464 // If the set only contains one global, there's no point in merging. 465 // Ignore the global for inclusion in other sets though, so keep it in 466 // PickedGlobals. 467 if (UGS.Globals.count() < 2) 468 continue; 469 Changed |= doMerge(Globals, UGS.Globals, M, isConst, AddrSpace); 470 } 471 472 return Changed; 473 } 474 475 bool GlobalMergeImpl::doMerge(const SmallVectorImpl<GlobalVariable *> &Globals, 476 const BitVector &GlobalSet, Module &M, 477 bool isConst, unsigned AddrSpace) const { 478 assert(Globals.size() > 1); 479 480 Type *Int32Ty = Type::getInt32Ty(M.getContext()); 481 Type *Int8Ty = Type::getInt8Ty(M.getContext()); 482 auto &DL = M.getDataLayout(); 483 484 LLVM_DEBUG(dbgs() << " Trying to merge set, starts with #" 485 << GlobalSet.find_first() << ", total of " << Globals.size() 486 << "\n"); 487 488 bool Changed = false; 489 ssize_t i = GlobalSet.find_first(); 490 while (i != -1) { 491 ssize_t j = 0; 492 uint64_t MergedSize = 0; 493 std::vector<Type*> Tys; 494 std::vector<Constant*> Inits; 495 std::vector<unsigned> StructIdxs; 496 497 bool HasExternal = false; 498 StringRef FirstExternalName; 499 Align MaxAlign; 500 unsigned CurIdx = 0; 501 for (j = i; j != -1; j = GlobalSet.find_next(j)) { 502 Type *Ty = Globals[j]->getValueType(); 503 504 // Make sure we use the same alignment AsmPrinter would use. 505 Align Alignment = DL.getPreferredAlign(Globals[j]); 506 unsigned Padding = alignTo(MergedSize, Alignment) - MergedSize; 507 MergedSize += Padding; 508 MergedSize += DL.getTypeAllocSize(Ty); 509 if (MergedSize > Opt.MaxOffset) { 510 break; 511 } 512 if (Padding) { 513 Tys.push_back(ArrayType::get(Int8Ty, Padding)); 514 Inits.push_back(ConstantAggregateZero::get(Tys.back())); 515 ++CurIdx; 516 } 517 Tys.push_back(Ty); 518 Inits.push_back(Globals[j]->getInitializer()); 519 StructIdxs.push_back(CurIdx++); 520 521 MaxAlign = std::max(MaxAlign, Alignment); 522 523 if (Globals[j]->hasExternalLinkage() && !HasExternal) { 524 HasExternal = true; 525 FirstExternalName = Globals[j]->getName(); 526 } 527 } 528 529 // Exit early if there is only one global to merge. 530 if (Tys.size() < 2) { 531 i = j; 532 continue; 533 } 534 535 // If merged variables doesn't have external linkage, we needn't to expose 536 // the symbol after merging. 537 GlobalValue::LinkageTypes Linkage = HasExternal 538 ? GlobalValue::ExternalLinkage 539 : GlobalValue::InternalLinkage; 540 // Use a packed struct so we can control alignment. 541 StructType *MergedTy = StructType::get(M.getContext(), Tys, true); 542 Constant *MergedInit = ConstantStruct::get(MergedTy, Inits); 543 544 // On Darwin external linkage needs to be preserved, otherwise 545 // dsymutil cannot preserve the debug info for the merged 546 // variables. If they have external linkage, use the symbol name 547 // of the first variable merged as the suffix of global symbol 548 // name. This avoids a link-time naming conflict for the 549 // _MergedGlobals symbols. 550 Twine MergedName = 551 (IsMachO && HasExternal) 552 ? "_MergedGlobals_" + FirstExternalName 553 : "_MergedGlobals"; 554 auto MergedLinkage = IsMachO ? Linkage : GlobalValue::PrivateLinkage; 555 auto *MergedGV = new GlobalVariable( 556 M, MergedTy, isConst, MergedLinkage, MergedInit, MergedName, nullptr, 557 GlobalVariable::NotThreadLocal, AddrSpace); 558 559 MergedGV->setAlignment(MaxAlign); 560 MergedGV->setSection(Globals[i]->getSection()); 561 562 LLVM_DEBUG(dbgs() << "MergedGV: " << *MergedGV << "\n"); 563 564 const StructLayout *MergedLayout = DL.getStructLayout(MergedTy); 565 for (ssize_t k = i, idx = 0; k != j; k = GlobalSet.find_next(k), ++idx) { 566 GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage(); 567 std::string Name(Globals[k]->getName()); 568 GlobalValue::VisibilityTypes Visibility = Globals[k]->getVisibility(); 569 GlobalValue::DLLStorageClassTypes DLLStorage = 570 Globals[k]->getDLLStorageClass(); 571 572 // Copy metadata while adjusting any debug info metadata by the original 573 // global's offset within the merged global. 574 MergedGV->copyMetadata(Globals[k], 575 MergedLayout->getElementOffset(StructIdxs[idx])); 576 577 Constant *Idx[2] = { 578 ConstantInt::get(Int32Ty, 0), 579 ConstantInt::get(Int32Ty, StructIdxs[idx]), 580 }; 581 Constant *GEP = 582 ConstantExpr::getInBoundsGetElementPtr(MergedTy, MergedGV, Idx); 583 Globals[k]->replaceAllUsesWith(GEP); 584 Globals[k]->eraseFromParent(); 585 586 // Emit an alias for the original variable name. This is necessary for an 587 // external symbol, as it may be accessed from another object. For 588 // internal symbols, it's not strictly required, but it's useful. 589 // 590 // This _should_ also work on Mach-O ever since '.alt_entry' support was 591 // added in 2016. Unfortunately, there's a bug in ld-prime (present at 592 // least from Xcode 15.0 through Xcode 16.0), in which -dead_strip doesn't 593 // always honor alt_entry. To workaround this issue, we don't emit aliases 594 // on Mach-O. Except, we _must_ do so for external symbols. That means 595 // MergeExternal is broken with that linker. (That option is currently off 596 // by default on MachO). 597 if (!IsMachO || Linkage == GlobalValue::ExternalLinkage) { 598 GlobalAlias *GA = GlobalAlias::create(Tys[StructIdxs[idx]], AddrSpace, 599 Linkage, Name, GEP, &M); 600 GA->setVisibility(Visibility); 601 GA->setDLLStorageClass(DLLStorage); 602 } 603 604 NumMerged++; 605 } 606 Changed = true; 607 i = j; 608 } 609 610 return Changed; 611 } 612 613 void GlobalMergeImpl::collectUsedGlobalVariables(Module &M, StringRef Name) { 614 // Extract global variables from llvm.used array 615 const GlobalVariable *GV = M.getGlobalVariable(Name); 616 if (!GV || !GV->hasInitializer()) return; 617 618 // Should be an array of 'i8*'. 619 const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer()); 620 621 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) 622 if (const GlobalVariable *G = 623 dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts())) 624 MustKeepGlobalVariables.insert(G); 625 } 626 627 void GlobalMergeImpl::setMustKeepGlobalVariables(Module &M) { 628 collectUsedGlobalVariables(M, "llvm.used"); 629 collectUsedGlobalVariables(M, "llvm.compiler.used"); 630 631 for (Function &F : M) { 632 for (BasicBlock &BB : F) { 633 Instruction *Pad = BB.getFirstNonPHI(); 634 if (!Pad->isEHPad()) 635 continue; 636 637 // Keep globals used by landingpads and catchpads. 638 for (const Use &U : Pad->operands()) { 639 if (const GlobalVariable *GV = 640 dyn_cast<GlobalVariable>(U->stripPointerCasts())) 641 MustKeepGlobalVariables.insert(GV); 642 else if (const ConstantArray *CA = dyn_cast<ConstantArray>(U->stripPointerCasts())) { 643 for (const Use &Elt : CA->operands()) { 644 if (const GlobalVariable *GV = 645 dyn_cast<GlobalVariable>(Elt->stripPointerCasts())) 646 MustKeepGlobalVariables.insert(GV); 647 } 648 } 649 } 650 } 651 } 652 } 653 654 // This function returns true if the given data Section name has custom 655 // subsection-splitting semantics in Mach-O (such as splitting by a fixed size) 656 // 657 // See also ObjFile::parseSections and getRecordSize in lld/MachO/InputFiles.cpp 658 static bool isSpecialMachOSection(StringRef Section) { 659 // Uses starts_with, since section attributes can appear at the end of the 660 // name. 661 return Section.starts_with("__DATA,__cfstring") || 662 Section.starts_with("__DATA,__objc_classrefs") || 663 Section.starts_with("__DATA,__objc_selrefs"); 664 } 665 666 bool GlobalMergeImpl::run(Module &M) { 667 if (!EnableGlobalMerge) 668 return false; 669 670 IsMachO = Triple(M.getTargetTriple()).isOSBinFormatMachO(); 671 672 auto &DL = M.getDataLayout(); 673 MapVector<std::pair<unsigned, StringRef>, SmallVector<GlobalVariable *, 0>> 674 Globals, ConstGlobals, BSSGlobals; 675 bool Changed = false; 676 setMustKeepGlobalVariables(M); 677 678 LLVM_DEBUG({ 679 dbgs() << "Number of GV that must be kept: " << 680 MustKeepGlobalVariables.size() << "\n"; 681 for (const GlobalVariable *KeptGV : MustKeepGlobalVariables) 682 dbgs() << "Kept: " << *KeptGV << "\n"; 683 }); 684 // Grab all non-const globals. 685 for (auto &GV : M.globals()) { 686 // Merge is safe for "normal" internal or external globals only 687 if (GV.isDeclaration() || GV.isThreadLocal() || GV.hasImplicitSection()) 688 continue; 689 690 // It's not safe to merge globals that may be preempted 691 if (TM && !TM->shouldAssumeDSOLocal(&GV)) 692 continue; 693 694 if (!(Opt.MergeExternal && GV.hasExternalLinkage()) && 695 !GV.hasLocalLinkage()) 696 continue; 697 698 PointerType *PT = dyn_cast<PointerType>(GV.getType()); 699 assert(PT && "Global variable is not a pointer!"); 700 701 unsigned AddressSpace = PT->getAddressSpace(); 702 StringRef Section = GV.getSection(); 703 704 // On Mach-O, some section names have special semantics. Don't merge these. 705 if (IsMachO && isSpecialMachOSection(Section)) 706 continue; 707 708 // Ignore all 'special' globals. 709 if (GV.getName().starts_with("llvm.") || GV.getName().starts_with(".llvm.")) 710 continue; 711 712 // Ignore all "required" globals: 713 if (isMustKeepGlobalVariable(&GV)) 714 continue; 715 716 // Don't merge tagged globals, as each global should have its own unique 717 // memory tag at runtime. TODO(hctim): This can be relaxed: constant globals 718 // with compatible alignment and the same contents may be merged as long as 719 // the globals occupy the same number of tag granules (i.e. `size_a / 16 == 720 // size_b / 16`). 721 if (GV.isTagged()) 722 continue; 723 724 Type *Ty = GV.getValueType(); 725 TypeSize AllocSize = DL.getTypeAllocSize(Ty); 726 if (AllocSize < Opt.MaxOffset && AllocSize >= Opt.MinSize) { 727 if (TM && 728 TargetLoweringObjectFile::getKindForGlobal(&GV, *TM).isBSS()) 729 BSSGlobals[{AddressSpace, Section}].push_back(&GV); 730 else if (GV.isConstant()) 731 ConstGlobals[{AddressSpace, Section}].push_back(&GV); 732 else 733 Globals[{AddressSpace, Section}].push_back(&GV); 734 } 735 LLVM_DEBUG(dbgs() << "GV " 736 << ((DL.getTypeAllocSize(Ty) < Opt.MaxOffset) 737 ? "to merge: " 738 : "not to merge: ") 739 << GV << "\n"); 740 } 741 742 for (auto &P : Globals) 743 if (P.second.size() > 1) 744 Changed |= doMerge(P.second, M, false, P.first.first); 745 746 for (auto &P : BSSGlobals) 747 if (P.second.size() > 1) 748 Changed |= doMerge(P.second, M, false, P.first.first); 749 750 if (Opt.MergeConstantGlobals) 751 for (auto &P : ConstGlobals) 752 if (P.second.size() > 1) 753 Changed |= doMerge(P.second, M, true, P.first.first); 754 755 return Changed; 756 } 757 758 Pass *llvm::createGlobalMergePass(const TargetMachine *TM, unsigned Offset, 759 bool OnlyOptimizeForSize, 760 bool MergeExternalByDefault, 761 bool MergeConstantByDefault) { 762 bool MergeExternal = (EnableGlobalMergeOnExternal == cl::BOU_UNSET) ? 763 MergeExternalByDefault : (EnableGlobalMergeOnExternal == cl::BOU_TRUE); 764 bool MergeConstant = EnableGlobalMergeOnConst || MergeConstantByDefault; 765 return new GlobalMerge(TM, Offset, OnlyOptimizeForSize, MergeExternal, 766 MergeConstant); 767 } 768