106#define DEBUG_TYPE "global-merge"
111 cl::desc(
"Enable the global merge pass"),
116 cl::desc(
"Set maximum offset for global merge pass"),
125 cl::desc(
"Merge all const globals without looking at uses"),
130 cl::desc(
"Improve global merge pass to ignore globals only used alone"),
135 cl::desc(
"Enable global merge pass on constants"),
142 cl::desc(
"Enable global merge pass on external linkage"));
146 cl::desc(
"The minimum size in bytes of each global "
147 "that should considered in merging."),
154class GlobalMergeImpl {
157 bool IsMachO =
false;
161 bool isConst,
unsigned AddrSpace)
const;
167 unsigned AddrSpace)
const;
173 return MustKeepGlobalVariables.count(GV);
178 void setMustKeepGlobalVariables(
Module &M);
188 :
TM(
TM), Opt(Opt) {}
204 explicit GlobalMerge(
const TargetMachine *TM,
unsigned MaximalOffset,
205 bool OnlyOptimizeForSize,
bool MergeExternalGlobals,
206 bool MergeConstantGlobals,
bool MergeConstAggressive)
217 auto GetSmallDataLimit = [](
Module &
M) -> std::optional<uint64_t> {
221 return mdconst::extract<ConstantInt>(SDL)->getZExtValue();
225 else if (
auto SDL = GetSmallDataLimit(M);
SDL && *
SDL > 0)
230 GlobalMergeImpl
P(TM, Opt);
246 GlobalMergeImpl
P(TM, Options);
247 bool Changed =
P.run(M);
256char GlobalMerge::ID = 0;
262 unsigned AddrSpace)
const {
263 auto &
DL = M.getDataLayout();
274 BitVector AllGlobals(Globals.size(),
true);
275 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
297 struct UsedGlobalSet {
299 unsigned UsageCount = 1;
301 UsedGlobalSet(
size_t Size) : Globals(
Size) {}
305 std::vector<UsedGlobalSet> UsedGlobalSets;
308 auto CreateGlobalSet = [&]() -> UsedGlobalSet & {
309 UsedGlobalSets.emplace_back(Globals.size());
310 return UsedGlobalSets.
back();
314 CreateGlobalSet().UsageCount = 0;
335 std::vector<size_t> EncounteredUGS;
337 for (
size_t GI = 0, GE = Globals.size(); GI != GE; ++GI) {
342 EncounteredUGS.assign(UsedGlobalSets.size(), 0);
346 size_t CurGVOnlySetIdx = 0;
349 for (
auto &U : GV->
uses()) {
353 if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(
U.getUser())) {
356 UI = &*
CE->use_begin();
358 }
else if (isa<Instruction>(
U.getUser())) {
367 for (; UI != UE; UI = UI->getNext()) {
372 Function *ParentFn =
I->getParent()->getParent();
378 size_t UGSIdx = GlobalUsesByFunction[ParentFn];
384 if (!CurGVOnlySetIdx) {
385 CurGVOnlySetIdx = UsedGlobalSets.size();
386 CreateGlobalSet().Globals.set(GI);
388 ++UsedGlobalSets[CurGVOnlySetIdx].UsageCount;
391 GlobalUsesByFunction[ParentFn] = CurGVOnlySetIdx;
397 if (UsedGlobalSets[UGSIdx].Globals.test(GI)) {
398 ++UsedGlobalSets[UGSIdx].UsageCount;
403 --UsedGlobalSets[UGSIdx].UsageCount;
407 if (
size_t ExpandedIdx = EncounteredUGS[UGSIdx]) {
408 ++UsedGlobalSets[ExpandedIdx].UsageCount;
409 GlobalUsesByFunction[ParentFn] = ExpandedIdx;
415 GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] =
416 UsedGlobalSets.size();
418 UsedGlobalSet &NewUGS = CreateGlobalSet();
419 NewUGS.Globals.set(GI);
420 NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals;
430 for (
const UsedGlobalSet &UGS : UsedGlobalSets) {
431 if (UGS.UsageCount == 0)
433 if (UGS.Globals.count() > 1)
434 AllGlobals |= UGS.Globals;
436 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
446 [](
const UsedGlobalSet &UGS1,
const UsedGlobalSet &UGS2) {
447 return UGS1.Globals.count() * UGS1.UsageCount <
448 UGS2.Globals.count() * UGS2.UsageCount;
458 bool Changed =
false;
460 for (
const UsedGlobalSet &UGS :
llvm::reverse(UsedGlobalSets)) {
461 if (UGS.UsageCount == 0)
463 if (PickedGlobals.anyCommon(UGS.Globals))
465 PickedGlobals |= UGS.Globals;
469 if (UGS.Globals.count() < 2)
471 Changed |= doMerge(Globals, UGS.Globals, M, isConst, AddrSpace);
479 bool isConst,
unsigned AddrSpace)
const {
484 auto &
DL =
M.getDataLayout();
490 bool Changed =
false;
495 std::vector<Type*>
Tys;
496 std::vector<Constant*> Inits;
497 std::vector<unsigned> StructIdxs;
499 bool HasExternal =
false;
504 Type *Ty = Globals[
j]->getValueType();
507 Align Alignment =
DL.getPreferredAlign(Globals[j]);
510 MergedSize +=
DL.getTypeAllocSize(Ty);
520 Inits.push_back(Globals[j]->getInitializer());
521 StructIdxs.push_back(CurIdx++);
523 MaxAlign = std::max(MaxAlign, Alignment);
525 if (Globals[j]->hasExternalLinkage() && !HasExternal) {
527 FirstExternalName = Globals[
j]->getName();
532 if (
Tys.size() < 2) {
553 (IsMachO && HasExternal)
554 ?
"_MergedGlobals_" + FirstExternalName
558 M, MergedTy, isConst, MergedLinkage, MergedInit, MergedName,
nullptr,
561 MergedGV->setAlignment(MaxAlign);
562 MergedGV->setSection(Globals[i]->
getSection());
567 for (ssize_t k = i, idx = 0;
k !=
j;
k = GlobalSet.
find_next(k), ++idx) {
572 Globals[
k]->getDLLStorageClass();
576 MergedGV->copyMetadata(Globals[k],
580 ConstantInt::get(Int32Ty, 0),
581 ConstantInt::get(Int32Ty, StructIdxs[idx]),
585 Globals[
k]->replaceAllUsesWith(
GEP);
586 Globals[
k]->eraseFromParent();
626 MustKeepGlobalVariables.insert(
G);
629void GlobalMergeImpl::setMustKeepGlobalVariables(
Module &M) {
636 auto *
II = dyn_cast<IntrinsicInst>(Pad);
637 if (!Pad->isEHPad() &&
638 !(
II &&
II->getIntrinsicID() == Intrinsic::eh_typeid_for))
643 for (
const Use &U : Pad->operands()) {
645 dyn_cast<GlobalVariable>(
U->stripPointerCasts()))
646 MustKeepGlobalVariables.insert(GV);
647 else if (
const ConstantArray *CA = dyn_cast<ConstantArray>(
U->stripPointerCasts())) {
648 for (
const Use &Elt : CA->operands()) {
650 dyn_cast<GlobalVariable>(Elt->stripPointerCasts()))
651 MustKeepGlobalVariables.insert(GV);
666 return Section.starts_with(
"__DATA,__cfstring") ||
667 Section.starts_with(
"__DATA,__objc_classrefs") ||
668 Section.starts_with(
"__DATA,__objc_selrefs");
671bool GlobalMergeImpl::run(
Module &M) {
677 auto &
DL =
M.getDataLayout();
679 Globals, ConstGlobals, BSSGlobals;
680 bool Changed =
false;
681 setMustKeepGlobalVariables(M);
684 dbgs() <<
"Number of GV that must be kept: " <<
685 MustKeepGlobalVariables.size() <<
"\n";
687 dbgs() <<
"Kept: " << *KeptGV <<
"\n";
690 for (
auto &GV :
M.globals()) {
696 if (TM && !
TM->shouldAssumeDSOLocal(&GV))
704 assert(PT &&
"Global variable is not a pointer!");
718 if (isMustKeepGlobalVariable(&GV))
745 for (
auto &
P : Globals)
746 if (
P.second.size() > 1)
747 Changed |= doMerge(
P.second, M,
false,
P.first.first);
749 for (
auto &
P : BSSGlobals)
750 if (
P.second.size() > 1)
751 Changed |= doMerge(
P.second, M,
false,
P.first.first);
754 for (
auto &
P : ConstGlobals)
755 if (
P.second.size() > 1)
756 Changed |= doMerge(
P.second, M,
true,
P.first.first);
762 bool OnlyOptimizeForSize,
763 bool MergeExternalByDefault,
764 bool MergeConstantByDefault,
765 bool MergeConstAggressiveByDefault) {
771 : MergeConstAggressiveByDefault;
772 return new GlobalMerge(TM,
Offset, OnlyOptimizeForSize, MergeExternal,
773 MergeConstant, MergeConstAggressive);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements the BitVector class.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
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))
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))
static bool isSpecialMachOSection(StringRef Section)
static cl::opt< bool > GlobalMergeAllConst("global-merge-all-const", cl::Hidden, cl::desc("Merge all const globals without looking at uses"), cl::init(false))
static cl::opt< bool > EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, cl::desc("Enable global merge pass on constants"), cl::init(false))
static cl::opt< unsigned > GlobalMergeMinDataSize("global-merge-min-data-size", cl::desc("The minimum size in bytes of each global " "that should considered in merging."), cl::init(0), cl::Hidden)
static cl::opt< unsigned > GlobalMergeMaxOffset("global-merge-max-offset", cl::Hidden, cl::desc("Set maximum offset for global merge pass"), cl::init(0))
static cl::opt< bool > EnableGlobalMerge("enable-global-merge", cl::Hidden, cl::desc("Enable the global merge pass"), cl::init(true))
static cl::opt< cl::boolOrDefault > EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden, cl::desc("Enable global merge pass on external linkage"))
Module.h This file contains the declarations for the Module class.
This defines the Use class.
This file implements a map that provides insertion order iteration.
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static StringRef getName(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
LLVM Basic Block Representation.
InstListType::iterator iterator
Instruction iterators...
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
bool back() const
Return the last element in the vector.
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Represents analyses that only rely on functions' control flow.
static ConstantAggregateZero * get(Type *Ty)
ConstantArray - Constant Array Declarations.
A constant value that is initialized with an expression using other constant values.
static Constant * getInBoundsGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList)
Create an "inbounds" getelementptr.
static Constant * get(StructType *T, ArrayRef< Constant * > V)
This is an important base class in LLVM.
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
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...
PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM)
StringRef getSection() const
Get the custom section of this global if it has one.
bool hasExternalLinkage() const
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
bool hasLocalLinkage() const
void setDLLStorageClass(DLLStorageClassTypes C)
DLLStorageClassTypes
Storage classes of global values for PE targets.
PointerType * getType() const
Global values are always pointers.
VisibilityTypes
An enumeration for the kinds of visibility of global values.
void setVisibility(VisibilityTypes V)
LinkageTypes
An enumeration for the kinds of linkage for global values.
@ PrivateLinkage
Like Internal, but omit from symbol table.
@ InternalLinkage
Rename collisions when linking (static functions).
@ ExternalLinkage
Externally visible function.
Type * getValueType() const
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
bool hasInitializer() const
Definitions have initializers, declarations don't.
bool hasImplicitSection() const
Check if section name is present.
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
This class implements a map that also provides access to all stored values in a deterministic order.
A Module instance is used to store all the information related to an LLVM module.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
bool starts_with(StringRef Prefix) const
Check if this string starts with the given Prefix.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
Class to represent struct types.
static StructType * get(LLVMContext &Context, ArrayRef< Type * > Elements, bool isPacked=false)
This static method is the primary way to create a literal StructType.
static SectionKind getKindForGlobal(const GlobalObject *GO, const TargetMachine &TM)
Classify the specified global variable into a set of target independent categories embodied in Sectio...
Primary interface to the complete machine description for the target machine.
Triple - Helper class for working with autoconf configuration names.
bool isOSBinFormatMachO() const
Tests whether the environment is MachO.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
static IntegerType * getInt8Ty(LLVMContext &C)
static IntegerType * getInt32Ty(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
int getNumOccurrences() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
ID ArrayRef< Type * > Tys
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Linkage
Describes symbol linkage. This can be used to resolve definition clashes.
Expected< const typename ELFT::Shdr * > getSection(typename ELFT::ShdrRange Sections, uint32_t Index)
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
Pass * createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset, bool OnlyOptimizeForSize=false, bool MergeExternalByDefault=false, bool MergeConstantByDefault=false, bool MergeConstAggressiveByDefault=false)
GlobalMerge - This pass merges internal (by default) globals into structs to enable reuse of a base p...
void initializeGlobalMergePass(PassRegistry &)
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
GlobalVariable * collectUsedGlobalVariables(const Module &M, SmallVectorImpl< GlobalValue * > &Vec, bool CompilerUsed)
Given "llvm.used" or "llvm.compiler.used" as a global name, collect the initializer elements of that ...
This struct is a compact representation of a valid (non-zero power of two) alignment.
bool MergeConstAggressive
Whether we should merge constant global variables aggressively without looking at use.
bool SizeOnly
Whether we should try to optimize for size only.
bool MergeExternal
Whether we should merge global variables that have external linkage.
bool MergeConstantGlobals
Whether we should merge constant global variables.