Sunday 13 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 language, check Previous 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.cpp)
 
#include<stdlib.h>
#include<iostream>
using namespace std;

/* 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 bin_tree node;

class dag
{
private:
/* 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;

public:

void initializestack(node *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 */
    int temp=top;
    for(int i=0;i<=top;i++)
       {
          R[i]=temp;
          temp--;
       }
}

/* 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);

    cout << "\nEnter number of children of " << val <<" :";
    cin >> numofchildren;

  if(numofchildren==2)
   {
    cout << "\nEnter Left Child of " << val <<" :";
    cin >> l;
    insertnode(&(*tree)->left,l);

    cout << "\nEnter Right Child of " << val <<" :";
    cin >> 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);
        cout << tree->data <<" with Label "<< tree->label << "\n";
        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 */

void  nameofoperation(char temp)
{
switch(temp)
{
case '+': op =(char *)"ADD"; break;
case '-': op =(char *)"SUB"; break;
case '*': op =(char *)"MUL"; break;
case '/': op =(char *)"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)
{
cout << "MOV "<< tree->left->data << "," << "R[" << R[top] << "]\n";
nameofoperation(tree->data);
cout << op << " " << tree->right->data << ",R[" << R[top] << "]\n";
}

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

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

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

}

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

}

/* 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 */

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

    dag d;
   
    /* Inserting nodes into tree(DAG) */

    cout << "\nEnter root of tree:";
    cin >> val;

    d.insert(&root,val);

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

    /* Finding Labels of Interior nodes */
    while(root->label == -1)
       d.findinteriornodelabel(root);
    /* Initializing Stack contents and top variable */
    d.initializestack(root);

    /* Printing inorder of nodes of tree(DAG) */
    cout << "\nInorder Display:\n";
    d.print_inorder(root);
   
    /* Printing assembly code w.r.t. labels of tree(DAG) */
    cout << "\nAssembly Code:\n";
    d.gencode(root);
      
    /* Deleting all nodes of tree */
    d.deltree(root);

    return 0;
}



How To Run:
To Compile:
>>>g++ codegeneration.cpp

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,

Example3
For following DAG,
Code generation will be as follows,



Next: Vedic mathematics method to find a square of a number  

Previous: Code generation using DAG / labeled tree - C Language Implementation


5 comments:

  1. it is giving error as segmentation fault, core dumped

    ReplyDelete
    Replies
    1. Just now I checked it, it is working correctly. Here I used single character for each node of tree. You might have used double characters like [ ], for any node. That may be the reason for your error.

      Delete
  2. why are we swapping in gencode()

    ReplyDelete
    Replies
    1. We store the result of left subtree into top register. In case, when right subtree's root has higher label than left one, we have to evaluate right subtree first. Hence we swap the registers. After processing right subtree, again we swap the registers.

      Delete
  3. This won't work for DAG containing common sub-expression ?

    ReplyDelete