## Tuesday 8 September 2015

### Code generation using DAG / labeled tree - C Language Implementation

In this post, we will see C language implementation of Code Generation using DAG / Labeled tree. (For implementation in  C++, check Next Post).
Code Generation is the last phase among the six phases of compilation.
We will see algorithms for Labeling the nodes of tree(DAG) and Code Generation using DAG /Labeled tree followed by their implementation in C language. These algorithms take input of tree(DAG).
At the end of this post, I have provided two examples.

Algorithm for labeling the nodes of tree(DAG):

1. For Leaf Nodes
Assign label 1 to left child node and label 0 to right child node.

2. For Interior Nodes
Case 1: If Node's children's labels are different, then
Node's Label = Maximum among Children's Labels.
Case 2: If Node's children's labels are same, then
Node's Label = (Left Child's Label OR Right Child's Label) + 1.

Following Algorithm for Generating Assembly Code requires a Stack of registers. Number of registers in stack=Label of Root of DAG. As indices start from 0, index of topmost element(i.e. top)=Label of Root - 1.

Algorithm for Generating Assembly Code:
(Say, R is a Stack consists of registers.)
void gencode(Node)
{
if Node is intermediate node of tree(DAG)

{
Case 1: if Node's left child's label == 1 && Node's right child's label == 0 && Node's left child is leaf node && Node's right child is leaf node

{
print "MOV Node's left child's data,R[top]"
print "op Node's right child's data,R[top]"
}

Case 2: else if Node's left child's label >= 1 && Node's right child's label == 0
{
gencode(Node's left child);
print "op Node's right child's data,R[top]"

}

Case 3: else if Node's left child's label < Node's right child's label

{
int temp;
Swap Register Stack's top and second top element;
gencode(Node's right child);
temp=pop();
gencode(Node's left child);
push(temp);

Swap Register Stack's top and second top element;
print "op R[top-1],R[top]"
}

Case 4: else if Node's left child's label >= Node's right child's label

{
int temp;
gencode(Node's left child);
temp=pop();
gencode(Node's right child);
push(temp);
print "op R[top-1],R[top]"

}

}

else if Node is leaf node and it is left child of it's immediate parent
{
print "MOV Node's data,R[top]"

}

}

Program: (codegeneration.c)
#include<stdlib.h>
#include<stdio.h>

/* We will implement DAG as Strictly Binary Tree where each node has zero or two children */

struct bin_tree
{
char data;
int label;
struct bin_tree *right, *left;
};
typedef struct bin_tree node;

/* R is stack for storing registers */
int R[10];
int top;

/* op will be used for opcode name w.r.t. arithmetic operator e.g. ADD for + */
char *op;

/* insertnode() and insert() functions are for adding nodes to tree(DAG) */

void insertnode(node **tree,char val)
{
node *temp = NULL;

if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
temp->label=-1;
*tree = temp;
}
}

void insert(node **tree,char val)
{
char l,r;
int numofchildren;

insertnode(tree, val);

printf("\nEnter number of children of %c:",val);
scanf("%d",&numofchildren);

if(numofchildren==2)
{
printf("\nEnter Left Child of %c:",val);
scanf("%s",&l);
insertnode(&(*tree)->left,l);

printf("\nEnter Right Child of %c:",val);
scanf("%s",&r);
insertnode(&(*tree)->right,r);

insert(&(*tree)->left,l);
insert(&(*tree)->right,r);
}
}

/* findleafnodelabel() will find out the label of leaf nodes of tree(DAG) */

void findleafnodelabel(node *tree,int val)
{

if(tree->left != NULL && tree->right !=NULL)
{
findleafnodelabel(tree->left,1);
findleafnodelabel(tree->right,0);
}

else
{
tree->label=val;
}

}

/* findinteriornodelabel() will find out the label of interior nodes of tree(DAG) */

void findinteriornodelabel(node *tree)
{
if(tree->left->label==-1)
{
findinteriornodelabel(tree->left);
}

else if(tree->right->label==-1)
{
findinteriornodelabel(tree->right);
}

else
{

if(tree->left != NULL && tree->right !=NULL)
{

if(tree->left->label == tree->right->label)
{

tree->label=(tree->left->label)+1;
}

else
{

if(tree->left->label > tree->right->label)
{
tree->label=tree->left->label;
}
else
{
tree->label=tree->right->label;
}

}
}
}
}

/* function print_inorder() will print inorder of nodes. Here we are also printing label of each node of tree(DAG) */

void print_inorder(node * tree)
{
if (tree)
{
print_inorder(tree->left);
printf("%c with Label %d\n",tree->data,tree->label);
print_inorder(tree->right);
}
}

/* function swap() will swap the top and second top elements of Register stack R */

void swap()
{
int temp;
temp=R[0];
R[0]=R[1];
R[1]=temp;
}

/* function pop() will remove and return topmost element of stack */

int pop()
{
int temp=R[top];
top--;
return temp;
}

/* function push() will increment top by one and will insert element at top position of Register stack */

void push(int temp)
{
top++;
R[top]=temp;
}

/* nameofoperation() will return opcode w.r.t. arithmetic operator */

char* nameofoperation(char temp)
{
switch(temp)
{
case '-': return "SUB"; break;
case '*': return "MUL"; break;
case '/': return "DIV"; break;
}
}

/* gencode() will generate Assembly code w.r.t. labels of tree(DAG) */

void gencode(node * tree)
{
if(tree->left != NULL && tree->right != NULL)
{
if(tree->left->label == 1 && tree->right->label == 0 && tree->left->left==NULL && tree->left->right==NULL && tree->right->left==NULL && tree->right->right==NULL)
{
printf("MOV %c,R[%d]\n",tree->left->data,R[top]);
op=nameofoperation(tree->data);
printf("%s %c,R[%d]\n",op,tree->right->data,R[top]);
}

else if(tree->left->label >= 1 && tree->right->label == 0)
{
gencode(tree->left);
op=nameofoperation(tree->data);
printf("%s %c,R[%d]\n",op,tree->right->data,R[top]);
}

else if(tree->left->label < tree->right->label)
{
int temp;
swap();
gencode(tree->right);
temp=pop();
gencode(tree->left);
push(temp);
swap();
op=nameofoperation(tree->data);
printf("%s R[%d],R[%d]\n",op,R[top-1],R[top]);
}

else if(tree->left->label >= tree->right->label)
{
int temp;
gencode(tree->left);
temp=pop();
gencode(tree->right);
push(temp);
op=nameofoperation(tree->data);
printf("%s R[%d],R[%d]\n",op,R[top-1],R[top]);
}

}

else if(tree->left == NULL && tree->right == NULL && tree->label == 1)
{
printf("MOV %c,R[%d]\n",tree->data,R[top]);
}

}

/* deltree() will free the memory allocated for tree(DAG) */

void deltree(node * tree)
{
if (tree)
{
deltree(tree->left);
deltree(tree->right);
free(tree);
}
}

/* Program execution will start from main() function */

void main()
{
node *root;
root = NULL;
node *tmp;
char val;
int i,temp;

/* Inserting nodes into tree(DAG) */

printf("\nEnter root of tree:");
scanf("%c",&val);

insert(&root,val);

/* Finding Labels of Leaf nodes */
findleafnodelabel(root,1);

/* Finding Labels of Interior nodes */
while(root->label == -1)
findinteriornodelabel(root);

/* value of top = index of topmost element of stack R = label of Root of tree(DAG) minus one */
top=root->label - 1;

/* Allocating Stack Registers */
temp=top;
for(i=0;i<=top;i++)
{
R[i]=temp;
temp--;
}

/* Printing inorder of nodes of tree(DAG) */
printf("\nInorder Display:\n");
print_inorder(root);

/* Printing assembly code w.r.t. labels of tree(DAG) */
printf("\nAssembly Code:\n");
gencode(root);

/* Deleting all nodes of tree */
deltree(root);
}

How To Run:
To Compile:
>>>gcc codegeneration.c

To Run:
>>>./a.out

Output:
Example 1
For following DAG,
Code Generation will be as follows,

Example 2
For following DAG,
Code Generation will be as follows,

Example 3
For following dag,
Code generation will be as follows,

Check Other Posts on Compiler