LLVM  10.0.0svn
GlobalMerge.cpp
Go to the documentation of this file.
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/ADT/BitVector.h"
64 #include "llvm/ADT/DenseMap.h"
65 #include "llvm/ADT/SmallPtrSet.h"
66 #include "llvm/ADT/SmallVector.h"
67 #include "llvm/ADT/Statistic.h"
68 #include "llvm/ADT/StringRef.h"
69 #include "llvm/ADT/Triple.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/Pass.h"
86 #include "llvm/Support/Casting.h"
88 #include "llvm/Support/Debug.h"
92 #include <algorithm>
93 #include <cassert>
94 #include <cstddef>
95 #include <cstdint>
96 #include <string>
97 #include <vector>
98 
99 using namespace llvm;
100 
101 #define DEBUG_TYPE "global-merge"
102 
103 // FIXME: This is only useful as a last-resort way to disable the pass.
104 static cl::opt<bool>
105 EnableGlobalMerge("enable-global-merge", cl::Hidden,
106  cl::desc("Enable the global merge pass"),
107  cl::init(true));
108 
109 static cl::opt<unsigned>
110 GlobalMergeMaxOffset("global-merge-max-offset", cl::Hidden,
111  cl::desc("Set maximum offset for global merge pass"),
112  cl::init(0));
113 
115  "global-merge-group-by-use", cl::Hidden,
116  cl::desc("Improve global merge pass to look at uses"), cl::init(true));
117 
119  "global-merge-ignore-single-use", cl::Hidden,
120  cl::desc("Improve global merge pass to ignore globals only used alone"),
121  cl::init(true));
122 
123 static cl::opt<bool>
124 EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden,
125  cl::desc("Enable global merge pass on constants"),
126  cl::init(false));
127 
128 // FIXME: this could be a transitional option, and we probably need to remove
129 // it if only we are sure this optimization could always benefit all targets.
131 EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden,
132  cl::desc("Enable global merge pass on external linkage"));
133 
134 STATISTIC(NumMerged, "Number of globals merged");
135 
136 namespace {
137 
138  class GlobalMerge : public FunctionPass {
139  const TargetMachine *TM = nullptr;
140 
141  // FIXME: Infer the maximum possible offset depending on the actual users
142  // (these max offsets are different for the users inside Thumb or ARM
143  // functions), see the code that passes in the offset in the ARM backend
144  // for more information.
145  unsigned MaxOffset;
146 
147  /// Whether we should try to optimize for size only.
148  /// Currently, this applies a dead simple heuristic: only consider globals
149  /// used in minsize functions for merging.
150  /// FIXME: This could learn about optsize, and be used in the cost model.
151  bool OnlyOptimizeForSize = false;
152 
153  /// Whether we should merge global variables that have external linkage.
154  bool MergeExternalGlobals = false;
155 
156  bool IsMachO;
157 
158  bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
159  Module &M, bool isConst, unsigned AddrSpace) const;
160 
161  /// Merge everything in \p Globals for which the corresponding bit
162  /// in \p GlobalSet is set.
163  bool doMerge(const SmallVectorImpl<GlobalVariable *> &Globals,
164  const BitVector &GlobalSet, Module &M, bool isConst,
165  unsigned AddrSpace) const;
166 
167  /// Check if the given variable has been identified as must keep
168  /// \pre setMustKeepGlobalVariables must have been called on the Module that
169  /// contains GV
170  bool isMustKeepGlobalVariable(const GlobalVariable *GV) const {
171  return MustKeepGlobalVariables.count(GV);
172  }
173 
174  /// Collect every variables marked as "used" or used in a landing pad
175  /// instruction for this Module.
176  void setMustKeepGlobalVariables(Module &M);
177 
178  /// Collect every variables marked as "used"
180 
181  /// Keep track of the GlobalVariable that must not be merged away
182  SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables;
183 
184  public:
185  static char ID; // Pass identification, replacement for typeid.
186 
187  explicit GlobalMerge()
188  : FunctionPass(ID), MaxOffset(GlobalMergeMaxOffset) {
190  }
191 
192  explicit GlobalMerge(const TargetMachine *TM, unsigned MaximalOffset,
193  bool OnlyOptimizeForSize, bool MergeExternalGlobals)
194  : FunctionPass(ID), TM(TM), MaxOffset(MaximalOffset),
195  OnlyOptimizeForSize(OnlyOptimizeForSize),
196  MergeExternalGlobals(MergeExternalGlobals) {
198  }
199 
200  bool doInitialization(Module &M) override;
201  bool runOnFunction(Function &F) override;
202  bool doFinalization(Module &M) override;
203 
204  StringRef getPassName() const override { return "Merge internal globals"; }
205 
206  void getAnalysisUsage(AnalysisUsage &AU) const override {
207  AU.setPreservesCFG();
209  }
210  };
211 
212 } // end anonymous namespace
213 
214 char GlobalMerge::ID = 0;
215 
216 INITIALIZE_PASS(GlobalMerge, DEBUG_TYPE, "Merge global variables", false, false)
217 
218 bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
219  Module &M, bool isConst, unsigned AddrSpace) const {
220  auto &DL = M.getDataLayout();
221  // FIXME: Find better heuristics
223  Globals, [&DL](const GlobalVariable *GV1, const GlobalVariable *GV2) {
224  return DL.getTypeAllocSize(GV1->getValueType()) <
225  DL.getTypeAllocSize(GV2->getValueType());
226  });
227 
228  // If we want to just blindly group all globals together, do so.
229  if (!GlobalMergeGroupByUse) {
230  BitVector AllGlobals(Globals.size());
231  AllGlobals.set();
232  return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
233  }
234 
235  // If we want to be smarter, look at all uses of each global, to try to
236  // discover all sets of globals used together, and how many times each of
237  // these sets occurred.
238  //
239  // Keep this reasonably efficient, by having an append-only list of all sets
240  // discovered so far (UsedGlobalSet), and mapping each "together-ness" unit of
241  // code (currently, a Function) to the set of globals seen so far that are
242  // used together in that unit (GlobalUsesByFunction).
243  //
244  // When we look at the Nth global, we know that any new set is either:
245  // - the singleton set {N}, containing this global only, or
246  // - the union of {N} and a previously-discovered set, containing some
247  // combination of the previous N-1 globals.
248  // Using that knowledge, when looking at the Nth global, we can keep:
249  // - a reference to the singleton set {N} (CurGVOnlySetIdx)
250  // - a list mapping each previous set to its union with {N} (EncounteredUGS),
251  // if it actually occurs.
252 
253  // We keep track of the sets of globals used together "close enough".
254  struct UsedGlobalSet {
255  BitVector Globals;
256  unsigned UsageCount = 1;
257 
258  UsedGlobalSet(size_t Size) : Globals(Size) {}
259  };
260 
261  // Each set is unique in UsedGlobalSets.
262  std::vector<UsedGlobalSet> UsedGlobalSets;
263 
264  // Avoid repeating the create-global-set pattern.
265  auto CreateGlobalSet = [&]() -> UsedGlobalSet & {
266  UsedGlobalSets.emplace_back(Globals.size());
267  return UsedGlobalSets.back();
268  };
269 
270  // The first set is the empty set.
271  CreateGlobalSet().UsageCount = 0;
272 
273  // We define "close enough" to be "in the same function".
274  // FIXME: Grouping uses by function is way too aggressive, so we should have
275  // a better metric for distance between uses.
276  // The obvious alternative would be to group by BasicBlock, but that's in
277  // turn too conservative..
278  // Anything in between wouldn't be trivial to compute, so just stick with
279  // per-function grouping.
280 
281  // The value type is an index into UsedGlobalSets.
282  // The default (0) conveniently points to the empty set.
283  DenseMap<Function *, size_t /*UsedGlobalSetIdx*/> GlobalUsesByFunction;
284 
285  // Now, look at each merge-eligible global in turn.
286 
287  // Keep track of the sets we already encountered to which we added the
288  // current global.
289  // Each element matches the same-index element in UsedGlobalSets.
290  // This lets us efficiently tell whether a set has already been expanded to
291  // include the current global.
292  std::vector<size_t> EncounteredUGS;
293 
294  for (size_t GI = 0, GE = Globals.size(); GI != GE; ++GI) {
295  GlobalVariable *GV = Globals[GI];
296 
297  // Reset the encountered sets for this global...
298  std::fill(EncounteredUGS.begin(), EncounteredUGS.end(), 0);
299  // ...and grow it in case we created new sets for the previous global.
300  EncounteredUGS.resize(UsedGlobalSets.size());
301 
302  // We might need to create a set that only consists of the current global.
303  // Keep track of its index into UsedGlobalSets.
304  size_t CurGVOnlySetIdx = 0;
305 
306  // For each global, look at all its Uses.
307  for (auto &U : GV->uses()) {
308  // This Use might be a ConstantExpr. We're interested in Instruction
309  // users, so look through ConstantExpr...
310  Use *UI, *UE;
311  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U.getUser())) {
312  if (CE->use_empty())
313  continue;
314  UI = &*CE->use_begin();
315  UE = nullptr;
316  } else if (isa<Instruction>(U.getUser())) {
317  UI = &U;
318  UE = UI->getNext();
319  } else {
320  continue;
321  }
322 
323  // ...to iterate on all the instruction users of the global.
324  // Note that we iterate on Uses and not on Users to be able to getNext().
325  for (; UI != UE; UI = UI->getNext()) {
326  Instruction *I = dyn_cast<Instruction>(UI->getUser());
327  if (!I)
328  continue;
329 
330  Function *ParentFn = I->getParent()->getParent();
331 
332  // If we're only optimizing for size, ignore non-minsize functions.
333  if (OnlyOptimizeForSize && !ParentFn->hasMinSize())
334  continue;
335 
336  size_t UGSIdx = GlobalUsesByFunction[ParentFn];
337 
338  // If this is the first global the basic block uses, map it to the set
339  // consisting of this global only.
340  if (!UGSIdx) {
341  // If that set doesn't exist yet, create it.
342  if (!CurGVOnlySetIdx) {
343  CurGVOnlySetIdx = UsedGlobalSets.size();
344  CreateGlobalSet().Globals.set(GI);
345  } else {
346  ++UsedGlobalSets[CurGVOnlySetIdx].UsageCount;
347  }
348 
349  GlobalUsesByFunction[ParentFn] = CurGVOnlySetIdx;
350  continue;
351  }
352 
353  // If we already encountered this BB, just increment the counter.
354  if (UsedGlobalSets[UGSIdx].Globals.test(GI)) {
355  ++UsedGlobalSets[UGSIdx].UsageCount;
356  continue;
357  }
358 
359  // If not, the previous set wasn't actually used in this function.
360  --UsedGlobalSets[UGSIdx].UsageCount;
361 
362  // If we already expanded the previous set to include this global, just
363  // reuse that expanded set.
364  if (size_t ExpandedIdx = EncounteredUGS[UGSIdx]) {
365  ++UsedGlobalSets[ExpandedIdx].UsageCount;
366  GlobalUsesByFunction[ParentFn] = ExpandedIdx;
367  continue;
368  }
369 
370  // If not, create a new set consisting of the union of the previous set
371  // and this global. Mark it as encountered, so we can reuse it later.
372  GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] =
373  UsedGlobalSets.size();
374 
375  UsedGlobalSet &NewUGS = CreateGlobalSet();
376  NewUGS.Globals.set(GI);
377  NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals;
378  }
379  }
380  }
381 
382  // Now we found a bunch of sets of globals used together. We accumulated
383  // the number of times we encountered the sets (i.e., the number of blocks
384  // that use that exact set of globals).
385  //
386  // Multiply that by the size of the set to give us a crude profitability
387  // metric.
388  llvm::stable_sort(UsedGlobalSets,
389  [](const UsedGlobalSet &UGS1, const UsedGlobalSet &UGS2) {
390  return UGS1.Globals.count() * UGS1.UsageCount <
391  UGS2.Globals.count() * UGS2.UsageCount;
392  });
393 
394  // We can choose to merge all globals together, but ignore globals never used
395  // with another global. This catches the obviously non-profitable cases of
396  // having a single global, but is aggressive enough for any other case.
398  BitVector AllGlobals(Globals.size());
399  for (size_t i = 0, e = UsedGlobalSets.size(); i != e; ++i) {
400  const UsedGlobalSet &UGS = UsedGlobalSets[e - i - 1];
401  if (UGS.UsageCount == 0)
402  continue;
403  if (UGS.Globals.count() > 1)
404  AllGlobals |= UGS.Globals;
405  }
406  return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
407  }
408 
409  // Starting from the sets with the best (=biggest) profitability, find a
410  // good combination.
411  // The ideal (and expensive) solution can only be found by trying all
412  // combinations, looking for the one with the best profitability.
413  // Don't be smart about it, and just pick the first compatible combination,
414  // starting with the sets with the best profitability.
415  BitVector PickedGlobals(Globals.size());
416  bool Changed = false;
417 
418  for (size_t i = 0, e = UsedGlobalSets.size(); i != e; ++i) {
419  const UsedGlobalSet &UGS = UsedGlobalSets[e - i - 1];
420  if (UGS.UsageCount == 0)
421  continue;
422  if (PickedGlobals.anyCommon(UGS.Globals))
423  continue;
424  PickedGlobals |= UGS.Globals;
425  // If the set only contains one global, there's no point in merging.
426  // Ignore the global for inclusion in other sets though, so keep it in
427  // PickedGlobals.
428  if (UGS.Globals.count() < 2)
429  continue;
430  Changed |= doMerge(Globals, UGS.Globals, M, isConst, AddrSpace);
431  }
432 
433  return Changed;
434 }
435 
436 bool GlobalMerge::doMerge(const SmallVectorImpl<GlobalVariable *> &Globals,
437  const BitVector &GlobalSet, Module &M, bool isConst,
438  unsigned AddrSpace) const {
439  assert(Globals.size() > 1);
440 
442  Type *Int8Ty = Type::getInt8Ty(M.getContext());
443  auto &DL = M.getDataLayout();
444 
445  LLVM_DEBUG(dbgs() << " Trying to merge set, starts with #"
446  << GlobalSet.find_first() << "\n");
447 
448  bool Changed = false;
449  ssize_t i = GlobalSet.find_first();
450  while (i != -1) {
451  ssize_t j = 0;
452  uint64_t MergedSize = 0;
453  std::vector<Type*> Tys;
454  std::vector<Constant*> Inits;
455  std::vector<unsigned> StructIdxs;
456 
457  bool HasExternal = false;
458  StringRef FirstExternalName;
459  unsigned MaxAlign = 1;
460  unsigned CurIdx = 0;
461  for (j = i; j != -1; j = GlobalSet.find_next(j)) {
462  Type *Ty = Globals[j]->getValueType();
463 
464  // Make sure we use the same alignment AsmPrinter would use.
465  unsigned Align = DL.getPreferredAlignment(Globals[j]);
466  unsigned Padding = alignTo(MergedSize, Align) - MergedSize;
467  MergedSize += Padding;
468  MergedSize += DL.getTypeAllocSize(Ty);
469  if (MergedSize > MaxOffset) {
470  break;
471  }
472  if (Padding) {
473  Tys.push_back(ArrayType::get(Int8Ty, Padding));
474  Inits.push_back(ConstantAggregateZero::get(Tys.back()));
475  ++CurIdx;
476  }
477  Tys.push_back(Ty);
478  Inits.push_back(Globals[j]->getInitializer());
479  StructIdxs.push_back(CurIdx++);
480 
481  MaxAlign = std::max(MaxAlign, Align);
482 
483  if (Globals[j]->hasExternalLinkage() && !HasExternal) {
484  HasExternal = true;
485  FirstExternalName = Globals[j]->getName();
486  }
487  }
488 
489  // Exit early if there is only one global to merge.
490  if (Tys.size() < 2) {
491  i = j;
492  continue;
493  }
494 
495  // If merged variables doesn't have external linkage, we needn't to expose
496  // the symbol after merging.
497  GlobalValue::LinkageTypes Linkage = HasExternal
500  // Use a packed struct so we can control alignment.
501  StructType *MergedTy = StructType::get(M.getContext(), Tys, true);
502  Constant *MergedInit = ConstantStruct::get(MergedTy, Inits);
503 
504  // On Darwin external linkage needs to be preserved, otherwise
505  // dsymutil cannot preserve the debug info for the merged
506  // variables. If they have external linkage, use the symbol name
507  // of the first variable merged as the suffix of global symbol
508  // name. This avoids a link-time naming conflict for the
509  // _MergedGlobals symbols.
510  Twine MergedName =
511  (IsMachO && HasExternal)
512  ? "_MergedGlobals_" + FirstExternalName
513  : "_MergedGlobals";
514  auto MergedLinkage = IsMachO ? Linkage : GlobalValue::PrivateLinkage;
515  auto *MergedGV = new GlobalVariable(
516  M, MergedTy, isConst, MergedLinkage, MergedInit, MergedName, nullptr,
517  GlobalVariable::NotThreadLocal, AddrSpace);
518 
519  MergedGV->setAlignment(MaxAlign);
520  MergedGV->setSection(Globals[i]->getSection());
521 
522  const StructLayout *MergedLayout = DL.getStructLayout(MergedTy);
523  for (ssize_t k = i, idx = 0; k != j; k = GlobalSet.find_next(k), ++idx) {
524  GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage();
525  std::string Name = Globals[k]->getName();
527  Globals[k]->getDLLStorageClass();
528 
529  // Copy metadata while adjusting any debug info metadata by the original
530  // global's offset within the merged global.
531  MergedGV->copyMetadata(Globals[k],
532  MergedLayout->getElementOffset(StructIdxs[idx]));
533 
534  Constant *Idx[2] = {
535  ConstantInt::get(Int32Ty, 0),
536  ConstantInt::get(Int32Ty, StructIdxs[idx]),
537  };
538  Constant *GEP =
539  ConstantExpr::getInBoundsGetElementPtr(MergedTy, MergedGV, Idx);
540  Globals[k]->replaceAllUsesWith(GEP);
541  Globals[k]->eraseFromParent();
542 
543  // When the linkage is not internal we must emit an alias for the original
544  // variable name as it may be accessed from another object. On non-Mach-O
545  // we can also emit an alias for internal linkage as it's safe to do so.
546  // It's not safe on Mach-O as the alias (and thus the portion of the
547  // MergedGlobals variable) may be dead stripped at link time.
548  if (Linkage != GlobalValue::InternalLinkage || !IsMachO) {
549  GlobalAlias *GA = GlobalAlias::create(Tys[StructIdxs[idx]], AddrSpace,
550  Linkage, Name, GEP, &M);
551  GA->setDLLStorageClass(DLLStorage);
552  }
553 
554  NumMerged++;
555  }
556  Changed = true;
557  i = j;
558  }
559 
560  return Changed;
561 }
562 
564  // Extract global variables from llvm.used array
565  const GlobalVariable *GV = M.getGlobalVariable(Name);
566  if (!GV || !GV->hasInitializer()) return;
567 
568  // Should be an array of 'i8*'.
569  const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer());
570 
571  for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i)
572  if (const GlobalVariable *G =
573  dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts()))
574  MustKeepGlobalVariables.insert(G);
575 }
576 
577 void GlobalMerge::setMustKeepGlobalVariables(Module &M) {
578  collectUsedGlobalVariables(M, "llvm.used");
579  collectUsedGlobalVariables(M, "llvm.compiler.used");
580 
581  for (Function &F : M) {
582  for (BasicBlock &BB : F) {
583  Instruction *Pad = BB.getFirstNonPHI();
584  if (!Pad->isEHPad())
585  continue;
586 
587  // Keep globals used by landingpads and catchpads.
588  for (const Use &U : Pad->operands()) {
589  if (const GlobalVariable *GV =
590  dyn_cast<GlobalVariable>(U->stripPointerCasts()))
591  MustKeepGlobalVariables.insert(GV);
592  }
593  }
594  }
595 }
596 
597 bool GlobalMerge::doInitialization(Module &M) {
598  if (!EnableGlobalMerge)
599  return false;
600 
601  IsMachO = Triple(M.getTargetTriple()).isOSBinFormatMachO();
602 
603  auto &DL = M.getDataLayout();
605  Globals, ConstGlobals, BSSGlobals;
606  bool Changed = false;
607  setMustKeepGlobalVariables(M);
608 
609  // Grab all non-const globals.
610  for (auto &GV : M.globals()) {
611  // Merge is safe for "normal" internal or external globals only
612  if (GV.isDeclaration() || GV.isThreadLocal() || GV.hasImplicitSection())
613  continue;
614 
615  // It's not safe to merge globals that may be preempted
616  if (TM && !TM->shouldAssumeDSOLocal(M, &GV))
617  continue;
618 
619  if (!(MergeExternalGlobals && GV.hasExternalLinkage()) &&
620  !GV.hasInternalLinkage())
621  continue;
622 
624  assert(PT && "Global variable is not a pointer!");
625 
626  unsigned AddressSpace = PT->getAddressSpace();
628 
629  // Ignore all 'special' globals.
630  if (GV.getName().startswith("llvm.") ||
631  GV.getName().startswith(".llvm."))
632  continue;
633 
634  // Ignore all "required" globals:
635  if (isMustKeepGlobalVariable(&GV))
636  continue;
637 
638  Type *Ty = GV.getValueType();
639  if (DL.getTypeAllocSize(Ty) < MaxOffset) {
640  if (TM &&
642  BSSGlobals[{AddressSpace, Section}].push_back(&GV);
643  else if (GV.isConstant())
644  ConstGlobals[{AddressSpace, Section}].push_back(&GV);
645  else
646  Globals[{AddressSpace, Section}].push_back(&GV);
647  }
648  }
649 
650  for (auto &P : Globals)
651  if (P.second.size() > 1)
652  Changed |= doMerge(P.second, M, false, P.first.first);
653 
654  for (auto &P : BSSGlobals)
655  if (P.second.size() > 1)
656  Changed |= doMerge(P.second, M, false, P.first.first);
657 
659  for (auto &P : ConstGlobals)
660  if (P.second.size() > 1)
661  Changed |= doMerge(P.second, M, true, P.first.first);
662 
663  return Changed;
664 }
665 
666 bool GlobalMerge::runOnFunction(Function &F) {
667  return false;
668 }
669 
670 bool GlobalMerge::doFinalization(Module &M) {
671  MustKeepGlobalVariables.clear();
672  return false;
673 }
674 
676  bool OnlyOptimizeForSize,
677  bool MergeExternalByDefault) {
678  bool MergeExternal = (EnableGlobalMergeOnExternal == cl::BOU_UNSET) ?
679  MergeExternalByDefault : (EnableGlobalMergeOnExternal == cl::BOU_TRUE);
680  return new GlobalMerge(TM, Offset, OnlyOptimizeForSize, MergeExternal);
681 }
size_t size() const
Definition: Function.h:685
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
StringRef getSection() const
Get the custom section of this global if it has one.
Definition: GlobalObject.h:94
const std::string & getTargetTriple() const
Get the target triple which is a string describing the target host.
Definition: Module.h:240
BitVector & set()
Definition: BitVector.h:397
iterator_range< use_iterator > uses()
Definition: Value.h:374
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
static cl::opt< bool > GlobalMergeGroupByUse("global-merge-group-by-use", cl::Hidden, cl::desc("Improve global merge pass to look at uses"), cl::init(true))
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:270
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1363
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:56
Externally visible function.
Definition: GlobalValue.h:48
GlobalVariable * getGlobalVariable(StringRef Name) const
Look up the specified global variable in the module symbol table.
Definition: Module.h:390
Pass * createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset, bool OnlyOptimizeForSize=false, bool MergeExternalByDefault=false)
GlobalMerge - This pass merges internal (by default) globals into structs to enable reuse of a base p...
STATISTIC(NumFunctions, "Total number of functions")
F(f)
Hexagon Common GEP
This defines the Use class.
#define DEBUG_TYPE
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:559
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:331
Class to represent struct types.
Definition: DerivedTypes.h:233
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:244
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:339
static cl::opt< bool > EnableGlobalMerge("enable-global-merge", cl::Hidden, cl::desc("Enable the global merge pass"), cl::init(true))
void setDLLStorageClass(DLLStorageClassTypes C)
Definition: GlobalValue.h:271
static StructType * get(LLVMContext &Context, ArrayRef< Type *> Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
Definition: Type.cpp:341
Expected< const typename ELFT::Shdr * > getSection(typename ELFT::ShdrRange Sections, uint32_t Index)
Definition: ELF.h:310
bool hasExternalLinkage() const
Definition: GlobalValue.h:431
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:888
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:96
bool hasImplicitSection() const
Check if section name is present.
Value * getOperand(unsigned i) const
Definition: User.h:169
Class to represent pointers.
Definition: DerivedTypes.h:544
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
bool shouldAssumeDSOLocal(const Module &M, const GlobalValue *GV) const
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Represent the analysis usage information of a pass.
bool hasInternalLinkage() const
Definition: GlobalValue.h:443
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
DLLStorageClassTypes
Storage classes of global values for PE targets.
Definition: GlobalValue.h:69
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1075
op_range operands()
Definition: User.h:237
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:572
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:525
size_t size() const
Definition: SmallVector.h:52
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:40
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:43
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:33
bool isBSS() const
Definition: SectionKind.h:159
GlobalVariable * collectUsedGlobalVariables(const Module &M, SmallPtrSetImpl< GlobalValue *> &Set, bool CompilerUsed)
Given "llvm.used" or "llvm.compiler.used" as a global name, collect the initializer elements of that ...
Definition: Module.cpp:598
unsigned getNumOperands() const
Definition: User.h:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
AddressSpace
Definition: NVPTXBaseInfo.h:21
static cl::opt< bool > GlobalMergeIgnoreSingleUse("global-merge-ignore-single-use", cl::Hidden, cl::desc("Improve global merge pass to ignore globals only used alone"), cl::init(true))
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
static Constant * getInitializer(Constant *C)
Definition: Evaluator.cpp:205
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:653
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static cl::opt< cl::boolOrDefault > EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden, cl::desc("Enable global merge pass on external linkage"))
ConstantArray - Constant Array Declarations.
Definition: Constants.h:413
LinkageTypes
An enumeration for the kinds of linkage for global values.
Definition: GlobalValue.h:47
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:126
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:581
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
static Constant * getInBoundsGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant *> IdxList)
Create an "inbounds" getelementptr.
Definition: Constants.h:1180
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:619
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:582
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
Type * getValueType() const
Definition: GlobalValue.h:279
uint32_t Size
Definition: Profile.cpp:46
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
static cl::opt< unsigned > GlobalMergeMaxOffset("global-merge-max-offset", cl::Hidden, cl::desc("Set maximum offset for global merge pass"), cl::init(0))
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:231
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void stable_sort(R &&Range)
Definition: STLExtras.h:1289
static cl::opt< bool > EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, cl::desc("Enable global merge pass on constants"), cl::init(false))
bool hasInitializer() const
Definitions have initializers, declarations don&#39;t.
void initializeGlobalMergePass(PassRegistry &)
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:593
bool isThreadLocal() const
If the value is "Thread Local", its value isn&#39;t shared by the threads.
Definition: GlobalValue.h:250
iterator_range< global_iterator > globals()
Definition: Module.h:587
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
static SectionKind getKindForGlobal(const GlobalObject *GO, const TargetMachine &TM)
Classify the specified global variable into a set of target independent categories embodied in Sectio...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:173
static GlobalAlias * create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Constant *Aliasee, Module *Parent)
If a parent module is specified, the alias is automatically inserted into the end of the specified mo...
Definition: Globals.cpp:485
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:277
IntegerType * Int32Ty
const BasicBlock * getParent() const
Definition: Instruction.h:66