Non-deterministic metadata generated

[rjmansfield]

Compiling the attached reduce.txt creduced testcase multiple times will eventually lead to an object file that differs.

#!/bin/bash
set -e

FILENAME="reduced.i"
COPTS="-O2 -flto -g -c "

clang $FILENAME $COPTS -o a.o > /dev/null 2>&1
oldsha=`shasum a.o | cut -f1 -d' '`
for i in {1..100}
do
clang $FILENAME $COPTS -o b.o > /dev/null 2>&1
newsha=`shasum b.o | cut -f1 -d' '`
if [[ "$oldsha" != "$newsha" ]]
then
   echo "difference found"
   llvm-bcanalyzer --dump a.o > a
   llvm-bcanalyzer --dump b.o > b
   diff -u a b
   exit 1
fi
done

Which shows a difference in metadata

@@ -309,8 +309,8 @@
       <BASIC_TYPE op0=0 op1=36 op2=83 op3=8 op4=0 op5=6 op6=0/>
       <DERIVED_TYPE op0=0 op1=13 op2=82 op3=35 op4=18 op5=104 op6=153 op7=8 op8=0 op9=64 op10=0 op11=0 op12=0 op13=0/>
       <NODE op0=151 op1=152 op2=154/>
-      <EXPRESSION op0=6 op1=4101 op2=0 op3=4101 op4=1 op5=4097 op6=32 op7=7 op8=4097 op9=64 op10=7 op11=33 op12=159/>
       <EXPRESSION op0=6 op1=4101 op2=0 op3=4097 op4=32 op5=7 op6=4097 op7=64 op8=7 op9=16 op10=32 op11=36 op12=4101 op13=1 op14=4097 op15=32 op16=7 op17=4097 op18=64 op19=7 op20=33 op21=159/>
+      <EXPRESSION op0=6 op1=4101 op2=0 op3=4101 op4=1 op5=4097 op6=32 op7=7 op8=4097 op9=64 op10=7 op11=33 op12=159/>
       <EXPRESSION op0=6 op1=4096 op2=0 op3=32/>
       <EXPRESSION op0=6 op1=4101 op2=0 op3=4097 op4=32 op5=7 op6=4097 op7=64 op8=7 op9=16 op10=32 op11=36 op12=4101 op13=1 op14=16 op15=4294967295 op16=26 op17=33 op18=159/>
       <EXPRESSION op0=6 op1=16 op2=4294967295 op3=26 op4=16 op5=21474836480 op6=33 op7=159/>
@@ -326,8 +326,8 @@
       <VALUE op0=1 op1=27/>
       <VALUE op0=2 op1=28/>
       <VALUE op0=2 op1=30/>
-      <ARG_LIST op0=88 op1=88/>
       <ARG_LIST op0=89 op1=88/>
+      <ARG_LIST op0=88 op1=88/>
       <ARG_LIST op0=169 op1=21/>
       <ARG_LIST op0=170 op1=21/>
       <ARG_LIST op0=169 op1=91/>
@@ -370,7 +370,7 @@
     <DEBUG_LOC_AGAIN/>
     <INST_CALL op0=0 op1=32768 op2=9 op3=21 op4=4294967235 op5=4294967214 op6=4294967288/>
     <DEBUG_LOC op0=0 op1=0 op2=94 op3=0 op4=0/>
-    <INST_CALL op0=0 op1=32768 op2=9 op3=21 op4=4294967150 op5=4294967179 op6=4294967165/>
+    <INST_CALL op0=0 op1=32768 op2=9 op3=21 op4=4294967151 op5=4294967179 op6=4294967165/>
     <DEBUG_LOC op0=0 op1=0 op2=105 op3=106 op4=0/>
     <INST_CALL op0=0 op1=32768 op2=9 op3=21 op4=4294967235 op5=4294967179 op6=4294967164/>
     <DEBUG_LOC_AGAIN/>
@@ -386,7 +386,7 @@
     <DEBUG_LOC_AGAIN/>
     <INST_CALL op0=0 op1=32768 op2=9 op3=22 op4=4294967155 op5=4294967186 op6=4294967184/>
     <DEBUG_LOC_AGAIN/>
-    <INST_CALL op0=0 op1=32768 op2=9 op3=22 op4=4294967150 op5=4294967180 op6=4294967168/>
+    <INST_CALL op0=0 op1=32768 op2=9 op3=22 op4=4294967150 op5=4294967180 op6=4294967169/>
     <DEBUG_LOC op0=0 op1=0 op2=105 op3=108 op4=0/>
     <INST_CALL op0=0 op1=32768 op2=9 op3=22 op4=4294967239 op5=4294967183 op6=4294967289/>
     <DEBUG_LOC_AGAIN/>
@@ -444,7 +444,7 @@

Bisecting, this change in behaviour was introduced here

commit e0039b8d6a5bd05e70203962f448569f2d2ef1c2
Author: Kazu Hirata <kazu@google.com>
Date:   Sat Jun 4 22:48:32 2022 -0700

    Use llvm::less_second (NFC)

Specifically the change in Metadata.cpp

diff --git a/llvm/lib/IR/Metadata.cpp b/llvm/lib/IR/Metadata.cpp
index b5ea17f77914..55db2d22dcae 100644
--- a/llvm/lib/IR/Metadata.cpp
+++ b/llvm/lib/IR/Metadata.cpp
@@ -282,9 +282,7 @@ void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) {
   // Copy out uses since UseMap will get touched below.
   using UseTy = std::pair<void *, std::pair<OwnerTy, uint64_t>>;
   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
-  llvm::sort(Uses, [](const UseTy &L, const UseTy &R) {
-    return L.second.second < R.second.second;
-  });
+  llvm::sort(Uses, llvm::less_second());
   for (const auto &Pair : Uses) {
     // Check that this Ref hasn't disappeared after RAUW (when updating a
     // previous Ref).

Reverting the change to the previous comparison of L.second.second < R.second.second fixes the issue of non-determinism.

This was with Clang version 17.0.0 (https://github.com/llvm/llvm-project.git 41a1415)

[OCHyams]

cc @kazutakahirata (patch author)