PROGRAM 15:

Write a program to perform constant propagation.

ALGORITHM:

1. For all 4-tuples do 
   1.1 get next 4-tuple
   1.2 If the operator is "Label" then 
        1.2.1 free the constant table
        1.2.2 write the 4-tuple
 1.3 If either or both of the operands are in the constant table then
       1.3.1 substitute the constant value(s) for the operand(s) 
       1.3.2 if either of the operands are intermediate results then  
               1.3.2.1 remove those operand(s) from the constant table. 
1.4 if 4-tuple operand(s) are constant then 
      1.4.1 if operator is "JPCT" then 
              1.4.1.1 if the operand is true then 
                         1.4.1.1.1 replace the JPCT with JP 
                         1.4.1.1.2 write the new 4-tuple else
                         1.4.1.1.3 eliminate the 4-tuple 
1.4.2  if operator is "=" then 
               1.4.2.1 place the variable and constant in the constant table 
               1.4.2.2 write the 4-tuple with the constant operand 
1.4.3 else 
              1.4.3.1 Perform the operation.
              1.4.3.2 Place the intermediate result name and constant value in the constant table.Else
 1.4.4  write the 4-tuple Consider the following sequence.

PROGRAM:

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<conio.h>
void input();
void output();
void change(int p,char *res);
void constant();
struct expr
{
char op[2],op1[5],op2[5],res[5];
int flag;
}arr[10];
int n;
void main()
{
clrscr();
input();
constant();
output();
getch();
}
void input()
{
int i;
printf("\n\nEnter the maximum number of  expressions : ");
scanf("%d",&n);
printf("\nEnter the input : \n");
for(i=0;i<n;i++)
{
scanf("%s",arr[i].op);
scanf("%s",arr[i].op1);
scanf("%s",arr[i].op2);
scanf("%s",arr[i].res);
arr[i].flag=0;
}
}
void constant()
{
int i;
int op1,op2,res;
char op,res1[5];
for(i=0;i<n;i++)
{
if(isdigit(arr[i].op1[0]) && isdigit(arr[i].op2[0]) || strcmp(arr[i].op,"=")==0) /*if both digits, store them in variables*/
{
op1=atoi(arr[i].op1);
op2=atoi(arr[i].op2);
op=arr[i].op[0];
switch(op)
{
case '+':
res=op1+op2;
break;
case '-':
res=op1-op2;
break;
case '*':
res=op1*op2;
break;
case '/':
res=op1/op2;
break;
case '=':
res=op1;
break;
}
sprintf(res1,"%d",res);
arr[i].flag=1; /*eliminate expr and replace any operand below that uses result of this expr */
change(i,res1);
}
}
}
void output()
{
int i=0;
printf("\nOptimized code is : ");
for(i=0;i<n;i++)
{
if(!arr[i].flag)
{
printf("\n%s %s %s %s",arr[i].op,arr[i].op1,arr[i].op2,arr[i].res);
}
}
}
void change(int p,char *res)
{
int i;
for(i=p+1;i<n;i++)
{
if(strcmp(arr[p].res,arr[i].op1)==0)
strcpy(arr[i].op1,res);
else if(strcmp(arr[p].res,arr[i].op2)==0)
strcpy(arr[i].op2,res);
}
}


INPUT:

Enter the maximum number of  expressions : 4

Enter the input :
= 3 - a
+ a b t1
+ a c t2
+ t1 t2 t3

OUTPUT:

Optimized code is :
+ 3 b t1
+ 3 c t2
+ t1 t2 t3