[AsmWriter] Properly handle uselistorder for global symbols

[nikic]

Summary

Currently, AsmWriter will stick uselistorder directives for global values inside individual functions. This doesn't make a lot of sense, and interacts badly with D104950, as use list order adjustments will be performed while still working on a forward reference.

This patch instead always prints uselistorder directives for globals at the module level. This isn't really compatible with the previously used implementation approach. Rather than walking through all values again, use the OrderMap (after stabilizing its order) to go through all values and compute the use list shuffles for them. Classify them per-function, or nullptr for globals.

Even independently of D104950, this seems to fix a few verify-uselistorder failures. Conveniently, there is even a pre-existing failing test that this fixes.

[dexonsmith]

Thanks! This is a nice approach; LGTM with a couple of minor nits.

Currently, AsmWriter will stick uselistorder directives for global values inside individual functions.

FWIW (not much I think), I vaguely remember a desire (mine? reviewers?) to avoid top-level uselistorder directives... but I guess at some point the dam broke. This is easier to reason about.

llvm/lib/IR/AsmWriter.cpp

241

Nit: this could be inverted with a continue to reduce nesting.

244

Nit: this could inverted with a continue to reduce nesting.

llvm/test/Bitcode/use-list-order2.ll

2

Looks like this was disabled to "fix" PR24755, which was introduced by the refactor of Function operands... a bit unfortunate for the test to have been turned off instead of reverting the patch that broke it (this approach seems to defeat the point of adding tests?)...

[aeubanks]

perhaps I'm reading this wrong, but could we add a test for a global that previously had its uselistorder written in a function but is now written at the module level?

[nikic]

Address style suggestions.

[dexonsmith]

In D104976#2845353, @aeubanks wrote:

perhaps I'm reading this wrong, but could we add a test for a global that previously had its uselistorder written in a function but is now written at the module level?

Yeah, that seems like a good idea.

[nikic]

Add additional test. I'm not sure if this is what you had in mind. This test shows how the previous representation that stores info in individual functions gets converted into the module level form now.

[dexonsmith]

llvm/test/Assembler/uselistorder_global.ll

1 ↗

(On Diff #355023)

Might as well add a RUN: verify-uselistorder %s?

4 ↗

(On Diff #355023)

My thought was that this would check that uselistorder is emitted in the "right" place:

// Check that global uselistorders are emitted at the top-level.
CHECK: define void @func1() {
CHECK: }
CHECK: define void @func2() {
CHECK: }
CHECK: uselistorder @g, {3, 2, 0, 1}

Probably not important to test that we can parse the directives in the "old" place. You could probably start with exact textual IR you want to see pop out the other side.

@aeubanks , WDYT?

[aeubanks]

llvm/test/Assembler/uselistorder_global.ll

4 ↗

(On Diff #355023)

yeah, that's exactly what I was thinking

[aeubanks]

otherwise lgtm

[nikic]

Update test. Does this match what you had in mind?

[dexonsmith]

In D104976#2845464, @nikic wrote:

Update test. Does this match what you had in mind?

LGTM.

[aeubanks]

lgtm
should BitcodeWriter also be updated?

[dexonsmith]

In D104976#2845503, @aeubanks wrote:

lgtm
should BitcodeWriter also be updated?

I think if verify-uselistorder is passing on the use-list-order2.ll test, then the bitcode part is already working.

[dexonsmith]

In D104976#2845294, @dexonsmith wrote:

Currently, AsmWriter will stick uselistorder directives for global values inside individual functions.

FWIW (not much I think), I vaguely remember a desire (mine? reviewers?) to avoid top-level uselistorder directives... but I guess at some point the dam broke. This is easier to reason about.

In case you're interested, more of the history just paged itself in for me. IIRC, an early design for this directive named the users directly, requiring a directive in each function that had locals that used a global value. The final design, as you've seen, uses a shuffle vector based on predicting the "natural" order in the reader. This can live quite happily at the global scope (as you've done in this patch).

llvm/lib/IR/AsmWriter.cpp

 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ModuleSlotTracker.h"
 #include "llvm/IR/ModuleSummaryIndex.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/TypeFinder.h"
 #include "llvm/IR/Use.h"
-#include "llvm/IR/UseListOrder.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"

 
 // Make virtual table appear in this compilation unit.
 AssemblyAnnotationWriter::~AssemblyAnnotationWriter() = default;
 
 //===----------------------------------------------------------------------===//
 // Helper Functions
 //===----------------------------------------------------------------------===//
 
-namespace {
-
-struct OrderMap {
-  DenseMap<const Value *, std::pair<unsigned, bool>> IDs;
-
-  unsigned size() const { return IDs.size(); }
-  std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; }
-
-  std::pair<unsigned, bool> lookup(const Value *V) const {
-    return IDs.lookup(V);
-  }
+using OrderMap = MapVector<const Value *, unsigned>;
 
-  void index(const Value *V) {
-    // Explicitly sequence get-size and insert-value operations to avoid UB.
-    unsigned ID = IDs.size() + 1;
-    IDs[V].first = ID;
-  }
-};
-
-} // end anonymous namespace
+using UseListOrderMap =
+    DenseMap<const Function *, MapVector<const Value *, std::vector<unsigned>>>;
 
 /// Look for a value that might be wrapped as metadata, e.g. a value in a
 /// metadata operand. Returns the input value as-is if it is not wrapped.
 static const Value *skipMetadataWrapper(const Value *V) {
   if (const auto *MAV = dyn_cast<MetadataAsValue>(V))
     if (const auto *VAM = dyn_cast<ValueAsMetadata>(MAV->getMetadata()))
       return VAM->getValue();
   return V;
 }
 
 static void orderValue(const Value *V, OrderMap &OM) {
-  if (OM.lookup(V).first)
+  if (OM.lookup(V))
     return;
 
   if (const Constant *C = dyn_cast<Constant>(V))
     if (C->getNumOperands() && !isa<GlobalValue>(C))
       for (const Value *Op : C->operands())
         if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
           orderValue(Op, OM);
 
   // Note: we cannot cache this lookup above, since inserting into the map
   // changes the map's size, and thus affects the other IDs.
-  OM.index(V);
+  unsigned ID = OM.size() + 1;
+  OM[V] = ID;
 }
 
 static OrderMap orderModule(const Module *M) {
   OrderMap OM;
 
   for (const GlobalVariable &G : M->globals()) {
     if (G.hasInitializer())
       if (!isa<GlobalValue>(G.getInitializer()))
for (const BasicBlock &BB : F) {
         }
         orderValue(&I, OM);
       }
     }
   }
   return OM;
 }
 
-static void predictValueUseListOrderImpl(const Value *V, const Function *F,
-                                         unsigned ID, const OrderMap &OM,
-                                         UseListOrderStack &Stack) {
+static std::vector<unsigned> predictValueUseListOrder(
+    const Value *V, unsigned ID, const OrderMap &OM) {
   // Predict use-list order for this one.
   using Entry = std::pair<const Use *, unsigned>;
   SmallVector<Entry, 64> List;
   for (const Use &U : V->uses())
     // Check if this user will be serialized.
-    if (OM.lookup(U.getUser()).first)
+    if (OM.lookup(U.getUser()))
       List.push_back(std::make_pair(&U, List.size()));
 
   if (List.size() < 2)
     // We may have lost some users.
-    return;
+    return {};
 
   bool GetsReversed =
       !isa<GlobalVariable>(V) && !isa<Function>(V) && !isa<BasicBlock>(V);
   if (auto *BA = dyn_cast<BlockAddress>(V))
-    ID = OM.lookup(BA->getBasicBlock()).first;
+    ID = OM.lookup(BA->getBasicBlock());
   llvm::sort(List, [&](const Entry &L, const Entry &R) {
     const Use *LU = L.first;
     const Use *RU = R.first;
     if (LU == RU)
       return false;
 
-    auto LID = OM.lookup(LU->getUser()).first;
-    auto RID = OM.lookup(RU->getUser()).first;
+    auto LID = OM.lookup(LU->getUser());
+    auto RID = OM.lookup(RU->getUser());
 
     // If ID is 4, then expect: 7 6 5 1 2 3.
     if (LID < RID) {
       if (GetsReversed)
         if (RID <= ID)
           return true;
       return false;
     }
if (GetsReversed)
         return LU->getOperandNo() < RU->getOperandNo();
     return LU->getOperandNo() > RU->getOperandNo();
   });
 
   if (llvm::is_sorted(List, [](const Entry &L, const Entry &R) {
         return L.second < R.second;
       }))
     // Order is already correct.
-    return;
+    return {};
 
   // Store the shuffle.
-  Stack.emplace_back(V, F, List.size());
-  assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
+  std::vector<unsigned> Shuffle(List.size());
   for (size_t I = 0, E = List.size(); I != E; ++I)
-    Stack.back().Shuffle[I] = List[I].second;
+    Shuffle[I] = List[I].second;
+  return Shuffle;
 }
 
-static void predictValueUseListOrder(const Value *V, const Function *F,
-                                     OrderMap &OM, UseListOrderStack &Stack) {
-  auto &IDPair = OM[V];
-  assert(IDPair.first && "Unmapped value");
-  if (IDPair.second)
-    // Already predicted.
-    return;
-
-  // Do the actual prediction.
-  IDPair.second = true;
-  if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())
-    predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);
-
-  // Recursive descent into constants.
-  if (const Constant *C = dyn_cast<Constant>(V))
-    if (C->getNumOperands()) // Visit GlobalValues.
-      for (const Value *Op : C->operands())
-        if (isa<Constant>(Op)) // Visit GlobalValues.
-          predictValueUseListOrder(Op, F, OM, Stack);
-}
-
-static UseListOrderStack predictUseListOrder(const Module *M) {
+static UseListOrderMap predictUseListOrder(const Module *M) {
   OrderMap OM = orderModule(M);
-
-  // Use-list orders need to be serialized after all the users have been added
-  // to a value, or else the shuffles will be incomplete.  Store them per
-  // function in a stack.
-  //
-  // Aside from function order, the order of values doesn't matter much here.
-  UseListOrderStack Stack;
-
-  // We want to visit the functions backward now so we can list function-local
-  // constants in the last Function they're used in.  Module-level constants
-  // have already been visited above.
-  for (const Function &F : make_range(M->rbegin(), M->rend())) {
-    if (F.isDeclaration())
-      continue;
-    for (const BasicBlock &BB : F)
-      predictValueUseListOrder(&BB, &F, OM, Stack);
-    for (const Argument &A : F.args())
-      predictValueUseListOrder(&A, &F, OM, Stack);
-    for (const BasicBlock &BB : F)
-      for (const Instruction &I : BB)
-        for (const Value *Op : I.operands()) {
-          Op = skipMetadataWrapper(Op);
-          if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
-            predictValueUseListOrder(Op, &F, OM, Stack);
-        }
-    for (const BasicBlock &BB : F)
-      for (const Instruction &I : BB)
-        predictValueUseListOrder(&I, &F, OM, Stack);
-  }
-
-  // Visit globals last.
-  for (const GlobalVariable &G : M->globals())
-    predictValueUseListOrder(&G, nullptr, OM, Stack);
-  for (const Function &F : *M)
-    predictValueUseListOrder(&F, nullptr, OM, Stack);
-  for (const GlobalAlias &A : M->aliases())
-    predictValueUseListOrder(&A, nullptr, OM, Stack);
-  for (const GlobalIFunc &I : M->ifuncs())
-    predictValueUseListOrder(&I, nullptr, OM, Stack);
-  for (const GlobalVariable &G : M->globals())
-    if (G.hasInitializer())
-      predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);
-  for (const GlobalAlias &A : M->aliases())
-    predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);
-  for (const GlobalIFunc &I : M->ifuncs())
-    predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack);
-  for (const Function &F : *M)
-    for (const Use &U : F.operands())
-      predictValueUseListOrder(U.get(), nullptr, OM, Stack);
-
-  return Stack;
+  UseListOrderMap ULOM;
+  for (const auto &Pair : OM) {
+    const Value *V = Pair.first;
+    if (!V->use_empty() && std::next(V->use_begin()) != V->use_end()) {
+      std::vector<unsigned> Shuffle =
+          predictValueUseListOrder(V, Pair.second, OM);
+      if (!Shuffle.empty()) {
+        const Function *F = nullptr;
+        if (auto *I = dyn_cast<Instruction>(V))
+          F = I->getFunction();
+        if (auto *A = dyn_cast<Argument>(V))
+          F = A->getParent();
+        if (auto *BB = dyn_cast<BasicBlock>(V))
+          F = BB->getParent();
+        ULOM[F][V] = std::move(Shuffle);
+    }
+  }
+  return ULOM;
 }
 
 static const Module *getModuleFromVal(const Value *V) {
   if (const Argument *MA = dyn_cast<Argument>(V))
     return MA->getParent() ? MA->getParent()->getParent() : nullptr;
 
   if (const BasicBlock *BB = dyn_cast<BasicBlock>(V))
     return BB->getParent() ? BB->getParent()->getParent() : nullptr;
class AssemblyWriter {
   const ModuleSummaryIndex *TheIndex = nullptr;
   std::unique_ptr<SlotTracker> SlotTrackerStorage;
   SlotTracker &Machine;
   TypePrinting TypePrinter;
   AssemblyAnnotationWriter *AnnotationWriter = nullptr;
   SetVector<const Comdat *> Comdats;
   bool IsForDebug;
   bool ShouldPreserveUseListOrder;
-  UseListOrderStack UseListOrders;
+  UseListOrderMap UseListOrders;
   SmallVector<StringRef, 8> MDNames;
   /// Synchronization scope names registered with LLVMContext.
   SmallVector<StringRef, 8> SSNs;
   DenseMap<const GlobalValueSummary *, GlobalValue::GUID> SummaryToGUIDMap;
 
 public:
   /// Construct an AssemblyWriter with an external SlotTracker
   AssemblyWriter(formatted_raw_ostream &o, SlotTracker &Mac, const Module *M,
public:
   void printIndirectSymbol(const GlobalIndirectSymbol *GIS);
   void printComdat(const Comdat *C);
   void printFunction(const Function *F);
   void printArgument(const Argument *FA, AttributeSet Attrs);
   void printBasicBlock(const BasicBlock *BB);
   void printInstructionLine(const Instruction &I);
   void printInstruction(const Instruction &I);
 
-  void printUseListOrder(const UseListOrder &Order);
+  void printUseListOrder(const Value *V, const std::vector<unsigned> &Shuffle);
   void printUseLists(const Function *F);
 
   void printModuleSummaryIndex();
   void printSummaryInfo(unsigned Slot, const ValueInfo &VI);
   void printSummary(const GlobalValueSummary &Summary);
   void printAliasSummary(const AliasSummary *AS);
   void printGlobalVarSummary(const GlobalVarSummary *GS);
   void printFunctionSummary(const FunctionSummary *FS);
void AssemblyWriter::printModule(const Module *M) {
   for (const GlobalAlias &GA : M->aliases())
     printIndirectSymbol(&GA);
 
   // Output all ifuncs.
   if (!M->ifunc_empty()) Out << "\n";
   for (const GlobalIFunc &GI : M->ifuncs())
     printIndirectSymbol(&GI);
 
-  // Output global use-lists.
-  printUseLists(nullptr);
-
   // Output all of the functions.
   for (const Function &F : *M) {
     Out << '\n';
     printFunction(&F);
   }
-  assert(UseListOrders.empty() && "All use-lists should have been consumed");
+
+  // Output global use-lists.
+  printUseLists(nullptr);
 
   // Output all attribute groups.
   if (!Machine.as_empty()) {
     Out << '\n';
     writeAllAttributeGroups();
   }
 
   // Output named metadata.
void AssemblyWriter::writeAllAttributeGroups() {
   for (auto &I : llvm::make_range(Machine.as_begin(), Machine.as_end()))
     asVec[I.second] = I;
 
   for (const auto &I : asVec)
     Out << "attributes #" << I.second << " = { "
         << I.first.getAsString(true) << " }\n";
 }
 
-void AssemblyWriter::printUseListOrder(const UseListOrder &Order) {
+void AssemblyWriter::printUseListOrder(const Value *V,
+                                       const std::vector<unsigned> &Shuffle) {
   bool IsInFunction = Machine.getFunction();
   if (IsInFunction)
     Out << "  ";
 
   Out << "uselistorder";
-  if (const BasicBlock *BB =
-          IsInFunction ? nullptr : dyn_cast<BasicBlock>(Order.V)) {
+  if (const BasicBlock *BB = IsInFunction ? nullptr : dyn_cast<BasicBlock>(V)) {
     Out << "_bb ";
     writeOperand(BB->getParent(), false);
     Out << ", ";
     writeOperand(BB, false);
   } else {
     Out << " ";
-    writeOperand(Order.V, true);
+    writeOperand(V, true);
   }
   Out << ", { ";
 
-  assert(Order.Shuffle.size() >= 2 && "Shuffle too small");
-  Out << Order.Shuffle[0];
-  for (unsigned I = 1, E = Order.Shuffle.size(); I != E; ++I)
-    Out << ", " << Order.Shuffle[I];
+  assert(Shuffle.size() >= 2 && "Shuffle too small");
+  Out << Shuffle[0];
+  for (unsigned I = 1, E = Shuffle.size(); I != E; ++I)
+    Out << ", " << Shuffle[I];
   Out << " }\n";
 }
 
 void AssemblyWriter::printUseLists(const Function *F) {
-  auto hasMore =
-      [&]() { return !UseListOrders.empty() && UseListOrders.back().F == F; };
-  if (!hasMore())
-    // Nothing to do.
+  auto It = UseListOrders.find(F);
+  if (It == UseListOrders.end())
     return;
 
   Out << "\n; uselistorder directives\n";
-  while (hasMore()) {
-    printUseListOrder(UseListOrders.back());
-    UseListOrders.pop_back();
-  }
+  for (const auto &Pair : It->second)
+    printUseListOrder(Pair.first, Pair.second);
 }
 
 //===----------------------------------------------------------------------===//
 //                       External Interface declarations
 //===----------------------------------------------------------------------===//
 
 void Function::print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW,
                      bool ShouldPreserveUseListOrder,

llvm/test/Bitcode/use-list-order2.ll

 ; RUN: verify-uselistorder %s
-; XFAIL: *
 
 ; Test 1
 @g1 = global i8 0
 
 declare void @llvm.donothing() nounwind readnone
 
 define void @f.no_personality1() personality i8 0 {
   invoke void @llvm.donothing() to label %normal unwind label %exception