StableFunctionMap.cpp Source File (original) (raw)

22#define DEBUG_TYPE "stable-function-map"

24using namespace llvm;

28 cl::desc("Minimum number of similar functions with "

29 "the same hash required for merging."),

32 "global-merging-min-instrs",

33 cl::desc("The minimum instruction count required when merging functions."),

36 "global-merging-max-params",

38 "The maximum number of parameters allowed when merging functions."),

41 "global-merging-skip-no-params",

42 cl::desc("Skip merging functions with no parameters."), cl::init(true),

45 "global-merging-inst-overhead",

46 cl::desc("The overhead cost associated with each instruction when lowering "

47 "to machine instruction."),

50 "global-merging-param-overhead",

51 cl::desc("The overhead cost associated with each parameter when merging "

52 "functions."),

56 cl::desc("The overhead cost associated with each "

57 "function call when merging functions."),

60 "global-merging-extra-threshold",

61 cl::desc("An additional cost threshold that must be exceeded for merging "

62 "to be considered beneficial."),

66 auto It = NameToId.find(Name);

67 if (It != NameToId.end())

68 return It->second;

69 unsigned Id = IdToName.size();

70 assert(Id == NameToId.size() && "ID collision");

71 IdToName.emplace_back(Name.str());

72 NameToId[IdToName.back()] = Id;

73 return Id;

74}

77 if (Id >= IdToName.size())

78 return std::nullopt;

79 return IdToName[Id];

80}

83 assert(!Finalized && "Cannot insert after finalization");

86 auto IndexOperandHashMap = std::make_unique();

87 for (auto &[Index, Hash] : Func.IndexOperandHashes)

88 (*IndexOperandHashMap)[Index] = Hash;

89 auto FuncEntry = std::make_unique(

90 Func.Hash, FuncNameId, ModuleNameId, Func.InstCount,

91 std::move(IndexOperandHashMap));

92 insert(std::move(FuncEntry));

93}

96 assert(!Finalized && "Cannot merge after finalization");

97 deserializeLazyLoadingEntries();

98 for (auto &[Hash, Funcs] : OtherMap.HashToFuncs) {

99 auto &ThisFuncs = HashToFuncs[Hash].Entries;

100 for (auto &Func : Funcs.Entries) {

101 auto FuncNameId =

103 auto ModuleNameId =

105 auto ClonedIndexOperandHashMap =

106 std::make_unique(*Func->IndexOperandHashMap);

107 ThisFuncs.emplace_back(std::make_unique(

108 Func->Hash, FuncNameId, ModuleNameId, Func->InstCount,

109 std::move(ClonedIndexOperandHashMap)));

110 }

111 }

112}

113

115 switch (Type) {

117 return HashToFuncs.size();

119 deserializeLazyLoadingEntries();

120 size_t Count = 0;

121 for (auto &Funcs : HashToFuncs)

122 Count += Funcs.second.Entries.size();

124 }

126 deserializeLazyLoadingEntries();

127 size_t Count = 0;

128 for (auto &[Hash, Funcs] : HashToFuncs)

129 if (Funcs.Entries.size() >= 2)

130 Count += Funcs.Entries.size();

132 }

133 }

135}

136

139 auto It = HashToFuncs.find(FunctionHash);

140 assert(It != HashToFuncs.end() && "FunctionHash not found!");

141 if (isLazilyLoaded())

142 deserializeLazyLoadingEntry(It);

143 return It->second.Entries;

144}

145

146void StableFunctionMap::deserializeLazyLoadingEntry(

147 HashFuncsMapType::iterator It) const {

148 assert(isLazilyLoaded() && "Cannot deserialize non-lazily-loaded map");

149 auto &[Hash, Storage] = *It;

150 std::call_once(Storage.LazyLoadFlag,

151 [this, HashArg = Hash, &StorageArg = Storage]() {

152 for (auto Offset : StorageArg.Offsets)

153 StableFunctionMapRecord::deserializeEntry(

154 reinterpret_cast<const unsigned char *>(Offset),

155 HashArg, const_cast<StableFunctionMap *>(this));

156 });

157}

158

159void StableFunctionMap::deserializeLazyLoadingEntries() const {

160 if (!isLazilyLoaded())

161 return;

162 for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It)

163 deserializeLazyLoadingEntry(It);

164}

165

168

169 if (isLazilyLoaded())

170 deserializeLazyLoadingEntries();

171 return HashToFuncs;

172}

173

175static void

177 auto &RSF = SFS[0];

178 unsigned StableFunctionCount = SFS.size();

179

181 for (auto &[Pair, Hash] : *(RSF->IndexOperandHashMap)) {

182 bool Identical = true;

183 for (unsigned J = 1; J < StableFunctionCount; ++J) {

184 auto &SF = SFS[J];

185 const auto &SHash = SF->IndexOperandHashMap->at(Pair);

186 if (Hash != SHash) {

187 Identical = false;

188 break;

189 }

190 }

191

192

193

194 if (Identical)

196 }

197

198 for (auto &Pair : ToDelete)

199 for (auto &SF : SFS)

200 SF->IndexOperandHashMap->erase(Pair);

201}

202

204 unsigned StableFunctionCount = SFS.size();

206 return false;

207

208 unsigned InstCount = SFS[0]->InstCount;

210 return false;

211

212 double Cost = 0.0;

214 for (auto &SF : SFS) {

215 UniqueHashVals.clear();

216 for (auto &[IndexPair, Hash] : *SF->IndexOperandHashMap)

217 UniqueHashVals.insert(Hash);

218 unsigned ParamCount = UniqueHashVals.size();

220 return false;

221

222

223

224

225

227 return false;

229 }

231

232 double Benefit =

234 bool Result = Benefit > Cost;

235 LLVM_DEBUG(dbgs() << "isProfitable: Hash = " << SFS[0]->Hash << ", "

236 << "StableFunctionCount = " << StableFunctionCount

237 << ", InstCount = " << InstCount

238 << ", Benefit = " << Benefit << ", Cost = " << Cost

239 << ", Result = " << (Result ? "true" : "false") << "\n");

240 return Result;

241}

242

244 deserializeLazyLoadingEntries();

246 for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It) {

247 auto &[StableHash, Storage] = *It;

248 auto &SFS = Storage.Entries;

249

250

251 llvm::stable_sort(SFS, [&](const std::unique_ptr &L,

252 const std::unique_ptr &R) {

254 });

255

256

257 auto &RSF = SFS[0];

258

260 unsigned StableFunctionCount = SFS.size();

261 for (unsigned I = 1; I < StableFunctionCount; ++I) {

262 auto &SF = SFS[I];

263 assert(RSF->Hash == SF->Hash);

264 if (RSF->InstCount != SF->InstCount) {

266 break;

267 }

268 if (RSF->IndexOperandHashMap->size() != SF->IndexOperandHashMap->size()) {

270 break;

271 }

272 for (auto &P : *RSF->IndexOperandHashMap) {

273 auto &InstOpndIndex = P.first;

274 if (!SF->IndexOperandHashMap->count(InstOpndIndex)) {

276 break;

277 }

278 }

279 }

282 continue;

283 }

284

285 if (SkipTrim)

286 continue;

287

288

289

291

294 }

295 for (auto It : ToDelete)

296 HashToFuncs.erase(It);

297

298 Finalized = true;

299}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file defines the SmallSet class.

static bool isProfitable(const StableFunctionMap::StableFunctionEntries &SFS)

Definition StableFunctionMap.cpp:203

static cl::opt< bool > GlobalMergingSkipNoParams("global-merging-skip-no-params", cl::desc("Skip merging functions with no parameters."), cl::init(true), cl::Hidden)

static cl::opt< double > GlobalMergingParamOverhead("global-merging-param-overhead", cl::desc("The overhead cost associated with each parameter when merging " "functions."), cl::init(2.0), cl::Hidden)

static cl::opt< unsigned > GlobalMergingMinMerges("global-merging-min-merges", cl::desc("Minimum number of similar functions with " "the same hash required for merging."), cl::init(2), cl::Hidden)

static void removeIdenticalIndexPair(StableFunctionMap::StableFunctionEntries &SFS)

Definition StableFunctionMap.cpp:176

static cl::opt< double > GlobalMergingInstOverhead("global-merging-inst-overhead", cl::desc("The overhead cost associated with each instruction when lowering " "to machine instruction."), cl::init(1.2), cl::Hidden)

static cl::opt< double > GlobalMergingCallOverhead("global-merging-call-overhead", cl::desc("The overhead cost associated with each " "function call when merging functions."), cl::init(1.0), cl::Hidden)

static cl::opt< unsigned > GlobalMergingMaxParams("global-merging-max-params", cl::desc("The maximum number of parameters allowed when merging functions."), cl::init(std::numeric_limits< unsigned >::max()), cl::Hidden)

static cl::opt< unsigned > GlobalMergingMinInstrs("global-merging-min-instrs", cl::desc("The minimum instruction count required when merging functions."), cl::init(1), cl::Hidden)

static cl::opt< double > GlobalMergingExtraThreshold("global-merging-extra-threshold", cl::desc("An additional cost threshold that must be exceeded for merging " "to be considered beneficial."), cl::init(0.0), cl::Hidden)

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

std::pair< const_iterator, bool > insert(const T &V)

insert - Insert an element into the set if it isn't already there.

reference emplace_back(ArgTypes &&... Args)

iterator erase(const_iterator CI)

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

The instances of the Type class are immutable: once they are created, they are never changed.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

void stable_sort(R &&Range)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

FunctionAddr VTableAddr Count

SmallVector< IndexPair, 4 > ParamLocs

std::pair< unsigned, unsigned > IndexPair

The pair of an instruction index and a operand index.

std::unordered_map< stable_hash, EntryStorage > HashFuncsMapType

SmallVector< std::unique_ptr< StableFunctionEntry > > StableFunctionEntries

LLVM_ABI void finalize(bool SkipTrim=false)

Finalize the stable function map by trimming content.

Definition StableFunctionMap.cpp:243

LLVM_ABI size_t size(SizeType Type=UniqueHashCount) const

Definition StableFunctionMap.cpp:114

LLVM_ABI void insert(const StableFunction &Func)

Insert a StableFunction object into the function map.

Definition StableFunctionMap.cpp:82

const StableFunctionEntries & at(HashFuncsMapType::key_type FunctionHash) const

Definition StableFunctionMap.cpp:138

LLVM_ABI void merge(const StableFunctionMap &OtherMap)

Merge a OtherMap into this function map.

Definition StableFunctionMap.cpp:95

LLVM_ABI std::optional< std::string > getNameForId(unsigned Id) const

Get the name associated with a given ID.

Definition StableFunctionMap.cpp:76

LLVM_ABI_FOR_TEST const HashFuncsMapType & getFunctionMap() const

Get the HashToFuncs map for serialization.

Definition StableFunctionMap.cpp:167

LLVM_ABI unsigned getIdOrCreateForName(StringRef Name)

Get an existing ID associated with the given name or create a new ID if it doesn't exist.

Definition StableFunctionMap.cpp:65

A stable function is a function with a stable hash while tracking the locations of ignored operands a...