[PGO] Fix computation of fuction Hash

[serge-sans-paille]

Summary

Previous implementation was incorrectly passing an uint64_t, that got converted
to an uint8_t, to finalize the hash computation. This led to different functions
having the same hash if they only differ by the remaining statements, which is
incorrect.

Added a new test case that trivially tests that a small function change is
reflected in the hash value.

Not that as this patch fixes the hash computation, it invalidates all hashes
computed before that patch applies, which could be an issue for large build
system that pre-compute the profile data and let client download them as part of
the build process.

[serge-sans-paille]

Update test case

[MaskRay]

This patch is correct. A clarification of the description:

Previous implementation was incorrectly passing an integer, that got converted to a pointer, to finalize the hash computation.

Working (an uint64_t) was truncated to an uint8_t, converted to a one-element ArrayRef<uint8_t>, then passed to MD5.update

[MaskRay]

clang/lib/CodeGen/CodeGenPGO.cpp

759

Can the using be deleted?

[serge-sans-paille]

Updated summary + removed namespace.

[hans]

Nice fix, and nice test :-)

May I ask how you found this?

[serge-sans-paille]

May I ask how you found this?

This was a long (and painful) quest when tracking https://bugzilla.redhat.com/show_bug.cgi?id=1827282

[serge-sans-paille]

Up?

[hans]

lgtm

[ormris]

There's a few test failures related to this change on the PS4 bot. Could you take a look?

http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/68111

[serge-sans-paille]

@bkramer rightfully reverted this, faster than I could patch it :-) Here is the patch though, with the updated test case. @hans the only meaningful change is that I'm keeping the buggy behavior for hash v1 for compatibility reason.

[serge-sans-paille]

Update profile data hash entries due to hash function update, unless the version
used is V1, in which case we keep the buggy behavior for backward compatibility.

[MaskRay]

Thanks!

[serge-sans-paille]

@hans/ @MaskRay I'm starting to wonder if I should bump the version number of the hash function, so that clang could still read profile data generated before that patch?

[serge-sans-paille]

Bump the version number to be compatible with existing profdata, in a similar fashion to v1/v2 transition.

[hans]

In D79961#2053806, @serge-sans-paille wrote:

Bump the version number to be compatible with existing profdata, in a similar fashion to v1/v2 transition.

Did you forget to include some files? I don't see the bump anywhere.

clang/lib/CodeGen/CodeGenPGO.cpp

754

Maybe explicitly show the conversion to array of uint8_t here, to make it more clear what's going on.

[serge-sans-paille]

With v3 version + Make cast explicit

[serge-sans-paille]

@hans updated!

[hans]

I worry that the hash version bump isn't complete. Doesn't the hash version used need to be read/written with the profile data file somewhere?

clang/lib/CodeGen/CodeGenPGO.cpp

147

I guess this needs an update now?

291

Should this be >= PGO_HASH_V2 now? And similarly below?

753

Maybe just "HashVersion < PGO_HASH_V3" would be simpler?

[serge-sans-paille]

Update version bump parts

[hans]

lgtm

[alanphipps]

It looks like clang/test/Profile/Inputs/c-general.profdata.v5 is being read as v6 rather than v5. Can you double check?

[serge-sans-paille]

In D79961#2065605, @alanphipps wrote:

It looks like clang/test/Profile/Inputs/c-general.profdata.v5 is being read as v6 rather than v5. Can you double check?

Yep, I'll have a look.

[serge-sans-paille]

In D79961#2065605, @alanphipps wrote:

It looks like clang/test/Profile/Inputs/c-general.profdata.v5 is being read as v6 rather than v5. Can you double check?

Thanks for spotting the issue. Should be fixed by 63489c39deeffb24a085b3766c5d5ff76a52fa2f

clang/lib/CodeGen/CodeGenPGO.cpp

 const unsigned PGOHash::NumTypesPerWord;
 const unsigned PGOHash::TooBig;
 
 /// Get the PGO hash version used in the given indexed profile.
 static PGOHashVersion getPGOHashVersion(llvm::IndexedInstrProfReader *PGOReader,
                                         CodeGenModule &CGM) {
   if (PGOReader->getVersion() <= 4)
     return PGO_HASH_V1;
   return PGO_HASH_V2;
 }
 
 /// A RecursiveASTVisitor that fills a map of statements to PGO counters.
 struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
   using Base = RecursiveASTVisitor<MapRegionCounters>;
 
   /// The next counter value to assign.
   unsigned NextCounter;
PGOHash::HashType getHashType(PGOHashVersion HashVersion, const Stmt *S) {
     case Stmt::BinaryConditionalOperatorClass:
       return PGOHash::BinaryConditionalOperator;
     case Stmt::BinaryOperatorClass: {
       const BinaryOperator *BO = cast<BinaryOperator>(S);
       if (BO->getOpcode() == BO_LAnd)
         return PGOHash::BinaryOperatorLAnd;
       if (BO->getOpcode() == BO_LOr)
         return PGOHash::BinaryOperatorLOr;
       if (HashVersion == PGO_HASH_V2) {
         switch (BO->getOpcode()) {
         default:
           break;
         case BO_LT:
           return PGOHash::BinaryOperatorLT;
         case BO_GT:
           return PGOHash::BinaryOperatorGT;
         case BO_LE:
uint64_t PGOHash::finalize() {
   // Use Working as the hash directly if we never used MD5.
   if (Count <= NumTypesPerWord)
     // No need to byte swap here, since none of the math was endian-dependent.
     // This number will be byte-swapped as required on endianness transitions,
     // so we will see the same value on the other side.
     return Working;
 
   // Check for remaining work in Working.
-  if (Working)
-    MD5.update(Working);
+  if (Working) {
+    using namespace llvm::support;
+    uint64_t Swapped = endian::byte_swap<uint64_t, little>(Working);
+    MD5.update(llvm::makeArrayRef((uint8_t *)&Swapped, sizeof(Swapped)));
+  }
 
   // Finalize the MD5 and return the hash.
   llvm::MD5::MD5Result Result;
   MD5.final(Result);
   using namespace llvm::support;
   return Result.low();
 }
 
 void CodeGenPGO::assignRegionCounters(GlobalDecl GD, llvm::Function *Fn) {
   const Decl *D = GD.getDecl();
   if (!D->hasBody())
     return;
 

clang/test/Profile/c-collision.c

+// Test that a slight change in the code leads to a different hash.
+// RUN: %clang_cc1 -UEXTRA -triple x86_64-unknown-linux-gnu -main-file-name c-collision.c %s -o - -emit-llvm -fprofile-instrument=llvm | FileCheck %s --check-prefix=CHECK-NOEXTRA
+// RUN: %clang_cc1 -DEXTRA -triple x86_64-unknown-linux-gnu -main-file-name c-collision.c %s -o - -emit-llvm -fprofile-instrument=llvm | FileCheck %s --check-prefix=CHECK-EXTRA
+
+// CHECK-NOEXTRA: @__profd_main = private global { {{.*}} } { i64 -2624081020897602054, i64 88870893692,
+// CHECK-EXTRA:   @__profd_main = private global { {{.*}} } { i64 -2624081020897602054, i64 101970072141,
+
+int main(int n, char **v) {
+  if (n)
+    n += 1;
+  if (n)
+    n += 1;
+  if (n)
+    n += 1;
+  if (n)
+    n += 1;
+  if (n)
+    n += 1;
+  if (n)
+    n += 1;
+#ifdef EXTRA
+  if (n)
+    n += 1;
+#endif
+  return n;
+}