2
$\begingroup$

I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG).

That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent interprocedural call and return. The impact of these is that they determine which edge must be traversed on a call return.

Is there a shortest path algorithm adapted to this kind of graph?

Edit Clarification: suppose that I am able to identify a pair of nodes of interest (n1, n2) in the graph using a plain boring graph traversal, I want to obtain the shortest path between n1 and n2 that respects the constraints of the graph.

$\endgroup$
  • 1
    $\begingroup$ It seems easy to adapt BFS to consider only legal paths; just propagate the latest "function call" edge downwards until you meet another one, or a "return" edge. (You have a restriction on paths, not special graphs!) What have you tried and where did you get stuck? $\endgroup$ – Raphael Jun 10 '16 at 21:25
  • $\begingroup$ I adapted Dijkstra and got stuck at the data structure containing the shortest path information. Basically, this data structure contains only one value, whereas a function may have multiple return edges. $\endgroup$ – malaverdiere Jun 13 '16 at 15:54
2
$\begingroup$

Yes. You want CFL-reachability.

You put a left-parenthesis on each call edge and a right-parenthesis on each return edge (with a different kind of parenthesis for each function). Then, you look for a path where the sequence of symbols along the edges in the path form matched parentheses.

This is basically the intersection of a context-free language (CFL) with a graph reachability problem (finite state automaton), and as you know, the intersection of a CFL and a regular language is itself a CFL. As a result, there are efficient algorithms for CFL-reachability.

There's also lots of theory and work on algorithms to make this as efficient as possible. You can even find existing tools for this sort of thing.

I'd suggest you start by looking at the following papers:

Thomas Reps. Program Analysis via Graph Reachability. Information and Software Technology, vol 40 no 11-12, Nov/Dec 1998, pp.701--726.

Thomas Reps, Susan Horwitz, Mooly Sagiv. Precise interprocedural dataflow analysis via graph reachability. POPL '95.

Thomas Reps, Stefan Schwoon, Somesh Jha, David Melski. Weighted Pushdown Systems and their Application to Interprocedural Dataflow Analysis. Science of Computing Programming, vol 58 no 1-2, Oct 2005, pp.206--263.

The first two consider only the reachability problem (is there a path from $s$ to $t$?). The third can be used for the shortest paths from (find the shortest path from $s$ to $t$).

$\endgroup$
  • $\begingroup$ I'm familiar with Reps' papers on IFDS and IDE so I started looking at the third reference. It feels overkill right now, but I'll keep reading. $\endgroup$ – malaverdiere Jun 13 '16 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.