[DebugInfo][NFC] Early-exit when analysing for single-location variables

[jmorse]

Summary

This is a performance patch that hoists two conditions in DwarfDebug's validThroughout to avoid a linear-scan of all instructions in a block. We now exit early if validThrougout will never return true for the variable location. No test as this is a performance change, but:

• It halves the time in DWARF emission for several code samples I'm working on, which have large volumes of inlining to deal with,
• A clang-10 stage2 build produces an identical binary with/without this patch.

The first added clause filters for the two circumstances where validThroughout will return true. The second added clause should be identical to the one that's deleted from after the linear-scan.

[dstenb]

Adding a nit. I'll try to take a closer look at the functionality later today.

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1483

Nit: neither *is* ?

[dstenb]

Two minor nits, but otherwise this looks good to me. Thanks!

(It would be interesting to revisit this "Single, constant DBG_VALUEs" behavior sometime in the future, but I don't expect you do that just because you improved the performance of the existing behavior.)

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1485

Nit: It might be preferred to use !RangeEnd here since the rest of the code in this function does nullptr checks like that.

[aprantl]

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1485

You probably mean RangeEnd?
I also think that is better.

1498

like here

[dstenb]

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

1485

Oops, yes!

[jmorse]

Thanks for the reviews,

David wrote:

(It would be interesting to revisit this "Single, constant DBG_VALUEs" behavior sometime in the future, but I don't expect you do that just because you improved the performance of the existing behavior.)

Weeelllll, I did toy with this a while back, I think the fact that we only emit single locations for "open ended" (i.e. is the last block in the function) locations is a large limitation. I tried inserting another piece of linear-scanning code [0] to test the following:

• The lexical scope only covers one block (this one),
• The variable location starts before/at the start of the scope,
• The variable location ends at/after the end of the scope

Of which the third test is new, and the first two are already tested by validThroughout.

The result was, on a clang-trunk stage2reldeb build on Ubuntu 18.04:

• a 27% reduction in the size of .debug_loc (450MiB -> 329MiB),
• Leading to a 6% reduction in binary size overall (2077MiB -> 1954MiB).

Which is quite attractive. Pursuing this involves making an argument that representing this situation with a single-location in DWARF, and I'm not familiar enough with DWARF right now. The hard part however is doing this efficiently, as touching every instruction in a block for every variable doesn't scale. (If anyone picks this up, please let me know, otherwise we'll eventually get around to addressing this).

[0] https://github.com/jmorse/llvm-project/commit/903338d971c9c1c9c46a6e1aebc6f1e1b405d37c

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

static bool validThroughout(LexicalScopes &LScopes,
   auto *LScope = LScopes.findLexicalScope(DL);
   // Scope doesn't exist; this is a dead DBG_VALUE.
   if (!LScope)
     return false;
   auto &LSRange = LScope->getRanges();
   if (LSRange.size() == 0)
     return false;
 
+  // If this range is neither open ended nor a constant, then it is not a
+  // candidate for being validThroughout.
+  if (RangeEnd && !DbgValue->getOperand(0).isImm())
+    return false;
+
   // Determine if the DBG_VALUE is valid at the beginning of its lexical block.
   const MachineInstr *LScopeBegin = LSRange.front().first;
   // Early exit if the lexical scope begins outside of the current block.
   if (LScopeBegin->getParent() != MBB)
     return false;
+
+  // If there are instructions belonging to our scope in another block, and
+  // we're not a constant (see DWARF2 comment below), then we can't be
+  // validThroughout.
+  const MachineInstr *LScopeEnd = LSRange.back().second;
+  if (RangeEnd && LScopeEnd->getParent() != MBB)
+    return false;
+
   MachineBasicBlock::const_reverse_iterator Pred(DbgValue);
   for (++Pred; Pred != MBB->rend(); ++Pred) {
     if (Pred->getFlag(MachineInstr::FrameSetup))
       break;
     auto PredDL = Pred->getDebugLoc();
     if (!PredDL || Pred->isMetaInstruction())
       continue;
     // Check whether the instruction preceding the DBG_VALUE is in the same
     // (sub)scope as the DBG_VALUE.
     if (DL->getScope() == PredDL->getScope())
       return false;
     auto *PredScope = LScopes.findLexicalScope(PredDL);
     if (!PredScope || LScope->dominates(PredScope))
       return false;
   }
 
   // If the range of the DBG_VALUE is open-ended, report success.
   if (!RangeEnd)
     return true;
 
-  // Fail if there are instructions belonging to our scope in another block.
-  const MachineInstr *LScopeEnd = LSRange.back().second;
-  if (LScopeEnd->getParent() != MBB)
-    return false;
-
   // Single, constant DBG_VALUEs in the prologue are promoted to be live
   // throughout the function. This is a hack, presumably for DWARF v2 and not
   // necessarily correct. It would be much better to use a dbg.declare instead
   // if we know the constant is live throughout the scope.
   if (DbgValue->getOperand(0).isImm() && MBB->pred_empty())
     return true;
 
   return false;