[DebugInfo] Prevent non-determinism when updating DIArgList users of a value

[StephenTozer]

Summary

This patch fixes the most recent issue mentioned in the discussion for patch D91722, in which some builds had non-deterministic output. This bug is rooted in ReplaceableMetadataImpl::getAllArgListUsers, which returns a vector of Metadata*; this vector is built by iterating over a map, and the result is later used to modify/produce instructions. This patch uses the IDs associated with each user to ensure that the vector is deterministically ordered; there is no importance to the ordering itself, other than that it is deterministic.

[rnk]

Thanks for finding this, I think it looks good.

llvm/lib/IR/Metadata.cpp

199

This is a bit pedantic, but it seems like it could be less code to build a vector of pointers to pairs in the DenseMap, sort those pointers to pairs, and then extract the owners afterwards. Fewer new pairs with new implied meanings of .second, that sort of thing.

[StephenTozer]

llvm/lib/IR/Metadata.cpp

199

I tried implementing this, but in this case it doesn't look to make the code any less verbose or easier to read in my opinion (see below).

199–214

llvm/lib/IR/Metadata.cpp

bool MetadataTracking::retrack(void *Ref, Metadata &MD, void *New) {
   return false;
 }
 
 bool MetadataTracking::isReplaceable(const Metadata &MD) {
   return ReplaceableMetadataImpl::isReplaceable(MD);
 }
 
 SmallVector<Metadata *, 4> ReplaceableMetadataImpl::getAllArgListUsers() {
-  SmallVector<Metadata *, 4> MDUsers;
+  SmallVector<std::pair<OwnerTy, uint64_t> *> MDUsersWithID;
   for (auto Pair : UseMap) {
     OwnerTy Owner = Pair.second.first;
     if (!Owner.is<Metadata *>())
       continue;
     Metadata *OwnerMD = Owner.get<Metadata *>();
     if (OwnerMD->getMetadataID() == Metadata::DIArgListKind)
-      MDUsers.push_back(OwnerMD);
+      MDUsersWithID.push_back(&UseMap[Pair.first]);
   }
+  llvm::sort(MDUsersWithID, [](auto UserA, auto UserB) {
+    return UserA->second < UserB->second;
+  });
+  SmallVector<Metadata *> MDUsers;
+  for (auto UserWithID : MDUsersWithID)
+    MDUsers.push_back(UserWithID->first.get<Metadata *>());
   return MDUsers;
 }
 
 void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) {
   bool WasInserted =
       UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex)))
           .second;
   (void)WasInserted;
   assert(WasInserted && "Expected to add a reference");