Use a stable topological sort instead of std::stable_sort in DIE *DwarfCompileUnit::createScopeChildrenDIE()

[aprantl]

Summary

This addresses review feedback for D42940. The new code is somewhat more heavyweight, but it can now also detect cycles in the dependencies and actually works correctly.

[aprantl]

Initialize the DenseSets with the size of Input.

[vsapsai]

Sorting algorithm looks correct to me and in debugger it works as expected. I don't think we are going to visit DbgVariable more than 3 times so time complexity is reasonable too.

There is a problem with SmallDenseSet size and other than that maybe improve testing? Some of the ideas: make variables in order "array, unrelated, vla_expr" to expose problem with std::stable_sort; have dependencies that aren't local variables (this can be already covered by other tests); have more than 8 local variables that is not a power of 2.

lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

589

Parameter can be const and the line is > 80 characters.

595

It worked on the reduced test case but for a bigger file it failed with

Assertion failed: ((getNumBuckets() & (getNumBuckets()-1)) == 0 && "# initial buckets must be a power of two!"), function initEmpty, file llvm/include/llvm/ADT/DenseMap.h, line 344.

That happened for the Input of size 10.

596

You have a few comments inside the function that start with triple slash. Is this on purpose? Not saying it is wrong, but I would use just 2 slashes inside the function, so maybe it is a chance for me to learn something new.

605

I am unfamiliar with this code so I can be completely wrong. For me, subjectively, N strongly indicates it is a number but in this case it is not. So I need to keep in mind that N is of type DbgVariable. It get's especially confusing when it is next to actual number like {N, 1}. To avoid criticizing without offering alternatives, personally, I would prefer Var and later for dependencies maybe to use LocalVar.

It is a personal readability opinion, it's up to you to decide how well it actually works.

637

What would happen and if it is even possible if Dependency is not a local variable?

And in this case dyn_cast<> should be enough, we don't add nullptr dependencies.

[aprantl]

In D43036#1001124, @vsapsai wrote:

Sorting algorithm looks correct to me and in debugger it works as expected. I don't think we are going to visit DbgVariable more than 3 times so time complexity is reasonable too.

There is a problem with SmallDenseSet size and other than that maybe improve testing? Some of the ideas: make variables in order "array, unrelated, vla_expr" to expose problem with std::stable_sort; have dependencies that aren't local variables (this can be already covered by other tests); have more than 8 local variables that is not a power of 2.

This really difficult because we can only very indirectly influence the order in which variables appear in the LexcicalScopes data structure from LLVM IR input. But I'll try!

[aprantl]

Address most review feedback, still need to come up with a better testcase.

[aprantl]

Added a bunch of interesting test cases, including the one with a global variable as dependency.
Note that none of these testcases trigger a crash in the old stable_sort code, since neither the order of the dbg.values nor the order in the list of local variables in the DIFunction has an effect on the order in which the locals appear in LexicalScopes.

[vsapsai]

Looks good to me and tests I'm running are all passing.

[aprantl]

Thanks! Landed as r324677.

lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

637

In theory a frontend could produce metadata where the count is a global variable. This doesn't make much sense in practice, but we don't reject it in the verifier, so we might as well handle it gracefully.

[vsapsai]

lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

637

For those who aren't following the review closely, I think global variables are handled at

// Dependency is in a different lexical scope or a global.
if (!Var)
  continue;

And no need to worry that dependencies loop has no null checks.

lib/CodeGen/AsmPrinter/DwarfCompileUnit.cpp

DIE *DwarfCompileUnit::constructVariableDIE(DbgVariable &DV,
                                             const LexicalScope &Scope,
                                             DIE *&ObjectPointer) {
   auto Var = constructVariableDIE(DV, Scope.isAbstractScope());
   if (DV.isObjectPointer())
     ObjectPointer = Var;
   return Var;
 }
 
-/// Determine whether a variable appears in a count: expression.
-static bool dependsOn(DbgVariable *A, DbgVariable *B) {
-  auto *Array = dyn_cast<DICompositeType>(A->getType());
+/// Return all DIVariables that appear in count: expressions.
+static SmallVector<const DIVariable *, 2> dependencies(DbgVariable *Var) {
+  SmallVector<const DIVariable *, 2> Result;
+  auto *Array = dyn_cast<DICompositeType>(Var->getType());
   if (!Array || Array->getTag() != dwarf::DW_TAG_array_type)
-    return false;
-  return llvm::any_of(Array->getElements(), [&](DINode *El) {
+    return Result;
+  for (auto *El : Array->getElements()) {
     if (auto *Subrange = dyn_cast<DISubrange>(El)) {
       auto Count = Subrange->getCount();
-      if (auto *Var = Count.dyn_cast<DIVariable *>())
-        return Var == B->getVariable();
+      if (auto *Dependency = Count.dyn_cast<DIVariable *>())
+        Result.push_back(Dependency);
     }
-    return false;
-  });
+  }
+  return Result;
 }
 
 /// Sort local variables so that variables appearing inside of helper
 /// expressions come first.
-static bool sortLocalVars(DbgVariable *A, DbgVariable *B) {
-  return dependsOn(B, A);
+static SmallVector<DbgVariable *, 8> sortLocalVars(SmallVectorImpl<DbgVariable *> &Input) {
+  SmallVector<DbgVariable *, 8> Result;
+  SmallVector<PointerIntPair<DbgVariable *, 1>, 8> WorkList;
+  /// Map back from a DIVariable to its containing DbgVariable.
+  SmallDenseMap<const DILocalVariable *, DbgVariable *> DbgVar;
+  /// Set of DbgVariables in Result.
+  SmallDenseSet<DbgVariable *, 8> Visited(Input.size());
+  /// For cycle detection.
+  SmallDenseSet<DbgVariable *, 8> Visiting(Input.size());
+  for (auto N : reverse(Input)) {
+    DbgVar.insert({N->getVariable(), N});
+    WorkList.push_back({N, 0});
+  }
+  // Perform a stable topological sort by doing a DFS.
+  while (!WorkList.empty()) {
+    auto Item = WorkList.back();
+    DbgVariable *N = Item.getPointer();
+    bool visitedAllDependencies = Item.getInt();
+    
+    WorkList.pop_back();
+
+    assert(N && "dependency is in a different lexical scope");
+    if (!N)
+      continue;
+    
+    // Already handled.
+    if (Visited.count(N))
+      continue;
+
+    // Add to Result if all dependencies are visited.
+    if (visitedAllDependencies) {
+      Visited.insert(N);
+      Result.push_back(N);
+      continue;
+    }
+
+    // Detect cycles.
+    auto Res = Visiting.insert(N);
+    if (!Res.second) {
+      assert(false && "dependency cycle in local variables");
+      return Result;
+    }
+
+    // Push dependencies and this node onto the worklist, so that this node is
+    // visited again after all of its dependencies are handled.
+    WorkList.push_back({N, 1});
+    for (auto *Dependency : dependencies(N)) {
+      auto Var = dyn_cast_or_null<const DILocalVariable>(Dependency);
+      WorkList.push_back({DbgVar[Var], 0});
+    }
+  }
+  return Result;
 }
 
 DIE *DwarfCompileUnit::createScopeChildrenDIE(LexicalScope *Scope,
                                               SmallVectorImpl<DIE *> &Children,
                                               bool *HasNonScopeChildren) {
   assert(Children.empty());
   DIE *ObjectPointer = nullptr;
 
   // Emit function arguments (order is significant).
   auto Vars = DU->getScopeVariables().lookup(Scope);
   for (auto &DV : Vars.Args)
     Children.push_back(constructVariableDIE(*DV.second, *Scope, ObjectPointer));
 
   // Emit local variables.
-  std::stable_sort(Vars.Locals.begin(), Vars.Locals.end(), sortLocalVars);
-  for (DbgVariable *DV : Vars.Locals)
+  auto Locals = sortLocalVars(Vars.Locals);
+  for (DbgVariable *DV : Locals)
     Children.push_back(constructVariableDIE(*DV, *Scope, ObjectPointer));
 
   // Skip imported directives in gmlt-like data.
   if (!includeMinimalInlineScopes()) {
     // There is no need to emit empty lexical block DIE.
     for (const auto *IE : ImportedEntities[Scope->getScopeNode()])
       Children.push_back(
           constructImportedEntityDIE(cast<DIImportedEntity>(IE)));