Page MenuHomePhabricator
Differential D3432 Diff 9137 lib/Transforms/Scalar/GlobalMerge.cpp

Changeset View

Standalone View

View Options

lib/Transforms/Scalar/GlobalMerge.cpp

PropertyOld ValueNew Value
File Mode100644100755
Context not available.
#define DEBUG_TYPE "global-merge" #define DEBUG_TYPE "global-merge"
static cl::opt<bool> static cl::opt<bool>
EnableGlobalMerge("global-merge", cl::Hidden, EnableGlobalMerge("enable-global-merge", cl::NotHidden,
cl::desc("Enable global merge pass"), cl::desc("Enable global merge pass"),
cl::init(true)); cl::init(true));
Context not available.
cl::desc("Enable global merge pass on constants"), cl::desc("Enable global merge pass on constants"),
cl::init(false)); cl::init(false));
static cl::opt<bool>
EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden,
cl::desc("Enable global merge pass on external linkage"),
cl::init(false));
STATISTIC(NumMerged , "Number of globals merged"); STATISTIC(NumMerged , "Number of globals merged");
namespace { namespace {
class GlobalMerge : public FunctionPass { class GlobalMerge : public FunctionPass {
Context not available.
} // end anonymous namespace } // end anonymous namespace
char GlobalMerge::ID = 0; char GlobalMerge::ID = 0;
INITIALIZE_PASS(GlobalMerge, "global-merge",
"Global Merge", false, false)
static void *initializeGlobalMergePassOnce(PassRegistry &Registry) {
PassInfo *PI = new PassInfo(
"Merge global variables",
"global-merge", &GlobalMerge::ID,
PassInfo::NormalCtor_t(callDefaultCtor<GlobalMerge>), false,
false, PassInfo::TargetMachineCtor_t(
callTargetMachineCtor<GlobalMerge>));
Registry.registerPass(*PI, true);
return PI;
}
void llvm::initializeGlobalMergePass(PassRegistry &Registry) {
CALL_ONCE_INITIALIZATION(initializeGlobalMergePassOnce)
}
bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals, bool GlobalMerge::doMerge(SmallVectorImpl<GlobalVariable*> &Globals,
Module &M, bool isConst, unsigned AddrSpace) const { Module &M, bool isConst, unsigned AddrSpace) const {
qcolombetUnsubmitted
Not Done
ReplyInline Actions

Should be hoisted outside of the loop, since we assert this does not change within the loop.

qcolombet: Should be hoisted outside of the loop, since we assert this does not change within the loop.
JiangningAuthorUnsubmitted
Not Done
ReplyInline Actions

Accept and fixed by the new version uploaded.

Jiangning: Accept and fixed by the new version uploaded.
Context not available.
Type *Int32Ty = Type::getInt32Ty(M.getContext()); Type *Int32Ty = Type::getInt32Ty(M.getContext());
assert (Globals.size() > 1);
bool IsExternal = Globals[0]->hasExternalLinkage();
// If merged variables doesn't have external linkage, we needn't to expose
// the symbol after merging.
GlobalValue::LinkageTypes Linkage = IsExternal ?
GlobalValue::ExternalLinkage :
GlobalValue::InternalLinkage ;
for (size_t i = 0, e = Globals.size(); i != e; ) { for (size_t i = 0, e = Globals.size(); i != e; ) {
size_t j = 0; size_t j = 0;
uint64_t MergedSize = 0; uint64_t MergedSize = 0;
std::vector<Type*> Tys; std::vector<Type*> Tys;
std::vector<Constant*> Inits; std::vector<Constant*> Inits;
for (j = i; j != e; ++j) { for (j = i; j != e; ++j) {
qcolombetUnsubmitted
Not Done
ReplyInline Actions

Ditto.

qcolombet: Ditto.
JiangningAuthorUnsubmitted
Not Done
ReplyInline Actions

Accept and fixed by the new version uploaded.

Jiangning: Accept and fixed by the new version uploaded.
Type *Ty = Globals[j]->getType()->getElementType(); Type *Ty = Globals[j]->getType()->getElementType();
MergedSize += DL->getTypeAllocSize(Ty); MergedSize += DL->getTypeAllocSize(Ty);
Context not available.
} }
Tys.push_back(Ty); Tys.push_back(Ty);
Inits.push_back(Globals[j]->getInitializer()); Inits.push_back(Globals[j]->getInitializer());
// Globals have been classified, the globals passed to this function
// must all have the same linkage.
assert(Globals[i]->hasExternalLinkage() == IsExternal);
} }
StructType *MergedTy = StructType::get(M.getContext(), Tys); StructType *MergedTy = StructType::get(M.getContext(), Tys);
Constant *MergedInit = ConstantStruct::get(MergedTy, Inits); Constant *MergedInit = ConstantStruct::get(MergedTy, Inits);
qcolombetUnsubmitted
Not Done
ReplyInline Actions

This is the alignment thing I was talking about.

qcolombet: This is the alignment thing I was talking about.
JiangningAuthorUnsubmitted
Not Done
ReplyInline Actions

Hi Quentin,

Appreciate for your further feedback!

I understand your point. Actually I think we have three solutions to solve this ADRP issue, let me summarize them, and make sure our discussion is on the same page.

  1. Materialize the base address of merged global data structure with a single register. MOVAddr in ARM64 just does this work. This is essentially to use "adrp + add" to compute the base of merged global data structure. This way, the merge global data structure needn't the structure size alignment, but the natural alignment. The disadvantage of this solution is, at compile time we don't really know if the offset in add instruction can really be propagated and combined into load/store instructions, because it might be larger than a page size. For this solution the instruction sequence could be like below, (Suppose we have three loads)

adrp r0, MergedGlobal@PAGE
add r1, r0, MergedGlobal@PAGE_OFF
load [r1, var1_offset_within_MergedGlobal]
load [r1, var2_offset_within_MergedGlobal]
load [r1, var3_offset_within_MergedGlobal]

Refer to the chart below as well,

page 1                     page 2

r0
------------------------------r1-----------| // merged global data structure
----------------------------s-------e
var1_offset_within_MergedGlobal = e - s

(MergedGlobal@PAGE_OFF + var1_offset_within_MergedGlobal) > PageSize
  1. We don't use a single register to describe the base address of merged global data structure at all. If we can guarantee the merged global data structure is always within a page, and doesn't cross page boundary, we would be able make sure the offset from the page boundary is always smaller than a page, so at compile time, the offset to page boundary would be able to be fused into load/store instruction directly. Setting the alignment to be the maximum merged data structure size could guarantee the merged data structure doesn't cross page boundary. The disadvantage of this solution is, we would probably increase run-time memory consumption, because there might be some "holes" in data section. With this solution, we would have the following instruction sequence finally,

adrp r0, MergedGlobal@PAGE
load [r0, var1_offset_within_PAGE]
load [r0, var2_offset_within_PAGE]
load [r0, var3_offset_within_PAGE]

Refer to the chart below as well,

page 1                     page 2

r0
--------------------|----------| // merged global data structure
s----------------------e
var1_offset_within_PAGE = e - s

  1. We use link-time solution to help the removal of ADRP and ADD. Link-time optimization might not be cost-less because the dead instruction can only be replaced with NOP instruction.

Both solution 1) and 2) can remove some ADRPs statically. And the ADD introduced in solution 1) could probably be reduced by solution 3) as well.

Do you think the disadvantage with solution 2) is unacceptable?

Thanks,
-Jiangning

Jiangning: Hi Quentin, Appreciate for your further feedback! I understand your point. Actually I think…
// If merged variables have external linkage, we use symbol name of the
// first variable merged as the suffix of global symbol name.
Twine MergedGVName = IsExternal ?
"_MergedGlobals_" + Globals[i]->getName() :
"_MergedGlobals" ;
GlobalVariable *MergedGV = new GlobalVariable(M, MergedTy, isConst, GlobalVariable *MergedGV = new GlobalVariable(M, MergedTy, isConst,
GlobalValue::InternalLinkage, Linkage, MergedInit, MergedGVName,
MergedInit, "_MergedGlobals", nullptr, GlobalVariable::NotThreadLocal,
nullptr, AddrSpace);
GlobalVariable::NotThreadLocal,
AddrSpace); if (EnableGlobalMergeOnExternal && IsExternal) {
qcolombetUnsubmitted
Not Done
ReplyInline Actions

Any reason why we do not want to set an alignment for the internal too?

qcolombet: Any reason why we do not want to set an alignment for the internal too?
// If the alignment is not a power of 2, round up to the next power of 2.
unsigned Align = TLI->getGMOnExternalAlignment(MergedTy);
assert(((Align % DL->getABITypeAlignment(MergedTy)) == 0) &&
"Specified alignment doesn't meet natural alignment requirement.");
MergedGV->setAlignment(Align);
}
for (size_t k = i; k < j; ++k) { for (size_t k = i; k < j; ++k) {
GlobalValue::LinkageTypes Linkage = Globals[k]->getLinkage();
std::string Name = Globals[k]->getName();
Constant *Idx[2] = { Constant *Idx[2] = {
ConstantInt::get(Int32Ty, 0), ConstantInt::get(Int32Ty, 0),
ConstantInt::get(Int32Ty, k-i) ConstantInt::get(Int32Ty, k-i)
Context not available.
Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx); Constant *GEP = ConstantExpr::getInBoundsGetElementPtr(MergedGV, Idx);
Globals[k]->replaceAllUsesWith(GEP); Globals[k]->replaceAllUsesWith(GEP);
Globals[k]->eraseFromParent(); Globals[k]->eraseFromParent();
if (Linkage != GlobalValue::InternalLinkage) {
// Generate a new alias...
new GlobalAlias(GEP->getType(), Linkage, Name, GEP, &M);
}
NumMerged++; NumMerged++;
} }
i = j; i = j;
t.p.northoverUnsubmitted
Not Done
ReplyInline Actions

This might be clearer split up. I know my brain starts to melt when I see massive nested conditionals like this. Perhaps linkage conditions vs intrinsic blockers?

t.p.northover: This might be clearer split up. I know my brain starts to melt when I see massive nested…
JiangningAuthorUnsubmitted
Not Done
ReplyInline Actions

Tim, That's OK, and I've split it up in new version.

Jiangning: Tim, That's OK, and I've split it up in new version.
Context not available.
// Grab all non-const globals. // Grab all non-const globals.
for (Module::global_iterator I = M.global_begin(), for (Module::global_iterator I = M.global_begin(),
E = M.global_end(); I != E; ++I) { E = M.global_end(); I != E; ++I) {
// Merge is safe for "normal" internal globals only // Merge is safe for "normal" internal or external globals only
if (!I->hasLocalLinkage() || I->isThreadLocal() || I->hasSection()) if (I->isDeclaration() || I->isThreadLocal() || I->hasSection())
continue;
if (!(EnableGlobalMergeOnExternal && I->hasExternalLinkage())
&& !I->hasInternalLinkage())
continue; continue;
PointerType *PT = dyn_cast<PointerType>(I->getType()); PointerType *PT = dyn_cast<PointerType>(I->getType());
Context not available.