How to measure the complexity of debug information?

[IOVOVHS]

The compiler generates debugging information, and the debugger knows how to debug the program by parsing the debugging information. Compared to simple debugging information, complex debugging information must be meaningful to the test debugger, the question is how to measure the complexity of debugging information? Here is a formula to measure the complexity of debugging information, probably equivalent to the significance of this program for testing a debugger. For example:

$$ debugInfoComplexity = \sum_{i=1}^n(LocExprComplexity(i)+LocRangeCount(i)+RegSwitchCount(i))+(InlineDepth*InlineFactor=1.5) $$

LocExprComplexity(i):loction expression complexity for variable i
LocRangeCount(i):Number of loction ranges
RegSwitchCount:Number of transitions of variable i between registers
InlineDepth:Depth of inlined function
inlinedFactor:maybe 1.5?

$$ CS = (1 * OpCount) + (3 * MemAccesses) + ( 2 * RegAccess) + (2* CondComp) + (1.5*StackOps) + 2.5 * TypeConv + 1.5 * ArithLogicOps $$

OpCount:Number of opcodes
MemAccesses:Number of memory accesses
RegAccess:Number of register accesses
CondComp:Number of condition calculation
TypeConv:Number of type conversion
...

My understanding of debuggers is shallow, so I can't tell if it makes some sense to use this formula to measure the complexity of a test case for testing a debugger. I'd like to get an acknowledgement or outright dismissal from the developers if I can.

[llvmbot]

@llvm/issue-subscribers-debuginfo

Author: None (IOVOVHS)

The compiler generates debugging information, and the debugger knows how to debug the program by parsing the debugging information. Compared to simple debugging information, complex debugging information must be meaningful to the test debugger, the question is how to measure the complexity of debugging information? Here is a formula to measure the complexity of debugging information, probably equivalent to the significance of this program for testing a debugger. For example:

$$ debugInfoComplexity = \sum_{i=1}^n(LocExprComplexity(i)+LocRangeCount(i)+RegSwitchCount(i))+(InlineDepth*InlineFactor=1.5) $$

LocExprComplexity(i):loction expression complexity for variable i
LocRangeCount(i):Number of loction ranges
RegSwitchCount:Number of transitions of variable i between registers
InlineDepth:Depth of inlined function
inlinedFactor:maybe 1.5?

$$ CS = (1 * OpCount) + (3 * MemAccesses) + ( 2 * RegAccess) + (2* CondComp) + (1.5*StackOps) + 2.5 * TypeConv + 1.5 * ArithLogicOps $$

OpCount:Number of opcodes
MemAccesses:Number of memory accesses
RegAccess:Number of register accesses
CondComp:Number of condition calculation
TypeConv:Number of type conversion
...

My understanding of debuggers is shallow, so I can't tell if it makes some sense to use this formula to measure the complexity of a test case for testing a debugger. I'd like to get an acknowledgement or outright dismissal from the developers if I can.

[dwblaikie]

I don't know that this is a question for this forum - I'm not aware of any use we'd have in the LLVM project for a measure of debug info complexity...

[jimingham]

Note that while parsing DWARF location expressions is a complex task the debugger has to perform, it is by no means the only complex task it does. Managing 100 threads all hitting breakpoints in a single work function simultaneously and not dropping any of the hits, for instance, has taken quite a bit of work to get right even though the debug information in that scenario is trivial.

Also, it isn't the case that we only want to test complex scenarios. There's no guarantee that every bug that breaks a simple expression will always break a more complex expression. So we need to start out making sure all the common stuff works. I can't see any scenario where we'd start rejecting tests because the DWARF expressions they exercise aren't complex enough. At best this would aid in the "we already have pretty good coverage for simple expressions, now let's try to craft some gnarlier ones" project, though I'm not sure you really need a formula for this job.

[IOVOVHS]

Thank you for your reply and correction. My understanding of testing starts from the input space, that is, searching for meaningful inputs in the entire input space. Therefore, input generation is guided to a specific goal, or the input is as evenly distributed as possible. I think what you want to express is the second one, that is, the input should be as rich and diverse as possible.

So maybe we can change another indicator here, that is, the similarity between debug information, and the goal is to make the generated program as different as possible in debug information after compilation and optimization. This may increase the efficiency of testing, rather than the random method of csmith. But I can't think of how to use a formula to measure the difference between two debug information, there are too many things to consider. Considering that dwarf information organizes DIE in the form of a tree, perhaps graph neural networks or other methods can be used to extract the features of dwarf information. Then calculate the difference between the two debug information, and this difference can guide the subsequent test case generation process. This is just a guess.

In short, if the understanding from the perspective of similarity is also wrong, then probably the randomness is enough in generating test cases. Please also answer whether this understanding makes sense. Sorry to bother you again.Yes or no is enough.

[dwblaikie]

A measure of input diversity is probably code coverage, rather than complexity for the sake of complexity.

Perhaps some combinations of code coverage - some tests that cover distinct parts of the codebase, and others that try to cover more in a single test, while minimizing the size of the test (so it's more likely it covers multiple parts of the codebase with related entities - rather than just by concatenating unrelated tests together that in total cover larger portions of the codebase but relatively independently)