Code Generation

Introduction

Architecture

instruction-set opertions, instruction formats, addressing modes, data formats, CPU registers, I/O instructions, etc (conventional machine language)

front end

machine independent (lexical and syntactical analysis)

back end

code generation and optimization

maintainability

separation of concerns

portability

Machine Architectures

• Zero address architecture (stack machine)
• One address architecture (accumulator machine)
• Two address architecture
• Three address architecture (register machine)

As the source program is processed, it is converted to an internal form. The internal representation in the example is that of an implicit parse tree. Other internal forms may be used which resemble assembly code. The internal form is translated by the code generator into object code. Typically, the object code is a program for a virtual machine. The virtual machine chosen for Simple consists of three segments. A data segment, a code segment and an expression stack.

The data segment contains the values associated with the variables. Each variable is assigned to a location which holds the associated value. Thus, part of the activity of code generation is to associate an address with each variable. The code segment consists of a sequence of operations. Program constants are incorporated in the code segment since their values do not change. The expression stack is a stack which is used to hold intermediate values in the evaluation of expressions. The presence of the expression stack indicates that the virtual machine for Simple is a ``stack machine''.

Converting Atoms to Instructions

Single Pass vs. Multiple Passes

Single pass

code generation and address resolution integrated with the parser utilizing a fixup table.

Multiple pass

scan atoms determining label addresses, second scan generates code incorporating label addresses.

Register Allocation

Declaration translation

integer x,y,z.         DATA 2

Statement translation

x := expr            code for expr
                     STORE X

if cond then         code for cond
   S1                BR_FALSE L1
else                 code for S1
   S2                BR L2
end              L1: code for S2
                 L2:

while cond do    L1: code for cond
   S                 BR_FALSE L2
end                  code for S
                     BR L1
                 L2:

read X               IN_INT X

write expr           code for expr
                     OUT_INT

Expression translation

constant             LD_INT constant

variable             LD variable

e1 op e2             code for e1
                     code for e2
                     code for op

Function translation

• pseudo-instructions to announce the beginning of a function
• label definition for function name
• instructions to adjust the stack pointer
• instructions to save environment
• store instructions to save callee registers including return address register
• Function Body
• instruction to return result
• load instructions to restore callee-saved registers
• an instruction to reset the stack pointer
• a return instruction
• pseudo-instructions as needed to announce the end of the function

The Code Generator Module

int data_offset = 0;  
int data_location() { return data_offset++; }

}

int code_offset = 0; 
int reserve_loc()
{  
   return code_offset++;
}
int gen_label()          
{  
   return code_offset;
}

The functions gen_code and back_patch are used to generate code. gen_code generates code at the current offset while back_patch is used to generate code at some previously reserved address.

void gen_code( enum code_ops operation, int arg )
{ code[code_offset].op    = operation;
  code[code_offset++].arg = arg;
}
void back_patch( int addr,  enum code_ops operation, int arg  )
{
  code[addr].op  = operation;
  code[addr].arg = arg;
}

}

The Symbol Table Modifications

struct symrec
{
  char *name;                    /* name of symbol      */
  int offset;                    /* data offset         */
  struct symrec *next;           /* link field          */
};
...
symrec * putsym (char *sym_name)
{
  symrec *ptr;
  ptr = (symrec *) malloc (sizeof(symrec));
  ptr->name = (char *) malloc (strlen(sym_name)+1);
  strcpy (ptr->name,sym_name);
  ptr->offset = data_location();
  ptr->next = (struct symrec *)sym_table;
  sym_table = ptr;
  return ptr;
}
...

}

The Parser Modifications

%{#include <stdio.h>      /* For I/O                                 */
#include <stdlib.h>       /* For malloc here and in symbol table     */
#include <string.h>       /* For strcmp in symbol table              */
#include "ST.h"           /* Symbol Table                            */
#include "SM.h"           /* Stack Machine                           */
#include "CG.h"           /* Code Generator                          */
#define  YYDEBUG 1        /* For Debugging                           */
int  errors;              /* Error Count-incremented in CG, ckd here */
 struct  lbs              /* For labels: if and while                */
 {
  int for_goto;  
  int for_jmp_false;
  };         
struct lbs * newlblrec()  /* Allocate space for the labels           */
{
  return  (struct lbs *) malloc(sizeof(struct lbs));
}
install ( char *sym_name )
{
   symrec *s;
   s = getsym (sym_name);
   if (s == 0)
        s = putsym (sym_name);
   else { errors++;
          printf( "%s is already defined\n", sym_name );
   }
}
context_check( enum code_ops operation, char *sym_name )
{ symrec *identifier;
  identifier = getsym( sym_name );
  if ( identifier == 0 ) 
       { errors++;
         printf( "%s", sym_name );
         printf( "%s\n", " is an undeclared identifier"  );
       }
  else gen_code( operation, identifier->offset );
}
%}
%union semrec             /* The Semantic Records         */
{ 
 int     intval;          /* Integer values               */
 char    *id;             /* Identifiers                  */
 struct  lbs *lbls        /* For backpatching             */
} 
%start program
%token <intval>  NUMBER         /* Simple integer                   */
%token <id>      IDENTIFIER     /* Simple identifier                */
%token <lbls>    IF WHILE       /* For backpatching labels          */
%token SKIP THEN ELSE FI DO END  
%token INTEGER READ WRITE LET IN
%token ASSGNOP
%left '-' '+'
%left '*' '/'
%right '^' 
%% 
/* Grammar Rules and Actions */
%%
/* C subroutines */

}

The actions associated with code generation for a stack-machine based architecture are added to the grammar section. The code generated for the declaration section must reserve space for the variables.

/* C and Parser declarations */
%% 
program : LET 
             declarations
          IN           { gen_code( DATA, sym_table->offset );            }
             commands 
          END          { gen_code( HALT, 0 ); YYACCEPT;                  }
;
declarations : /* empty */
   | INTEGER id_seq IDENTIFIER '.' { install( $3 );                      }
;
id_seq : /* empty */
   | id_seq IDENTIFIER ','  { install( $2 );                             }
;

}

commands : /* empty */
   | commands command ';'
;
command : SKIP 
   | READ IDENTIFIER   { context_check( READ_INT, $2 );                  }
   | WRITE exp         { gen_code( WRITE_INT, 0 );                       }
   | IDENTIFIER ASSGNOP exp { context_check( STORE, $1 );                }

   | IF exp            { $1 = (struct lbs *) newlblrec();
                         $1->for_jmp_false = reserve_loc();              }
     THEN commands     { $1->for_goto = reserve_loc();                   }
     ELSE              { back_patch( $1->for_jmp_false, 
                                    JMP_FALSE, 
                                    gen_label() );                       }
          commands
     FI                { back_patch( $1->for_goto, GOTO, gen_label() );  }

   | WHILE             { $1 = (struct lbs *) newlblrec();
                         $1->for_goto = gen_label();                     }
        exp            { $1->for_jmp_false = reserve_loc();              } 
     DO
        commands
     END               { gen_code( GOTO, $1->for_goto );
                         back_patch( $1->for_jmp_false, 
                                    JMP_FALSE, 
                                    gen_label() );                       }
;

}

exp : NUMBER           { gen_code( LD_INT, $1 );                         }
   | IDENTIFIER        { context_check( LD_VAR,  $1 );                   } 
   | exp '<' exp       { gen_code( LT,   0 );                            }
   | exp '=' exp       { gen_code( EQ,   0 );                            }
   | exp '>' exp       { gen_code( GT,   0 );                            }
   | exp '+' exp       { gen_code( ADD,  0 );                            }
   | exp '-' exp       { gen_code( SUB,  0 );                            }
   | exp '*' exp       { gen_code( MULT, 0 );                            }
   | exp '/' exp       { gen_code( DIV,  0 );                            }
   | exp '^' exp       { gen_code( PWR,  0 );                            }
   | '(' exp ')'       
;
%%
/* C subroutines */

}

The Scanner Modifications

%{
#include <string.h>     /* for strdup                       */   
#include "simple.tab.h" /* for token definitions and yylval */
%}
DIGIT    [0-9]
ID       [a-z][a-z0-9]*
%%
{DIGIT}+ { yylval.intval = atoi( yytext );
           return(INT);      }
...
{ID}     { yylval.id = (char *) strdup(yytext); 
           return(IDENT);    }
[ \t\n]+ /* eat up whitespace */
.        { return(yytext[0]);}
%%

}

An Example