4
$\begingroup$

Say I have the interprocedural control flow graph (ICFG) of a program.

Now I am only interested in the control flow between two functions f1 and f2.

  • What is the most straight-forward way to remove the non-relevant part of the ICFG?
  • Is there a standard performance-optimized algorithm for this task?
  • Does the result, that is, the interprocedural control flow "subgraph", have a special name?

I guess it would not be appropriate to call this a "slice" because its creation is based on the control flow graph reachability but not on data dependency relations. But I am not 100% sure.

EDIT:

I have to clarify: I am interested in the control flow starting at function f1, optionally passing via other functions, but eventually ending at function f2. In other words, the subgraph that contains all paths in the ICFG whose start node is f1 and whose end node is f2. This also includes paths with other nodes in between f1 and f2. Sorry in case my first explanation was not clear enough.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You are asking several questions. Here are answers to some of them. Your process is obtained by contracting all vertices not belonging to $f_1,f_2$, a process which is similar to the process of contracting edges in the definition of graph minors (though your graph is directed). Semantically, you can produce the graph by repeatedly performing the following contracting procedure for each vertex $v$ which is not $f_1,f_2$:

Let $(x_i,v)$ be all the incoming edges, and $(v,y_j)$ all the outgoing edges. Delete $v$ and replaces the edges adjacent to $v$ by the edges $(x_i,y_j)$ for all $i,j$.

I don't know what is the most efficient implementation of this process, though I suspect you could find it in the literature once you determine what this operation is known as.

Improve this answer
$\endgroup$
6
  • $\begingroup$ did you see my updated question? Your answer targets not the problem I am having. $\endgroup$
    – langlauf.io
    Commented Sep 30, 2015 at 9:11
  • $\begingroup$ @stackoverflowwww I disagree with your evaluation. $\endgroup$
    – Yuval Filmus
    Commented Sep 30, 2015 at 9:26
  • $\begingroup$ Ok, then I must have misunderstood your answer. Could you give an example of the algo you outlined? $\endgroup$
    – langlauf.io
    Commented Sep 30, 2015 at 12:24
  • $\begingroup$ @stackoverflowwww You can try it out and see if it does what you want it to do. If it doesn't, try to find a simple example and explain the desired outcome versus what my algorithm gives. $\endgroup$
    – Yuval Filmus
    Commented Sep 30, 2015 at 13:03
  • $\begingroup$ I found a related post on SO with this answer: stackoverflow.com/a/32631302 Does this correspond to your algorithm? $\endgroup$
    – langlauf.io
    Commented Oct 15, 2015 at 13:35

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.