2
$\begingroup$

Control flow graphs

Considering above terminologies for drawing control flow graphs for any program, it is very simple. For example :

While A
if B
do ..
else do ..
end while

For above example, while doing decomposition, I can say its

D2 (D1)

i.e while and then inside while, its if-then-else.

Considering same situation. How can you represent

CONTINUE and BREAK statements

Ever for FOR statement there is no defined terminology like for while and if then else. FOR statement falls under while.

My prof says in theory, there is nothing about Break and continue statement and I couldnt find anything online too.

For example :

# include <stdio.h>
int main(){
   float num,average,sum;
   int i,n;
   printf("Maximum no. of inputs\n");
   scanf("%d",&n);
   for(i=1;i<=n;++i){
       printf("Enter n%d: ",i);
       scanf("%f",&num);
       if(num<0.0)
       break;                     //for loop breaks if num<0.0
       sum=sum+num;
}
  average=sum/(i-1);       
  printf("Average=%.2f",average);
  return 0;
}

Control flow graph for this is as below: the nodes has line number written : (Sorry the image is side ways) enter image description here

I decomposed this as :

P1;P1;D2(P1;P1;D1);P1

* P1 represents set of statements outside loops

I'm not sure if this is correct. My professors says to use something as D22 for break, like create a new term from above image.

My main question here is the decomposition. I Know that i drew the CFG correctly, but is the decomposition correct according to the first image?. The break state kind of creates a while as you can see in CFG, but i'm not sure if it has to be considered as while and I guess we cannot, as per my professor.

I am working on this and wanted to know, if anyone has come across something for Break and continue statements while decomposition of graphs, please let me know.

Thanks.

PS : Please, Let me know, if am unclear and if anymore info is needed. I can probably write down an example and upload the picture.

$\endgroup$
  • 1
    $\begingroup$ A continue is a jump to the beginning of the loop, and a break is the jump to the statement following the loop. Do you want anything more? $\endgroup$ – Yuval Filmus Apr 18 '14 at 3:36
  • $\begingroup$ Hey, Thanks. I know what continue and break do, and I drew the control flow graph accordingly. My main concern is decomposition. I need to know, how to decompose the CFG, especially when break comes into picture. Because the break kind of creates another while loop as per CFG, but i cannot consider it as a while, I guess. I hope I am clear now. Thanks $\endgroup$ – Polynomial Proton Apr 18 '14 at 3:39
  • 1
    $\begingroup$ You can implement continue as an if, and break as an if which in addition modifies the loop condition. I'm not sure that is enlightening for your applications. $\endgroup$ – Yuval Filmus Apr 18 '14 at 4:30
  • $\begingroup$ Despite all the verbiage, I can't understand what you are asking. Can you give a concise summary of the question? Are you asking, given a CFG, find a decomposition into structured control flow? I think there might known impossibility results if you want to map it perfectly in all cases, without extra variables (e.g., irreducible graphs), but all of them can be handled if you are willing to add extra variables and if-statements. What research have you done? Have you done a search on decompilation of control-flow graphs? $\endgroup$ – D.W. Apr 18 '14 at 20:19
  • $\begingroup$ Hey, thanks for asking. My question is already answered by Wandering logic. I was looking for how to represent Break and Continue statements. Anyway, thanks. $\endgroup$ – Polynomial Proton Apr 19 '14 at 0:03
3
$\begingroup$

There are many different kinds of control-flow constructs that only map to "structured programming" (tree decomposition) constructs when you add extra data variables and extra tests. continue is usually okay (as long as its not nested any deeper), but break is one of the hard ones. Another relatively painful case is short-circuit conditional evaluation.

A preprocessing step of converting while x stmt to if x repeat stmt until not(x) will make everything a little easier (and you want to do this anyway, because it lets you safely optimize loop invariants). Example:

while i<=n:
  something
  if condition break
  something_else
  i = i+1

becomes

if i<=n:
  repeat:
    something
    if condition break
    something_else
    i = i+1
  until not(i<=n)

A second preprocessing step of saving the (possibly complicated) calculation of the loop condition as a boolean temporary variable will also help. So:

if i<=n:
  repeat:
    something
    if condition break
    something_else
    i = i+1
    t0 = not(i<=n)
  until t0

Now we can convert our break into a if-else:

if i<=n:
  repeat:
    something
    if condition:
      t0 = false
    else:
      something_else
      i = i+1
      t0 = not(i<=n)
  until t0

So we've converted, but the result is kind of ugly: we now have to keep track of t0 and we have two tests where we only had one before. "Structured programming" is not the panacea it is often made out to be.

$\endgroup$
  • $\begingroup$ Awesome, this works out. But like you said, the result is increasing work, since we need to keep track of t0 too. Is there any other way too, you know of, to implement this? I couldnt find anything in theory about this. How do people treat this situation in professional world? Although this works out, I'm curious to know about different ways to handle such conditions. Thanks a lot for the explanation too :) $\endgroup$ – Polynomial Proton Apr 18 '14 at 19:15
  • 1
    $\begingroup$ I think it's impossible to convert to tree form without adding extra work. In the "professional world" people don't convert to tree form, modern compilers tend to work directly on the control-flow graph. I've worked on research parallelizing compilers (SUIF) in the late 1990s that needed tree-form, and they did what I described above. $\endgroup$ – Wandering Logic Apr 18 '14 at 20:05
  • $\begingroup$ Awesome, thanks for the answers. So informative and detailed. $\endgroup$ – Polynomial Proton Apr 19 '14 at 0:00

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.