Skip to content

Commit a89a593

Browse files
mtrofinmtrofin
authored
[CFI] Refactor CfiFunctionIndex to externalize GUID calculation (#201635)
In preparation for PR #201370 - the goal is to decouple CFI from _how_ ThinLTO computes its GUIDs, and enable PR #184065 (for this [RFC](https://discourse.llvm.org/t/rfc-keep-globalvalue-guids-stable/84801)). This PR just changes APIs and the internal implementation of CfiFunctionIndex, the subsequent one (201370) actually propagates GUIDs through metadata. It's _almost_ NFC - the YAML format does change though.
1 parent e4828aa commit a89a593

13 files changed

Lines changed: 172 additions & 115 deletions

File tree

‎llvm/include/llvm/IR/ModuleSummaryIndex.h‎

Lines changed: 56 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -18,11 +18,13 @@
1818
#include "llvm/ADT/ArrayRef.h"
1919
#include "llvm/ADT/DenseMap.h"
2020
#include "llvm/ADT/STLExtras.h"
21+
#include "llvm/ADT/SetVector.h"
2122
#include "llvm/ADT/SmallString.h"
2223
#include "llvm/ADT/SmallVector.h"
2324
#include "llvm/ADT/StringExtras.h"
2425
#include "llvm/ADT/StringMap.h"
2526
#include "llvm/ADT/StringRef.h"
27+
#include "llvm/ADT/StringSet.h"
2628
#include "llvm/ADT/iterator_range.h"
2729
#include "llvm/IR/ConstantRange.h"
2830
#include "llvm/IR/GlobalValue.h"
@@ -1317,72 +1319,77 @@ struct TypeIdSummary {
13171319
std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
13181320
};
13191321

1322+
/// Encapsulate the names of CFI target functions. It interfaces with ThinLTO to
1323+
/// determine efficiently which of the names need to be exported for a
1324+
/// particular module.
13201325
class CfiFunctionIndex {
1321-
DenseMap<GlobalValue::GUID, std::set<std::string, std::less<>>> Index;
1322-
using IndexIterator =
1323-
DenseMap<GlobalValue::GUID,
1324-
std::set<std::string, std::less<>>>::const_iterator;
1325-
using NestedIterator = std::set<std::string, std::less<>>::const_iterator;
1326+
// `Names` is the authoritative source of data. `ThinLTOToNamesIndex` is there
1327+
// just to efficiently retrieve which names in this index need exporting for
1328+
// a particular module index. We cannot guarantee the ThinLTO GUIDs are
1329+
// collision - free, so we associate a collection to a guid. Functions with
1330+
// the same name may have different GUIDs, too. So we index a list of names
1331+
// with the same GUID under that GUID key. We don't need the reverse because
1332+
// the queries from ThinLTO use GUIDs as key.
1333+
// Note that StringSet rehashing doesn't move keys, so we can safely store the
1334+
// StringRef value inserted in `Names` in ThinLTOToNamesIndex, and avoid
1335+
// copies.
1336+
// Design note: we could do away with Names and use ThinLTOToNamesIndex as
1337+
// index and data source, but opted against, for a small heap penalty, to
1338+
// avoid confusion wrt the role GUIDs play in this case: they are an artifact
1339+
// of the need to interface with ThinLTO, not otherwise necessary to CFI.
1340+
StringSet<> Names;
1341+
1342+
using InternalIndexGroup = SetVector<StringRef>;
1343+
DenseMap<GlobalValue::GUID, InternalIndexGroup> ThinLTOToNamesIndex;
1344+
1345+
using NestedIterator = InternalIndexGroup::const_iterator;
13261346

13271347
public:
1328-
// Iterates keys of the DenseMap.
1329-
class GUIDIterator : public iterator_adaptor_base<GUIDIterator, IndexIterator,
1330-
std::forward_iterator_tag,
1331-
GlobalValue::GUID> {
1332-
using base = GUIDIterator::iterator_adaptor_base;
1333-
1334-
public:
1335-
GUIDIterator() = default;
1336-
explicit GUIDIterator(IndexIterator I) : base(I) {}
1337-
1338-
GlobalValue::GUID operator*() const { return this->wrapped()->first; }
1339-
};
1340-
13411348
CfiFunctionIndex() = default;
1342-
template <typename It> CfiFunctionIndex(It B, It E) {
1343-
for (; B != E; ++B)
1344-
emplace(*B);
1345-
}
1346-
1347-
std::vector<StringRef> symbols() const {
1348-
std::vector<StringRef> Symbols;
1349-
for (auto &[GUID, Syms] : Index) {
1350-
(void)GUID;
1351-
llvm::append_range(Symbols, Syms);
1352-
}
1349+
CfiFunctionIndex(const CfiFunctionIndex &) = delete;
1350+
CfiFunctionIndex(CfiFunctionIndex &&) = default;
1351+
1352+
/// API used for serialization, e.g. YAML.
1353+
std::vector<std::pair<StringRef, GlobalValue::GUID>>
1354+
getSortedSymbols() const {
1355+
std::vector<std::pair<StringRef, GlobalValue::GUID>> Symbols;
1356+
for (auto &[GUID, Names] : ThinLTOToNamesIndex)
1357+
for (auto Name : Names)
1358+
Symbols.emplace_back(Name, GUID);
1359+
llvm::sort(Symbols);
13531360
return Symbols;
13541361
}
13551362

1356-
GUIDIterator guid_begin() const { return GUIDIterator(Index.begin()); }
1357-
GUIDIterator guid_end() const { return GUIDIterator(Index.end()); }
1358-
iterator_range<GUIDIterator> guids() const {
1359-
return make_range(guid_begin(), guid_end());
1363+
/// get the set of GUIDs that should also be exported because they are the
1364+
/// GUIDs of the cfi functions encapsulated here.
1365+
auto getExportedThinLTOGUIDs() const {
1366+
return map_range(ThinLTOToNamesIndex, [](auto I) { return I.first; });
13601367
}
13611368

1362-
iterator_range<NestedIterator> forGuid(GlobalValue::GUID GUID) const {
1363-
auto I = Index.find(GUID);
1364-
if (I == Index.end())
1369+
/// get the name(s) associated with a given ThinLTO GUID. This enables
1370+
/// efficient identification of the subset of names that should be included in
1371+
/// a module summary.
1372+
auto getNamesForGUID(GlobalValue::GUID GUID) const {
1373+
auto I = ThinLTOToNamesIndex.find(GUID);
1374+
if (I == ThinLTOToNamesIndex.end())
13651375
return make_range(NestedIterator{}, NestedIterator{});
13661376
return make_range(I->second.begin(), I->second.end());
13671377
}
13681378

1369-
template <typename... Args> void emplace(Args &&...A) {
1370-
StringRef S(std::forward<Args>(A)...);
1371-
GlobalValue::GUID GUID = GlobalValue::getGUIDAssumingExternalLinkage(
1372-
GlobalValue::dropLLVMManglingEscape(S));
1373-
Index[GUID].emplace(S);
1379+
/// Add the function name and the GUID that ThinLTO uses for it.
1380+
void addSymbolWithThinLTOGUID(StringRef Name, GlobalValue::GUID GUID) {
1381+
auto [Iter, _] = Names.insert(Name);
1382+
ThinLTOToNamesIndex[GUID].insert(Iter->first());
13741383
}
13751384

1376-
size_t count(StringRef S) const {
1377-
GlobalValue::GUID GUID = GlobalValue::getGUIDAssumingExternalLinkage(
1378-
GlobalValue::dropLLVMManglingEscape(S));
1379-
auto I = Index.find(GUID);
1380-
if (I == Index.end())
1381-
return 0;
1382-
return I->second.count(S);
1385+
bool contains(StringRef Name) const {
1386+
return Names.find(Name) != Names.end();
13831387
}
13841388

1385-
bool empty() const { return Index.empty(); }
1389+
bool empty() const {
1390+
assert(Names.empty() == ThinLTOToNamesIndex.empty());
1391+
return Names.empty();
1392+
}
13861393
};
13871394

13881395
/// 160 bits SHA1

‎llvm/include/llvm/IR/ModuleSummaryIndexYAML.h‎

Lines changed: 28 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -327,6 +327,24 @@ template <> struct CustomMappingTraits<TypeIdSummaryMapTy> {
327327
}
328328
};
329329

330+
template <> struct MappingTraits<std::pair<StringRef, GlobalValue::GUID>> {
331+
static void mapping(IO &io,
332+
std::pair<StringRef, GlobalValue::GUID> &NameAndGUID) {
333+
io.mapRequired("Name", NameAndGUID.first);
334+
io.mapRequired("GUID", NameAndGUID.second);
335+
}
336+
};
337+
338+
using StringAndGUID = std::pair<llvm::StringRef, llvm::GlobalValue::GUID>;
339+
340+
} // namespace yaml
341+
} // namespace llvm
342+
343+
LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::yaml::StringAndGUID)
344+
345+
namespace llvm {
346+
namespace yaml {
347+
330348
template <> struct MappingTraits<ModuleSummaryIndex> {
331349
static void mapping(IO &io, ModuleSummaryIndex& index) {
332350
io.mapOptional("GlobalValueMap", index.GlobalValueMap);
@@ -352,25 +370,24 @@ template <> struct MappingTraits<ModuleSummaryIndex> {
352370
index.WithGlobalValueDeadStripping);
353371

354372
if (io.outputting()) {
355-
auto CfiFunctionDefs = index.CfiFunctionDefs.symbols();
356-
llvm::sort(CfiFunctionDefs);
373+
auto CfiFunctionDefs = index.CfiFunctionDefs.getSortedSymbols();
357374
io.mapOptional("CfiFunctionDefs", CfiFunctionDefs);
358-
auto CfiFunctionDecls(index.CfiFunctionDecls.symbols());
359-
llvm::sort(CfiFunctionDecls);
375+
auto CfiFunctionDecls(index.CfiFunctionDecls.getSortedSymbols());
360376
io.mapOptional("CfiFunctionDecls", CfiFunctionDecls);
361377
} else {
362-
std::vector<std::string> CfiFunctionDefs;
378+
std::vector<std::pair<StringRef, GlobalValue::GUID>> CfiFunctionDefs;
363379
io.mapOptional("CfiFunctionDefs", CfiFunctionDefs);
364-
index.CfiFunctionDefs = {CfiFunctionDefs.begin(), CfiFunctionDefs.end()};
365-
std::vector<std::string> CfiFunctionDecls;
380+
for (auto &[S, G] : CfiFunctionDefs)
381+
index.CfiFunctionDefs.addSymbolWithThinLTOGUID(S, G);
382+
std::vector<std::pair<StringRef, GlobalValue::GUID>> CfiFunctionDecls;
366383
io.mapOptional("CfiFunctionDecls", CfiFunctionDecls);
367-
index.CfiFunctionDecls = {CfiFunctionDecls.begin(),
368-
CfiFunctionDecls.end()};
384+
for (auto &[S, G] : CfiFunctionDecls)
385+
index.CfiFunctionDecls.addSymbolWithThinLTOGUID(S, G);
369386
}
370387
}
371388
};
372389

373-
} // End yaml namespace
374-
} // End llvm namespace
390+
} // namespace yaml
391+
} // namespace llvm
375392

376393
#endif

‎llvm/lib/Bitcode/Reader/BitcodeReader.cpp‎

Lines changed: 14 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8149,17 +8149,25 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary(unsigned ID) {
81498149

81508150
case bitc::FS_CFI_FUNCTION_DEFS: {
81518151
auto &CfiFunctionDefs = TheIndex.cfiFunctionDefs();
8152-
for (unsigned I = 0; I != Record.size(); I += 2)
8153-
CfiFunctionDefs.emplace(Strtab.data() + Record[I],
8154-
static_cast<size_t>(Record[I + 1]));
8152+
for (unsigned I = 0; I != Record.size(); I += 2) {
8153+
StringRef Name(Strtab.data() + Record[I],
8154+
static_cast<size_t>(Record[I + 1]));
8155+
GlobalValue::GUID GUID = GlobalValue::getGUIDAssumingExternalLinkage(
8156+
GlobalValue::dropLLVMManglingEscape(Name));
8157+
CfiFunctionDefs.addSymbolWithThinLTOGUID(Name, GUID);
8158+
}
81558159
break;
81568160
}
81578161

81588162
case bitc::FS_CFI_FUNCTION_DECLS: {
81598163
auto &CfiFunctionDecls = TheIndex.cfiFunctionDecls();
8160-
for (unsigned I = 0; I != Record.size(); I += 2)
8161-
CfiFunctionDecls.emplace(Strtab.data() + Record[I],
8162-
static_cast<size_t>(Record[I + 1]));
8164+
for (unsigned I = 0; I != Record.size(); I += 2) {
8165+
StringRef Name(Strtab.data() + Record[I],
8166+
static_cast<size_t>(Record[I + 1]));
8167+
GlobalValue::GUID GUID = GlobalValue::getGUIDAssumingExternalLinkage(
8168+
GlobalValue::dropLLVMManglingEscape(Name));
8169+
CfiFunctionDecls.addSymbolWithThinLTOGUID(Name, GUID);
8170+
}
81638171
break;
81648172
}
81658173

‎llvm/lib/Bitcode/Writer/BitcodeWriter.cpp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5329,8 +5329,8 @@ void IndexBitcodeWriter::writeCombinedGlobalValueSummary() {
53295329
if (CfiIndex.empty())
53305330
return;
53315331
for (GlobalValue::GUID GUID : DefOrUseGUIDs) {
5332-
auto Defs = CfiIndex.forGuid(GUID);
5333-
llvm::append_range(Functions, Defs);
5332+
auto Names = CfiIndex.getNamesForGUID(GUID);
5333+
llvm::append_range(Functions, Names);
53345334
}
53355335
if (Functions.empty())
53365336
return;

‎llvm/lib/LTO/LTO.cpp‎

Lines changed: 11 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1585,9 +1585,9 @@ class CGThinBackend : public ThinBackendProc {
15851585
OnWrite, ShouldEmitImportsFiles, ThinLTOParallelism),
15861586
ShouldEmitIndexFiles(ShouldEmitIndexFiles) {
15871587
auto &Defs = CombinedIndex.cfiFunctionDefs();
1588-
CfiFunctionDefs.insert_range(Defs.guids());
1588+
CfiFunctionDefs.insert_range(Defs.getExportedThinLTOGUIDs());
15891589
auto &Decls = CombinedIndex.cfiFunctionDecls();
1590-
CfiFunctionDecls.insert_range(Decls.guids());
1590+
CfiFunctionDecls.insert_range(Decls.getExportedThinLTOGUIDs());
15911591
}
15921592
};
15931593

@@ -1948,10 +1948,10 @@ class WriteIndexesThinBackend : public ThinBackendProc {
19481948
OldPrefix(OldPrefix), NewPrefix(NewPrefix),
19491949
NativeObjectPrefix(NativeObjectPrefix),
19501950
LinkedObjectsFile(LinkedObjectsFile) {
1951-
auto &Defs = CombinedIndex.cfiFunctionDefs();
1952-
CfiFunctionDefs.insert(Defs.guid_begin(), Defs.guid_end());
1953-
auto &Decls = CombinedIndex.cfiFunctionDecls();
1954-
CfiFunctionDecls.insert(Decls.guid_begin(), Decls.guid_end());
1951+
auto Defs = CombinedIndex.cfiFunctionDefs().getExportedThinLTOGUIDs();
1952+
CfiFunctionDefs.insert(Defs.begin(), Defs.end());
1953+
auto Decls = CombinedIndex.cfiFunctionDecls().getExportedThinLTOGUIDs();
1954+
CfiFunctionDecls.insert(Decls.begin(), Decls.end());
19551955
}
19561956

19571957
Error start(
@@ -2181,10 +2181,11 @@ Error LTO::runThinLTO(AddStreamFn AddStream, FileCache Cache,
21812181

21822182
// Any functions referenced by the jump table in the regular LTO object must
21832183
// be exported.
2184-
auto &Defs = ThinLTO.CombinedIndex.cfiFunctionDefs();
2185-
ExportedGUIDs.insert(Defs.guid_begin(), Defs.guid_end());
2186-
auto &Decls = ThinLTO.CombinedIndex.cfiFunctionDecls();
2187-
ExportedGUIDs.insert(Decls.guid_begin(), Decls.guid_end());
2184+
auto Defs = ThinLTO.CombinedIndex.cfiFunctionDefs().getExportedThinLTOGUIDs();
2185+
ExportedGUIDs.insert(Defs.begin(), Defs.end());
2186+
auto Decls =
2187+
ThinLTO.CombinedIndex.cfiFunctionDecls().getExportedThinLTOGUIDs();
2188+
ExportedGUIDs.insert(Decls.begin(), Decls.end());
21882189

21892190
auto isExported = [&](StringRef ModuleIdentifier, ValueInfo VI) {
21902191
const auto &ExportList = ExportLists.find(ModuleIdentifier);

‎llvm/lib/Transforms/IPO/LowerTypeTests.cpp‎

Lines changed: 9 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1788,10 +1788,15 @@ void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
17881788
}
17891789

17901790
if (IsExported) {
1791+
// TODO: use F->getGUID() once #184065 is relanded.
1792+
GlobalValue::GUID GUID = GlobalValue::getGUIDAssumingExternalLinkage(
1793+
GlobalValue::dropLLVMManglingEscape(F->getName()));
17911794
if (IsJumpTableCanonical)
1792-
ExportSummary->cfiFunctionDefs().emplace(F->getName());
1795+
ExportSummary->cfiFunctionDefs().addSymbolWithThinLTOGUID(F->getName(),
1796+
GUID);
17931797
else
1794-
ExportSummary->cfiFunctionDecls().emplace(F->getName());
1798+
ExportSummary->cfiFunctionDecls().addSymbolWithThinLTOGUID(F->getName(),
1799+
GUID);
17951800
}
17961801

17971802
if (!IsJumpTableCanonical) {
@@ -2123,9 +2128,9 @@ bool LowerTypeTestsModule::lower() {
21232128
// have the same name, but it's not the one we are looking for.
21242129
if (F.hasLocalLinkage())
21252130
continue;
2126-
if (ImportSummary->cfiFunctionDefs().count(F.getName()))
2131+
if (ImportSummary->cfiFunctionDefs().contains(F.getName()))
21272132
Defs.push_back(&F);
2128-
else if (ImportSummary->cfiFunctionDecls().count(F.getName()))
2133+
else if (ImportSummary->cfiFunctionDecls().contains(F.getName()))
21292134
Decls.push_back(&F);
21302135
}
21312136

‎llvm/test/Transforms/LowerTypeTests/Inputs/blockaddr-import.yaml‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,6 @@ TypeIdMap:
44
TTRes:
55
Kind: AllOnes
66
CfiFunctionDefs:
7-
- m
8-
CfiFunctionDecls:
9-
...
7+
- Name: m
8+
GUID: 2799708793537531759
9+
CfiFunctionDecls: null

‎llvm/test/Transforms/LowerTypeTests/Inputs/cfi-direct-call.yaml‎

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4,9 +4,12 @@ TypeIdMap:
44
TTRes:
55
Kind: AllOnes
66
CfiFunctionDefs:
7-
- internal_default_def
8-
- internal_hidden_def
9-
- dsolocal_default_def
7+
- Name: internal_default_def
8+
GUID: 2377677245844927262
9+
- Name: internal_hidden_def
10+
GUID: 12222722662536945321
11+
- Name: dsolocal_default_def
12+
GUID: 11010557671720506420
1013
CfiFunctionDecls:
11-
- external_decl
12-
...
14+
- Name: external_decl
15+
GUID: 2828901536631366483

‎llvm/test/Transforms/LowerTypeTests/Inputs/cfi-direct-call1.yaml‎

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -4,10 +4,14 @@ TypeIdMap:
44
TTRes:
55
Kind: AllOnes
66
CfiFunctionDefs:
7-
- local_func1
8-
- local_func2
9-
- local_func3
7+
- Name: local_func1
8+
GUID: 15974708163032388986
9+
- Name: local_func2
10+
GUID: 10016086976061028907
11+
- Name: local_func3
12+
GUID: 161148068062889559
1013
CfiFunctionDecls:
11-
- extern_decl
12-
- extern_weak
13-
...
14+
- Name: extern_decl
15+
GUID: 15001569853432741044
16+
- Name: extern_weak
17+
GUID: 9772975595203342681

‎llvm/test/Transforms/LowerTypeTests/Inputs/import-alias.yaml‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,6 @@ TypeIdMap:
66
SizeM1BitWidth: 7
77
WithGlobalValueDeadStripping: false
88
CfiFunctionDefs:
9-
- f
10-
CfiFunctionDecls:
11-
...
9+
- Name: f
10+
GUID: 14740650423002898831
11+
CfiFunctionDecls: null

0 commit comments

Comments
 (0)