[GlobalISel] Hash collisions / hitting EmptyKey or TombstoneKey on map key in RegisterBankInfo

[marcauberer]

We experience sporadic failures in RegisterBankInfo::getOperandsMapping. These failures seem to be triggered by

hash_code Hash = hash_combine_range(Begin, End);

hitting the value of EmptyKey or TombstoneKey in the DenseMap member MapOfOperandsMappings. We still use LLVM 13, but the coding seems to have remained the same until to date.

We also see failures in RegisterBankInfo::ValueMapping::verify that seem to be triggered by hash collisions from

hash_code Hash = hash_combine_range(Begin, End);

To us it seems that this coding is not protected against these problems and therefore failures can happen randomly.

Already posted the problem in the Forum, but got no answer there:
https://discourse.llvm.org/t/registerbankinfo-getoperandsmapping-not-protected-against-hash-collisions-emptykey-tombstonekey/77659

[marcauberer]

@qcolombet Do you have an idea how to solve this?

[marcauberer]

What can be done in any case is to change the key type of the four maps to hash_code, so we do not truncate the 64-bit size_t value of the hash to uint32_t for the map key.

llvm-project/llvm/include/llvm/CodeGen/RegisterBankInfo.h

Lines 402 to 422 in 89bae85

	mutable DenseMap<unsigned, std::unique_ptr<const PartialMapping>>
	MapOfPartialMappings;
	/// Keep dynamically allocated ValueMapping in a separate map.
	/// This shouldn't be needed when everything gets TableGen'ed.
	mutable DenseMap<unsigned, std::unique_ptr<const ValueMapping>>
	MapOfValueMappings;
	/// Keep dynamically allocated array of ValueMapping in a separate map.
	/// This shouldn't be needed when everything gets TableGen'ed.
	mutable DenseMap<unsigned, std::unique_ptr<ValueMapping[]>>
	MapOfOperandsMappings;
	/// Keep dynamically allocated InstructionMapping in a separate map.
	/// This shouldn't be needed when everything gets TableGen'ed.
	mutable DenseMap<unsigned, std::unique_ptr<const InstructionMapping>>
	MapOfInstructionMappings;
	/// Getting the minimal register class of a physreg is expensive.
	/// Cache this information as we get it.
	mutable DenseMap<unsigned, const TargetRegisterClass *> PhysRegMinimalRCs;

This will reduce the likelyhood of hitting EmptyKey or TombstoneKey dramatically. I will prepare a patch for this ...