[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

767–768

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

757

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

148–150

I guess this needs an update now?

294

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

756

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/docs/ReleaseNotes.rst

- Users of UBSan, PGO, and coverage on Windows will now need to add clang's
   directory. For example, if LLVM is installed in ``C:\Program Files\LLVM``,
   then the profile runtime library will appear at
   ``C:\Program Files\LLVM\lib\clang\11.0.0\lib\windows\clang_rt.profile-x86_64.lib``.
   To ensure that the linker can find the appropriate library, users should pass
   ``/LIBPATH:C:\Program Files\LLVM\lib\clang\11.0.0\lib\windows`` to the
   linker. If the user links the program with the ``clang`` or ``clang-cl``
   drivers, the driver will pass this flag for them.
 
+- Clang's profile files generated through ``-fprofile-instr-generate`` are using
+  a fixed hashing algorithm that prevents some collision when loading
+  out-of-date profile informations. Clang can still read old profile files.
+
 New Compiler Flags
 ------------------
 
 - -fstack-clash-protection will provide a protection against the stack clash
   attack for x86 architecture through automatic probing of each page of
   allocated stack.
 
 - -ffp-exception-behavior={ignore,maytrap,strict} allows the user to specify

clang/lib/CodeGen/CodeGenPGO.cpp

void CodeGenPGO::setFuncName(llvm::Function *Fn) {
   // Create PGOFuncName meta data.
   llvm::createPGOFuncNameMetadata(*Fn, FuncName);
 }
 
 /// The version of the PGO hash algorithm.
 enum PGOHashVersion : unsigned {
   PGO_HASH_V1,
   PGO_HASH_V2,
+  PGO_HASH_V3,
 
   // Keep this set to the latest hash version.
-  PGO_HASH_LATEST = PGO_HASH_V2
+  PGO_HASH_LATEST = PGO_HASH_V3
 };
 
 namespace {
 /// Stable hasher for PGO region counters.
 ///
 /// PGOHash produces a stable hash of a given function's control flow.
 ///
 /// Changing the output of this hash will invalidate all previously generated
enum HashType : unsigned char {
     ThrowExpr,
     UnaryOperatorLNot,
     BinaryOperatorLT,
     BinaryOperatorGT,
     BinaryOperatorLE,
     BinaryOperatorGE,
     BinaryOperatorEQ,
     BinaryOperatorNE,
-    // The preceding values are available with PGO_HASH_V2.
+    // The preceding values are available since PGO_HASH_V2.
 
     // Keep this last.  It's for the static assert that follows.
     LastHashType
   };
   static_assert(LastHashType <= TooBig, "Too many types in HashType");
 
   PGOHash(PGOHashVersion HashVersion)
       : Working(0), Count(0), HashVersion(HashVersion), MD5() {}
   void combine(HashType Type);
   uint64_t finalize();
   PGOHashVersion getHashVersion() const { return HashVersion; }
 };
 const int PGOHash::NumBitsPerType;
 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;
+  if (PGOReader->getVersion() <= 5)
     return PGO_HASH_V2;
+  return PGO_HASH_V3;
 }
 
 /// 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) {
+      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:
           return PGOHash::BinaryOperatorLE;
         case BO_GE:
           return PGOHash::BinaryOperatorGE;
         case BO_EQ:
           return PGOHash::BinaryOperatorEQ;
         case BO_NE:
           return PGOHash::BinaryOperatorNE;
         }
       }
       break;
     }
     }
 
-    if (HashVersion == PGO_HASH_V2) {
+    if (HashVersion >= PGO_HASH_V2) {
       switch (S->getStmtClass()) {
       default:
         break;
       case Stmt::GotoStmtClass:
         return PGOHash::GotoStmt;
       case Stmt::IndirectGotoStmtClass:
         return PGOHash::IndirectGotoStmt;
       case Stmt::BreakStmtClass:
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) {
+    // Keep the buggy behavior from v1 and v2 for backward-compatibility. This
+    // is buggy because it converts a uint64_t into an array of uint8_t.
+    if (HashVersion < PGO_HASH_V3) {
+      MD5.update({(uint8_t)Working});
+    } else {
+      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;
 
   bool InstrumentRegions = CGM.getCodeGenOpts().hasProfileClangInstr();

clang/test/Profile/Inputs/c-counter-overflows.proftext

 main
-10111551811706059223
+7779561829442898616
 8
 1
 68719476720
 64424509425
 68719476720
 21474836475
 21474836475
 21474836475
 4294967295
 

clang/test/Profile/Inputs/c-general.proftext

 simple_loops
 1245818015463121
 4
 1
 100
 100
 75
 
 conditionals
-4190663230902537370
+4904767535850050386
 11
 1
 100
 50
 50
 33
 33
 16
 99
 100
 99
 100
 
 early_exits
-8265526549255474475
+2880354649761471549
 9
 1
 0
 51
 1
 25
 1
 25
 1
 0
 
 jumps
-15872630527555456493
+15051420506203462683
 22
 1
 1
 0
 1
 0
 0
 1

 1
 1
 10
 0
 10
 9
 
 switches
-11892326508727782373
+43242458792028222
 19
 1
 1
 1
 15
 7
 1
 0
 2
 2
 3
 3
 4
 4
 0
 4
 4
 5
 1
 0
 
 big_switch
-16933280399284440835
+13144136522122330070
 17
 1
 32
 32
 1
 0
 1
 1

 34
 66
 17
 34
 33
 50
 
 boolop_loops
-11270260636676715317
+12402604614320574815
 9
 1
 50
 51
 50
 26
 50
 51
 50
 26
 
 conditional_operator
 54992
 3
 1
 0
 1
 
 do_fallthrough
-6898770640283947069
+8714614136504380050
 4
 1
 10
 2
 8
 
 main
 24

clang/test/Profile/Inputs/c-unprofiled-blocks.proftext

 never_called
-5644096560937528444
+6820425066224770721
 9
 0
 0
 0
 0
 0
 0
 0
 0
 0
 
 main
 24
 1
 1
 
 dead_code
-9636018207904213947
+5254464978620792806
 10
 1
 0
 0
 0
 0
 0
 0
 0
 0
 0
 

clang/test/Profile/Inputs/cxx-rangefor.proftext

 _Z9range_forv
-6169071350249721981
+8789831523895825398
 5
 1
 4
 1
 1
 1
 
 main
 24
 1
 1

clang/test/Profile/Inputs/cxx-throws.proftext

 _Z6throwsv
-340120998528097520
+18172607911962830854
 9
 1
 100
 100
 66
 33
 17
 50

clang/test/Profile/Inputs/misexpect-switch-default.proftext

 main
 # Func Hash:
-8712453512413296413
+8734802134600123338
 # Num Counters:
 9
 # Counter Values:
 1
 20000
 20000
 4066
 11889
 0
 0
 4045
 0
 

clang/test/Profile/Inputs/misexpect-switch-nonconst.proftext

 main
 # Func Hash:
-1965403898329309329
+3721743393642630379
 # Num Counters:
 10
 # Counter Values:
 1
 20
 20000
 20000
 1
 0
 0
 0
 19999
 0
 

clang/test/Profile/Inputs/misexpect-switch.proftext

 main
 # Func Hash:
-1965403898329309329
+872687477373597607
 # Num Counters:
 9
 # Counter Values:
 1
 20
 20000
 20000
 12
 26
 0
 0
 19962
 

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=clang | 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=clang | FileCheck %s --check-prefix=CHECK-EXTRA
+
+// CHECK-NOEXTRA: @__profd_foo = private global { {{.*}} } { i64 6699318081062747564, i64 7156072912471487002,
+// CHECK-EXTRA:   @__profd_foo = private global { {{.*}} } { i64 6699318081062747564, i64 -4383447408116050035,
+
+extern int bar;
+void foo() {
+  if (bar) {
+  }
+  if (bar) {
+  }
+  if (bar) {
+    if (bar) {
+#ifdef EXTRA
+      if (bar) {
+      }
+#endif
+    }
+  }
+}

clang/test/Profile/c-general.c

 // Test instrumentation of general constructs in C.
 
 // RUN: %clang_cc1 -triple x86_64-apple-macosx10.9 -main-file-name c-general.c %s -o - -emit-llvm -fprofile-instrument=clang | FileCheck -allow-deprecated-dag-overlap  -check-prefix=PGOGEN %s
 
 // RUN: llvm-profdata merge %S/Inputs/c-general.proftext -o %t.profdata
 // RUN: %clang_cc1 -triple x86_64-apple-macosx10.9 -main-file-name c-general.c %s -o - -emit-llvm -fprofile-instrument-use-path=%t.profdata | FileCheck -allow-deprecated-dag-overlap  -check-prefix=PGOUSE %s
+// RUN: %clang_cc1 -triple x86_64-apple-macosx10.9 -main-file-name c-general.c %s -o - -emit-llvm -fprofile-instrument-use-path=%S/Inputs/c-general.profdata.v5 | FileCheck -allow-deprecated-dag-overlap  -check-prefix=PGOUSE %s
 // RUN: %clang_cc1 -triple x86_64-apple-macosx10.9 -main-file-name c-general.c %s -o - -emit-llvm -fprofile-instrument-use-path=%S/Inputs/c-general.profdata.v3 | FileCheck -allow-deprecated-dag-overlap  -check-prefix=PGOUSE %s
 // Also check compatibility with older profiles.
 // RUN: %clang_cc1 -triple x86_64-apple-macosx10.9 -main-file-name c-general.c %s -o - -emit-llvm -fprofile-instrument-use-path=%S/Inputs/c-general.profdata.v1 | FileCheck -allow-deprecated-dag-overlap  -check-prefix=PGOUSE %s
 
 // PGOGEN: @[[SLC:__profc_simple_loops]] = private global [4 x i64] zeroinitializer
 // PGOGEN: @[[IFC:__profc_conditionals]] = private global [11 x i64] zeroinitializer
 // PGOGEN: @[[EEC:__profc_early_exits]] = private global [9 x i64] zeroinitializer
 // PGOGEN: @[[JMC:__profc_jumps]] = private global [22 x i64] zeroinitializer

llvm/include/llvm/ProfileData/InstrProf.h

enum ProfVersion {
   // Version 3 supports value profile data. The value profile data is expected
   // to follow the block counter profile data.
   Version3 = 3,
   // In this version, profile summary data \c IndexedInstrProf::Summary is
   // stored after the profile header.
   Version4 = 4,
   // In this version, the frontend PGO stable hash algorithm defaults to V2.
   Version5 = 5,
+  // In this version, the frontend PGO stable hash algorithm got fixed and
+  // may produce hashes different from Version5.
+  Version6 = 6,
   // The current version is 5.
   CurrentVersion = INSTR_PROF_INDEX_VERSION
 };
 const uint64_t Version = ProfVersion::CurrentVersion;
 
 const HashT HashType = HashT::MD5;
 
 inline uint64_t ComputeHash(StringRef K) { return ComputeHash(HashType, K); }

llvm/include/llvm/ProfileData/InstrProfData.inc

#define INSTR_PROF_RAW_MAGIC_64 (uint64_t)255 << 56 | (uint64_t)'l' << 48 | \
         (uint64_t)'f' << 16 | (uint64_t)'r' << 8 | (uint64_t)129
 #define INSTR_PROF_RAW_MAGIC_32 (uint64_t)255 << 56 | (uint64_t)'l' << 48 | \
        (uint64_t)'p' << 40 | (uint64_t)'r' << 32 | (uint64_t)'o' << 24 |  \
         (uint64_t)'f' << 16 | (uint64_t)'R' << 8 | (uint64_t)129
 
 /* Raw profile format version (start from 1). */
 #define INSTR_PROF_RAW_VERSION 5
 /* Indexed profile format version (start from 1). */
-#define INSTR_PROF_INDEX_VERSION 5
+#define INSTR_PROF_INDEX_VERSION 6
 /* Coverage mapping format version (start from 0). */
 #define INSTR_PROF_COVMAP_VERSION 3
 
 /* Profile version is always of type uint64_t. Reserve the upper 8 bits in the
  * version for other variants of profile. We set the lowest bit of the upper 8
  * bits (i.e. bit 56) to 1 to indicate if this is an IR-level instrumentaiton
  * generated profile, and 0 if this is a Clang FE generated profile.
  * 1 in bit 57 indicates there are context-sensitive records in the profile.