From d84440ec919019ac446241db72cfd905c6ac9dfa Mon Sep 17 00:00:00 2001 From: serge-sans-paille Date: Wed, 24 Feb 2021 16:15:24 +0100 Subject: [PATCH] Use the default seed value for djb hash for StringMap See original comment in 560ce2c70fb1fe8e4b9b5e39c54e494a50373ba8 Baiscally the default seed value results in less collision, but changes the iteration order, which matters for a few test cases. Differential Revision: https://reviews.llvm.org/D97396 --- llvm/lib/Support/StringMap.cpp | 4 ++-- .../DebugInfo/Generic/accel-table-hash-collisions.ll | 6 +++--- .../DebugInfo/Generic/debug-names-hash-collisions.ll | 4 ++-- llvm/test/DebugInfo/X86/debug-pubtables-dwarf64.ll | 2 +- llvm/test/DebugInfo/X86/gnu-public-names.ll | 18 ++++++++++++------ .../tools/llvm-dwarfdump/X86/section_sizes_elf.test | 1 + .../tools/llvm-dwarfdump/X86/section_sizes_macho.test | 1 + llvm/test/tools/llvm-dwarfdump/X86/statistics.ll | 2 ++ 8 files changed, 24 insertions(+), 14 deletions(-) diff --git a/llvm/lib/Support/StringMap.cpp b/llvm/lib/Support/StringMap.cpp index f65d384..69a144f 100644 --- a/llvm/lib/Support/StringMap.cpp +++ b/llvm/lib/Support/StringMap.cpp @@ -77,7 +77,7 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { init(16); HTSize = NumBuckets; } - unsigned FullHashValue = djbHash(Name, 0); + unsigned FullHashValue = djbHash(Name); unsigned BucketNo = FullHashValue & (HTSize - 1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); @@ -133,7 +133,7 @@ int StringMapImpl::FindKey(StringRef Key) const { unsigned HTSize = NumBuckets; if (HTSize == 0) return -1; // Really empty table? - unsigned FullHashValue = djbHash(Key, 0); + unsigned FullHashValue = djbHash(Key); unsigned BucketNo = FullHashValue & (HTSize - 1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); diff --git a/llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll b/llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll index 2e321c9..268e9cd 100644 --- a/llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll +++ b/llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll @@ -27,20 +27,20 @@ ; Check that all the names are present in the output ; CHECK: Hash 0x597841 -; CHECK: String: 0x{{[0-9a-f]*}} "is" ; CHECK: String: 0x{{[0-9a-f]*}} "k1" +; CHECK: String: 0x{{[0-9a-f]*}} "is" ; CHECK: Hash 0xa4b42a1e -; CHECK: String: 0x{{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE" ; CHECK: String: 0x{{[0-9a-f]*}} "_ZN4llvm16DenseMapIteratorIPNS_10MDLocationENS_6detail13DenseSetEmptyENS_10MDNodeInfoIS1_EENS3_12DenseSetPairIS2_EELb0EE23AdvancePastEmptyBucketsEv" +; CHECK: String: 0x{{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE" ; CHECK: Hash 0xeee7c0b2 ; CHECK: String: 0x{{[0-9a-f]*}} "_ZNK4llvm12LivePhysRegs5printERNS_11raw_ostreamE" ; CHECK: String: 0x{{[0-9a-f]*}} "_ZN4llvm15ScalarEvolution14getSignedRangeEPKNS_4SCEVE" ; CHECK: Hash 0xea48ac5f -; CHECK: String: 0x{{[0-9a-f]*}} "ForceTopDown" ; CHECK: String: 0x{{[0-9a-f]*}} "_ZNSt3__116allocator_traitsINS_9allocatorINS_11__tree_nodeINS_12__value_typeIPN4llvm10BasicBlockEPNS4_10RegionNodeEEEPvEEEEE11__constructIS9_JNS_4pairIS6_S8_EEEEEvNS_17integral_constantIbLb1EEERSC_PT_DpOT0_" +; CHECK: String: 0x{{[0-9a-f]*}} "ForceTopDown" ; CHECK: Hash 0x6b22f71f ; CHECK: String: 0x{{[0-9a-f]*}} "_ZNK5clang12OverrideAttr5cloneERNS_10ASTContextE" diff --git a/llvm/test/DebugInfo/Generic/debug-names-hash-collisions.ll b/llvm/test/DebugInfo/Generic/debug-names-hash-collisions.ll index c105701..27d2a44 100644 --- a/llvm/test/DebugInfo/Generic/debug-names-hash-collisions.ll +++ b/llvm/test/DebugInfo/Generic/debug-names-hash-collisions.ll @@ -44,9 +44,9 @@ ; CHECK: Hash: 0x2841B989 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL11NumCommutes" ; CHECK: Hash: 0x3E190F5F -; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL9NumRemats" -; CHECK: Hash: 0x3E190F5F ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL9NumReMats" +; CHECK: Hash: 0x3E190F5F +; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL9NumRemats" ; CHECK-NOT: String: ; CHECK: Bucket 3 ; CHECK: Hash: 0x2642207F diff --git a/llvm/test/DebugInfo/X86/debug-pubtables-dwarf64.ll b/llvm/test/DebugInfo/X86/debug-pubtables-dwarf64.ll index 5ac3551..8fa46a8 100644 --- a/llvm/test/DebugInfo/X86/debug-pubtables-dwarf64.ll +++ b/llvm/test/DebugInfo/X86/debug-pubtables-dwarf64.ll @@ -19,8 +19,8 @@ ; CHECK: .debug_pubtypes contents: ; CHECK-NEXT: length = 0x0000000000000032, format = DWARF64, version = 0x0002, unit_offset = ; CHECK-NEXT: Offset Name -; CHECK-NEXT: 0x00000000[[STRUCT]] "Foo" ; CHECK-NEXT: 0x00000000[[BASET]] "int" +; CHECK-NEXT: 0x00000000[[STRUCT]] "Foo" ; IR generated and reduced from: ; $ cat foo.c diff --git a/llvm/test/DebugInfo/X86/gnu-public-names.ll b/llvm/test/DebugInfo/X86/gnu-public-names.ll index 6535fce..ca4da7b 100644 --- a/llvm/test/DebugInfo/X86/gnu-public-names.ll +++ b/llvm/test/DebugInfo/X86/gnu-public-names.ll @@ -66,10 +66,14 @@ ; ASM: .section .debug_gnu_pubnames ; ASM: .byte 32 # Attributes: VARIABLE, EXTERNAL +; ASM-NEXT: .asciz "C::static_member_variable" # External Name +; ASM: .byte 32 # Attributes: VARIABLE, EXTERNAL ; ASM-NEXT: .asciz "global_variable" # External Name ; ASM: .section .debug_gnu_pubtypes ; ASM: .byte 16 # Attributes: TYPE, EXTERNAL +; ASM-NEXT: .asciz "named_enum_class" # External Name +; ASM: .byte 16 # Attributes: TYPE, EXTERNAL ; ASM-NEXT: .asciz "C" # External Name ; CHECK: .debug_info contents: @@ -241,6 +245,11 @@ ; CHECK-LABEL: .debug_gnu_pubnames contents: ; CHECK-NEXT: length = {{.*}}, version = 0x0002, unit_offset = 0x00000000, unit_size = {{.*}} ; CHECK-NEXT: Offset Linkage Kind Name +; CHECK-NEXT: [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable" +; CHECK-NEXT: [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function" +; CHECK-NEXT: [[UNNAMED_ENUM_ENUMERATOR]] STATIC VARIABLE "unnamed_enum_enumerator" +; CHECK-NEXT: EXTERNAL FUNCTION "f7" +; CHECK-NEXT: EXTERNAL FUNCTION "f3" ; CHECK-NEXT: [[GLOBAL_FUNC]] EXTERNAL FUNCTION "global_function" ; CHECK-NEXT: [[NS]] EXTERNAL TYPE "ns" ; CHECK-NEXT: [[OUTER_ANON_C]] STATIC VARIABLE "outer::(anonymous namespace)::c" @@ -259,22 +268,19 @@ ; CHECK-NEXT: [[NAMED_ENUM_CLASS_ENUMERATOR]] STATIC VARIABLE "named_enum_class_enumerator" ; CHECK-NEXT: [[MEM_FUNC]] EXTERNAL FUNCTION "C::member_function" ; CHECK-NEXT: [[GLOB_VAR]] EXTERNAL VARIABLE "global_variable" -; CHECK-NEXT: [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable" ; CHECK-NEXT: [[ANON_INNER]] EXTERNAL TYPE "(anonymous namespace)::inner" +; CHECK-NEXT: [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable" ; CHECK-NEXT: [[D_VAR]] EXTERNAL VARIABLE "ns::d" ; CHECK-NEXT: [[NAMED_ENUM_ENUMERATOR]] STATIC VARIABLE "named_enum_enumerator" -; CHECK-NEXT: [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable" -; CHECK-NEXT: [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function" -; CHECK-NEXT: [[UNNAMED_ENUM_ENUMERATOR]] STATIC VARIABLE "unnamed_enum_enumerator" ; CHECK-LABEL: debug_gnu_pubtypes contents: ; CHECK: Offset Linkage Kind Name +; CHECK-NEXT: [[INT]] STATIC TYPE "int" +; CHECK-NEXT: [[NAMED_ENUM_CLASS]] EXTERNAL TYPE "named_enum_class" ; CHECK-NEXT: [[C]] EXTERNAL TYPE "C" ; CHECK-NEXT: [[UNSIGNED_INT]] STATIC TYPE "unsigned int" ; CHECK-NEXT: [[D]] EXTERNAL TYPE "ns::D" ; CHECK-NEXT: [[NAMED_ENUM]] EXTERNAL TYPE "named_enum" -; CHECK-NEXT: [[INT]] STATIC TYPE "int" -; CHECK-NEXT: [[NAMED_ENUM_CLASS]] EXTERNAL TYPE "named_enum_class" %struct.C = type { i8 } %"struct.ns::D" = type { i32 } diff --git a/llvm/test/tools/llvm-dwarfdump/X86/section_sizes_elf.test b/llvm/test/tools/llvm-dwarfdump/X86/section_sizes_elf.test index 7d234e6..eb2e66b 100644 --- a/llvm/test/tools/llvm-dwarfdump/X86/section_sizes_elf.test +++ b/llvm/test/tools/llvm-dwarfdump/X86/section_sizes_elf.test @@ -15,6 +15,7 @@ # CHECK-NEXT:.debug_type 26 (2.48%) # CHECK-NEXT:.debug_foo 100 (9.54%) # CHECK-NEXT:.debug_info.dwo 9 (0.86%) +# # CHECK-EMPTY: # CHECK-NEXT: Total Size: 172 (16.41%) # CHECK-NEXT: Total File Size: 1048 diff --git a/llvm/test/tools/llvm-dwarfdump/X86/section_sizes_macho.test b/llvm/test/tools/llvm-dwarfdump/X86/section_sizes_macho.test index efa4cdd..190d38c 100644 --- a/llvm/test/tools/llvm-dwarfdump/X86/section_sizes_macho.test +++ b/llvm/test/tools/llvm-dwarfdump/X86/section_sizes_macho.test @@ -17,6 +17,7 @@ # CHECK-NEXT:__apple_namespac 36 (1.92%) # CHECK-NEXT:__apple_types 71 (3.79%) # CHECK-NEXT:__debug_line 61 (3.26%) + # CHECK-EMPTY: # CHECK-NEXT: Total Size: 588 (31.41%) # CHECK-NEXT: Total File Size: 1872 diff --git a/llvm/test/tools/llvm-dwarfdump/X86/statistics.ll b/llvm/test/tools/llvm-dwarfdump/X86/statistics.ll index 4ecff4f..1a3eda2 100644 --- a/llvm/test/tools/llvm-dwarfdump/X86/statistics.ll +++ b/llvm/test/tools/llvm-dwarfdump/X86/statistics.ll @@ -64,6 +64,8 @@ ; CHECK-NEXT: "#bytes in __apple_types": 133, ; CHECK-NEXT: "#bytes in __debug_line": 126, + + ; ModuleID = '/tmp/quality.cpp' source_filename = "/tmp/quality.cpp" target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" -- 2.7.4