Compute and process Differentiation Request graph

[vaithak]

This is the initial PR for capturing the differentiation plan in a graphical format.

However, the traversal order is still breadth-first, as we don't have the complete graph in the first pass - mainly because of a lack of information about the args required for pushforward and pullbacks.

This can be improved with the help of activity analysis to capture the complete graph in the first pass, processing the plan in a topologically sorted manner and pruning the graph for user-defined functions. I started this with this approach, and the initial experimental commit is available here for future reference: https://github.com/vaithak/clad/commit/82c0b4250c1f0399b21ebbc71e50b52a218eae27.

[vaithak]

@vgvassilev One improvement that we can make in this PR itself is to fix the printing order of generated functions; this can be done because we have dynamically created the graph during traversals. This will help us minimize (or, in some cases, completely remove) the printing of declarations first, and definitions later. Do you think it would be a good idea?

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 99.15966% with 1 lines in your changes are missing coverage. Please review.

Project coverage is 94.81%. Comparing base (922bd1c) to head (ed6a89a).

Additional details and impacted files

@@           Coverage Diff           @@
##           master     #873   +/-   ##
=======================================
  Coverage   94.81%   94.81%           
=======================================
  Files          51       52    +1     
  Lines        7620     7701   +81     
=======================================
+ Hits         7225     7302   +77     
- Misses        395      399    +4     

Files	Coverage Δ
include/clad/Differentiator/DerivativeBuilder.h	100.00% <ø> (ø)
include/clad/Differentiator/DerivedFnCollector.h	100.00% <ø> (ø)
include/clad/Differentiator/DiffPlanner.h	100.00% <100.00%> (ø)
include/clad/Differentiator/Differentiator.h	100.00% <ø> (ø)
lib/Differentiator/BaseForwardModeVisitor.cpp	98.90% <100.00%> (+0.09%)	:arrow_up:
lib/Differentiator/DerivativeBuilder.cpp	99.00% <100.00%> (+0.02%)	:arrow_up:
lib/Differentiator/DerivedFnCollector.cpp	100.00% <100.00%> (ø)
lib/Differentiator/DiffPlanner.cpp	98.64% <100.00%> (+<0.01%)	:arrow_up:
lib/Differentiator/HessianModeVisitor.cpp	99.49% <100.00%> (+0.02%)	:arrow_up:
lib/Differentiator/ReverseModeVisitor.cpp	97.18% <100.00%> (ø)
... and 3 more

... and 2 files with indirect coverage changes

Files	Coverage Δ
include/clad/Differentiator/DerivativeBuilder.h	100.00% <ø> (ø)
include/clad/Differentiator/DerivedFnCollector.h	100.00% <ø> (ø)
include/clad/Differentiator/DiffPlanner.h	100.00% <100.00%> (ø)
include/clad/Differentiator/Differentiator.h	100.00% <ø> (ø)
lib/Differentiator/BaseForwardModeVisitor.cpp	98.90% <100.00%> (+0.09%)	:arrow_up:
lib/Differentiator/DerivativeBuilder.cpp	99.00% <100.00%> (+0.02%)	:arrow_up:
lib/Differentiator/DerivedFnCollector.cpp	100.00% <100.00%> (ø)
lib/Differentiator/DiffPlanner.cpp	98.64% <100.00%> (+<0.01%)	:arrow_up:
lib/Differentiator/HessianModeVisitor.cpp	99.49% <100.00%> (+0.02%)	:arrow_up:
lib/Differentiator/ReverseModeVisitor.cpp	97.18% <100.00%> (ø)
... and 3 more

... and 2 files with indirect coverage changes

[vgvassilev]

@vgvassilev One improvement that we can make in this PR itself is to fix the printing order of generated functions; this can be done because we have dynamically created the graph during traversals. This will help us minimize (or, in some cases, completely remove) the printing of declarations first, and definitions later. Do you think it would be a good idea?

I think so, is there a catch?

[vaithak]

I think so, is there a catch?

The only issue I see is that diagnostic messages won't align with the sequence of generated functions in the code dump. So, maybe it's a little bit tough for debugging.

[vgvassilev]

I think so, is there a catch?

The only issue I see is that diagnostic messages won't align with the sequence of generated functions in the code dump. So, maybe it's a little bit tough for debugging.

Hm... I am confused - how is it different from now?

[vaithak]

Hm... I am confused - how is it different from now?

Currently, if the order of differentiation is f1 followed by f2. Then, any diagnostic warning or error in f2 will appear after f1 has been dumped/printed and before f2 is dumped. This won't be true anymore.

[vgvassilev]

Hm... I am confused - how is it different from now?

Currently, if the order of differentiation is f1 followed by f2. Then, any diagnostic warning or error in f2 will appear after f1 has been dumped/printed and before f2 is dumped. This won't be true anymore.

Let's have this improvement in a separate PR and then we can discuss further. What do you think?

[vaithak]

Let's have this improvement in a separate PR and then we can discuss further. What do you think?

Sounds good 👍🏼