#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Module.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetLoweringObjectFile.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>
using namespace llvm;
#define DEBUG_TYPE "global-merge"
static cl::opt<bool>
EnableGlobalMerge("enable-global-merge", cl::Hidden,
cl::desc("Enable the global merge pass"),
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> 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>
EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden,
cl::desc("Enable global merge pass on constants"),
cl::init(false));
static cl::opt<cl::boolOrDefault>
EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden,
cl::desc("Enable global merge pass on external linkage"));
STATISTIC(NumMerged, "Number of globals merged");
namespace {
class GlobalMerge : public FunctionPass {
const TargetMachine *TM;
unsigned MaxOffset;
bool OnlyOptimizeForSize;
bool MergeExternalGlobals;
bool doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
Module &M, bool isConst, unsigned AddrSpace) const;
bool doMerge(const SmallVectorImpl<GlobalVariable *> &Globals,
const BitVector &GlobalSet, Module &M, bool isConst,
unsigned AddrSpace) const;
bool isMustKeepGlobalVariable(const GlobalVariable *GV) const {
return MustKeepGlobalVariables.count(GV);
}
void setMustKeepGlobalVariables(Module &M);
void collectUsedGlobalVariables(Module &M);
SmallPtrSet<const GlobalVariable *, 16> MustKeepGlobalVariables;
public:
static char ID; explicit GlobalMerge(const TargetMachine *TM = nullptr,
unsigned MaximalOffset = 0,
bool OnlyOptimizeForSize = false,
bool MergeExternalGlobals = false)
: FunctionPass(ID), TM(TM), MaxOffset(MaximalOffset),
OnlyOptimizeForSize(OnlyOptimizeForSize),
MergeExternalGlobals(MergeExternalGlobals) {
initializeGlobalMergePass(*PassRegistry::getPassRegistry());
}
bool doInitialization(Module &M) override;
bool runOnFunction(Function &F) override;
bool doFinalization(Module &M) override;
const char *getPassName() const override {
return "Merge internal globals";
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
FunctionPass::getAnalysisUsage(AU);
}
};
}
char GlobalMerge::ID = 0;
INITIALIZE_PASS_BEGIN(GlobalMerge, "global-merge", "Merge global variables",
false, false)
INITIALIZE_PASS_END(GlobalMerge, "global-merge", "Merge global variables",
false, false)
bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
Module &M, bool isConst, unsigned AddrSpace) const {
auto &DL = M.getDataLayout();
std::stable_sort(Globals.begin(), Globals.end(),
[&DL](const GlobalVariable *GV1, const GlobalVariable *GV2) {
return DL.getTypeAllocSize(GV1->getValueType()) <
DL.getTypeAllocSize(GV2->getValueType());
});
if (!GlobalMergeGroupByUse) {
BitVector AllGlobals(Globals.size());
AllGlobals.set();
return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
}
struct UsedGlobalSet {
UsedGlobalSet(size_t Size) : Globals(Size), UsageCount(1) {}
BitVector Globals;
unsigned UsageCount;
};
std::vector<UsedGlobalSet> UsedGlobalSets;
auto CreateGlobalSet = [&]() -> UsedGlobalSet & {
UsedGlobalSets.emplace_back(Globals.size());
return UsedGlobalSets.back();
};
CreateGlobalSet().UsageCount = 0;
DenseMap<Function *, size_t > GlobalUsesByFunction;
std::vector<size_t> EncounteredUGS;
for (size_t GI = 0, GE = Globals.size(); GI != GE; ++GI) {
GlobalVariable *GV = Globals[GI];
std::fill(EncounteredUGS.begin(), EncounteredUGS.end(), 0);
EncounteredUGS.resize(UsedGlobalSets.size());
size_t CurGVOnlySetIdx = 0;
for (auto &U : GV->uses()) {
Use *UI, *UE;
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U.getUser())) {
if (CE->use_empty())
continue;
UI = &*CE->use_begin();
UE = nullptr;
} else if (isa<Instruction>(U.getUser())) {
UI = &U;
UE = UI->getNext();
} else {
continue;
}
for (; UI != UE; UI = UI->getNext()) {
Instruction *I = dyn_cast<Instruction>(UI->getUser());
if (!I)
continue;
Function *ParentFn = I->getParent()->getParent();
if (OnlyOptimizeForSize && !ParentFn->optForMinSize())
continue;
size_t UGSIdx = GlobalUsesByFunction[ParentFn];
if (!UGSIdx) {
if (!CurGVOnlySetIdx) {
CurGVOnlySetIdx = UsedGlobalSets.size();
CreateGlobalSet().Globals.set(GI);
} else {
++UsedGlobalSets[CurGVOnlySetIdx].UsageCount;
}
GlobalUsesByFunction[ParentFn] = CurGVOnlySetIdx;
continue;
}
if (UsedGlobalSets[UGSIdx].Globals.test(GI)) {
++UsedGlobalSets[UGSIdx].UsageCount;
continue;
}
--UsedGlobalSets[UGSIdx].UsageCount;
if (size_t ExpandedIdx = EncounteredUGS[UGSIdx]) {
++UsedGlobalSets[ExpandedIdx].UsageCount;
GlobalUsesByFunction[ParentFn] = ExpandedIdx;
continue;
}
GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] =
UsedGlobalSets.size();
UsedGlobalSet &NewUGS = CreateGlobalSet();
NewUGS.Globals.set(GI);
NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals;
}
}
}
std::sort(UsedGlobalSets.begin(), UsedGlobalSets.end(),
[](const UsedGlobalSet &UGS1, const UsedGlobalSet &UGS2) {
return UGS1.Globals.count() * UGS1.UsageCount <
UGS2.Globals.count() * UGS2.UsageCount;
});
if (GlobalMergeIgnoreSingleUse) {
BitVector AllGlobals(Globals.size());
for (size_t i = 0, e = UsedGlobalSets.size(); i != e; ++i) {
const UsedGlobalSet &UGS = UsedGlobalSets[e - i - 1];
if (UGS.UsageCount == 0)
continue;
if (UGS.Globals.count() > 1)
AllGlobals |= UGS.Globals;
}
return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);
}
BitVector PickedGlobals(Globals.size());
bool Changed = false;
for (size_t i = 0, e = UsedGlobalSets.size(); i != e; ++i) {
const UsedGlobalSet &UGS = UsedGlobalSets[e - i - 1];
if (UGS.UsageCount == 0)
continue;
if (PickedGlobals.anyCommon(UGS.Globals))
continue;
PickedGlobals |= UGS.Globals;
if (UGS.Globals.count() < 2)
continue;
Changed |= doMerge(Globals, UGS.Globals, M, isConst, AddrSpace);
}
return Changed;
}
bool GlobalMerge::doMerge(const SmallVectorImpl<GlobalVariable *> &Globals,
const BitVector &GlobalSet, Module &M, bool isConst,
unsigned AddrSpace) const {
assert(Globals.size() > 1);
Type *Int32Ty = Type::getInt32Ty(M.getContext());
auto &DL = M.getDataLayout();
DEBUG(dbgs() << " Trying to merge set, starts with #"
<< GlobalSet.find_first() << "\n");
ssize_t i = GlobalSet.find_first();
while (i != -1) {
ssize_t j = 0;
uint64_t MergedSize = 0;
std::vector<Type*> Tys;
std::vector<Constant*> Inits;
for (j = i; j != -1; j = GlobalSet.find_next(j)) {
Type *Ty = Globals[j]->getValueType();
MergedSize += DL.getTypeAllocSize(Ty);
if (MergedSize > MaxOffset) {
break;
}
Tys.push_back(Ty);
Inits.push_back(Globals[j]->getInitializer());
}
StructType *MergedTy = StructType::get(M.getContext(), Tys);
Constant *MergedInit = ConstantStruct::get(MergedTy, Inits);
GlobalVariable *MergedGV = new GlobalVariable(
M, MergedTy, isConst, GlobalValue::PrivateLinkage, MergedInit,
"_MergedGlobals", nullptr, GlobalVariable::NotThreadLocal, AddrSpace);
for (ssize_t k = i, idx = 0; k != j; k = GlobalSet.find_next(k), ++idx) {
GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage();
std::string Name = Globals[k]->getName();
Constant *Idx[2] = {
ConstantInt::get(Int32Ty, 0),
ConstantInt::get(Int32Ty, idx),
};
Constant *GEP =
ConstantExpr::getInBoundsGetElementPtr(MergedTy, MergedGV, Idx);
Globals[k]->replaceAllUsesWith(GEP);
Globals[k]->eraseFromParent();
if (Linkage != GlobalValue::InternalLinkage ||
!TM->getTargetTriple().isOSBinFormatMachO()) {
GlobalAlias::create(Tys[idx], AddrSpace, Linkage, Name, GEP, &M);
}
NumMerged++;
}
i = j;
}
return true;
}
void GlobalMerge::collectUsedGlobalVariables(Module &M) {
const GlobalVariable *GV = M.getGlobalVariable("llvm.used");
if (!GV || !GV->hasInitializer()) return;
const ConstantArray *InitList = cast<ConstantArray>(GV->getInitializer());
for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i)
if (const GlobalVariable *G =
dyn_cast<GlobalVariable>(InitList->getOperand(i)->stripPointerCasts()))
MustKeepGlobalVariables.insert(G);
}
void GlobalMerge::setMustKeepGlobalVariables(Module &M) {
collectUsedGlobalVariables(M);
for (Module::iterator IFn = M.begin(), IEndFn = M.end(); IFn != IEndFn;
++IFn) {
for (Function::iterator IBB = IFn->begin(), IEndBB = IFn->end();
IBB != IEndBB; ++IBB) {
const InvokeInst *II = dyn_cast<InvokeInst>(IBB->getTerminator());
if (!II) continue;
const LandingPadInst *LPInst = II->getUnwindDest()->getLandingPadInst();
for (unsigned Idx = 0, NumClauses = LPInst->getNumClauses();
Idx != NumClauses; ++Idx)
if (const GlobalVariable *GV =
dyn_cast<GlobalVariable>(LPInst->getClause(Idx)
->stripPointerCasts()))
MustKeepGlobalVariables.insert(GV);
}
}
}
bool GlobalMerge::doInitialization(Module &M) {
if (!EnableGlobalMerge)
return false;
auto &DL = M.getDataLayout();
DenseMap<unsigned, SmallVector<GlobalVariable*, 16> > Globals, ConstGlobals,
BSSGlobals;
bool Changed = false;
setMustKeepGlobalVariables(M);
for (auto &GV : M.globals()) {
if (GV.isDeclaration() || GV.isThreadLocal() || GV.hasSection())
continue;
if (!(MergeExternalGlobals && GV.hasExternalLinkage()) &&
!GV.hasInternalLinkage())
continue;
PointerType *PT = dyn_cast<PointerType>(GV.getType());
assert(PT && "Global variable is not a pointer!");
unsigned AddressSpace = PT->getAddressSpace();
unsigned Alignment = DL.getPreferredAlignment(&GV);
Type *Ty = GV.getValueType();
if (Alignment > DL.getABITypeAlignment(Ty))
continue;
if (GV.getName().startswith("llvm.") ||
GV.getName().startswith(".llvm."))
continue;
if (isMustKeepGlobalVariable(&GV))
continue;
if (DL.getTypeAllocSize(Ty) < MaxOffset) {
if (TargetLoweringObjectFile::getKindForGlobal(&GV, *TM).isBSSLocal())
BSSGlobals[AddressSpace].push_back(&GV);
else if (GV.isConstant())
ConstGlobals[AddressSpace].push_back(&GV);
else
Globals[AddressSpace].push_back(&GV);
}
}
for (auto &P : Globals)
if (P.second.size() > 1)
Changed |= doMerge(P.second, M, false, P.first);
for (auto &P : BSSGlobals)
if (P.second.size() > 1)
Changed |= doMerge(P.second, M, false, P.first);
if (EnableGlobalMergeOnConst)
for (auto &P : ConstGlobals)
if (P.second.size() > 1)
Changed |= doMerge(P.second, M, true, P.first);
return Changed;
}
bool GlobalMerge::runOnFunction(Function &F) {
return false;
}
bool GlobalMerge::doFinalization(Module &M) {
MustKeepGlobalVariables.clear();
return false;
}
Pass *llvm::createGlobalMergePass(const TargetMachine *TM, unsigned Offset,
bool OnlyOptimizeForSize,
bool MergeExternalByDefault) {
bool MergeExternal = (EnableGlobalMergeOnExternal == cl::BOU_UNSET) ?
MergeExternalByDefault : (EnableGlobalMergeOnExternal == cl::BOU_TRUE);
return new GlobalMerge(TM, Offset, OnlyOptimizeForSize, MergeExternal);
}