IR: Add COMDATs to the IR
This new IR facility allows us to represent the object-file semantic of
a COMDAT group.
COMDATs allow us to tie together sections and make the inclusion of one
dependent on another. This is required to implement features like MS
ABI VFTables and optimizing away certain kinds of initialization in C++.
This functionality is only representable in COFF and ELF, Mach-O has no
similar mechanism.
Differential Revision: http://reviews.llvm.org/D4178
llvm-svn: 211920
diff --git a/llvm/lib/Linker/LinkModules.cpp b/llvm/lib/Linker/LinkModules.cpp
index 688b13f..eb73a49 100644
--- a/llvm/lib/Linker/LinkModules.cpp
+++ b/llvm/lib/Linker/LinkModules.cpp
@@ -426,6 +426,18 @@
return true;
}
+ bool getComdatLeader(Module *M, StringRef ComdatName,
+ const GlobalVariable *&GVar);
+ bool computeResultingSelectionKind(StringRef ComdatName,
+ Comdat::SelectionKind Src,
+ Comdat::SelectionKind Dst,
+ Comdat::SelectionKind &Result,
+ bool &LinkFromSrc);
+ std::map<const Comdat *, std::pair<Comdat::SelectionKind, bool>>
+ ComdatsChosen;
+ bool getComdatResult(const Comdat *SrcC, Comdat::SelectionKind &SK,
+ bool &LinkFromSrc);
+
/// getLinkageResult - This analyzes the two global values and determines
/// what the result will look like in the destination module.
bool getLinkageResult(GlobalValue *Dest, const GlobalValue *Src,
@@ -534,6 +546,115 @@
return DF;
}
+bool ModuleLinker::getComdatLeader(Module *M, StringRef ComdatName,
+ const GlobalVariable *&GVar) {
+ const GlobalValue *GVal = M->getNamedValue(ComdatName);
+ if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
+ GVal = GA->getBaseObject();
+ if (!GVal)
+ // We cannot resolve the size of the aliasee yet.
+ return emitError("Linking COMDATs named '" + ComdatName +
+ "': COMDAT key involves incomputable alias size.");
+ }
+
+ GVar = dyn_cast_or_null<GlobalVariable>(GVal);
+ if (!GVar)
+ return emitError(
+ "Linking COMDATs named '" + ComdatName +
+ "': GlobalVariable required for data dependent selection!");
+
+ return false;
+}
+
+bool ModuleLinker::computeResultingSelectionKind(StringRef ComdatName,
+ Comdat::SelectionKind Src,
+ Comdat::SelectionKind Dst,
+ Comdat::SelectionKind &Result,
+ bool &LinkFromSrc) {
+ // The ability to mix Comdat::SelectionKind::Any with
+ // Comdat::SelectionKind::Largest is a behavior that comes from COFF.
+ bool DstAnyOrLargest = Dst == Comdat::SelectionKind::Any ||
+ Dst == Comdat::SelectionKind::Largest;
+ bool SrcAnyOrLargest = Src == Comdat::SelectionKind::Any ||
+ Src == Comdat::SelectionKind::Largest;
+ if (DstAnyOrLargest && SrcAnyOrLargest) {
+ if (Dst == Comdat::SelectionKind::Largest ||
+ Src == Comdat::SelectionKind::Largest)
+ Result = Comdat::SelectionKind::Largest;
+ else
+ Result = Comdat::SelectionKind::Any;
+ } else if (Src == Dst) {
+ Result = Dst;
+ } else {
+ return emitError("Linking COMDATs named '" + ComdatName +
+ "': invalid selection kinds!");
+ }
+
+ switch (Result) {
+ case Comdat::SelectionKind::Any:
+ // Go with Dst.
+ LinkFromSrc = false;
+ break;
+ case Comdat::SelectionKind::NoDuplicates:
+ return emitError("Linking COMDATs named '" + ComdatName +
+ "': noduplicates has been violated!");
+ case Comdat::SelectionKind::ExactMatch:
+ case Comdat::SelectionKind::Largest:
+ case Comdat::SelectionKind::SameSize: {
+ const GlobalVariable *DstGV;
+ const GlobalVariable *SrcGV;
+ if (getComdatLeader(DstM, ComdatName, DstGV) ||
+ getComdatLeader(SrcM, ComdatName, SrcGV))
+ return true;
+
+ const DataLayout *DstDL = DstM->getDataLayout();
+ const DataLayout *SrcDL = SrcM->getDataLayout();
+ if (!DstDL || !SrcDL) {
+ return emitError(
+ "Linking COMDATs named '" + ComdatName +
+ "': can't do size dependent selection without DataLayout!");
+ }
+ uint64_t DstSize =
+ DstDL->getTypeAllocSize(DstGV->getType()->getPointerElementType());
+ uint64_t SrcSize =
+ SrcDL->getTypeAllocSize(SrcGV->getType()->getPointerElementType());
+ if (Result == Comdat::SelectionKind::ExactMatch) {
+ if (SrcGV->getInitializer() != DstGV->getInitializer())
+ return emitError("Linking COMDATs named '" + ComdatName +
+ "': ExactMatch violated!");
+ LinkFromSrc = false;
+ } else if (Result == Comdat::SelectionKind::Largest) {
+ LinkFromSrc = SrcSize > DstSize;
+ } else if (Result == Comdat::SelectionKind::SameSize) {
+ if (SrcSize != DstSize)
+ return emitError("Linking COMDATs named '" + ComdatName +
+ "': SameSize violated!");
+ LinkFromSrc = false;
+ } else {
+ llvm_unreachable("unknown selection kind");
+ }
+ break;
+ }
+ }
+
+ return false;
+}
+
+bool ModuleLinker::getComdatResult(const Comdat *SrcC,
+ Comdat::SelectionKind &Result,
+ bool &LinkFromSrc) {
+ StringRef ComdatName = SrcC->getName();
+ Module::ComdatSymTabType &ComdatSymTab = DstM->getComdatSymbolTable();
+ Module::ComdatSymTabType::iterator DstCI = ComdatSymTab.find(ComdatName);
+ if (DstCI != ComdatSymTab.end()) {
+ const Comdat *DstC = &DstCI->second;
+ Comdat::SelectionKind SSK = SrcC->getSelectionKind();
+ Comdat::SelectionKind DSK = DstC->getSelectionKind();
+ if (computeResultingSelectionKind(ComdatName, SSK, DSK, Result, LinkFromSrc))
+ return true;
+ }
+ return false;
+}
/// getLinkageResult - This analyzes the two global values and determines what
/// the result will look like in the destination module. In particular, it
@@ -764,34 +885,47 @@
llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
bool HasUnnamedAddr = SGV->hasUnnamedAddr();
+ bool LinkFromSrc = false;
+ Comdat *DC = nullptr;
+ if (const Comdat *SC = SGV->getComdat()) {
+ Comdat::SelectionKind SK;
+ std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
+ DC = DstM->getOrInsertComdat(SC->getName());
+ DC->setSelectionKind(SK);
+ }
+
if (DGV) {
- // Concatenation of appending linkage variables is magic and handled later.
- if (DGV->hasAppendingLinkage() || SGV->hasAppendingLinkage())
- return linkAppendingVarProto(cast<GlobalVariable>(DGV), SGV);
+ if (!DC) {
+ // Concatenation of appending linkage variables is magic and handled later.
+ if (DGV->hasAppendingLinkage() || SGV->hasAppendingLinkage())
+ return linkAppendingVarProto(cast<GlobalVariable>(DGV), SGV);
- // Determine whether linkage of these two globals follows the source
- // module's definition or the destination module's definition.
- GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
- GlobalValue::VisibilityTypes NV;
- bool LinkFromSrc = false;
- if (getLinkageResult(DGV, SGV, NewLinkage, NV, LinkFromSrc))
- return true;
- NewVisibility = NV;
- HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
+ // Determine whether linkage of these two globals follows the source
+ // module's definition or the destination module's definition.
+ GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
+ GlobalValue::VisibilityTypes NV;
+ if (getLinkageResult(DGV, SGV, NewLinkage, NV, LinkFromSrc))
+ return true;
+ NewVisibility = NV;
+ HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
- // If we're not linking from the source, then keep the definition that we
- // have.
+ // If we're not linking from the source, then keep the definition that we
+ // have.
+ if (!LinkFromSrc) {
+ // Special case for const propagation.
+ if (GlobalVariable *DGVar = dyn_cast<GlobalVariable>(DGV))
+ if (DGVar->isDeclaration() && SGV->isConstant() &&
+ !DGVar->isConstant())
+ DGVar->setConstant(true);
+
+ // Set calculated linkage, visibility and unnamed_addr.
+ DGV->setLinkage(NewLinkage);
+ DGV->setVisibility(*NewVisibility);
+ DGV->setUnnamedAddr(HasUnnamedAddr);
+ }
+ }
+
if (!LinkFromSrc) {
- // Special case for const propagation.
- if (GlobalVariable *DGVar = dyn_cast<GlobalVariable>(DGV))
- if (DGVar->isDeclaration() && SGV->isConstant() && !DGVar->isConstant())
- DGVar->setConstant(true);
-
- // Set calculated linkage, visibility and unnamed_addr.
- DGV->setLinkage(NewLinkage);
- DGV->setVisibility(*NewVisibility);
- DGV->setUnnamedAddr(HasUnnamedAddr);
-
// Make sure to remember this mapping.
ValueMap[SGV] = ConstantExpr::getBitCast(DGV,TypeMap.get(SGV->getType()));
@@ -803,6 +937,12 @@
}
}
+ // If the Comdat this variable was inside of wasn't selected, skip it.
+ if (DC && !DGV && !LinkFromSrc) {
+ DoNotLinkFromSource.insert(SGV);
+ return false;
+ }
+
// No linking to be performed or linking from the source: simply create an
// identical version of the symbol over in the dest module... the
// initializer will be filled in later by LinkGlobalInits.
@@ -818,6 +958,9 @@
NewDGV->setVisibility(*NewVisibility);
NewDGV->setUnnamedAddr(HasUnnamedAddr);
+ if (DC)
+ NewDGV->setComdat(DC);
+
if (DGV) {
DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDGV, DGV->getType()));
DGV->eraseFromParent();
@@ -835,21 +978,33 @@
llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
bool HasUnnamedAddr = SF->hasUnnamedAddr();
+ bool LinkFromSrc = false;
+ Comdat *DC = nullptr;
+ if (const Comdat *SC = SF->getComdat()) {
+ Comdat::SelectionKind SK;
+ std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
+ DC = DstM->getOrInsertComdat(SC->getName());
+ DC->setSelectionKind(SK);
+ }
+
if (DGV) {
- GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
- bool LinkFromSrc = false;
- GlobalValue::VisibilityTypes NV;
- if (getLinkageResult(DGV, SF, NewLinkage, NV, LinkFromSrc))
- return true;
- NewVisibility = NV;
- HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
+ if (!DC) {
+ GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
+ GlobalValue::VisibilityTypes NV;
+ if (getLinkageResult(DGV, SF, NewLinkage, NV, LinkFromSrc))
+ return true;
+ NewVisibility = NV;
+ HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
+
+ if (!LinkFromSrc) {
+ // Set calculated linkage
+ DGV->setLinkage(NewLinkage);
+ DGV->setVisibility(*NewVisibility);
+ DGV->setUnnamedAddr(HasUnnamedAddr);
+ }
+ }
if (!LinkFromSrc) {
- // Set calculated linkage
- DGV->setLinkage(NewLinkage);
- DGV->setVisibility(*NewVisibility);
- DGV->setUnnamedAddr(HasUnnamedAddr);
-
// Make sure to remember this mapping.
ValueMap[SF] = ConstantExpr::getBitCast(DGV, TypeMap.get(SF->getType()));
@@ -869,6 +1024,12 @@
return false;
}
+ // If the Comdat this function was inside of wasn't selected, skip it.
+ if (DC && !DGV && !LinkFromSrc) {
+ DoNotLinkFromSource.insert(SF);
+ return false;
+ }
+
// If there is no linkage to be performed or we are linking from the source,
// bring SF over.
Function *NewDF = Function::Create(TypeMap.get(SF->getFunctionType()),
@@ -878,6 +1039,9 @@
NewDF->setVisibility(*NewVisibility);
NewDF->setUnnamedAddr(HasUnnamedAddr);
+ if (DC)
+ NewDF->setComdat(DC);
+
if (DGV) {
// Any uses of DF need to change to NewDF, with cast.
DGV->replaceAllUsesWith(ConstantExpr::getBitCast(NewDF, DGV->getType()));
@@ -895,21 +1059,33 @@
llvm::Optional<GlobalValue::VisibilityTypes> NewVisibility;
bool HasUnnamedAddr = SGA->hasUnnamedAddr();
+ bool LinkFromSrc = false;
+ Comdat *DC = nullptr;
+ if (const Comdat *SC = SGA->getComdat()) {
+ Comdat::SelectionKind SK;
+ std::tie(SK, LinkFromSrc) = ComdatsChosen[SC];
+ DC = DstM->getOrInsertComdat(SC->getName());
+ DC->setSelectionKind(SK);
+ }
+
if (DGV) {
- GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
- GlobalValue::VisibilityTypes NV;
- bool LinkFromSrc = false;
- if (getLinkageResult(DGV, SGA, NewLinkage, NV, LinkFromSrc))
- return true;
- NewVisibility = NV;
- HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
+ if (!DC) {
+ GlobalValue::LinkageTypes NewLinkage = GlobalValue::InternalLinkage;
+ GlobalValue::VisibilityTypes NV;
+ if (getLinkageResult(DGV, SGA, NewLinkage, NV, LinkFromSrc))
+ return true;
+ NewVisibility = NV;
+ HasUnnamedAddr = HasUnnamedAddr && DGV->hasUnnamedAddr();
+
+ if (!LinkFromSrc) {
+ // Set calculated linkage.
+ DGV->setLinkage(NewLinkage);
+ DGV->setVisibility(*NewVisibility);
+ DGV->setUnnamedAddr(HasUnnamedAddr);
+ }
+ }
if (!LinkFromSrc) {
- // Set calculated linkage.
- DGV->setLinkage(NewLinkage);
- DGV->setVisibility(*NewVisibility);
- DGV->setUnnamedAddr(HasUnnamedAddr);
-
// Make sure to remember this mapping.
ValueMap[SGA] = ConstantExpr::getBitCast(DGV,TypeMap.get(SGA->getType()));
@@ -920,6 +1096,12 @@
}
}
+ // If the Comdat this alias was inside of wasn't selected, skip it.
+ if (DC && !DGV && !LinkFromSrc) {
+ DoNotLinkFromSource.insert(SGA);
+ return false;
+ }
+
// If there is no linkage to be performed or we're linking from the source,
// bring over SGA.
auto *PTy = cast<PointerType>(TypeMap.get(SGA->getType()));
@@ -1254,6 +1436,18 @@
// Loop over all of the linked values to compute type mappings.
computeTypeMapping();
+ ComdatsChosen.clear();
+ for (const StringMapEntry<llvm::Comdat> &SMEC : SrcM->getComdatSymbolTable()) {
+ const Comdat &C = SMEC.getValue();
+ if (ComdatsChosen.count(&C))
+ continue;
+ Comdat::SelectionKind SK;
+ bool LinkFromSrc;
+ if (getComdatResult(&C, SK, LinkFromSrc))
+ return true;
+ ComdatsChosen[&C] = std::make_pair(SK, LinkFromSrc);
+ }
+
// Insert all of the globals in src into the DstM module... without linking
// initializers (which could refer to functions not yet mapped over).
for (Module::global_iterator I = SrcM->global_begin(),