1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, I will read up on it. But wouldn't )* be a valid solution yet not be properly nested? You could have the first statement in a function call deeply nested in subcalls and the second statement is simply the next statement from the call starting of those subcalls. $\endgroup$
    – Sim
    Jun 5, 2020 at 6:58
  • 1
    $\begingroup$ @Sim, see edited answer. I'd recommend reading papers on context-free reachability, as I expect you'll find discussion of a number of details that I've omitted. $\endgroup$
    – D.W.
    Jun 5, 2020 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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