1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
//===-- StableFunctionMap.cpp ---------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This implements the functionality for the StableFunctionMap class, which
// manages the mapping of stable function hashes to their metadata. It includes
// methods for inserting, merging, and finalizing function entries, as well as
// utilities for handling function names and IDs.
//
//===----------------------------------------------------------------------===//
#include "llvm/CGData/StableFunctionMap.h"
#define DEBUG_TYPE "stable-function-map"
using namespace llvm;
unsigned StableFunctionMap::getIdOrCreateForName(StringRef Name) {
auto It = NameToId.find(Name);
if (It == NameToId.end()) {
unsigned Id = IdToName.size();
assert(Id == NameToId.size() && "ID collision");
IdToName.emplace_back(Name.str());
NameToId[IdToName.back()] = Id;
return Id;
} else {
return It->second;
}
}
std::optional<std::string> StableFunctionMap::getNameForId(unsigned Id) const {
if (Id >= IdToName.size())
return std::nullopt;
return IdToName[Id];
}
void StableFunctionMap::insert(const StableFunction &Func) {
assert(!Finalized && "Cannot insert after finalization");
auto FuncNameId = getIdOrCreateForName(Func.FunctionName);
auto ModuleNameId = getIdOrCreateForName(Func.ModuleName);
auto IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
for (auto &[Index, Hash] : Func.IndexOperandHashes)
(*IndexOperandHashMap)[Index] = Hash;
auto FuncEntry = std::make_unique<StableFunctionEntry>(
Func.Hash, FuncNameId, ModuleNameId, Func.InstCount,
std::move(IndexOperandHashMap));
insert(std::move(FuncEntry));
}
void StableFunctionMap::merge(const StableFunctionMap &OtherMap) {
assert(!Finalized && "Cannot merge after finalization");
for (auto &[Hash, Funcs] : OtherMap.HashToFuncs) {
auto &ThisFuncs = HashToFuncs[Hash];
for (auto &Func : Funcs) {
auto FuncNameId =
getIdOrCreateForName(*OtherMap.getNameForId(Func->FunctionNameId));
auto ModuleNameId =
getIdOrCreateForName(*OtherMap.getNameForId(Func->ModuleNameId));
auto ClonedIndexOperandHashMap =
std::make_unique<IndexOperandHashMapType>(*Func->IndexOperandHashMap);
ThisFuncs.emplace_back(std::make_unique<StableFunctionEntry>(
Func->Hash, FuncNameId, ModuleNameId, Func->InstCount,
std::move(ClonedIndexOperandHashMap)));
}
}
}
size_t StableFunctionMap::size(SizeType Type) const {
switch (Type) {
case UniqueHashCount:
return HashToFuncs.size();
case TotalFunctionCount: {
size_t Count = 0;
for (auto &Funcs : HashToFuncs)
Count += Funcs.second.size();
return Count;
}
case MergeableFunctionCount: {
size_t Count = 0;
for (auto &[Hash, Funcs] : HashToFuncs)
if (Funcs.size() >= 2)
Count += Funcs.size();
return Count;
}
}
return 0;
}
using ParamLocs = SmallVector<IndexPair>;
static void removeIdenticalIndexPair(
SmallVector<std::unique_ptr<StableFunctionEntry>> &SFS) {
auto &RSF = SFS[0];
unsigned StableFunctionCount = SFS.size();
SmallVector<IndexPair> ToDelete;
for (auto &[Pair, Hash] : *(RSF->IndexOperandHashMap)) {
bool Identical = true;
for (unsigned J = 1; J < StableFunctionCount; ++J) {
auto &SF = SFS[J];
assert(SF->IndexOperandHashMap->count(Pair));
auto SHash = (*SF->IndexOperandHashMap)[Pair];
if (Hash != SHash) {
Identical = false;
break;
}
}
// No need to parameterize them if the hashes are identical across stable
// functions.
if (Identical)
ToDelete.emplace_back(Pair);
}
for (auto &Pair : ToDelete)
for (auto &SF : SFS)
SF->IndexOperandHashMap->erase(Pair);
}
void StableFunctionMap::finalize() {
Finalized = true;
for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It) {
auto &[StableHash, SFS] = *It;
// Group stable functions by ModuleIdentifier.
std::stable_sort(SFS.begin(), SFS.end(),
[&](const std::unique_ptr<StableFunctionEntry> &L,
const std::unique_ptr<StableFunctionEntry> &R) {
return *getNameForId(L->ModuleNameId) <
*getNameForId(R->ModuleNameId);
});
// Consider the first function as the root function.
auto &RSF = SFS[0];
bool IsValid = true;
unsigned StableFunctionCount = SFS.size();
for (unsigned I = 1; I < StableFunctionCount; ++I) {
auto &SF = SFS[I];
assert(RSF->Hash == SF->Hash);
if (RSF->InstCount != SF->InstCount) {
IsValid = false;
break;
}
if (RSF->IndexOperandHashMap->size() != SF->IndexOperandHashMap->size()) {
IsValid = false;
break;
}
for (auto &P : *RSF->IndexOperandHashMap) {
auto &InstOpndIndex = P.first;
if (!SF->IndexOperandHashMap->count(InstOpndIndex)) {
IsValid = false;
break;
}
}
}
if (!IsValid) {
HashToFuncs.erase(It);
continue;
}
// Trim the index pair that has the same operand hash across
// stable functions.
removeIdenticalIndexPair(SFS);
}
}
|
