3
$\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.

$\endgroup$
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.

$\endgroup$
  • $\begingroup$ did you see my updated question? Your answer targets not the problem I am having. $\endgroup$ – langlauf.io Sep 30 '15 at 9:11
  • $\begingroup$ @stackoverflowwww I disagree with your evaluation. $\endgroup$ – Yuval Filmus Sep 30 '15 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 Sep 30 '15 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 Sep 30 '15 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 Oct 15 '15 at 13:35

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.