This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by aprantl on Feb 7 2018, 11:40 AM.

Details

Reviewers
vsapsai
davide
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.

Diff Detail

Event Timeline

aprantl created this revision.Feb 7 2018, 11:40 AM
aprantl updated this revision to Diff 133271.Feb 7 2018, 11:43 AM

Initialize the DenseSets with the size of Input.

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–643

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.

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 updated this revision to Diff 133366.Feb 7 2018, 8:39 PM
aprantl marked 3 inline comments as done.

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

aprantl updated this revision to Diff 133463.Feb 8 2018, 11:41 AM

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 accepted this revision.Feb 8 2018, 1:47 PM

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

This revision is now accepted and ready to land.Feb 8 2018, 1:47 PM
aprantl closed this revision.Feb 8 2018, 4:45 PM

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 added inline comments.Feb 8 2018, 4:57 PM
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.