[Support] change StringMap hash function from djbHash to xxHash

[erikdesjardins]

Summary

Depends on https://reviews.llvm.org/D142861.

Alternative to https://reviews.llvm.org/D137601.

xxHash is much faster than djbHash. This makes a simple Rust test case with a large constant string 10% faster to compile.

Previous attempts at changing this hash function (e.g. https://reviews.llvm.org/D97396) had to be reverted due to breaking tests that depended on iteration order.
No additional tests fail with this patch compared to main when running check-all with -DLLVM_ENABLE_PROJECTS="all" (on a Linux host), so I hope I found everything that needs to be changed.

[erikdesjardins]

llvm/test/DebugInfo/X86/gnu-public-names.ll

68–71

Previously, this was

; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
; ASM-NEXT: .asciz  "global_variable"       # External Name
...more lines...
; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
; ASM-NEXT: .asciz  "ns::global_namespace_variable"       # External Name

but the reordering resulted in there being another .byte 32 (a very fragile check line!) before global_variable.

189–192

Similarly here--f7 used to be at the end of the list below, and was just ignored, but now it appears in the middle

[serge-sans-paille]

Can you take a shot against https://llvm-compile-time-tracker.com/ so that we get an hint of the practical speedup?

Looks like xxhash.h is missing from the patch.

[serge-sans-paille]

Do you intend to (optionnaly) provide XXH3 as described in https://github.com/Cyan4973/xxHash ?

[erikdesjardins]

In D142862#4089860, @serge-sans-paille wrote:

Can you take a shot against https://llvm-compile-time-tracker.com/ so that we get an hint of the practical speedup?

I don't think I have permission to use that. @nikic?

Looks like xxhash.h is missing from the patch.

It already exists: https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Support/xxhash.h

[MaskRay]

To enable smooth hash function migration in the future, we can explore the idea of adding #ifdef EXPENSIVE_CHECKS\nshuffle to StringMap (see https://github.com/llvm/llvm-project/issues/34483).
That means we should fix these tests properly to be non-dependent on the iteration order.

[goldstein.w.n]

FWIW, if the only use if hashtables xxhash has a slight perf bug in XXH3_len_129to240_128b and XXH3_len_129to240_64b where it will repeat the last the block if length is a factor of 32/16 respectively.
XXH3_len_129to240_128b:

• https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L3981

XXH3_len_129to240_64b:

• https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L5877

It's not fixed b.c xxhash needs to have a stable result for compression, but for hashtable it might be worth fixing in the internal llvm version?

[erikdesjardins]

rebase over landed D142861

[erikdesjardins]

In D142862#4089860, @serge-sans-paille wrote:

Can you take a shot against https://llvm-compile-time-tracker.com/ so that we get an hint of the practical speedup?

I ran rustc perf tests using a patched LLVM in https://github.com/rust-lang/rust/pull/107552#issuecomment-1411927687,
you can see the results here: https://perf.rust-lang.org/compare.html?start=ad8e1dc2863f63c35ef3ceef3064d0851a1d2582&end=8aaf54b663467dc48ff24d764aa9f73c61db2733&stat=instructions:u
Improvements from 0.2%-2% on various benchmarks, no regressions.

@serge-sans-paille it looks like you have access to llvm-compile-time-tracker, can you push this patch up so we can see those perf tests too?
Probable oneliner: git remote add erikdesjardins https://github.com/erikdesjardins/llvm-project.git && git fetch erikdesjardins && git push origin erikdesjardins/xxhash-perf:refs/heads/perf/xxhash

Do you intend to (optionnaly) provide XXH3 as described in https://github.com/Cyan4973/xxHash ?

The current version of xxhash in tree is stripped down to just xxhash64. I don't intend to change that as part of this patch.

[serge-sans-paille]

https://llvm-compile-time-tracker.com/compare.php?from=1a17739d3aa78599c32f6106e05dcfa7f3f9e823&to=9c1adc5fcca177d6628bdb22c72e7546c7b691aa&stat=instructions:u

looks good to me!

[MaskRay]

clang-tools-extra/clangd/unittests/BackgroundIndexTests.cpp

638 ↗

(On Diff #494155)

Rebase. I've changed this to UnorderedElementsAre

clang-tools-extra/test/modularize/ProblemsInconsistent.modularize

6 ↗

(On Diff #494155)

Rebase. I've fixed modularize's misuse of StringMap https://llvm.org/docs/ProgrammersManual.html#llvm-adt-stringmap-h

StringMap iteration order, however, is not guaranteed to be deterministic, so any uses which require that should instead use a std::map.

[erikdesjardins]

mlir/test/Transforms/print-op-graph.mlir

9 ↗

(On Diff #494155)

Opened https://reviews.llvm.org/D143239 for this test, I'll rebase once it lands.

[MaskRay]

mlir/test/Transforms/print-op-graph.mlir

1 ↗

(On Diff #494155)

I fixed mlir/lib/Transforms/ViewOpGraph.cpp. Please rebase and drop changes to this file.

[MaskRay]

For posterity, the tests that fail on main are:

Skipped : 43
[...]

You can remove these from the description. They are flaky tests unrelated to this patch (openmp tests tend to be flaky from my experience).

[erikdesjardins]

rebase, remove now-unnecessary test changes

[erikdesjardins]

update description

[MaskRay]

llvm/test/ObjectYAML/Offload/multiple_members.yaml

21 ↗

(On Diff #494836)

Rebase:) I fixed obj2yaml

llvm/test/tools/llvm-profdata/suppl-instr-with-sample.test

1

llvm-profdata uses OnDiskHashTable.h which I think is infeasible to stabilize without drastic change to the format. So keep the change.

[erikdesjardins]

rebase

clang-tools-extra/test/modularize/ProblemsDisplayLists.modularize

 # RUN: not modularize -display-file-lists %S/Inputs/CompileError/module.modulemap 2>&1 | FileCheck %s
 
 # CHECK: {{.*}}{{[/\\]}}Inputs{{[/\\]}}CompileError{{[/\\]}}HasError.h:1:9: error: unknown type name 'WithoutDep'
 
 # CHECK: These are the files with possible errors:
 
 # CHECK: Inputs/CompileError/HasError.h
 
 # CHECK: These are the files with no detected errors:
 
 # CHECK: Inputs/CompileError/Level1A.h
 
 # CHECK: These are the combined files, with problem files preceded by #:
 
-# CHECK: {{.*}}Inputs/CompileError/HasError.h
 # CHECK: Inputs/CompileError/Level1A.h
+# CHECK: {{.*}}Inputs/CompileError/HasError.h

clang/unittests/Basic/SarifTest.cpp

TEST_F(SarifDocumentWriterTest, checkSerializingArtifacts) {
 
   // THEN: Assert that the serialized SARIF is as expected
   ASSERT_THAT(Output, ::testing::StrEq(ExpectedOutput));
 }
 
 TEST_F(SarifDocumentWriterTest, checkSerializingCodeflows) {
   // GIVEN:
   const std::string ExpectedOutput =
-      R"({"$schema":"https://docs.oasis-open.org/sarif/sarif/v2.1.0/cos02/schemas/sarif-schema-2.1.0.json","runs":[{"artifacts":[{"length":27,"location":{"index":1,"uri":"file:///test-header-1.h"},"mimeType":"text/plain","roles":["resultFile"]},{"length":30,"location":{"index":2,"uri":"file:///test-header-2.h"},"mimeType":"text/plain","roles":["resultFile"]},{"length":28,"location":{"index":3,"uri":"file:///test-header-3.h"},"mimeType":"text/plain","roles":["resultFile"]},{"length":41,"location":{"index":0,"uri":"file:///main.cpp"},"mimeType":"text/plain","roles":["resultFile"]}],"columnKind":"unicodeCodePoints","results":[{"codeFlows":[{"threadFlows":[{"locations":[{"importance":"essential","location":{"message":{"text":"Message #1"},"physicalLocation":{"artifactLocation":{"index":1,"uri":"file:///test-header-1.h"},"region":{"endColumn":8,"endLine":2,"startColumn":1,"startLine":1}}}},{"importance":"important","location":{"message":{"text":"Message #2"},"physicalLocation":{"artifactLocation":{"index":2,"uri":"file:///test-header-2.h"},"region":{"endColumn":8,"endLine":2,"startColumn":1,"startLine":1}}}},{"importance":"unimportant","location":{"message":{"text":"Message #3"},"physicalLocation":{"artifactLocation":{"index":3,"uri":"file:///test-header-3.h"},"region":{"endColumn":8,"endLine":2,"startColumn":1,"startLine":1}}}}]}]}],"level":"warning","locations":[{"physicalLocation":{"artifactLocation":{"index":0,"uri":"file:///main.cpp"},"region":{"endColumn":8,"endLine":2,"startColumn":5,"startLine":2}}}],"message":{"text":"Redefinition of 'foo'"},"ruleId":"clang.unittest","ruleIndex":0}],"tool":{"driver":{"fullName":"sarif test runner","informationUri":"https://clang.llvm.org/docs/UsersManual.html","language":"en-US","name":"sarif test","rules":[{"defaultConfiguration":{"enabled":true,"level":"warning","rank":-1},"fullDescription":{"text":"Example rule created during unit tests"},"id":"clang.unittest","name":"clang unit test"}],"version":"1.0.0"}}}],"version":"2.1.0"})";
+      R"({"$schema":"https://docs.oasis-open.org/sarif/sarif/v2.1.0/cos02/schemas/sarif-schema-2.1.0.json","runs":[{"artifacts":[{"length":28,"location":{"index":3,"uri":"file:///test-header-3.h"},"mimeType":"text/plain","roles":["resultFile"]},{"length":41,"location":{"index":0,"uri":"file:///main.cpp"},"mimeType":"text/plain","roles":["resultFile"]},{"length":30,"location":{"index":2,"uri":"file:///test-header-2.h"},"mimeType":"text/plain","roles":["resultFile"]},{"length":27,"location":{"index":1,"uri":"file:///test-header-1.h"},"mimeType":"text/plain","roles":["resultFile"]}],"columnKind":"unicodeCodePoints","results":[{"codeFlows":[{"threadFlows":[{"locations":[{"importance":"essential","location":{"message":{"text":"Message #1"},"physicalLocation":{"artifactLocation":{"index":1,"uri":"file:///test-header-1.h"},"region":{"endColumn":8,"endLine":2,"startColumn":1,"startLine":1}}}},{"importance":"important","location":{"message":{"text":"Message #2"},"physicalLocation":{"artifactLocation":{"index":2,"uri":"file:///test-header-2.h"},"region":{"endColumn":8,"endLine":2,"startColumn":1,"startLine":1}}}},{"importance":"unimportant","location":{"message":{"text":"Message #3"},"physicalLocation":{"artifactLocation":{"index":3,"uri":"file:///test-header-3.h"},"region":{"endColumn":8,"endLine":2,"startColumn":1,"startLine":1}}}}]}]}],"level":"warning","locations":[{"physicalLocation":{"artifactLocation":{"index":0,"uri":"file:///main.cpp"},"region":{"endColumn":8,"endLine":2,"startColumn":5,"startLine":2}}}],"message":{"text":"Redefinition of 'foo'"},"ruleId":"clang.unittest","ruleIndex":0}],"tool":{"driver":{"fullName":"sarif test runner","informationUri":"https://clang.llvm.org/docs/UsersManual.html","language":"en-US","name":"sarif test","rules":[{"defaultConfiguration":{"enabled":true,"level":"warning","rank":-1},"fullDescription":{"text":"Example rule created during unit tests"},"id":"clang.unittest","name":"clang unit test"}],"version":"1.0.0"}}}],"version":"2.1.0"})";
 
   const char *SourceText = "int foo = 0;\n"
                            "int foo = 1;\n"
                            "float x = 0.0;\n";
   FileID MainFileID =
       registerSource("/main.cpp", SourceText, /* IsMainFile = */ true);
   CharSourceRange DiagLoc{getFakeCharSourceRange(MainFileID, {2, 5}, {2, 8})};
 

compiler-rt/test/profile/Linux/instrprof-show-debug-info-correlation.c

 // RUN: %clang_pgogen -o %t -g -mllvm --debug-info-correlate -mllvm --disable-vp=true %s
 // RUN: llvm-profdata show --debug-info=%t --detailed-summary --show-prof-sym-list | FileCheck %s
 // RUN: llvm-profdata show --debug-info=%t --show-format=yaml | FileCheck %s --match-full-lines --check-prefix YAML
 
 // RUN: %clang_pgogen -o %t.no.dbg -mllvm --debug-info-correlate -mllvm --disable-vp=true %s
 // RUN: not llvm-profdata show --debug-info=%t.no.dbg 2>&1 | FileCheck %s --check-prefix NO-DBG
 // NO-DBG: unable to correlate profile: could not find any profile metadata in debug info
 
-// CHECK: a
 // YAML: Probes:
 // YAML:   - Function Name:   a
 // YAML:     Linkage Name:    a
 // YAML:     CFG Hash:        0x[[#%.1X,HASH:]]
 // YAML:     Counter Offset:  0x0
 // YAML:     Num Counters:    1
 // YAML:     File:            [[FILE:'.*']]
 // YAML:     Line:            [[@LINE+1]]
 void a() {}
 
-// CHECK: b
 // YAML:   - Function Name:   b
 // YAML:     Linkage Name:    b
 // YAML:     CFG Hash:        0x[[#%.1X,HASH:]]
 // YAML:     Counter Offset:  0x8
 // YAML:     Num Counters:    1
 // YAML:     File:            [[FILE:'.*']]
 // YAML:     Line:            [[@LINE+1]]
 void b() {}
 
-// CHECK: main
 // YAML:   - Function Name:   main
 // YAML:     Linkage Name:    main
 // YAML:     CFG Hash:        0x[[#%.1X,HASH:]]
 // YAML:     Counter Offset:  0x10
 // YAML:     Num Counters:    1
 // YAML:     File:            [[FILE]]
 // YAML:     Line:            [[@LINE+1]]
 int main() { return 0; }
 
+// CHECK: main
+// CHECK: a
+// CHECK: b
 // CHECK: Counters section size: 0x18 bytes
 // CHECK: Found 3 functions

lldb/test/API/functionalities/gdb_remote_client/TestGDBRemoteClient.py

def test_launch_QEnvironment(self):
                       None,  # stdout_path
                       None,  # stderr_path
                       None,  # working_directory
                       0,  # launch_flags
                       True,  # stop_at_entry
                       lldb.SBError())  # error
 
         self.assertPacketLogContains([
-          "QEnvironment:PLAIN=foo",
-          "QEnvironmentHexEncoded:4e45454453454e433d66726f6224",
-          "QEnvironmentHexEncoded:4e45454453454e43323d66722a6f62",
           "QEnvironmentHexEncoded:4e45454453454e43333d66726f7d62",
           "QEnvironmentHexEncoded:4e45454453454e43343d6623726f62",
+          "QEnvironment:PLAIN=foo",
+          "QEnvironmentHexEncoded:4e45454453454e43323d66722a6f62",
+          "QEnvironmentHexEncoded:4e45454453454e433d66726f6224",
           "QEnvironment:EQUALS=foo=bar",
         ])
 
     def test_launch_QEnvironmentHexEncoded_only(self):
         class MyResponder(MockGDBServerResponder):
             def qC(self):
                 return "E42"
 
def test_launch_QEnvironmentHexEncoded_only(self):
                       None,  # stdout_path
                       None,  # stderr_path
                       None,  # working_directory
                       0,  # launch_flags
                       True,  # stop_at_entry
                       lldb.SBError())  # error
 
         self.assertPacketLogContains([
-          "QEnvironmentHexEncoded:504c41494e3d666f6f",
-          "QEnvironmentHexEncoded:4e45454453454e433d66726f6224",
-          "QEnvironmentHexEncoded:4e45454453454e43323d66722a6f62",
           "QEnvironmentHexEncoded:4e45454453454e43333d66726f7d62",
           "QEnvironmentHexEncoded:4e45454453454e43343d6623726f62",
+          "QEnvironmentHexEncoded:504c41494e3d666f6f",
+          "QEnvironmentHexEncoded:4e45454453454e43323d66722a6f62",
+          "QEnvironmentHexEncoded:4e45454453454e433d66726f6224",
           "QEnvironmentHexEncoded:455155414c533d666f6f3d626172",
         ])
 
     def test_detach_no_multiprocess(self):
         class MyResponder(MockGDBServerResponder):
             def __init__(self):
                 super().__init__()
                 self.detached = None

llvm/lib/Support/StringMap.cpp

 //===--- StringMap.cpp - String Hash table map implementation -------------===//
 //
 // 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 file implements the StringMap class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringMap.h"
-#include "llvm/Support/DJB.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/xxhash.h"
 
 using namespace llvm;
 
 /// Returns the number of buckets to allocate to ensure that the DenseMap can
 /// accommodate \p NumEntries without need to grow().
 static inline unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
   // Ensure that "NumEntries * 4 < NumBuckets * 3"
   if (NumEntries == 0)

 /// up in.  If it already exists as a key in the map, the Item pointer for the
 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
 /// case, the FullHashValue field of the bucket will be set to the hash value
 /// of the string.
 unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
   // Hash table unallocated so far?
   if (NumBuckets == 0)
     init(16);
-  unsigned FullHashValue = djbHash(Name, 0);
+  unsigned FullHashValue = xxHash64(Name);
   unsigned BucketNo = FullHashValue & (NumBuckets - 1);
   unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   int FirstTombstone = -1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return it.

 }
 
 /// FindKey - Look up the bucket that contains the specified key. If it exists
 /// in the map, return the bucket number of the key.  Otherwise return -1.
 /// This does not modify the map.
 int StringMapImpl::FindKey(StringRef Key) const {
   if (NumBuckets == 0)
     return -1; // Really empty table?
-  unsigned FullHashValue = djbHash(Key, 0);
+  unsigned FullHashValue = xxHash64(Key);
   unsigned BucketNo = FullHashValue & (NumBuckets - 1);
   unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return.
     if (LLVM_LIKELY(!BucketItem))

llvm/test/DebugInfo/Generic/accel-table-hash-collisions.ll

 ; int _ZN4llvm22MachineModuleInfoMachOD2Ev;
 
 ; Check that we have the right amount of hashes.
 ; CHECK: Bucket count: 6
 ; CHECK: Hashes count: 6
 
 ; 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_"

llvm/test/DebugInfo/Generic/debug-names-hash-collisions.ll

 
 ; Check that we have the right amount of hashes and names.
 ; CHECK: Bucket count: 5
 ; CHECK: Name count: 10
 
 ; Check that all the names are present in the output
 ; CHECK: Bucket 0
 ; CHECK:     Hash: 0xF8CF70D
-; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBBlockaSERKS0_"
-; CHECK:     Hash: 0xF8CF70D
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBBlockC1ERKS0_"
-; CHECK:     Hash: 0x135A482C
-; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBErroraSERKS0_"
+; CHECK:     Hash: 0xF8CF70D
+; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBBlockaSERKS0_"
 ; CHECK:     Hash: 0x135A482C
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBErrorC1ERKS0_"
+; CHECK:     Hash: 0x135A482C
+; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBErroraSERKS0_"
 ; CHECK-NOT: String:
 ; CHECK: Bucket 1
 ; CHECK-NEXT: EMPTY
 ; CHECK: Bucket 2
 ; CHECK:     Hash: 0x2841B989
-; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL11numCommutes"
-; CHECK:     Hash: 0x2841B989
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZL11NumCommutes"
+; 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-NOT: String:
 ; CHECK: Bucket 3
 ; CHECK:     Hash: 0x2642207F
 ; CHECK-NEXT:String: 0x{{[0-9a-f]*}} "_ZN4lldb7SBValueaSERKS0_"

llvm/test/DebugInfo/X86/debug-pubtables-dwarf64.ll

 ; CHECK:      .debug_pubnames contents:
 ; CHECK-NEXT: length = 0x0000000000000026, format = DWARF64, version = 0x0002, unit_offset =
 ; CHECK-NEXT: Offset     Name
 ; CHECK-NEXT: 0x00000000[[VAR]] "foo"
 
 ; 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
 ; struct Foo { int bar; };
 ; struct Foo foo;
 ; $ clang -g -gpubnames -S -emit-llvm foo.c -o foo.ll
 
 target triple = "x86_64-unknown-linux-gnu"

llvm/test/DebugInfo/X86/gnu-public-names-gmlt.ll

 ;   $ clang++ -gmlt %s -emit-llvm -S
 
 ; GPUB: Compile Unit
 ; GPUB: DW_AT_GNU_pubnames
 
 ; GPUB: .debug_gnu_pubnames contents:
 ; GPUB-NEXT: unit_offset = 0x00000000
 ; GPUB-NEXT: Name
-; GPUB-NEXT: "f2"
 ; GPUB-NEXT: "f3"
+; GPUB-NEXT: "f2"
 
 ; GPUB: .debug_gnu_pubtypes contents:
 ; GPUB-NEXT: length = 0x0000000e, format = DWARF32, version = 0x0002, unit_offset = 0x00000000
 ; GPUB-NEXT: Name
 
 ; NONE-NOT: .debug_pubnames contents:
 ; NONE-NOT: .debug_pubtypes contents:
 ; NONE-NOT: .debug_gnu_pubnames contents:

llvm/test/DebugInfo/X86/gnu-public-names.ll

 ; }
 ; }
 ;
 ; int f7() {
 ;   return i + *f3() + inner::b + outer::c;
 ; }
 
 ; ASM: .section        .debug_gnu_pubnames
 ; ASM: .byte   32                      # Attributes: VARIABLE, EXTERNAL
+; ASM-NEXT: .asciz  "ns::global_namespace_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  "C"                     # External Name
 
 ; CHECK: .debug_info contents:
 ; CHECK: DW_TAG_compile_unit
 ; CHECK:   DW_AT_GNU_pubnames (true)

 ; CHECK:       DW_TAG_member
 ; CHECK:       NULL
 ; CHECK:     DW_TAG_variable
 ; CHECK:     [[GLOB_NS_FUNC:0x[0-9a-f]+]]: DW_TAG_subprogram
 ; CHECK:       DW_AT_linkage_name
 ; CHECK:       DW_AT_name ("global_namespace_function")
 ; CHECK:     NULL
 
-; CHECK:   DW_TAG_subprogram
+; CHECK:   [[F3:0x[0-9a-f]+]]: DW_TAG_subprogram
 ; CHECK:     DW_AT_name ("f3")
 ; CHECK:     [[F3_Z:.*]]: DW_TAG_variable
 ; CHECK:       DW_AT_name ("z")
 ; CHECK:       DW_AT_location
 ; CHECK:     NULL
 
 ; CHECK:   [[ANON:.*]]: DW_TAG_namespace
 ; CHECK-NOT: DW_AT_name

 
 ; CHECK:   [[STATIC_MEM_FUNC:0x[0-9a-f]+]]: DW_TAG_subprogram
 ; CHECK:     DW_AT_specification {{.*}} "_ZN1C22static_member_functionEv"
 
 ; CHECK:   [[GLOBAL_FUNC:0x[0-9a-f]+]]: DW_TAG_subprogram
 ; CHECK:     DW_AT_linkage_name
 ; CHECK:     DW_AT_name ("global_function")
 
-; CHECK:   DW_TAG_subprogram
+; CHECK:   [[GLOBAL_F7:0x[0-9a-f]+]]: DW_TAG_subprogram
+; CHECK:     DW_AT_linkage_name
+; CHECK:     DW_AT_name ("f7")
+
 ; CHECK:   DW_TAG_pointer_type
 ; CHECK:   DW_TAG_pointer_type
 ; CHECK:   NULL
 
 ; CHECK-LABEL: .debug_gnu_pubnames contents:
 ; CHECK-NEXT: length = {{.*}}, version = 0x0002, unit_offset = 0x00000000, unit_size = {{.*}}
 ; CHECK-NEXT: Offset     Linkage  Kind     Name
+; CHECK-NEXT:  [[ANON_INNER_B]] STATIC VARIABLE "(anonymous namespace)::inner::b"
+; CHECK-NEXT:  [[MEM_FUNC]] EXTERNAL FUNCTION "C::member_function"
+; CHECK-NEXT:  [[OUTER]] EXTERNAL TYPE "outer"
+; CHECK-NEXT:  [[GLOB_NS_VAR]] EXTERNAL VARIABLE "ns::global_namespace_variable"
+; CHECK-NEXT:  [[GLOB_VAR]] EXTERNAL VARIABLE "global_variable"
+; CHECK-NEXT:  [[UNNAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "unnamed_enum_enumerator"
+; CHECK-NEXT:  [[GLOBAL_F7]] EXTERNAL FUNCTION "f7"
+; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
+; FIXME: GCC produces enumerators as EXTERNAL, not STATIC
+; CHECK-NEXT:  [[NAMED_ENUM_CLASS_ENUMERATOR]] STATIC VARIABLE  "named_enum_class_enumerator"
 ; CHECK-NEXT:  [[GLOBAL_FUNC]] EXTERNAL FUNCTION "global_function"
+; CHECK-NEXT:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
 ; CHECK-NEXT:  [[NS]] EXTERNAL TYPE     "ns"
+; CHECK-NEXT:  [[NAMED_ENUM_ENUMERATOR]] STATIC VARIABLE  "named_enum_enumerator"
+; CHECK-NEXT:  [[ANON]] EXTERNAL TYPE "(anonymous namespace)"
 ; CHECK-NEXT:  [[OUTER_ANON_C]] STATIC VARIABLE "outer::(anonymous namespace)::c"
+; CHECK-NEXT:  [[D_VAR]] EXTERNAL VARIABLE "ns::d"
+; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
+; CHECK-NEXT:  [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable"
 ; CHECK-NEXT:  [[ANON_I]] STATIC VARIABLE "(anonymous namespace)::i"
-; CHECK-NEXT:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
+; CHECK-NEXT:  [[ANON_INNER]] EXTERNAL TYPE "(anonymous namespace)::inner"
+; CHECK-NEXT:  [[F3]] EXTERNAL FUNCTION "f3"
 ; GCC Doesn't put local statics in pubnames, but it seems not unreasonable and
 ; comes out naturally from LLVM's implementation, so I'm OK with it for now. If
 ; it's demonstrated that this is a major size concern or degrades debug info
 ; consumer behavior, feel free to change it.
 ; CHECK-NEXT:  [[F3_Z]] STATIC VARIABLE "f3::z"
-; CHECK-NEXT:  [[ANON]] EXTERNAL TYPE "(anonymous namespace)"
-; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
-; CHECK-NEXT:  [[ANON_INNER_B]] STATIC VARIABLE "(anonymous namespace)::inner::b"
-; CHECK-NEXT:  [[OUTER]] EXTERNAL TYPE "outer"
-; FIXME: GCC produces enumerators as EXTERNAL, not STATIC
-; 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:  [[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:  [[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"
+; CHECK-NEXT:  [[D]] EXTERNAL TYPE     "ns::D"
 
 %struct.C = type { i8 }
 %"struct.ns::D" = type { i32 }
 
 @_ZN1C22static_member_variableE = dso_local global i32 0, align 4, !dbg !0
 @global_variable = dso_local global %struct.C zeroinitializer, align 1, !dbg !18
 @_ZN2ns25global_namespace_variableE = dso_local global i32 1, align 4, !dbg !29
 @_ZN2ns1dE = dso_local global %"struct.ns::D" zeroinitializer, align 4, !dbg !32

llvm/test/tools/dsymutil/ARM/extern-alias.test

 
 $ xcrun --sdk iphoneos clang -g private_extern.c -c -o private_extern.o -target arm64-apple-ios14.0
 $ xcrun --sdk iphoneos clang -g main.c -c -o main.o -target arm64-apple-ios14.0
 $ xcrun --sdk iphoneos clang private_extern.o main.o -target arm64-apple-ios14.0 -o private_extern.out -Xlinker -alias_list -Xlinker alias_list
 
 RUN: dsymutil -oso-prepend-path %p/../Inputs %p/../Inputs/private/tmp/private_extern/private_extern.out -o %t.dSYM --verbose | FileCheck %s
 RUN: dsymutil -oso-prepend-path %p/../Inputs %p/../Inputs/private/tmp/extern/extern.out -o %t.dSYM --verbose | FileCheck %s
 CHECK-NOT: could not find object file symbol for symbol _baz
-CHECK: { sym: _foo, objAddr: 0x0, binAddr: 0x100007F58, size: 0x20 }
 CHECK: { sym: _baz, objAddr: 0x0, binAddr: 0x100007F58, size: 0x0 }
+CHECK: { sym: _foo, objAddr: 0x0, binAddr: 0x100007F58, size: 0x20 }

llvm/test/tools/llvm-profdata/suppl-instr-with-sample.test

 Some basic tests for supplementing instrumentation profile with sample profile.
 
 Test all of goo's counters will be set to PseudoHot.
 RUN: llvm-profdata merge \
 RUN:     -supplement-instr-with-sample=%p/Inputs/mix_sample.proftext \
 RUN:     -suppl-min-size-threshold=0 %p/Inputs/mix_instr.proftext -o %t
 RUN: llvm-profdata show %t -all-functions -counts | FileCheck %s --check-prefix=MIX1
 
-MIX1: foo:
-MIX1-NEXT: Hash: 0x0000000000000007
-MIX1-NEXT: Counters: 5
-MIX1-NEXT: Block counts: [12, 13, 0, 0, 0]
 MIX1: goo:
 MIX1-NEXT: Hash: 0x0000000000000005
 MIX1-NEXT: Counters: 3
 MIX1-NOT: Block counts:
 MIX1-SAME: <PseudoHot>
+MIX1: foo:
+MIX1-NEXT: Hash: 0x0000000000000007
+MIX1-NEXT: Counters: 5
+MIX1-NEXT: Block counts: [12, 13, 0, 0, 0]
 MIX1: moo:
 MIX1-NEXT: Hash: 0x0000000000000009
 MIX1-NEXT: Counters: 4
 MIX1-NEXT: Block counts: [3000, 1000, 2000, 500]
 
 Test when the zero counter ratio of foo is higher than zero-counter-threshold.
 RUN: llvm-profdata merge \
 RUN:     -supplement-instr-with-sample=%p/Inputs/mix_sample.proftext \
 RUN:     -suppl-min-size-threshold=0 -zero-counter-threshold=0.5 \
 RUN:     -instr-prof-cold-threshold=30 %p/Inputs/mix_instr.proftext -o %t
 RUN: llvm-profdata show %t -all-functions -counts | FileCheck %s --check-prefix=MIX2
 
-MIX2: foo:
-MIX2-NEXT: Hash: 0x0000000000000007
-MIX2-NEXT: Counters: 5
-MIX2-NOT: Block counts:
-MIX2-SAME: <PseudoHot>
 MIX2: goo:
 MIX2-NEXT: Hash: 0x0000000000000005
 MIX2-NEXT: Counters: 3
 MIX2-NOT: Block counts:
 MIX2-SAME: <PseudoHot>
+MIX2: foo:
+MIX2-NEXT: Hash: 0x0000000000000007
+MIX2-NEXT: Counters: 5
+MIX2-NOT: Block counts:
+MIX2-SAME: <PseudoHot>
 MIX2: moo:
 MIX2-NEXT: Hash: 0x0000000000000009
 MIX2-NEXT: Counters: 4
 MIX2-NEXT: Block counts: [3000, 1000, 2000, 500]
 
 Test when the zero counter ratio of foo is lower than zero-counter-threshold.
 RUN: llvm-profdata merge \
 RUN:     -supplement-instr-with-sample=%p/Inputs/mix_sample.proftext \
 RUN:     -suppl-min-size-threshold=0 -zero-counter-threshold=0.7 \
 RUN:     -instr-prof-cold-threshold=30 %p/Inputs/mix_instr.proftext -o %t
 RUN: llvm-profdata show %t -all-functions -counts | FileCheck %s --check-prefix=MIX3
 
-MIX3: foo:
-MIX3-NEXT: Hash: 0x0000000000000007
-MIX3-NEXT: Counters: 5
-MIX3-NEXT: Block counts: [1384, 1500, 0, 0, 0]
 MIX3: goo:
 MIX3-NEXT: Hash: 0x0000000000000005
 MIX3-NEXT: Counters: 3
 MIX3-NOT: Block counts:
 MIX3-SAME: <PseudoHot>
+MIX3: foo:
+MIX3-NEXT: Hash: 0x0000000000000007
+MIX3-NEXT: Counters: 5
+MIX3-NEXT: Block counts: [1384, 1500, 0, 0, 0]
 MIX3: moo:
 MIX3-NEXT: Hash: 0x0000000000000009
 MIX3-NEXT: Counters: 4
 MIX3-NEXT: Block counts: [3000, 1000, 2000, 500]
 
 Test foo's profile won't be adjusted because its size is smaller
 than suppl-min-size-threshold.
 RUN: llvm-profdata merge \
 RUN:     -supplement-instr-with-sample=%p/Inputs/mix_sample.proftext \
 RUN:     -suppl-min-size-threshold=2 -zero-counter-threshold=0.7 \
 RUN:     -instr-prof-cold-threshold=30 %p/Inputs/mix_instr_small.proftext -o %t
 RUN: llvm-profdata show %t -all-functions -counts | FileCheck %s --check-prefix=MIX4
 
-MIX4: foo:
-MIX4-NEXT: Hash: 0x0000000000000007
-MIX4-NEXT: Counters: 1
-MIX4-NEXT: Block counts: [0]
 MIX4: goo:
 MIX4-NEXT: Hash: 0x0000000000000005
 MIX4-NEXT: Counters: 3
 MIX4-NOT: Block counts:
 MIX4-SAME: <PseudoHot>
+MIX4: foo:
+MIX4-NEXT: Hash: 0x0000000000000007
+MIX4-NEXT: Counters: 1
+MIX4-NEXT: Block counts: [0]
 MIX4: moo:
 MIX4-NEXT: Hash: 0x0000000000000009
 MIX4-NEXT: Counters: 1
 MIX4-NEXT: Block counts: [0]
 
 Test profile summary won't be affected by pseudo counters.
 RUN: llvm-profdata merge \
 RUN:     -supplement-instr-with-sample=%p/Inputs/mix_sample.proftext \

mlir/test/mlir-lsp-server/completion.test

// -----
   "position":{"line":4,"character":8}
 }}
 // CHECK-LABEL: "id": 4
 // CHECK-NEXT:  "jsonrpc": "2.0",
 // CHECK-NEXT:  "result": {
 // CHECK-NEXT:    "isIncomplete": false,
 // CHECK-NEXT:    "items": [
 // CHECK-NEXT:      {
-// CHECK-NEXT:        "detail": "builtin.unrealized_conversion_cast: !pdl.value",
-// CHECK-NEXT:        "insertText": "cast",
+// CHECK-NEXT:        "detail": "arg #0: i32",
+// CHECK-NEXT:        "insertText": "arg",
 // CHECK-NEXT:        "insertTextFormat": 1,
 // CHECK-NEXT:        "kind": 6,
-// CHECK-NEXT:        "label": "%cast"
+// CHECK-NEXT:        "label": "%arg"
 // CHECK-NEXT:      },
 // CHECK-NEXT:      {
-// CHECK-NEXT:        "detail": "arg #0: i32",
-// CHECK-NEXT:        "insertText": "arg",
+// CHECK-NEXT:        "detail": "builtin.unrealized_conversion_cast: !pdl.value",
+// CHECK-NEXT:        "insertText": "cast",
 // CHECK-NEXT:        "insertTextFormat": 1,
 // CHECK-NEXT:        "kind": 6,
-// CHECK-NEXT:        "label": "%arg"
+// CHECK-NEXT:        "label": "%cast"
 // CHECK-NEXT:      }
 // CHECK:         ]
 // CHECK-NEXT:  }
 // -----
 {"jsonrpc":"2.0","id":5,"method":"textDocument/completion","params":{
   "textDocument":{"uri":"test:///foo.mlir"},
   "position":{"line":2,"character":10}
 }}