# Checking if two statements can be reached in one control flow

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.

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.