Checking if two statements can be reached in one control flow

Question

Assume I have a graph representing the control flow and the call graph of a given program. I also have a first and a second statement. I now want to figure out if it is possible to execute both statements (in order) within the same program execution.

Control Flow Graph: I have a graph with all the statements of the program and edges connecting the statements determining the control flow of the program intra function (i.e., within a function).

Call Graph: I also have edges connecting any function call with the start of the function control flow of the called function.

The literature I found concerning control flow covers only intra function flow analysis and the only correct approach I can come up with is a depth first (or breadth first) search starting from the first statement. This, however, hardly feels correct as it is quite cumbersome and I would expect a better solution.

Answer 1

This can be solved with a "context-free reachability" query in a graph. Each function call corresponds to an open parenthesis, each return corresponds to a close parenthesis, and you want to know whether there is a path in the graph such that the sequence of parentheses formed is properly nested and that traverses those two nodes in order. If you search on that term you should find papers with algorithms for that problem.

The exact nature of the context-free language depends on how you formulate the question. Suppose we want to know whether there is a path in the program that respects function calls and returns and visits $u$ and $v$, in that order. One way is to ask whether there exists a path through the graph that starts at $s$ (the start point of the program), then eventually visits $u$, then eventually visits $v$, and where the word formed by this path is in the Dyck language $L$ of properly nested parentheses, e.g., $S = L(S)$ where $S := \varepsilon | (S)$. Equivalently, you can ask whether there exists a path in the graph that starts at $u$ and ends at $v$, and where the word formed by this paths in a different context-free language $L'$, namely, the set of all suffixes of words in $L$. Here $L'$ is context-free, as it can be recognized by the grammar $S' := S | S)$. This then becomes a context-free reachability query on the graph. In practice we have multiple parentheses symbols, one per function. You can find these kinds of details in papers on context-free reachability.