optimization techniques: a)common sub-expression elimination b)variable propagation

###### tac.txt #######
1 + b a rep
2 * 2 c a
3 := c - res
4 + b a no1
5 - res no1 res
6 + 3 5 temp
7 := temp - x
8 * x c res1

###### pr_9.c ########

/*
8) WAP to implement following code optimization techniques:
   a)common sub-expression elimination   b)variable propagation
*/
#include<stdio.h>

struct holder
{
char seqno[3],op[3],arg1[8],arg2[8],result[8];
}tac[50];
int cnt=0,i,j,k,used=0;
char hunted[8];
void removeline()
{
for(k=j;k<=cnt;k++)
tac[k]=tac[k+1];
cnt--;
}
void eliminate()
{
//hunt value which having op arg1 arg2 same jst result different
for(i=0;i<cnt;i++)
{
used=0;
for(j=i+1;j<cnt;j++)
{
if(strcmp(tac[j].result,tac[i].result)==0||strcmp(tac[i].arg1,tac[j].result)==0 || strcmp(tac[i].arg2,tac[j].result)==0)
used=1;
if(strcmp(tac[j].op,tac[i].op)==0 && strcmp(tac[j].arg1,tac[i].arg1)==0 && strcmp(tac[j].arg2,tac[i].arg2)==0 && !used)
{
//remove this line and replace result field by original result ie of i th location
strcpy(hunted,tac[j].result);
for(k=j+1;k<cnt;k++)
{
if(strcmp(tac[k].arg1,hunted)==0)
strcpy(tac[k].arg1,tac[i].result);
if(strcmp(tac[k].arg2,hunted)==0)
strcpy(tac[k].arg2,tac[i].result);
}
removeline();
}
}
}
}
void var_propo()
{
//hunt var1 = var2 and insted of var2 replece var1
for(i=0;i<cnt;i++)
{
if(strcmp(tac[i].op,":=")==0 && strcmp(tac[i].arg2,"-")==0)
{
strcpy(hunted,tac[i].result);
for(k=i+1;k<cnt;k++)
{
if(strcmp(tac[k].arg1,hunted)==0)
strcpy(tac[k].arg1,tac[i].arg1);
if(strcmp(tac[k].arg2,hunted)==0)
strcpy(tac[k].arg2,tac[i].arg1);
}

}
}
}
int main()
{
FILE * fin =fopen("tac.txt","r");
int i;
while(!feof(fin))
{
fscanf(fin,"%s%s%s%s%s",tac[cnt].seqno,tac[cnt].op,tac[cnt].arg1,tac[cnt].arg2,tac[cnt].result);
cnt++;
}
cnt--;
printf("\n\t\t*** PURE INPUT ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}
eliminate();
var_propo();
printf("\n\t\t*** After Process ****");
printf("\n\tIndex\tOP\tArg1\tArg2\tResult");
for(i=0;i<cnt;i++)
{
printf("\n\t%s\t%s\t%s\t%s\t%s",tac[i].seqno,tac[i].op,tac[i].arg1,tac[i].arg2,tac[i].result);
}

fclose(fin);
}

##### output #######

*** PURE INPUT ****

Index OP Arg1 Arg2 Result

1 + b a c

2 * 2 c c

3 := c - res

4 + b a no1

5 - res no1 res

6 + 3 5 temp

7 := temp - x

8 * x c res1

*** After Process ****

Index OP Arg1 Arg2 Result

1 + b a c

2 * 2 c c

3 := c - res

5 - c c res

6 + 3 5 temp

7 := temp - x

8 * temp c res1

pr@prashant-HP:~/LEX&YACC/9$