Replace HashString algorithm with xxHash64

[scott.smith]

Summary

The previous algorithm processed one character at a time, which is very painful on a modern CPU. Replace it with xxHash64, which both already exists in the codebase and is fairly fast.

[ruiu]

include/llvm/ADT/StringExtras.h

128

Rename Result Seed.

[scott.smith]

rename param

[vsk]

Thanks for working on this! In the future, please set llvm-commits as a subscriber on differential revisions, not as a reviewer. Also, please upload patches with context (e.g "git diff -U1000").

IMO, tests which break when the string hash function is changed are suspicious. Why is a dependence on a specific hash function being tested? It might make sense to fix the tests in prep commits (ideally no test updates would be needed with this patch). I'll look into fixing the llvm-{cov,profdata} issues.

include/llvm/ADT/StringExtras.h

130

Would xxh32 run significantly faster/slower than xxh64?

[scott.smith]

In D32509#737488, @vsk wrote:

Thanks for working on this! In the future, please set llvm-commits as a subscriber on differential revisions, not as a reviewer. Also, please upload patches with context (e.g "git diff -U1000").

The list is both a subscriber and a reviewer. Next time I'll only make it a subscriber.
I assumed I had no context because Phabricator couldn't map my patch to the repository. Your comment makes me think it doesn't even try (ReviewBoard does this automatically). I didn't realize I'm supposed to supply the context!

IMO, tests which break when the string hash function is changed are suspicious. Why is a dependence on a specific hash function being tested? It might make sense to fix the tests in prep commits (ideally no test updates would be needed with this patch). I'll look into fixing the llvm-{cov,profdata} issues.

That was my first thought too - I was worried the hash value was encoded in the output some how. But I think this stems from the use of StringMap and StringSet, which place into buckets by hash value. So it isn't that anything interesting changed, just that the order of iteration changed. None of the interesting contents changed, AFAICT.

include/llvm/ADT/StringExtras.h

130

It isn't already in the llvm code base. If we're going that route of adding a hash function, there are probably even better choices.

[vsk]

In D32509#737490, @scott.smith wrote:

In D32509#737488, @vsk wrote:

Thanks for working on this! In the future, please set llvm-commits as a subscriber on differential revisions, not as a reviewer. Also, please upload patches with context (e.g "git diff -U1000").

The list is both a subscriber and a reviewer. Next time I'll only make it a subscriber.
I assumed I had no context because Phabricator couldn't map my patch to the repository. Your comment makes me think it doesn't even try (ReviewBoard does this automatically). I didn't realize I'm supposed to supply the context!

IMO, tests which break when the string hash function is changed are suspicious. Why is a dependence on a specific hash function being tested? It might make sense to fix the tests in prep commits (ideally no test updates would be needed with this patch). I'll look into fixing the llvm-{cov,profdata} issues.

That was my first thought too - I was worried the hash value was encoded in the output some how. But I think this stems from the use of StringMap and StringSet, which place into buckets by hash value. So it isn't that anything interesting changed, just that the order of iteration changed. None of the interesting contents changed, AFAICT.

Right, it looks like that's the only thing that's changed. My worry is that if we need to change the hash again, we'd have to go through another batch of test updates. It might be easier to convince people to not print things out in an order determined by a hash function now.

include/llvm/ADT/StringExtras.h

130

Ok. I think it's fine to switch to xxh64 for now.

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

218

I'm not familiar with this test, but it's a bit concerning that more checks get added than removed. @aprantl, what are your thoughts on going forward with the test updates vs. making the output of llvm-dwarfdump not depend on the string hash function?

[aprantl]

include/llvm/ADT/StringExtras.h

126

For consistency: x86_64?

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

218

DWARFDebugPubTable::dump() iterates over the elements of an llvm::Set. We should have separate change first that sorts the set.

[aprantl]

@echristo: Is there anything besides LLVM tests that depends on llvm-dwarfdump's output ordering for the .gnu_pubnames section?

[scott.smith]

Updated to reflect the testing changes made by Vedant.

[echristo]

In D32509#738202, @aprantl wrote:

@echristo: Is there anything besides LLVM tests that depends on llvm-dwarfdump's output ordering for the .gnu_pubnames section?

Shouldn't be, no.

[echristo]

This is fine with me.

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

218

Agreed.

[ruiu]

include/llvm/ADT/StringExtras.h

158–159

nit: in the LLVM coding style you want to put { at end of the previous line.

[scott.smith]

Addressed coding style Issue.

Can someone commit this for me? I don't have access. Thank you!

[ruiu]

I can do that for you.

[ruiu]

Scott,

I cannot submit this patch because there are a few tests failing with your patch. Here is a log. https://gist.github.com/rui314/ef9cc0845131eb6e5e1e00912aefa2b5

Can you take a look?

[vsk]

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

31

Might make these two 'CHECK-DAG' for some future-proofing.

35

Ditto.

[scott.smith]

Updated to include clang test changes.

[ruiu]

Looks like this patch broke several bots.

http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/8639/steps/test/logs/stdio
http://lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/7423/steps/test_lld/logs/stdio

Can you take a look? In the meantime, I'll revert this patch.

[scott.smith]

Fixed clang-tools-extra build issues, but doesn't fix Mac lld issues (http://lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/7423/steps/test_lld/logs/stdio) as I do not have access to a Mac. Can someone look into it? It's probably just an identifier ordering issue.

[vsk]

In D32509#738967, @scott.smith wrote:

Fixed clang-tools-extra build issues, but doesn't fix Mac lld issues (http://lab.llvm.org:8011/builders/lld-x86_64-darwin13/builds/7423/steps/test_lld/logs/stdio) as I do not have access to a Mac. Can someone look into it? It's probably just an identifier ordering issue.

Is it necessary to have a mac to run the mach-o tests? At any rate, changing the 'CHECK'/'DCHECK' lines to 'CHECK-DAG'/'DCHECK-DAG' should do the trick.

[scott.smith]

In D32509#738971, @vsk wrote:

Is it necessary to have a mac to run the mach-o tests? At any rate, changing the 'CHECK'/'DCHECK' lines to 'CHECK-DAG'/'DCHECK-DAG' should do the trick.

AFAIK the test only failed on the mac buildbot. I'm of two minds on CHECK vs CHECK-DAG; it makes the test immune to hash order issues, but in some cases I believe it can make the test too permissive, since in the end it just makes sure the lines are present, not that they are grouped together in any meaningful way.

[vsk]

In D32509#739006, @scott.smith wrote:

In D32509#738971, @vsk wrote:

Is it necessary to have a mac to run the mach-o tests? At any rate, changing the 'CHECK'/'DCHECK' lines to 'CHECK-DAG'/'DCHECK-DAG' should do the trick.

AFAIK the test only failed on the mac buildbot. I'm of two minds on CHECK vs CHECK-DAG; it makes the test immune to hash order issues, but in some cases I believe it can make the test too permissive, since in the end it just makes sure the lines are present, not that they are grouped together in any meaningful way.

That's a fair point. My thinking was that since the output being tested relies on the hash function to for ordering, the test shouldn't be checking for a particular order. But, instead of making the tests more permissive, we could simply sort things before printing them.

[scott.smith]

Reopening as this was reverted.

[scott.smith]

I'll get much better performance by just replacing lldb::ConstString with a lock free hashtable utilizing its own hash function.

[davide]

In D32509#743851, @scott.smith wrote:

I'll get much better performance by just replacing lldb::ConstString with a lock free hashtable utilizing its own hash function.

I can't really comment on your lldb specific solution as I'm not familiar with that code, but I think this would be a valuable improvement for llvm independently.

Thanks!

Davide

include/llvm/ADT/StringExtras.h

 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/DataTypes.h"
+#include "llvm/Support/xxhash.h"
 #include <iterator>
 
 namespace llvm {

 
 /// HashString - Hash function for strings.
 ///
-/// This is the Bernstein hash function.
-//
-// FIXME: Investigate whether a modified bernstein hash function performs
-// better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
-//   X*33+c -> X*33^c
-static inline unsigned HashString(StringRef Str, unsigned Result = 0) {
-  for (StringRef::size_type i = 0, e = Str.size(); i != e; ++i)
-    Result = Result * 33 + (unsigned char)Str[i];
-  return Result;
+/// Just fall back on xxHash64.  Yes we drop the high bits on platforms where
+/// unsigned == 4 bytes (which includes amd64), but xxHash64 already has good
+/// avalanching, so we wouldn't gain much if anything.
+static inline unsigned HashString(StringRef Str, unsigned Seed = 0)
+{
+  return xxHash64(Str, Seed);
 }
 
 /// Returns the English suffix for an ordinal integer (-st, -nd, -rd, -th).

include/llvm/Support/xxhash.h

 #include "llvm/ADT/StringRef.h"
 
 namespace llvm {
-uint64_t xxHash64(llvm::StringRef Data);
+uint64_t xxHash64(llvm::StringRef Data, uint64_t Seed = 0);
 }
 
 #endif

lib/Support/xxhash.cpp

   return Acc;
 }
 
-uint64_t llvm::xxHash64(StringRef Data) {
+uint64_t llvm::xxHash64(StringRef Data, uint64_t Seed) {
   size_t Len = Data.size();
-  uint64_t Seed = 0;
   const char *P = Data.data();
   const char *const BEnd = P + Len;
   uint64_t H64;

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

 
 ; Check that all the names are present in the output
 ; CHECK:  Hash = 0x00597841
-; CHECK:    Name: {{[0-9a-f]*}} "is"
 ; CHECK:    Name: {{[0-9a-f]*}} "k1"
+; CHECK:    Name: {{[0-9a-f]*}} "is"
 
 ; CHECK: Hash = 0xa4b42a1e
-; CHECK:    Name: {{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE"
 ; CHECK:    Name: {{[0-9a-f]*}} "_ZN4llvm16DenseMapIteratorIPNS_10MDLocationENS_6detail13DenseSetEmptyENS_10MDNodeInfoIS1_EENS3_12DenseSetPairIS2_EELb0EE23AdvancePastEmptyBucketsEv"
+; CHECK:    Name: {{[0-9a-f]*}} "_ZN5clang23DataRecursiveASTVisitorIN12_GLOBAL__N_124UnusedBackingIvarCheckerEE26TraverseCUDAKernelCallExprEPNS_18CUDAKernelCallExprE"
 
 ; CHECK: Hash = 0xeee7c0b2
 ; CHECK:    Name: {{[0-9a-f]*}} "_ZNK4llvm12LivePhysRegs5printERNS_11raw_ostreamE"

test/DebugInfo/PDB/pdbdump-headers.test

 ; EMPTY-NEXT:   Guid: {0B355641-86A0-A249-896F-9988FAE52FF0}
 ; EMPTY-NEXT:   Features: 0x1
 ; EMPTY-NEXT:   Named Streams {
-; EMPTY-NEXT:     /names: 13
 ; EMPTY-NEXT:     /LinkInfo: 5
+; EMPTY-NEXT:     /names: 13
 ; EMPTY-NEXT:     /src/headerblock: 9
 ; EMPTY-NEXT:   }
 ; EMPTY-NEXT: }

 ; BIG-NEXT:   Guid: {880ECC89-DF81-0B4F-839C-58CBD052E937}
 ; BIG-NEXT:   Features: 0x1
 ; BIG-NEXT:   Named Streams {
-; BIG-NEXT:     /names: 13
 ; BIG-NEXT:     /LinkInfo: 5
+; BIG-NEXT:     /names: 13
 ; BIG-NEXT:     /src/headerblock: 61
 ; BIG-NEXT:   }
 ; BIG-NEXT: }

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

 
 ; ASM: .section        .debug_gnu_pubnames
 ; ASM: .byte   32                      # Kind: VARIABLE, EXTERNAL
+; ASM: .byte   32                      # Kind: VARIABLE, EXTERNAL
 ; ASM-NEXT: .asciz  "global_variable"       # External Name
 
 ; ASM: .section        .debug_gnu_pubtypes

 ; 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:  EXTERNAL FUNCTION "f7"
+; CHECK-NEXT:  [[OUTER_ANON]] EXTERNAL TYPE "outer::(anonymous namespace)"
 ; 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:  [[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:  [[ANON_INNER]] EXTERNAL TYPE "(anonymous namespace)::inner"
+; CHECK-NEXT:  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"
-; 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:  [[GLOB_NS_FUNC]] EXTERNAL FUNCTION "ns::global_namespace_function"
-; CHECK-NEXT:  [[STATIC_MEM_VAR]] EXTERNAL VARIABLE "C::static_member_variable"
-; CHECK-NEXT:  [[STATIC_MEM_FUNC]] EXTERNAL FUNCTION "C::static_member_function"
 
 ; CHECK-LABEL: debug_gnu_pubtypes contents:
 ; CHECK: Offset     Linkage  Kind     Name

test/tools/llvm-cov/Inputs/test_long_file_names.output

-File 'srcdir/./nested_dir/../test.h'
-Lines executed:100.00% of 1
-srcdir/./nested_dir/../test.h:creating 'test_paths.cpp##test.h.gcov'
-
 File 'srcdir/./nested_dir/../test.cpp'
 Lines executed:84.21% of 38
 srcdir/./nested_dir/../test.cpp:creating 'test_paths.cpp##test.cpp.gcov'
 
+File 'srcdir/./nested_dir/../test.h'
+Lines executed:100.00% of 1
+srcdir/./nested_dir/../test.h:creating 'test_paths.cpp##test.h.gcov'
+

test/tools/llvm-cov/Inputs/test_long_paths.output

-File 'srcdir/./nested_dir/../test.h'
-Lines executed:100.00% of 1
-srcdir/./nested_dir/../test.h:creating 'srcdir#^#test_paths.cpp##srcdir#nested_dir#^#test.h.gcov'
-
 File 'srcdir/./nested_dir/../test.cpp'
 Lines executed:84.21% of 38
 srcdir/./nested_dir/../test.cpp:creating 'srcdir#^#test_paths.cpp##srcdir#nested_dir#^#test.cpp.gcov'
 
+File 'srcdir/./nested_dir/../test.h'
+Lines executed:100.00% of 1
+srcdir/./nested_dir/../test.h:creating 'srcdir#^#test_paths.cpp##srcdir#nested_dir#^#test.h.gcov'
+

test/tools/llvm-cov/Inputs/test_missing.output

-File 'srcdir/./nested_dir/../test.h'
-Lines executed:100.00% of 1
-srcdir/./nested_dir/../test.h:creating 'test.h.gcov'
-
 File 'srcdir/./nested_dir/../test.cpp'
 Lines executed:84.21% of 38
 srcdir/./nested_dir/../test.cpp:creating 'test.cpp.gcov'
 
+File 'srcdir/./nested_dir/../test.h'
+Lines executed:100.00% of 1
+srcdir/./nested_dir/../test.h:creating 'test.h.gcov'
+

test/tools/llvm-cov/Inputs/test_no_preserve_paths.output

-File 'srcdir/./nested_dir/../test.h'
-Lines executed:100.00% of 1
-srcdir/./nested_dir/../test.h:creating 'test.h.gcov'
-
 File 'srcdir/./nested_dir/../test.cpp'
 Lines executed:84.21% of 38
 srcdir/./nested_dir/../test.cpp:creating 'test.cpp.gcov'
 
+File 'srcdir/./nested_dir/../test.h'
+Lines executed:100.00% of 1
+srcdir/./nested_dir/../test.h:creating 'test.h.gcov'
+

test/tools/llvm-cov/Inputs/test_preserve_paths.output

-File 'srcdir/./nested_dir/../test.h'
-Lines executed:100.00% of 1
-srcdir/./nested_dir/../test.h:creating 'srcdir#nested_dir#^#test.h.gcov'
-
 File 'srcdir/./nested_dir/../test.cpp'
 Lines executed:84.21% of 38
 srcdir/./nested_dir/../test.cpp:creating 'srcdir#nested_dir#^#test.cpp.gcov'
 
+File 'srcdir/./nested_dir/../test.h'
+Lines executed:100.00% of 1
+srcdir/./nested_dir/../test.h:creating 'srcdir#nested_dir#^#test.h.gcov'
+

test/tools/llvm-profdata/overflow-sample.test

 RUN: llvm-profdata merge -sample %p/Inputs/overflow-sample.proftext %p/Inputs/overflow-sample.proftext -o %t.out 2>&1 | FileCheck %s -check-prefix=MERGE_OVERFLOW
 RUN: llvm-profdata show -sample %t.out | FileCheck %s --check-prefix=SHOW_OVERFLOW
 MERGE_OVERFLOW: {{.*}}: main: Counter overflow
-SHOW_OVERFLOW: Function: main: 2000, 0, 2 sampled lines
+SHOW_OVERFLOW: Function: _Z3fooi: 18446744073709551615, 2000, 1 sampled lines
 SHOW_OVERFLOW-NEXT: Samples collected in the function's body {
-SHOW_OVERFLOW-NEXT:   1: 1000, calls: _Z3bari:18446744073709551615
-SHOW_OVERFLOW-NEXT:   2: 1000, calls: _Z3fooi:18446744073709551615
+SHOW_OVERFLOW-NEXT:   1: 18446744073709551615
 SHOW_OVERFLOW-NEXT: }
 SHOW_OVERFLOW-NEXT: No inlined callsites in this function
-SHOW_OVERFLOW-NEXT: Function: _Z3fooi: 18446744073709551615, 2000, 1 sampled lines
+SHOW_OVERFLOW-NEXT: Function: _Z3bari: 18446744073709551615, 2000, 1 sampled lines
 SHOW_OVERFLOW-NEXT: Samples collected in the function's body {
 SHOW_OVERFLOW-NEXT:   1: 18446744073709551615
 SHOW_OVERFLOW-NEXT: }
 SHOW_OVERFLOW-NEXT: No inlined callsites in this function
-SHOW_OVERFLOW-NEXT: Function: _Z3bari: 18446744073709551615, 2000, 1 sampled lines
+SHOW_OVERFLOW-NEXT: Function: main: 2000, 0, 2 sampled lines
 SHOW_OVERFLOW-NEXT: Samples collected in the function's body {
-SHOW_OVERFLOW-NEXT:   1: 18446744073709551615
+SHOW_OVERFLOW-NEXT:   1: 1000, calls: _Z3bari:18446744073709551615
+SHOW_OVERFLOW-NEXT:   2: 1000, calls: _Z3fooi:18446744073709551615
 SHOW_OVERFLOW-NEXT: }
 SHOW_OVERFLOW-NEXT: No inlined callsites in this function
 

 RUN: llvm-profdata merge -sample %p/Inputs/overflow-sample.proftext -o %t.out 2>&1 | FileCheck %s -allow-empty -check-prefix=MERGE_NO_OVERFLOW
 RUN: llvm-profdata show -sample %t.out | FileCheck %s --check-prefix=SHOW_NO_OVERFLOW
 MERGE_NO_OVERFLOW-NOT: {{.*}}: main: Counter overflow
-SHOW_NO_OVERFLOW: Function: main: 1000, 0, 2 sampled lines
+SHOW_NO_OVERFLOW: Function: _Z3fooi: 18446744073709551615, 1000, 1 sampled lines
 SHOW_NO_OVERFLOW-NEXT: Samples collected in the function's body {
-SHOW_NO_OVERFLOW-NEXT:   1: 500, calls: _Z3bari:18446744073709551615
-SHOW_NO_OVERFLOW-NEXT:   2: 500, calls: _Z3fooi:18446744073709551615
+SHOW_NO_OVERFLOW-NEXT:   1: 18446744073709551615
 SHOW_NO_OVERFLOW-NEXT: }
 SHOW_NO_OVERFLOW-NEXT: No inlined callsites in this function
-SHOW_NO_OVERFLOW-NEXT: Function: _Z3fooi: 18446744073709551615, 1000, 1 sampled lines
+SHOW_NO_OVERFLOW-NEXT: Function: _Z3bari: 18446744073709551615, 1000, 1 sampled lines
 SHOW_NO_OVERFLOW-NEXT: Samples collected in the function's body {
 SHOW_NO_OVERFLOW-NEXT:   1: 18446744073709551615
 SHOW_NO_OVERFLOW-NEXT: }
 SHOW_NO_OVERFLOW-NEXT: No inlined callsites in this function
-SHOW_NO_OVERFLOW-NEXT: Function: _Z3bari: 18446744073709551615, 1000, 1 sampled lines
+SHOW_NO_OVERFLOW-NEXT: Function: main: 1000, 0, 2 sampled lines
 SHOW_NO_OVERFLOW-NEXT: Samples collected in the function's body {
-SHOW_NO_OVERFLOW-NEXT:   1: 18446744073709551615
+SHOW_NO_OVERFLOW-NEXT:   1: 500, calls: _Z3bari:18446744073709551615
+SHOW_NO_OVERFLOW-NEXT:   2: 500, calls: _Z3fooi:18446744073709551615
 SHOW_NO_OVERFLOW-NEXT: }
 SHOW_NO_OVERFLOW-NEXT: No inlined callsites in this function

test/tools/llvm-profdata/sample-profile-basic.test

 
 1- Show all functions
 RUN: llvm-profdata show --sample %p/Inputs/sample-profile.proftext | FileCheck %s --check-prefix=SHOW1
-SHOW1: Function: main: 184019, 0, 7 sampled lines
-SHOW1: 9: 2064, calls: _Z3fooi:631 _Z3bari:1471
 SHOW1: Function: _Z3fooi: 7711, 610, 1 sampled lines
 SHOW1: Function: _Z3bari: 20301, 1437, 1 sampled lines
 SHOW1: 1: 1437
+SHOW1: Function: main: 184019, 0, 7 sampled lines
+SHOW1: 9: 2064, calls: _Z3fooi:631 _Z3bari:1471
 
 2- Show only bar
 RUN: llvm-profdata show --sample --function=_Z3bari %p/Inputs/sample-profile.proftext | FileCheck %s --check-prefix=SHOW2

    counters have doubled.
 RUN: llvm-profdata merge --sample %p/Inputs/sample-profile.proftext -o %t-binprof
 RUN: llvm-profdata merge --sample --text %p/Inputs/sample-profile.proftext %t-binprof -o - | FileCheck %s --check-prefix=MERGE1
+MERGE1: _Z3fooi:15422:1220
 MERGE1: main:368038:0
 MERGE1: 9: 4128 _Z3fooi:1262 _Z3bari:2942
-MERGE1: _Z3fooi:15422:1220
 
 5- Detect invalid text encoding (e.g. instrumentation profile text format).
 RUN: not llvm-profdata show --sample %p/Inputs/foo3bar3-1.proftext 2>&1 | FileCheck %s --check-prefix=BADTEXT

test/tools/llvm-profdata/weight-sample.test

 1- Merge the foo and bar profiles with unity weight and verify the combined output
 RUN: llvm-profdata merge -sample -text -weighted-input=1,%p/Inputs/weight-sample-bar.proftext -weighted-input=1,%p/Inputs/weight-sample-foo.proftext -o - | FileCheck %s -check-prefix=1X_1X_WEIGHT
 RUN: llvm-profdata merge -sample -text -weighted-input=1,%p/Inputs/weight-sample-bar.proftext %p/Inputs/weight-sample-foo.proftext -o - | FileCheck %s -check-prefix=1X_1X_WEIGHT
-1X_1X_WEIGHT: foo:1763288:35327
-1X_1X_WEIGHT-NEXT:  7: 35327
-1X_1X_WEIGHT-NEXT:  8: 35327
-1X_1X_WEIGHT-NEXT:  9: 6930
-1X_1X_WEIGHT-NEXT:  10: 29341
-1X_1X_WEIGHT-NEXT:  11: 11906
-1X_1X_WEIGHT-NEXT:  13: 18185 foo:19531
-1X_1X_WEIGHT-NEXT:  15: 36458
-1X_1X_WEIGHT-NEXT: bar:1772037:35370
+1X_1X_WEIGHT: bar:1772037:35370
 1X_1X_WEIGHT-NEXT:  17: 35370
 1X_1X_WEIGHT-NEXT:  18: 35370
 1X_1X_WEIGHT-NEXT:  19: 7005

 1X_1X_WEIGHT-NEXT:  21: 12170
 1X_1X_WEIGHT-NEXT:  23: 18150 bar:19829
 1X_1X_WEIGHT-NEXT:  25: 36666
+1X_1X_WEIGHT-NEXT: foo:1763288:35327
+1X_1X_WEIGHT-NEXT:  7: 35327
+1X_1X_WEIGHT-NEXT:  8: 35327
+1X_1X_WEIGHT-NEXT:  9: 6930
+1X_1X_WEIGHT-NEXT:  10: 29341
+1X_1X_WEIGHT-NEXT:  11: 11906
+1X_1X_WEIGHT-NEXT:  13: 18185 foo:19531
+1X_1X_WEIGHT-NEXT:  15: 36458
 
 2- Merge the foo and bar profiles with weight 3x and 5x respectively and verify the combined output
 RUN: llvm-profdata merge -sample -text -weighted-input=3,%p/Inputs/weight-sample-bar.proftext -weighted-input=5,%p/Inputs/weight-sample-foo.proftext -o - | FileCheck %s -check-prefix=3X_5X_WEIGHT
-3X_5X_WEIGHT: foo:8816440:176635
-3X_5X_WEIGHT-NEXT:  7: 176635
-3X_5X_WEIGHT-NEXT:  8: 176635
-3X_5X_WEIGHT-NEXT:  9: 34650
-3X_5X_WEIGHT-NEXT:  10: 146705
-3X_5X_WEIGHT-NEXT:  11: 59530
-3X_5X_WEIGHT-NEXT:  13: 90925 foo:97655
-3X_5X_WEIGHT-NEXT:  15: 182290
-3X_5X_WEIGHT-NEXT: bar:5316111:106110
+3X_5X_WEIGHT: bar:5316111:106110
 3X_5X_WEIGHT-NEXT:  17: 106110
 3X_5X_WEIGHT-NEXT:  18: 106110
 3X_5X_WEIGHT-NEXT:  19: 21015

 3X_5X_WEIGHT-NEXT:  21: 36510
 3X_5X_WEIGHT-NEXT:  23: 54450 bar:59487
 3X_5X_WEIGHT-NEXT:  25: 109998
+3X_5X_WEIGHT-NEXT: foo:8816440:176635
+3X_5X_WEIGHT-NEXT:  7: 176635
+3X_5X_WEIGHT-NEXT:  8: 176635
+3X_5X_WEIGHT-NEXT:  9: 34650
+3X_5X_WEIGHT-NEXT:  10: 146705
+3X_5X_WEIGHT-NEXT:  11: 59530
+3X_5X_WEIGHT-NEXT:  13: 90925 foo:97655
+3X_5X_WEIGHT-NEXT:  15: 182290
 
 3- Bad merge: invalid weight
 RUN: not llvm-profdata merge -sample -weighted-input=3,%p/Inputs/weight-sample-bar.proftext -weighted-input=0,%p/Inputs/weight-sample-foo.proftext -o %t.out 2>&1 | FileCheck %s -check-prefix=INVALID_WEIGHT