code gen ankit awal

8/8/2019 Code Gen Ankit Awal

1/23

PROBLEM

Develop the code generator which can incorporate the following:

a) Parentheses, multiplication, addition, subtraction, division operators.

b) 5 registers.

c) Generates the postfix expression.

d) Generates an expression tree.

SOLUTION


2/23

CODE GENERATOR

In computer science, code generation is the process by which a compiler'scode generator converts some intermediate representation ofsource codeinto a form (e.g., machine code) that can be readily executed by a machine(often a computer).

Sophisticated compilers typically perform multiple passes over variousintermediate forms. This multi-stage process is used because many

algorithms for code optimization are easier to apply one at a time, orbecause the input to one optimization relies on the processing performed byanother optimization. This organization also facilitates the creation of asingle compiler that can target multiple architectures, as only the last of thecode generation stages (the backend) needs to change from target to target.(For more information on compiler design, see Compiler.)

The input to the code generator typically consists of a parse tree or anabstract syntax tree. The tree is converted into a linear sequence ofinstructions, usually in an intermediate language such as three address code.Further stages of compilation may or may not be referred to as "code

generation", depending on whether they involve a significant change in therepresentation of the program. (For example, a peephole optimization passwould not likely be called "code generation", although a code generatormight incorporate a peephole optimization pass.)
http://en.wikipedia.org/wiki/Computer_sciencehttp://en.wikipedia.org/wiki/Compilerhttp://en.wikipedia.org/wiki/Intermediate_representationhttp://en.wikipedia.org/wiki/Source_codehttp://en.wikipedia.org/wiki/Machine_codehttp://en.wikipedia.org/wiki/Computerhttp://en.wikipedia.org/wiki/Algorithmshttp://en.wikipedia.org/wiki/Code_optimizationhttp://en.wikipedia.org/wiki/Compilerhttp://en.wikipedia.org/wiki/Parse_treehttp://en.wikipedia.org/wiki/Abstract_syntax_treehttp://en.wikipedia.org/wiki/Intermediate_languagehttp://en.wikipedia.org/wiki/Three_address_codehttp://en.wikipedia.org/wiki/Peephole_optimizationhttp://en.wikipedia.org/wiki/Computer_sciencehttp://en.wikipedia.org/wiki/Compilerhttp://en.wikipedia.org/wiki/Intermediate_representationhttp://en.wikipedia.org/wiki/Source_codehttp://en.wikipedia.org/wiki/Machine_codehttp://en.wikipedia.org/wiki/Computerhttp://en.wikipedia.org/wiki/Algorithmshttp://en.wikipedia.org/wiki/Code_optimizationhttp://en.wikipedia.org/wiki/Compilerhttp://en.wikipedia.org/wiki/Parse_treehttp://en.wikipedia.org/wiki/Abstract_syntax_treehttp://en.wikipedia.org/wiki/Intermediate_languagehttp://en.wikipedia.org/wiki/Three_address_codehttp://en.wikipedia.org/wiki/Peephole_optimization


3/23

MAJOR TASK IN CODE GENERATOR

In addition to the basic conversion from an intermediate representation intoa linear sequence of machine instructions, a typical code generator tries tooptimize the generated code in some way. The generator may try to usefaster instructions, use fewer instructions, exploit available registers, andavoid redundant computations.

Tasks which are typically part of a sophisticated compiler's "codegeneration" phase include:

Instruction selection: which instructions to use. Instruction scheduling: in which order to put those instructions.

Scheduling is a speed optimization that can have a critical effect onpipelined machines. Register allocation: the allocation ofvariables to processor registers.

Instruction selection is typically carried out by doing a recursivepostordertraversal on the abstract syntax tree, matching particular tree configurationsagainst templates; for example, the tree W := ADD(X,MUL(Y,Z)) might betransformed into a linear sequence of instructions by recursively generatingthe sequences for t1 := X and t2 := MUL(Y,Z), and then emitting the instructionADD W, t1, t2.

In a compiler that uses an intermediate language, there may be twoinstruction selection stages one to convert the parse tree intointermediate code, and a second phase much later to convert theintermediate code into instructions from the instruction set of the targetmachine. This second phase does not require a tree traversal; it can be donelinearly, and typically involves a simple replacement of intermediate-language operations with their corresponding opcodes. However, if thecompiler is actually a language translator (for example, one that convertsEiffel to C), then the second code-generation phase may involve building atree from the linear intermediate code.
http://en.wikipedia.org/wiki/Processor_registerhttp://en.wikipedia.org/wiki/Partial_redundancy_eliminationhttp://en.wikipedia.org/wiki/Instruction_selectionhttp://en.wikipedia.org/wiki/Instruction_schedulinghttp://en.wikipedia.org/wiki/Instruction_pipelinehttp://en.wikipedia.org/wiki/Register_allocationhttp://en.wikipedia.org/wiki/Variable_(programming)http://en.wikipedia.org/wiki/Processor_registerhttp://en.wikipedia.org/wiki/Recursionhttp://en.wikipedia.org/wiki/Postorder_traversalhttp://en.wikipedia.org/wiki/Postorder_traversalhttp://en.wikipedia.org/wiki/Instruction_sethttp://en.wikipedia.org/wiki/Opcodehttp://en.wikipedia.org/wiki/Transcompilerhttp://en.wikipedia.org/wiki/Eiffel_(programming_language)http://en.wikipedia.org/wiki/C_(programming_language)http://en.wikipedia.org/wiki/Processor_registerhttp://en.wikipedia.org/wiki/Partial_redundancy_eliminationhttp://en.wikipedia.org/wiki/Instruction_selectionhttp://en.wikipedia.org/wiki/Instruction_schedulinghttp://en.wikipedia.org/wiki/Instruction_pipelinehttp://en.wikipedia.org/wiki/Register_allocationhttp://en.wikipedia.org/wiki/Variable_(programming)http://en.wikipedia.org/wiki/Processor_registerhttp://en.wikipedia.org/wiki/Recursionhttp://en.wikipedia.org/wiki/Postorder_traversalhttp://en.wikipedia.org/wiki/Postorder_traversalhttp://en.wikipedia.org/wiki/Instruction_sethttp://en.wikipedia.org/wiki/Opcodehttp://en.wikipedia.org/wiki/Transcompilerhttp://en.wikipedia.org/wiki/Eiffel_(programming_language)http://en.wikipedia.org/wiki/C_(programming_language)


4/23

RUNTIME CODE GENERATION

When code generation occurs at runtime, as injust-in-time compilation (JIT),

it is important that the entire process be efficient with respect to space and

time. For example, when regular expressions are interpreted and used to

generate code at runtime, a non-determistic finite state machine is often

generated instead of a deterministic one, because usually the former can be

created more quickly and occupies less memory space than the latter.

Despite its generally generating less efficient code, JIT code generation can

take advantage ofprofiling information that is available only at runtime.

C++ PROGRAM TO IMPLEMENT CODE GENERATOR

#include

#include

#include

#include

#include

#define Operator 1

#define notOperator 0

struct node

{ char item;

struct node *l,*r;

char ch;

};

struct node *result[20]={NULL};

//void tree1(char *);
http://en.wikipedia.org/wiki/Run_time_(computing)http://en.wikipedia.org/wiki/Just-in-time_compilationhttp://en.wikipedia.org/wiki/Algorithmic_efficiencyhttp://en.wikipedia.org/wiki/Regular_expressionhttp://en.wikipedia.org/wiki/Finite_state_machinehttp://en.wikipedia.org/wiki/Profiling_(computer_programming)http://en.wikipedia.org/wiki/Run_time_(computing)http://en.wikipedia.org/wiki/Just-in-time_compilationhttp://en.wikipedia.org/wiki/Algorithmic_efficiencyhttp://en.wikipedia.org/wiki/Regular_expressionhttp://en.wikipedia.org/wiki/Finite_state_machinehttp://en.wikipedia.org/wiki/Profiling_(computer_programming)


5/23

int func(char*,char*,int,char);

struct node* tree(char*,int);

void postorder(struct node*);

int stackPtr = -1;

int top2=0;

char tag[20][5];

char plist[2][2]={'-','+','*','/'};

int priority(char,char);

void codegen(struct node*);

int chktable(struct node*);

char *fetchtable(int);

void inserttable(struct node*,char*);

int func(char *opr,char *opd,int top,char c)

{

int chk;

if(((65


6/23

while(1)

{

chk=priority(c,opr[top]);

if(chk)

{

opd[top2]=opr[top];

top--;

top2++;

}

else{

top++;

opr[top]=c;

break;

}

}

return top;

}

else if(c==')'){

while(opr[top]!='(')

{

opd[top2]=opr[top];

top2++;

top--;


7/23

}

top--;

return top;

}

cout


8/23


9/23


10/23

top1--;

}

else

if(temp->r!=NULL)

{

ptr=temp->r;

top1++;

stkprv[top1]=temp;

}

else

{

codegen(temp);

top--;

ptr=NULL;

}

if(stack[top]==NULL)

break;

}

}

void codegen(struct node *ptr)

{

char c=ptr->ch,opr[5]={NULL},op1[5]={NULL},op2[5]={NULL};


11/23

char *p;

static int reg=49,temp=49,chk;

if(((65


12/23

else{

op2[0]=ptr->r->ch;

}

switch(c)

{

//opr=(char*)malloc(3*sizeof(char));

case '-':

strcpy(opr,"SUB");

break;

case '+':

strcpy(opr,"ADD");

break;

case '*':

strcpy(opr,"MUL");

break;

case '/':

strcpy(opr,"DIV");

}

// if(chk)

inserttable(ptr,op1);

cout


13/23

int priority(char a,char b)

{

static int i,j;

if((a=='(')||(b=='('))

return 0;

if(a==b)

return 1;

for(i=0;i


14/23

{

if(result[i]==ptr)

return i;

i++;

}

return 0;

}

char *fetchtable(int i)

{

return tag[i];

}

void inserttable(struct node *ptr,char *op)

{

int i=1;

while(result[i]!=NULL)

i++;

result[i]=ptr;

strcpy(tag[i],op);

}

int chkElement(char);

void opFunc(char);


15/23

void varFunc(char);

void push(struct node*);

struct node* pop(void);

void dispTree(void);

char show(struct node*);

void infix(struct node*);

void postfix(struct node*);

struct node* stack[25];

struct node* root;

void main()

{ clrscr();

struct node *start=NULL;

char in[32],expr[32],oprtr[10],opnd[32];

int top=0,i=0,n=0,count;

cout>in;

while(in[n]!=NULL)

n++;

for(i=0;i


16/23

while(1)

{

top=func(oprtr,opnd,top,expr[i]);

i++;

if(top==0)

break;

}

cout


17/23

}

}

show(stack[stackPtr]);

getch();

coutl);

r=show(root->r);

cout


18/23

root = (struct node*)malloc(sizeof(struct node));

root->item = optr;

root->r = pop();

root->l = pop();

push(root);

}

struct node* pop(void)

{

return(stack[stackPtr--]);

}


19/23

void varFunc(char var)

{

root = (struct node*)malloc(sizeof(struct node));

root->item = var;

root->r = NULL;

root->l = NULL;

push(root);

}

void push(struct node* root)

{

stack[++stackPtr] = root;


20/23

}

int chkElement(char element)

{

switch(element)

{

case '+':

case '-':

case '*':

case '/':

case '%':


21/23

case '^':

return(Operator);

default:

return(notOperator);

}

}


22/23

OUTPUT


23/23

code gen ankit awal

Documents