104#define DEBUG_TYPE "global-merge"
109 cl::desc(
"Enable the global merge pass"),
114 cl::desc(
"Set maximum offset for global merge pass"),
123 cl::desc(
"Improve global merge pass to ignore globals only used alone"),
128 cl::desc(
"Enable global merge pass on constants"),
135 cl::desc(
"Enable global merge pass on external linkage"));
154 bool OnlyOptimizeForSize =
false;
157 bool MergeExternalGlobals =
false;
159 bool IsMachO =
false;
162 Module &M,
bool isConst,
unsigned AddrSpace)
const;
168 unsigned AddrSpace)
const;
174 return MustKeepGlobalVariables.count(GV);
179 void setMustKeepGlobalVariables(
Module &M);
190 explicit GlobalMerge()
195 explicit GlobalMerge(
const TargetMachine *TM,
unsigned MaximalOffset,
196 bool OnlyOptimizeForSize,
bool MergeExternalGlobals)
198 OnlyOptimizeForSize(OnlyOptimizeForSize),
199 MergeExternalGlobals(MergeExternalGlobals) {
217char GlobalMerge::ID = 0;
222 Module &M,
bool isConst,
unsigned AddrSpace)
const {
223 auto &
DL =
M.getDataLayout();
236 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
258 struct UsedGlobalSet {
260 unsigned UsageCount = 1;
262 UsedGlobalSet(
size_t Size) : Globals(
Size) {}
266 std::vector<UsedGlobalSet> UsedGlobalSets;
269 auto CreateGlobalSet = [&]() -> UsedGlobalSet & {
270 UsedGlobalSets.emplace_back(Globals.size());
271 return UsedGlobalSets.
back();
275 CreateGlobalSet().UsageCount = 0;
296 std::vector<size_t> EncounteredUGS;
298 for (
size_t GI = 0, GE = Globals.size(); GI != GE; ++GI) {
302 std::fill(EncounteredUGS.begin(), EncounteredUGS.end(), 0);
304 EncounteredUGS.resize(UsedGlobalSets.size());
308 size_t CurGVOnlySetIdx = 0;
311 for (
auto &U : GV->
uses()) {
315 if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(
U.getUser())) {
318 UI = &*
CE->use_begin();
320 }
else if (isa<Instruction>(
U.getUser())) {
329 for (; UI != UE; UI = UI->getNext()) {
334 Function *ParentFn =
I->getParent()->getParent();
337 if (OnlyOptimizeForSize && !ParentFn->
hasMinSize())
340 size_t UGSIdx = GlobalUsesByFunction[ParentFn];
346 if (!CurGVOnlySetIdx) {
347 CurGVOnlySetIdx = UsedGlobalSets.size();
348 CreateGlobalSet().Globals.set(GI);
350 ++UsedGlobalSets[CurGVOnlySetIdx].UsageCount;
353 GlobalUsesByFunction[ParentFn] = CurGVOnlySetIdx;
358 if (UsedGlobalSets[UGSIdx].Globals.test(GI)) {
359 ++UsedGlobalSets[UGSIdx].UsageCount;
364 --UsedGlobalSets[UGSIdx].UsageCount;
368 if (
size_t ExpandedIdx = EncounteredUGS[UGSIdx]) {
369 ++UsedGlobalSets[ExpandedIdx].UsageCount;
370 GlobalUsesByFunction[ParentFn] = ExpandedIdx;
376 GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] =
377 UsedGlobalSets.size();
379 UsedGlobalSet &NewUGS = CreateGlobalSet();
380 NewUGS.Globals.set(GI);
381 NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals;
393 [](
const UsedGlobalSet &UGS1,
const UsedGlobalSet &UGS2) {
394 return UGS1.Globals.count() * UGS1.UsageCount <
395 UGS2.Globals.count() * UGS2.UsageCount;
403 for (
const UsedGlobalSet &UGS :
llvm::reverse(UsedGlobalSets)) {
404 if (UGS.UsageCount == 0)
406 if (UGS.Globals.count() > 1)
407 AllGlobals |= UGS.Globals;
409 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
419 bool Changed =
false;
421 for (
const UsedGlobalSet &UGS :
llvm::reverse(UsedGlobalSets)) {
422 if (UGS.UsageCount == 0)
424 if (PickedGlobals.anyCommon(UGS.Globals))
426 PickedGlobals |= UGS.Globals;
430 if (UGS.Globals.count() < 2)
432 Changed |= doMerge(Globals, UGS.Globals, M, isConst, AddrSpace);
440 unsigned AddrSpace)
const {
445 auto &
DL =
M.getDataLayout();
450 bool Changed =
false;
455 std::vector<Type*> Tys;
456 std::vector<Constant*> Inits;
457 std::vector<unsigned> StructIdxs;
459 bool HasExternal =
false;
464 Type *Ty = Globals[
j]->getValueType();
467 Align Alignment =
DL.getPreferredAlign(Globals[j]);
470 MergedSize +=
DL.getTypeAllocSize(Ty);
471 if (MergedSize > MaxOffset) {
475 Tys.
push_back(ArrayType::get(Int8Ty, Padding));
480 Inits.push_back(Globals[j]->getInitializer());
481 StructIdxs.push_back(CurIdx++);
483 MaxAlign = std::max(MaxAlign, Alignment);
485 if (Globals[j]->hasExternalLinkage() && !HasExternal) {
487 FirstExternalName = Globals[
j]->getName();
492 if (Tys.size() < 2) {
513 (IsMachO && HasExternal)
514 ?
"_MergedGlobals_" + FirstExternalName
518 M, MergedTy, isConst, MergedLinkage, MergedInit, MergedName,
nullptr,
519 GlobalVariable::NotThreadLocal, AddrSpace);
521 MergedGV->setAlignment(MaxAlign);
522 MergedGV->setSection(Globals[i]->
getSection());
525 for (ssize_t k = i, idx = 0;
k !=
j;
k = GlobalSet.
find_next(k), ++idx) {
530 Globals[
k]->getDLLStorageClass();
534 MergedGV->copyMetadata(Globals[k],
543 Globals[
k]->replaceAllUsesWith(
GEP);
544 Globals[
k]->eraseFromParent();
578 MustKeepGlobalVariables.
insert(
G);
581void GlobalMerge::setMustKeepGlobalVariables(
Module &M) {
594 dyn_cast<GlobalVariable>(
U->stripPointerCasts()))
595 MustKeepGlobalVariables.
insert(GV);
596 else if (
const ConstantArray *CA = dyn_cast<ConstantArray>(
U->stripPointerCasts())) {
597 for (
const Use &Elt : CA->operands()) {
599 dyn_cast<GlobalVariable>(Elt->stripPointerCasts()))
600 MustKeepGlobalVariables.
insert(GV);
608bool GlobalMerge::doInitialization(
Module &M) {
614 auto &
DL =
M.getDataLayout();
616 Globals, ConstGlobals, BSSGlobals;
617 bool Changed =
false;
618 setMustKeepGlobalVariables(M);
621 dbgs() <<
"Number of GV that must be kept: " <<
622 MustKeepGlobalVariables.
size() <<
"\n";
624 dbgs() <<
"Kept: " << *KeptGV <<
"\n";
627 for (
auto &GV :
M.globals()) {
633 if (
TM && !
TM->shouldAssumeDSOLocal(M, &GV))
641 assert(PT &&
"Global variable is not a pointer!");
652 if (isMustKeepGlobalVariable(&GV))
664 if (
DL.getTypeAllocSize(Ty) < MaxOffset) {
675 for (
auto &
P : Globals)
676 if (
P.second.size() > 1)
677 Changed |= doMerge(
P.second, M,
false,
P.first.first);
679 for (
auto &
P : BSSGlobals)
680 if (
P.second.size() > 1)
681 Changed |= doMerge(
P.second, M,
false,
P.first.first);
684 for (
auto &
P : ConstGlobals)
685 if (
P.second.size() > 1)
686 Changed |= doMerge(
P.second, M,
true,
P.first.first);
691bool GlobalMerge::runOnFunction(
Function &
F) {
695bool GlobalMerge::doFinalization(
Module &M) {
696 MustKeepGlobalVariables.
clear();
701 bool OnlyOptimizeForSize,
702 bool MergeExternalByDefault) {
705 return new GlobalMerge(
TM,
Offset, OnlyOptimizeForSize, MergeExternal);
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 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 > 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.
const char LLVMTargetMachineRef TM
#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 SmallPtrSet class.
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)
This defines the Use class.
Represent the analysis usage information of a pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
LLVM Basic Block Representation.
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.
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(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
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...
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...
void setDLLStorageClass(DLLStorageClassTypes C)
DLLStorageClassTypes
Storage classes of global values for PE targets.
bool hasInternalLinkage() const
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...
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
void push_back(MachineInstr *MI)
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 bool doFinalization(Module &)
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
size_type size() const
Determine the number of elements in the SetVector.
void clear()
Completely clear the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
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 startswith(StringRef Prefix) const
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
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)
void initializeGlobalMergePass(PassRegistry &)
auto reverse(ContainerTy &&C)
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...
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.