LowerTypeTests: Fix non-determinism in code that handles icall branch funnels.

[pcc]

Summary

This was exposed by enabling expensive checks, which causes llvm::sort to sort randomly.

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

public:
   ArrayRef<MDNode *> types() const {
     return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes);
   }
 };
 
 struct ICallBranchFunnel final
     : TrailingObjects<ICallBranchFunnel, GlobalTypeMember *> {
   static ICallBranchFunnel *create(BumpPtrAllocator &Alloc, CallInst *CI,
-                                   ArrayRef<GlobalTypeMember *> Targets) {
+                                   ArrayRef<GlobalTypeMember *> Targets,
+                                   unsigned UniqueId) {
     auto *Call = static_cast<ICallBranchFunnel *>(
         Alloc.Allocate(totalSizeToAlloc<GlobalTypeMember *>(Targets.size()),
                        alignof(ICallBranchFunnel)));
     Call->CI = CI;
+    Call->UniqueId = UniqueId;
     Call->NTargets = Targets.size();
     std::uninitialized_copy(Targets.begin(), Targets.end(),
                             Call->getTrailingObjects<GlobalTypeMember *>());
     return Call;
   }
 
   CallInst *CI;
   ArrayRef<GlobalTypeMember *> targets() const {
     return makeArrayRef(getTrailingObjects<GlobalTypeMember *>(), NTargets);
   }
 
+  unsigned UniqueId;
+
 private:
   size_t NTargets;
 };
 
 class LowerTypeTestsModule {
   Module &M;
 
   ModuleSummaryIndex *ExportSummary;
bool LowerTypeTestsModule::lower() {
   // efficiently enumerate the type identifiers associated with a global:
   // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
   // of associated type metadata) and a mapping from type identifiers to their
   // list of GlobalTypeMembers and last observed index in the list of globals.
   // The indices will be used later to deterministically order the list of type
   // identifiers.
   BumpPtrAllocator Alloc;
   struct TIInfo {
-    unsigned Index;
+    unsigned UniqueId;
     std::vector<GlobalTypeMember *> RefGlobals;
   };
   DenseMap<Metadata *, TIInfo> TypeIdInfo;
-  unsigned I = 0;
+  unsigned CurUniqueId = 0;
   SmallVector<MDNode *, 2> Types;
 
   struct ExportedFunctionInfo {
     CfiFunctionLinkage Linkage;
     MDNode *FuncMD; // {name, linkage, type[, type...]}
   };
   DenseMap<StringRef, ExportedFunctionInfo> ExportedFunctions;
   if (ExportSummary) {
for (GlobalObject &GO : M.global_objects()) {
     }
 
     auto *GTM =
         GlobalTypeMember::create(Alloc, &GO, IsDefinition, IsExported, Types);
     GlobalTypeMembers[&GO] = GTM;
     for (MDNode *Type : Types) {
       verifyTypeMDNode(&GO, Type);
       auto &Info = TypeIdInfo[Type->getOperand(1)];
-      Info.Index = ++I;
+      Info.UniqueId = ++CurUniqueId;
       Info.RefGlobals.push_back(GTM);
     }
   }
 
   auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & {
     // Add the call site to the list of call sites for this type identifier. We
     // also use TypeIdUsers to keep track of whether we have seen this type
     // identifier before. If we have, we don't need to re-add the referenced
for (const Use &U : ICallBranchFunnelFunc->uses()) {
             GlobalClasses.findLeader(GlobalClasses.insert(GTM));
         if (I == 1)
           CurSet = NewSet;
         else
           CurSet = GlobalClasses.unionSets(CurSet, NewSet);
       }
 
       GlobalClasses.unionSets(
-          CurSet, GlobalClasses.findLeader(GlobalClasses.insert(
-                      ICallBranchFunnel::create(Alloc, CI, Targets))));
+          CurSet, GlobalClasses.findLeader(
+                      GlobalClasses.insert(ICallBranchFunnel::create(
+                          Alloc, CI, Targets, ++CurUniqueId))));
     }
   }
 
   if (ExportSummary) {
     DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
     for (auto &P : TypeIdInfo) {
       if (auto *TypeId = dyn_cast<MDString>(P.first))
         MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
bool LowerTypeTestsModule::lower() {
   std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
   for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
                                  E = GlobalClasses.end();
        I != E; ++I) {
     if (!I->isLeader())
       continue;
     ++NumTypeIdDisjointSets;
 
-    unsigned MaxIndex = 0;
+    unsigned MaxUniqueId = 0;
     for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
          MI != GlobalClasses.member_end(); ++MI) {
-      if ((*MI).is<Metadata *>())
-        MaxIndex = std::max(MaxIndex, TypeIdInfo[MI->get<Metadata *>()].Index);
+      if (auto *MD = MI->dyn_cast<Metadata *>())
+        MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId);
+      else if (auto *BF = MI->dyn_cast<ICallBranchFunnel *>())
+        MaxUniqueId = std::max(MaxUniqueId, BF->UniqueId);
     }
-    Sets.emplace_back(I, MaxIndex);
+    Sets.emplace_back(I, MaxUniqueId);
   }
   llvm::sort(Sets.begin(), Sets.end(),
              [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1,
                 const std::pair<GlobalClassesTy::iterator, unsigned> &S2) {
                return S1.second < S2.second;
              });
 
   // For each disjoint set we found...
   for (const auto &S : Sets) {
     // Build the list of type identifiers in this disjoint set.
     std::vector<Metadata *> TypeIds;
     std::vector<GlobalTypeMember *> Globals;
     std::vector<ICallBranchFunnel *> ICallBranchFunnels;
     for (GlobalClassesTy::member_iterator MI =
              GlobalClasses.member_begin(S.first);
          MI != GlobalClasses.member_end(); ++MI) {
       if (MI->is<Metadata *>())
         TypeIds.push_back(MI->get<Metadata *>());
       else if (MI->is<GlobalTypeMember *>())
         Globals.push_back(MI->get<GlobalTypeMember *>());
       else
         ICallBranchFunnels.push_back(MI->get<ICallBranchFunnel *>());
     }
 
-    // Order type identifiers by global index for determinism. This ordering is
-    // stable as there is a one-to-one mapping between metadata and indices.
+    // Order type identifiers by unique ID for determinism. This ordering is
+    // stable as there is a one-to-one mapping between metadata and unique IDs.
     llvm::sort(TypeIds.begin(), TypeIds.end(), [&](Metadata *M1, Metadata *M2) {
-      return TypeIdInfo[M1].Index < TypeIdInfo[M2].Index;
+      return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId;
+    });
+
+    // Same for the branch funnels.
+    llvm::sort(ICallBranchFunnels.begin(), ICallBranchFunnels.end(),
+               [&](ICallBranchFunnel *F1, ICallBranchFunnel *F2) {
+                 return F1->UniqueId < F2->UniqueId;
                });
 
     // Build bitsets for this disjoint set.
     buildBitSetsFromDisjointSet(TypeIds, Globals, ICallBranchFunnels);
   }
 
   allocateByteArrays();
 
   // Parse alias data to replace stand-in function declarations for aliases