in Compiler Design
605 views
0 votes
0 votes
  1. i=10
  2. j=1
  3. a=i*j
  4. b=i+j
  5. if a<=b goto 3
  6. else goto 8
  7. a=a+1
  8. i=i-1 goto 2           

    Include start and end nodes

  Find the number of nodes and edges in the control flow graph of the above code?

in Compiler Design
605 views

1 Answer

2 votes
2 votes

Correct Answer: 8 nodes and 10 edges 

To draw the Control Flow Graph, we have to find the number of basic blocks for given code snippet.

A Basic Block is a sequence of instructions where control enters at the beginning of the statement and leave at the end without any halt (except the last statement of the block).

To find number of basic blocks, we have to find the identify of leaders in the code. The rules for finding leaders are as follows:

  1. First statement in the code is always a leader.
  2. Statement that is target of an conditional or unconditional goto statement like: if....goto L or goto L is always a leader.
  3. Statement which immediately follows a conditional or unconditional goto statement is always a leader

Now, that we have found the leader statements, the basic block consists statements starting from one leader and all statement up to another leader, and not including the next leader.

The leaders and basic blocks for given code snippet:

The CFG for given code snippet:

As we can see, CFG has 8 nodes and 10 edges.

4 Comments

@girish13 But why at the end you have written stop because the program will never end.

0
0

Great ans @girish13

1
1

Thankyou :) @raja11sep

 

1
1
How control (edge)can go from B4 to B5 basic block,as unconditional goto have only one successor in control flow graph ,so there should be 8 node and 9 edges
0
0

Related questions