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

[jmorse]

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

[aprantl]

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]

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]

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.

[aprantl]

In D73725#1851836, @jmorse wrote:

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]

In D73725#1852265, @aprantl wrote:

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]

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]

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)

.

[jmorse]

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.

llvm/lib/CodeGen/LexicalScopes.cpp

if (!Scope)
     return;
 
   if (Scope == CurrentFnLexicalScope) {
     for (const auto &MBB : *MF)
       MBBs.insert(&MBB);
     return;
   }
 
+  // The scope ranges can cover multiple basic blocks in each span. Iterate over
+  // all blocks (in the order they are in the function) until we reach the one
+  // containing the end of the span.
   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
-  for (auto &R : InsnRanges)
-    MBBs.insert(R.first->getParent());
+  for (auto &R : InsnRanges) {
+    auto CurMBBIt = R.first->getParent()->getIterator();
+    auto EndBBIt = R.second->getParent()->getIterator();
+    do {
+      MBBs.insert(&*CurMBBIt);
+      if (CurMBBIt == EndBBIt)
+        break;
+      CurMBBIt++;
+    } while (true);
+  }
 }
 
 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
 /// machine instruction's lexical scope in a given machine basic block.
 bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) {
   assert(MF && "Unexpected uninitialized LexicalScopes object!");
   LexicalScope *Scope = getOrCreateLexicalScope(DL);
   if (!Scope)
     return false;
 
   // Current function scope covers all basic blocks in the function.
   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
     return true;
 
-  bool Result = false;
-  for (auto &I : *MBB) {
-    if (const DILocation *IDL = I.getDebugLoc())
-      if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
-        if (Scope->dominates(IScope))
-          return true;
-  }
-  return Result;
+  // Fetch all the blocks in DLs scope. Because the range / block list also
+  // contain any subscopes, any instruction that DL dominates can be found
+  // in the block set.
+  SmallPtrSet<const MachineBasicBlock *, 32> Set;
+  getMachineBasicBlocks(DL, Set);
+  return Set.count(MBB) != 0;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
   raw_ostream &err = dbgs();
   err.indent(Indent);
   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
   const MDNode *N = Desc;