This is an archive of the discontinued LLVM Phabricator instance.

[DebugInfo] Avoid a quadratic-complexity corner case in LiveDebugValues
ClosedPublic

Authored by jmorse on Jan 30 2020, 10:07 AM.

Details

Summary

Long ago [0], it was identified that part of LiveDebugValues had worst-case quadratic complexity. We test [1] whether a variable location would still be in scope when propagated into a block, to avoid needlessly propagating locations. If you have a block of DBG_VALUEs, all for different variables, then the LexicalScopes::dominates method will scan each instruction for each variable location, which is O(n^2). It doesn't appear to have been judged a high risk at the time.

We've run into a circumstance where this happens, once again with large amounts of inlining into a large basic block. To avoid the quadratic complexity, I think we can rely on the scope ranges that are computed in each LexicalScope object [2]. These identify spans of the function that the lexical scope contains. Crucially, these spans cover all subscopes [3] as well. This patch changes the LexicalScopes::dominates method to, rather than testing each instruction in a block to see if it's dominated, instead test whether this block is in the set of dominated instructions blocks. (Which is a mouthful). This also involves fixing the getMachineBasicBlocks method, which didn't seem to be aware that each span could cover multiple blocks.

This patch eliminates the performance problem we encountered, and the complexity of LexicalScopes::dominates becomes linear with the size of the scope (measured in blocks), rather than the number of instructions in this block. The worst case would now be a circumstance where there are a large number of variable locations in a lexical scope that covers a large number of blocks (meaning we had to iterate over many blocks on each call to dominates). This, I believe, is not a circumstance that the inliner tries to create, as opposed to "many inlined scopes in one large block", which it does.

I tried building clang-3.4 with this patch applied, and there was no observable change in compile time (I guess it doesn't hit the worst case). I also tried building a stage2 build of clang with itself, with both implementations of LexicalScopes::dominates, comparing their answers. This showed up that the (current) implementation of dominates will interpret a metainstruction as being dominated , instead of ignoring it like the rest of LexicalScopes [4]. Aside from that, both implementations of dominates agreed in all their results.

No test because this is a performance patch, although I can add one for the "don't consider metainstructions in scope dominance queries" matter if that's important.

[0] https://reviews.llvm.org/D24994#inline-215341
[1] https://github.com/llvm/llvm-project/blob/3ae11b42818363f70b3c6b0246bb617e35709c58/llvm/lib/CodeGen/LiveDebugValues.cpp#L1328
[2] https://github.com/llvm/llvm-project/blob/3ae11b42818363f70b3c6b0246bb617e35709c58/llvm/include/llvm/CodeGen/LexicalScopes.h#L129
[3] https://github.com/llvm/llvm-project/blob/3ae11b42818363f70b3c6b0246bb617e35709c58/llvm/include/llvm/CodeGen/LexicalScopes.h#L76
[4] https://github.com/llvm/llvm-project/blob/3ae11b42818363f70b3c6b0246bb617e35709c58/llvm/lib/CodeGen/LexicalScopes.cpp#L92

Diff Detail

Event Timeline

jmorse created this revision.Jan 30 2020, 10:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 30 2020, 10:07 AM

We don't have an existing unit test for LexicalScopes that generates IR manually and tests a few common queries, do we?

llvm/lib/CodeGen/LexicalScopes.cpp
299

Perhaps I'm missing something, but this looks like a really complicated way of writing a for(;;) loop?

327

return Set.count(MBB);

is idiomatic, I think.

vsk added inline comments.Jan 30 2020, 3:58 PM
llvm/lib/CodeGen/LexicalScopes.cpp
327

Does a LexicalScope always start at a MachineBasicBlock boundary? I.e. can Set.count(MBB) be non-zero even if no instruction in MBB has a location dominated by Scope?

jmorse marked 2 inline comments as done.Jan 31 2020, 7:10 AM

Adrian wrote:

We don't have an existing unit test for LexicalScopes that generates IR manually and tests a few common queries, do we?

Alas no, there doesn't appear to be any testing of LexicalScopes at all.

llvm/lib/CodeGen/LexicalScopes.cpp
299

It looks like I was missing caffeine at the time; I'll switch this to a for loop,

327

LexicalScopes don't always start at block boundaries; but the ranges only ever cover those instructions that are definitely part of the scope, and are inclusive, so if one had:

entry:
  // instructions in scope 1
  b %someblock
unrelated:
  // instructions in scope 2
  b %another block
someblock:
  // instructions in scope 1
  ret

And scope 2 was not a child of scope 1, then there would be two instruction ranges covering the "entry" and "someblock" block. The beginning and end of the ranges would point at instructions entirely in those two blocks, and "unrelated" wouldn't be reported as being in scope 1.

Adrian wrote:

We don't have an existing unit test for LexicalScopes that generates IR manually and tests a few common queries, do we?

Alas no, there doesn't appear to be any testing of LexicalScopes at all.

I'm not going to make you write one, but this would be a great opportunity ;-)

jmorse added a comment.Feb 4 2020, 9:02 AM

I'm not going to make you write one, but this would be a great opportunity ;-)

Well, I've never written any LLVM unit tests before, so "how hard can it be" :), I'll give it a shot.

jmorse updated this revision to Diff 246177.Feb 24 2020, 4:36 AM
jmorse marked an inline comment as done.

I've added some unit tests; without the patch to LexicalScopes.cpp, these failures occur:

[ RUN      ] LexicalScopesTest.TestGetBlocks
/fast/fs/llvm-project/llvm/unittests/CodeGen/LexicalScopesTest.cpp:410: Failure
      Expected: NotNestedBlockBlocks.count(MBB3)
      Which is: 0
To be equal to: 1u
      Which is: 1
[  FAILED  ] LexicalScopesTest.TestGetBlocks (1 ms)
[ RUN      ] LexicalScopesTest.TestMetaInst
/fast/fs/llvm-project/llvm/unittests/CodeGen/LexicalScopesTest.cpp:452: Failure
Value of: LS.dominates(InBlockLoc.get(), MBB2)
  Actual: true
Expected: false
/fast/fs/llvm-project/llvm/unittests/CodeGen/LexicalScopesTest.cpp:453: Failure
Value of: LS.dominates(InBlockLoc.get(), MBB3)
  Actual: true
Expected: false
[  FAILED  ] LexicalScopesTest.TestMetaInst (0 ms)

Which pass with the patch applied. The other tests are in for just general good coverage. It's generally unclear to me how much bogus / fake / mock implementation to rely on, it might be that manipulating MCInstrDesc structs directly isn't clever. I couldn't see another way of generating instructions without a backend though.

I've also split out some boilerplate code for generating machine functions into MFCommon.inc from the machine instruction tests.

aprantl accepted this revision.Feb 24 2020, 9:08 AM

Thanks!

llvm/lib/CodeGen/LexicalScopes.cpp
301

And now that it's simplified, this looks like we should use something like std::copy() instead of a loop :-)

llvm/unittests/CodeGen/LexicalScopesTest.cpp
1 ↗(On Diff #246177)

Super-nit: expand this to column 80?

53 ↗(On Diff #246177)

Very cool! Should we fire up artist-mode and put the CFG into an ASCII art comment? (mostly joking)

112 ↗(On Diff #246177)

.

This revision is now accepted and ready to land.Feb 24 2020, 9:08 AM
This revision was automatically updated to reflect the committed changes.
jmorse marked 4 inline comments as done.Feb 28 2020, 3:58 AM
jmorse added inline comments.
llvm/lib/CodeGen/LexicalScopes.cpp
301

I don't think std::copy can be used, there needs to be some conversion between MBB references to MBB pointers. There might be some way of doing this automagically, possibly using std::decay, however my C++-fu is weak.