Tool that outputs the longest chain of calls

Question

The context: I am carrying out the analysis procedure described here: approach.

The blocking point is finding the "longest chain of calls" for the project under observation. What tool can be used for finding this? I presume it will be a static analysis tool.

Otherwise, I presume a call graph generator can be used for this purpose. But then, how to infer the longest chain of calls?

Answer 1

The "longest" call chain in terms of hops is straightforward to determine from a call graph. This assumes you have acquired one, and yes this generally requires static analysis. (You can get a dynamically-generated call graph, but it likely won't exhibit all possible calls). Acquiring one for firefox, with function calls that cross language boundaries, if you want to take those into account, may be pretty challenging.

Given such a call graph: Start with the call graph with blank call-path-length values for each node. Mark the root(s) [your call graph may be a DAG] with the call-path-length value 0. For each unlabelled child, for which all parents have been determined, label that child with the max of the values from parents, plus 1. Repeat until all children are labelled. [If you have a cycle in the call graph, you have to decide to ignore it, or treat it as some constant addition to the path length.] The longest path is easily extracted by starting with the highest-value node, and walking backwards to the most expensive parents until a root is reached.

[EDIT] if you back propagate leaf values to parents, you can end up with the graph with every node labelled as to how far it reaches.

Are you sure you want longest-chain? Or do you want Worst Case Execution time?