Download - 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
-
8/8/2019 Code Gen Ankit Awal
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 -
8/8/2019 Code Gen Ankit Awal
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) -
8/8/2019 Code Gen Ankit Awal
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) -
8/8/2019 Code Gen Ankit Awal
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
-
8/8/2019 Code Gen Ankit Awal
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--;
-
8/8/2019 Code Gen Ankit Awal
7/23
}
top--;
return top;
}
cout
-
8/8/2019 Code Gen Ankit Awal
8/23
-
8/8/2019 Code Gen Ankit Awal
9/23
-
8/8/2019 Code Gen Ankit Awal
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};
-
8/8/2019 Code Gen Ankit Awal
11/23
char *p;
static int reg=49,temp=49,chk;
if(((65
-
8/8/2019 Code Gen Ankit Awal
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
-
8/8/2019 Code Gen Ankit Awal
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
-
8/8/2019 Code Gen Ankit Awal
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);
-
8/8/2019 Code Gen Ankit Awal
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
-
8/8/2019 Code Gen Ankit Awal
16/23
while(1)
{
top=func(oprtr,opnd,top,expr[i]);
i++;
if(top==0)
break;
}
cout
-
8/8/2019 Code Gen Ankit Awal
17/23
}
}
show(stack[stackPtr]);
getch();
coutl);
r=show(root->r);
cout
-
8/8/2019 Code Gen Ankit Awal
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--]);
}
-
8/8/2019 Code Gen Ankit Awal
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;
-
8/8/2019 Code Gen Ankit Awal
20/23
}
int chkElement(char element)
{
switch(element)
{
case '+':
case '-':
case '*':
case '/':
case '%':
-
8/8/2019 Code Gen Ankit Awal
21/23
case '^':
return(Operator);
default:
return(notOperator);
}
}
-
8/8/2019 Code Gen Ankit Awal
22/23
OUTPUT
-
8/8/2019 Code Gen Ankit Awal
23/23