7A. Implement control flow analysis

Ex. No: 7A

Date:

7A.  Implement control flow analysis

AIM:

  To write a C program to implement Control Flow Analysis.


INTRODUCTION:

Control flow analysis can be represented by basic blocks. It depicts how the program control is being passed among the blocks.

ALGORITHM:

Step-1: Start the Program Execution.

Step-2: Declare the necessary variables for accessing statements from cdp7.txt
Step-3: Find out the Leaders, Conditional Statements and blocks from the file.
Step-4: Display the blocks with Block No.
Step-5: Display the Control flow movement with block Number.
Step-6: Stop the Program Execution.

PROGRAM

CDP7A.C
# include<stdio.h>
# include<conio.h>
#include<alloc.h>
#include<string.h>
struct Listnode
{
char data[50];
int leader,block,u_goto,c_goto;
struct Listnode *next;
char label[10],target[10];
}*temp,*cur,*first=NULL,*last=NULL,*cur1;

FILE *fpr;
void createnode(char code[50])
{
temp=(struct Listnode *)malloc(sizeof(struct Listnode));
strcpy(temp->data,code);
strcpy(temp->label,'\0');
strcpy(temp->target,'\0');

temp->leader=0;
temp->block=0;
temp->u_goto=0;
temp->c_goto=0;
temp->next=NULL;

if(first==NULL)
{
first=temp;
last=temp;
}
else
{
last->next=temp;
last=temp;
}
}

void main()
{
char codeline[50];
char c,dup[50],target[10];
char *substring,*token;
int i=0,block,block1;
int j=0;
fpr= fopen("CDP7.txt","r");
clrscr();
while((c=getc(fpr))!=EOF)
{
if(c!='\n')
{
codeline[i]=c;
i++;
}
else
{
codeline[i]='\0';
createnode(codeline);
i=0;
}
}
//create last node
codeline[i]='\0';
createnode(codeline);
fclose(fpr);
// find out leaders,conditional stmts
cur=first;
cur->leader=1;
while(cur!=NULL)
{
substring=strstr((cur->data),"if");
if(substring==NULL)
{
if((strstr((cur->data),"goto"))!=NULL)
{
cur->u_goto=1;
(cur->next)->leader=1;
}
}
else
{
cur->c_goto=1;
(cur->next)->leader=1;
}
substring=strstr((cur->data),":");
if(substring!=NULL)
{
cur->leader=1;
}
substring=strstr((cur->data),"call");
if(substring!=NULL)
{
cur->leader=1;
}
if(strstr(cur->data,"return")!=NULL)
{
cur->leader=1;
(cur->next)->leader=1;
}
cur=cur->next;
}
//to find labels and targets
cur=first;
while(cur!=NULL)
{
if((cur->u_goto==1)||(cur->c_goto==1))
{
substring=strstr(cur->data,":");
if(substring!=NULL)
{
token=strstr(substring,"L" );
if(token!=NULL)
strcpy(cur->target,token);
}
else
{
substring=strstr(cur->data,"L");
if(substring!=NULL)
strcpy(cur->target,substring);
}
}

if(strstr(cur->data,":")!=NULL)
{
strcpy(dup,cur->data);
token=strtok(dup,":");
// printf("\ntoken:%s",token);
if(token!=NULL)
strcpy(cur->label,token);
}
cur=cur->next;
}
//to identify blocks
cur=first;
while(cur!= NULL)
{
cur=cur->next;
if((cur->leader)==1)
{
j++;
cur->block=j;
}
else
cur->block=j;
}
printf("\n\n......Basic Blocks......\n");
cur=first;
j=0;
printf("\nBlock %d:",j);
while(cur!=NULL)
{

if ((cur->block)==j)
{

printf("%s",cur->data);
printf("\n\t");
cur=cur->next;
}
else
{
j++;
printf("\nBlock %d:",j);
}

}
//to output the control flow from each block
printf ("\t\t.......Control Flow.......\n\n");
cur=first;
i=0;
while(cur!=NULL)
{
if((cur->block)!=(cur->next)->block)
{
block=cur->block;
if(cur->u_goto==1)
{
strcpy(target,cur->target);
cur1=first;
while(cur1!=NULL)
{
if(strcmp(cur1->label,target)==0)
{
block1=cur1->block;
printf("\t\tBlock%d---------->Block%d\n",block,block1);
}
cur1=cur1->next;
}
}
else if(cur->c_goto==1)
{
strcpy(target,cur->target);
cur1=first;
while(cur1!=NULL)
{
if(strcmp(cur1->label,target)==0)
{
block1=cur1->block;
printf("\t\tBlock%d---TRUE--->Block%d---FALSE--->Block%d\n",block,block1,(block+1));
}
cur1=cur1->next;
}
}
else if(strstr(cur->data,"return")==NULL)
{
printf("\t\tBlock%d---------->Block%d\n",block,(block+1));
}
else
printf("\t\tBlock%d---------->NULL\n",block);
}

cur=cur->next;
}
cur=last;
block= cur->block;
printf("\t\tBlock%d--------->NULL",block);
getch();
}




CDP7.TXT

m <- 0
v <- 0
L1 :  if v < n goto L2
r <- v
s <- 0
return
L2 : if r >= n goto L1
v <- v + 1

OUTPUT:

......Basic Blocks......

Block 0:m <- 0
        v <- 0

Block 1:L1 :  if v < n goto L2

Block 2:r <- v
        s <- 0

Block 3:return

Block 4:L2 : if r >= n goto L1

Block 5:v <- v + 1

.......Control Flow.......

                Block0---------->Block1
                Block 1---TRUE--->Block 4---FALSE--->Block 2   
                Block2---------->Block3
Block3---------->NULL
Block 4---TRUE--->Block 1---FALSE--->Block 5
                Block5--------->NULL












RESULT:

Thus the above program is compiled and executed successfully and output is verified.