Creating a control flow graph for a given function

Question

Given is a short Java function and I like to create a control flow graph for it but I'm not sure if it's fine like that? Because I left some things away such as variables that have already been created with the function together (int[] A, boolean[] boo).

boolean func(int[] A, boolean[] boo){
    boolean res;
    int n, leng;
    leng = A.length;
    n = 0;
    res = true;
    while(n < leng){
        if(A[n] <= 0 && !boo[n]){
            res = false;
        }
        n++;
    }
    return res;
}

Link to the chart

Is it fine like that? Because in the test I write soon I would do it like that : /

score 5 · Accepted Answer · answered Jan 23 '19 at 16:35

5

Control flow graphs are usually not written with one statement per node, but divide the code into basic blocks that combine multiple statements. A basic block starts with a jump target and ends with a jump to another block. The jump at the end may be conditional.

Your control flow graph is generally correct, except

that it could be simplified by using basic blocks
that the n++ node has multiple outgoing jumps, but isn't a conditional statement. There must not be a direct jump from n++ to return res, instead there should only be the jump back to the while (...).

answered Jan 23 '19 at 16:35

amon

132,749
27
279
375

Thank you very much for your answer! I understand now that the edge from node 7 to node 8 must be removed because the only way to get to return aka node 8 is right after the termination of the while loop aka node 4. But I'm not sure about the simplification using basic blocks. How could this graph be made simplier? Maybe it's possible to remove the nodes 2 and 3 and keep everything else as it is? I think that should work because both variables i and leng are inside the while loop aka node 4? – eyesima Jan 23 '19 at 17:50
1

@roblind yes, in that control flow graph nodes 1,2,3 can be merged into a single block because there are only branches at the start and end – amon Jan 23 '19 at 17:58

score 3 · Answer 2 · edited Apr 29 '20 at 12:45

No, it isn't fine:

A control flow graph is an abstraction of the your code in which the control is represented by arrows and commands are represented by nodes.

Control include branching (if), loops (while, for) or terminations (break, return).

Commands include assignment (a=b), operations on data (-x, x+y, x==y...), function calls (which can also introduce an edge if you are doing inter-procedural building) and whichever other constructs your language may have (in your example, Java has type annotations).

It is important to note that values shouldn't be nodes. So in a = b + 1, the node is the whole expression, and b and 1 aren't nodes. This may vary depending on your internal representation, but I think that it's a good guideline.

In your example, you are missing the nodes for:

leng = A.length;
n = 0;
res = true;

in the node 4, it should be the comparison (n < leng) instead of the while (while is control, it is already encoded as edges).

in the node 5, it should be the expression A[n] <= 0 && !boo[n] instead of if.

in node 7, there shouldn't be an arrow to node 8 (after the end of the while body, the control goes to the condition again)

in node 8, you are missing what you are returning (and return is also control, so it shouldn't be in the node)

Also, you should include the parameters of the function as local declarations.

Basic blocks are an optimization, you can build a perfectly fine CFG with just one command per node.

Creating a control flow graph for a given function

2 Answers2