Subgraph of an interprocedural control flow graph

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.

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.

StackExchange Computer Science Q#47640, answer score: 2