[UseListOrder] Fix use list order for function operands

[nikic]

Summary

Functions can have a personality function, as well as prefix and prologue data as additional operands. Unused operands are assigned a dummy value of i1* null. This patch addresses multiple issues in use-list order preservation for these:

• Fix verify-uselistorder to also enumerate the dummy values. This means that now use-list order values of these values are shuffled even if there is no other mention of i1* null in the module. This results in failures of Assembler/call-arg-is-callee.ll, Assembler/opaque-ptr.ll (how I got here...) and Bitcode/use-list-order2.ll
• The use-list order prediction in ValueEnumerator does not take into account the fact that a global may use a value more than once and leaves uses in the same global effectively unordered. We should be comparison the operand number here, as we do for the more general case.
• While we enumerate all operands of a function together (which seems sensible to me), the bitcode reader would resolve first prefix data for all function, then prologue data for all functions, then personality functions for all functions. Change this to resolve all operands for a given function together instead.

[dexonsmith]

LGTM, thanks for cleaning this up.

If there's an isolated test you can add to more consistently reproduce the problems addressed here that'd be great.

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

class BitcodeReader : public BitcodeReaderBase, public GVMaterializer {
   DenseMap<Function *, FunctionType *> FunctionTypes;
   BitcodeReaderValueList ValueList;
   Optional<MetadataLoader> MDLoader;
   std::vector<Comdat *> ComdatList;
   SmallVector<Instruction *, 64> InstructionList;
 
   std::vector<std::pair<GlobalVariable *, unsigned>> GlobalInits;
   std::vector<std::pair<GlobalIndirectSymbol *, unsigned>> IndirectSymbolInits;
-  std::vector<std::pair<Function *, unsigned>> FunctionPrefixes;
-  std::vector<std::pair<Function *, unsigned>> FunctionPrologues;
-  std::vector<std::pair<Function *, unsigned>> FunctionPersonalityFns;
+
+  struct FunctionOperandInfo {
+    Function *F;
+    unsigned PersonalityFn;
+    unsigned Prefix;
+    unsigned Prologue;
+  };
+  std::vector<FunctionOperandInfo> FunctionOperands;
 
   /// The set of attributes by index.  Index zero in the file is for null, and
   /// is thus not represented here.  As such all indices are off by one.
   std::vector<AttributeList> MAttributes;
 
   /// The set of attribute groups.
   std::map<unsigned, AttributeList> MAttributeGroups;
 
uint64_t BitcodeReader::decodeSignRotatedValue(uint64_t V) {
   return 1ULL << 63;
 }
 
 /// Resolve all of the initializers for global values and aliases that we can.
 Error BitcodeReader::resolveGlobalAndIndirectSymbolInits() {
   std::vector<std::pair<GlobalVariable *, unsigned>> GlobalInitWorklist;
   std::vector<std::pair<GlobalIndirectSymbol *, unsigned>>
       IndirectSymbolInitWorklist;
-  std::vector<std::pair<Function *, unsigned>> FunctionPrefixWorklist;
-  std::vector<std::pair<Function *, unsigned>> FunctionPrologueWorklist;
-  std::vector<std::pair<Function *, unsigned>> FunctionPersonalityFnWorklist;
+  std::vector<FunctionOperandInfo> FunctionOperandWorklist;
 
   GlobalInitWorklist.swap(GlobalInits);
   IndirectSymbolInitWorklist.swap(IndirectSymbolInits);
-  FunctionPrefixWorklist.swap(FunctionPrefixes);
-  FunctionPrologueWorklist.swap(FunctionPrologues);
-  FunctionPersonalityFnWorklist.swap(FunctionPersonalityFns);
+  FunctionOperandWorklist.swap(FunctionOperands);
 
   while (!GlobalInitWorklist.empty()) {
     unsigned ValID = GlobalInitWorklist.back().second;
     if (ValID >= ValueList.size()) {
       // Not ready to resolve this yet, it requires something later in the file.
       GlobalInits.push_back(GlobalInitWorklist.back());
     } else {
       if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
if (ValID >= ValueList.size()) {
       GlobalIndirectSymbol *GIS = IndirectSymbolInitWorklist.back().first;
       if (isa<GlobalAlias>(GIS) && C->getType() != GIS->getType())
         return error("Alias and aliasee types don't match");
       GIS->setIndirectSymbol(C);
     }
     IndirectSymbolInitWorklist.pop_back();
   }
 
-  while (!FunctionPrefixWorklist.empty()) {
-    unsigned ValID = FunctionPrefixWorklist.back().second;
-    if (ValID >= ValueList.size()) {
-      FunctionPrefixes.push_back(FunctionPrefixWorklist.back());
-    } else {
+  while (!FunctionOperandWorklist.empty()) {
+    FunctionOperandInfo &Info = FunctionOperandWorklist.back();
+    if (Info.PersonalityFn) {
+      unsigned ValID = Info.PersonalityFn - 1;
+      if (ValID < ValueList.size()) {
         if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
-        FunctionPrefixWorklist.back().first->setPrefixData(C);
+          Info.F->setPersonalityFn(C);
         else
           return error("Expected a constant");
+        Info.PersonalityFn = 0;
       }
-    FunctionPrefixWorklist.pop_back();
     }
-
-  while (!FunctionPrologueWorklist.empty()) {
-    unsigned ValID = FunctionPrologueWorklist.back().second;
-    if (ValID >= ValueList.size()) {
-      FunctionPrologues.push_back(FunctionPrologueWorklist.back());
-    } else {
+    if (Info.Prefix) {
+      unsigned ValID = Info.Prefix - 1;
+      if (ValID < ValueList.size()) {
         if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
-        FunctionPrologueWorklist.back().first->setPrologueData(C);
+          Info.F->setPrefixData(C);
         else
           return error("Expected a constant");
+        Info.Prefix = 0;
       }
-    FunctionPrologueWorklist.pop_back();
     }
-
-  while (!FunctionPersonalityFnWorklist.empty()) {
-    unsigned ValID = FunctionPersonalityFnWorklist.back().second;
-    if (ValID >= ValueList.size()) {
-      FunctionPersonalityFns.push_back(FunctionPersonalityFnWorklist.back());
-    } else {
+    if (Info.Prologue) {
+      unsigned ValID = Info.Prologue - 1;
+      if (ValID < ValueList.size()) {
         if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
-        FunctionPersonalityFnWorklist.back().first->setPersonalityFn(C);
+          Info.F->setPrologueData(C);
         else
           return error("Expected a constant");
+        Info.Prologue = 0;
+      }
     }
-    FunctionPersonalityFnWorklist.pop_back();
+    if (Info.PersonalityFn || Info.Prefix || Info.Prologue)
+      FunctionOperands.push_back(Info);
+    FunctionOperandWorklist.pop_back();
   }
 
   return Error::success();
 }
 
 APInt llvm::readWideAPInt(ArrayRef<uint64_t> Vals, unsigned TypeBits) {
   SmallVector<uint64_t, 8> Words(Vals.size());
   transform(Vals, Words.begin(),
if (Record.size() > 8 && Record[8]) {
     if (Record[8] - 1 >= GCTable.size())
       return error("Invalid ID");
     Func->setGC(GCTable[Record[8] - 1]);
   }
   GlobalValue::UnnamedAddr UnnamedAddr = GlobalValue::UnnamedAddr::None;
   if (Record.size() > 9)
     UnnamedAddr = getDecodedUnnamedAddrType(Record[9]);
   Func->setUnnamedAddr(UnnamedAddr);
-  if (Record.size() > 10 && Record[10] != 0)
-    FunctionPrologues.push_back(std::make_pair(Func, Record[10] - 1));
+
+  FunctionOperandInfo OperandInfo = {Func, 0, 0, 0};
+  if (Record.size() > 10)
+    OperandInfo.Prologue = Record[10];
 
   if (Record.size() > 11)
     Func->setDLLStorageClass(getDecodedDLLStorageClass(Record[11]));
   else
     upgradeDLLImportExportLinkage(Func, RawLinkage);
 
   if (Record.size() > 12) {
     if (unsigned ComdatID = Record[12]) {
       if (ComdatID > ComdatList.size())
         return error("Invalid function comdat ID");
       Func->setComdat(ComdatList[ComdatID - 1]);
     }
   } else if (hasImplicitComdat(RawLinkage)) {
     Func->setComdat(reinterpret_cast<Comdat *>(1));
   }
 
-  if (Record.size() > 13 && Record[13] != 0)
-    FunctionPrefixes.push_back(std::make_pair(Func, Record[13] - 1));
+  if (Record.size() > 13)
+    OperandInfo.Prefix = Record[13];
 
-  if (Record.size() > 14 && Record[14] != 0)
-    FunctionPersonalityFns.push_back(std::make_pair(Func, Record[14] - 1));
+  if (Record.size() > 14)
+    OperandInfo.PersonalityFn = Record[14];
 
   if (Record.size() > 15) {
     Func->setDSOLocal(getDecodedDSOLocal(Record[15]));
   }
   inferDSOLocal(Func);
 
   // Record[16] is the address space number.
 
   // Check whether we have enough values to read a partition name. Also make
   // sure Strtab has enough values.
   if (Record.size() > 18 && Strtab.data() &&
       Record[17] + Record[18] <= Strtab.size()) {
     Func->setPartition(StringRef(Strtab.data() + Record[17], Record[18]));
   }
 
   ValueList.push_back(Func);
 
+  if (OperandInfo.PersonalityFn || OperandInfo.Prefix || OperandInfo.Prologue)
+    FunctionOperands.push_back(OperandInfo);
+
   // If this is a function with a body, remember the prototype we are
   // creating now, so that we can match up the body with them later.
   if (!isProto) {
     Func->setIsMaterializable(true);
     FunctionsWithBodies.push_back(Func);
     DeferredFunctionInfo[Func] = 0;
   }
   return Error::success();

llvm/lib/Bitcode/Writer/ValueEnumerator.cpp

llvm::sort(List, [&](const Entry &L, const Entry &R) {
     auto RID = OM.lookup(RU->getUser()).first;
 
     // Global values are processed in reverse order.
     //
     // Moreover, initializers of GlobalValues are set *after* all the globals
     // have been read (despite having earlier IDs).  Rather than awkwardly
     // modeling this behaviour here, orderModule() has assigned IDs to
     // initializers of GlobalValues before GlobalValues themselves.
-    if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID))
+    if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID)) {
+      if (LID == RID)
+        return LU->getOperandNo() > RU->getOperandNo();
       return LID < RID;
+    }
 
     // If ID is 4, then expect: 7 6 5 1 2 3.
     if (LID < RID) {
       if (RID <= ID)
         if (!IsGlobalValue) // GlobalValue uses don't get reversed.
           return true;
       return false;
     }

llvm/test/Assembler/function-operand-uselistorder.ll

+; RUN: verify-uselistorder %s
+
+@g = global i8 0
+
+define void @f1() prefix i8* @g prologue i8* @g personality i8* @g {
+  ret void
+}
+
+define void @f2() prefix i8* @g prologue i8* @g personality i8* @g {
+  ret void
+}

llvm/tools/verify-uselistorder/verify-uselistorder.cpp

ValueMapping::ValueMapping(const Module &M) {
   // Constants used by globals.
   for (const GlobalVariable &G : M.globals())
     if (G.hasInitializer())
       map(G.getInitializer());
   for (const GlobalAlias &A : M.aliases())
     map(A.getAliasee());
   for (const GlobalIFunc &IF : M.ifuncs())
     map(IF.getResolver());
-  for (const Function &F : M) {
-    if (F.hasPrefixData())
-      map(F.getPrefixData());
-    if (F.hasPrologueData())
-      map(F.getPrologueData());
-    if (F.hasPersonalityFn())
-      map(F.getPersonalityFn());
-  }
+  for (const Function &F : M)
+    for (Value *Op : F.operands())
+      map(Op);
 
   // Function bodies.
   for (const Function &F : M) {
     for (const Argument &A : F.args())
       map(&A);
     for (const BasicBlock &BB : F)
       map(&BB);
     for (const BasicBlock &BB : F)
static void changeUseLists(Module &M, Changer changeValueUseList) {
   // Constants used by globals.
   for (GlobalVariable &G : M.globals())
     if (G.hasInitializer())
       changeValueUseList(G.getInitializer());
   for (GlobalAlias &A : M.aliases())
     changeValueUseList(A.getAliasee());
   for (GlobalIFunc &IF : M.ifuncs())
     changeValueUseList(IF.getResolver());
-  for (Function &F : M) {
-    if (F.hasPrefixData())
-      changeValueUseList(F.getPrefixData());
-    if (F.hasPrologueData())
-      changeValueUseList(F.getPrologueData());
-    if (F.hasPersonalityFn())
-      changeValueUseList(F.getPersonalityFn());
-  }
+  for (Function &F : M)
+    for (Value *Op : F.operands())
+      changeValueUseList(Op);
 
   // Function bodies.
   for (Function &F : M) {
     for (Argument &A : F.args())
       changeValueUseList(&A);
     for (BasicBlock &BB : F)
       changeValueUseList(&BB);
     for (BasicBlock &BB : F)