Page MenuHomePhabricator

[XRay] Account: recursion detection
ClosedPublic

Authored by lebedev.ri on Jul 25 2020, 5:34 AM.

Details

Summary

Recursion detection can be non-trivial. Currently, the state-of-the-art for LLVM,
as far as i'm concerned, is D72362 [clang-tidy] misc-no-recursion: a new check.
However, it is quite limited:

  • It does very basic call-graph based analysis, in the sense it will report even dynamically-unreachable recursion.
  • It is inherently limited to a single TU
  • It is hard to gauge how problematic each recursion is in practice.

Some of that can be addressed by adding clang analyzer-based check,
then it would at least support multiple TU's.

However, we can approach this problem from another angle - dynamic run-time analysis.
We already have means to capture a run-time callgraph (XRay, duh),
and there are already means to reconstruct it within llvm-xray tool.

This proposes to add a -recursive-calls-only switch to the account tool.
When the switch is on, when re-constructing callgraph for latency reconstruction,
each time we enter/leave some function, we increment/decrement an entry for the function
in a "recursion depth" map. If, when we leave the function, said entry was at 1,
then that means the function didn't call itself, however if it is at 2 or more,
then that means the function (possibly indirectly) called itself.

If the depth is 1, we don't account the time spent there,
unless within this call stack the function already recursed into itself.
Note that we don't pay for recursion depth tracking when recursive-calls-only is not on,
and the perf impact is insignificant (+0.3% regression)

The overhead of the option is actually negative, around -5.26% user time on a medium-sized (3.5G) XRay log.
As a practical example, that 3.5G log is a capture of the entire middle-end opt pipeline
at -O3 for RawSpeed unity build. There are total of 5500 functions in the log,
however -recursive-calls-only says that 269, or 5%, are recursive.

Having this functionality could be helpful for recursion eradication.

Diff Detail

Event Timeline

lebedev.ri created this revision.Jul 25 2020, 5:34 AM
lebedev.ri edited the summary of this revision. (Show Details)

On a second thought, just implement accounting for the outermost recursive call, too.

Fixup comment.

lebedev.ri edited the summary of this revision. (Show Details)

Fix performance implications by consistently using llvm::DenseMap instead of std::map.

dberris accepted this revision.Jul 26 2020, 6:53 PM

LGTM -- thank you, and I'm happy this has been useful for your needs!

This revision is now accepted and ready to land.Jul 26 2020, 6:53 PM

LGTM -- thank you, and I'm happy this has been useful for your needs!

Thank you for the review!

This revision was automatically updated to reflect the committed changes.