Writing a simple Compiler on my own - Generating Code for Assignments (part 1)




[Custom Thumbnail]

All the Code of the series can be found at the Github repository:

https://github.com/drifter1/compiler


Introduction

    Hello it's a me again @drifter1! Today we continue with my Compiler Series, a series where we implement a complete compiler for a simple C-like language by using the C-tools Flex and Bison. In this article we will generate code for variable and pointer assignment statements.

Requirements:

    Actually you need to read and understand all the topics that I covered in the series as a whole, as these articles will give you access to knowledge about:
  • What Compiler Design is (mainly the steps)
  • For which exact Language the Compiler is build for (Tokens and Grammar)
  • How to use Flex and Bison
  • How to implement a lexer and parser for the language using those tools
  • What the Symbol Table is and how we implement it
  • How we combine Flex and Bison together
  • How we can pass information from the Lexer to the Parser
  • How we define operator priorities, precedencies and associativity
  • What Semantic Analysis is (Attributes, SDT etc.)
  • How we do the so called "Scope Resolution"
  • How we declare types and check the type inter-compatibility for different cases that include function parameters and assignments
  • How we check function calls later on using a "Revisit queue", as function declarations mostly happen after functions get used (in our Language)
  • Intermediate Code Representations, including AST's
  • How we implement an AST (structure and management)
  • Action Rules for AST nodes and more
  • The target system's architecture and its assembly language (MIPS)
  • Register Allocation & Assignment and how we implement it
  • How we generate Assembly code for various cases

Difficulty:

Talking about the series in general this series can be rated:
  • Intermediate to Advanced
Today's topic(s) can be rated:
  • Medium
So, without further ado, let's now finally start with the actual Tutorial...

Actual Tutorial Content

Assignment Statements

Assignment Statements can be summarized by the following diagram:


    As you can see variables (and arrays) are assigned to expressions. Constant values are a special type of expression that have to be generated differently. In generic expressions we basically just have to move the register in which the result (assign_val) is stored to the register in which the assign-entry is stored in. For constants we use "LI" or "LI.D (GP or FP) to directly assign that value to the corresponding assignment-register. Of course we will also have to manage type-conversion between integers and doubles.

    In the case of arrays we don't store the index right now, and so we will manage those in the next part to not make things complicated today!

    Talking about pointers, we either update the pointing location or the value the pointer is pointing to. We don't store the "*" before the pointer ID to know if the address or the value is updated (which is something that we will take care of in the next part), but we can still check if the right-part is a reference or not, to update the pointer's location.

generate_assignment() Function

    The function that will be used for assignment generation is based on a switch-case of the symbol table entry's "st_type" variable.

We have the following cases:
switch (node->entry->st_type){
    case INT_TYPE:
    case CHAR_TYPE:
        ...
        break;
    case REAL_TYPE:
        ...
        break;
    case POINTER_TYPE:
        ...
        break;
    case ARRAY_TYPE:
        ...
        break;
    default:
        fprintf(stderr, "Error in case selection!\n");
        exit(1);
}

Variable Assignment

In simple variable-assignments, we basically have:
  • Integer-to-Integer: MOVE instruction
  • Constant-to-Integer: LI instruction
  • Double-to-Integer: MOVE after conversion using CVT.W.D and MFC1
  • Double-to-Double: MOV.D instruction
  • Constant-to-Double: LI.D instruction
  • Integer-to-Double: MOV.D after conversion using MTC1 and CVT.D.W

In Code this looks like this:
switch (node->entry->st_type){
    case INT_TYPE:
    case CHAR_TYPE:
        if(expression_data_type(node->assign_val) == INT_TYPE){
            /* constant */
            if(node->assign_val->type == CONST_NODE){
                temp_const = (AST_Node_Const *) node->assign_val;
                fprintf(fp, "LI %s, %d\n", 
                    GetRegisterName(node->entry->g_index, 0), temp_const->val);
            }
            /* variable */
            else{
                fprintf(fp, "MOVE %s, %s\n",
                    GetRegisterName(node->entry->g_index, 0),
                    GetRegisterName(getGraphIndex(node->assign_val), 0));
            }
        }
        else{
            if(node->assign_val->type == CONST_NODE){
                temp_const = (AST_Node_Const *) node->assign_val;                   
                fprintf(fp, "LI %s, %d\n",
                    GetRegisterName(node->entry->g_index, 0), temp_const->val); 
            }
            /* variable */
            else{
                fprintf(fp, "CVT.W.D %s, %s\n",
                    GetRegisterName(getGraphIndex(node->assign_val), 1),
                    GetRegisterName(getGraphIndex(node->assign_val), 1));
                fprintf(fp, "MFC1 %s, %s\n",
                    GetRegisterName(getGraphIndex(node->assign_val), 0),
                    GetRegisterName(getGraphIndex(node->assign_val), 1));
                fprintf(fp, "MOVE %s, %s\n",
                    GetRegisterName(node->entry->g_index, 0),
                    GetRegisterName(getGraphIndex(node->assign_val), 0));   
            }
        }
        break;
    case REAL_TYPE:
        if(expression_data_type(node->assign_val) == REAL_TYPE){
            /* constant */
            if(node->assign_val->type == CONST_NODE){
                temp_const = (AST_Node_Const *) node->assign_val;                   
                fprintf(fp, "LI.D %s, %.2f\n",
                    GetRegisterName(node->entry->g_index, 1), temp_const->val); 
            }
            /* variable*/
            else{
                fprintf(fp, "MOV.D %s, %s\n",
                    GetRegisterName(node->entry->g_index, 1),
                    GetRegisterName(getGraphIndex(node->assign_val), 1));
            }
        }
        else{
            /* constant */
            if(node->assign_val->type == CONST_NODE){
                temp_const = (AST_Node_Const *) node->assign_val;                   
                fprintf(fp, "LI.D %s, %d.0\n",
                    GetRegisterName(node->entry->g_index, 1), temp_const->val); 
            }
            /* variable*/
            else{
                fprintf(fp, "MTC1 %s, %s\n",
                    GetRegisterName(getGraphIndex(node->assign_val), 0),
                    GetRegisterName(getGraphIndex(node->assign_val), 1));
                fprintf(fp, "CVT.D.W %s, %s\n",
                    GetRegisterName(getGraphIndex(node->assign_val), 1),
                    GetRegisterName(getGraphIndex(node->assign_val), 1));
                fprintf(fp, "MOVE %s, %s\n",
                    GetRegisterName(node->entry->g_index, 1),
                    GetRegisterName(getGraphIndex(node->assign_val), 1));
            }
        }
        break;
...

Pointer Assignment

    For now, in the case of pointers we can check if the "assign_val" is a reference which tells us that we are updating the pointer's pointing address. Something like "p = p + 1" can't be managed right now, as the value "p+1" would be stored in the address pointer 'p' points to. Either way, right now we can write the following Code to check for References:
case POINTER_TYPE:
    if(node->assign_val->type == REF_NODE){
        AST_Node_Ref *temp_ref = (AST_Node_Ref *) node->assign_val;
        /* not a reference */
        if(temp_ref->ref == 0){
            /* integer */
            if(expression_data_type(node->assign_val) == INT_TYPE){
                fprintf(fp, "SW %s, 0(%s)\n",
                    GetRegisterName(getGraphIndex(node->assign_val), 0), 
                    GetRegisterName(node->entry->g_index, 0));
            }
            /* floating point */
            else{
                fprintf(fp, "S.D %s, 0(%s)\n",
                    GetRegisterName(getGraphIndex(node->assign_val), 1),
                    GetRegisterName(node->entry->g_index, 0));
            }
        }
        /* reference */
        else{
            fprintf(fp, "SW %s, %s($0)\n",
                GetRegisterName(getGraphIndex(node->assign_val), 0),
                node->entry->st_name);
            fprintf(fp, "MOVE %s, %s\n",
                GetRegisterName(node->entry->g_index, 0),
                GetRegisterName(getGraphIndex(node->assign_val), 0));
        }
    }
    else{
        /* integer */
        if(expression_data_type(node->assign_val) == INT_TYPE){
            fprintf(fp, "SW %s, 0(%s)\n",
                GetRegisterName(getGraphIndex(node->assign_val), 0),
                GetRegisterName(node->entry->g_index, 0));
        }
        /* floating point */
        else{
            fprintf(fp, "S.D %s, 0(%s)\n",
                GetRegisterName(getGraphIndex(node->assign_val), 1),
                GetRegisterName(node->entry->g_index, 0));
        }
    }
    break;
...

    For the case of Array Assignments I will for now just print out "Array Assignment".

Compiler Output

    Lastly, let's run our compiler for the three examples that we use through-out the series...

Simple Example 1

Running for example.c we get the following output file:
.data
# variables
i: .word 0
val: .double 0.000000
res: .double 0.000000
# messages
.text main: LI.D $f2, 2.50 LI.D $f28, 1.0 ADD.D $f6, $f2 $f28 MOV.D $f4, $f6

By also looking at the console output:


we can see that "res" gets the value "val + 1" or "2.5 + 1" or 3.5 as it should!

Simple Example 2

Running for example.c we get the following output file:
.data
# variables
i: .word 0
val: .double 2.500000
res: .space 80
# messages
.text main: LI $s0, 0 LW $s0, i($0) BGE $s0, 10, Temp_Label L.D $f2, val LW $s0, i($0) LI.D $f6, 0.0 Array Assignment LW $s2, res($0) MOV.D $f2, $f4 LW $s2, res($0) ADDI $s0, $s0, 1

Here we can see that an array assignment is missing!

Full Example

Running for full_example.c we get the following output file:
.data
# variables
c: .byte 'c'
i: .word 0
p: .word 0
val: .double 2.500000
res: .double 0.500000, 1.500000, 2.500000, 3.500000, 4.500000, 5.500000
# messages
msg1: .asciiz "\n"
msg2: .asciiz "\n"
msg3: .asciiz "iteration: 3\n"
msg4: .asciiz " "
msg5: .asciiz "\n"
.text main: LA $s3, res($0) SW $s3, p($0) MOVE $s4, $s3 LI $s0, 0 LW $s0, i($0) BGE $s0, 10, Temp_Label LW $s0, i($0) BGT $s0, 5, Temp_Label J Temp_Label LW $s0, i($0) BNE $s0, 5, Temp_Label LW $s0, i($0) MULI $s5, $s0, 2 MOVE $s0, $s5 LI $s6, 0 MTC1 $s6, $f12 CVT.D.W $f12, $f12 MOVE $f4, $f12 L.D $f4, val LW $s0, i($0) LI.D $f14, 0.0 S.D $f14, 0($s4) LW $s3, res($0) J Temp_Label L.D $f4, val LW $s0, i($0) LI.D $f16, 0.0 S.D $f16, 0($s4) LW $s3, res($0) MOV.D $f4, $f6 LW $s3, res($0) LW $s4, p($0) ADDI $t1, $s4, 1 SW $t1, 0($s4) LW $s0, i($0) BNE $s0, 2, Temp_Label L.D $f4, val LI.D $f28, 4.50 C.EQ.D $f4 $f28 BC1F Temp_Label AND $s0, $s0, $s0 ADDI $s0, $s0, 1 LW $s0, i($0) BGE $s0, 12, Temp_Label LW $s0, i($0) LW $s1, c($0) ADDI $s0, $s0, 1

    The only problem that we have right now is in the "bold" code. As you can see we update the pointer's location storing "p+1" in $t1, but that value gets then stored in the address that p is pointing to, not updating p itself as it should! The rest is OK.

RESOURCES

References:

No references, just using code that I implemented in my previous articles.

Images:

All of the images are custom-made!

Previous parts of the series

General Knowledge and Lexical Analysis

Syntax Analysis

Semantic Analysis (1)

Intermediate Code Generation (AST)

Semantic Analysis (2)

Machine Code Generation


Final words | Next up on the project

    And this is actually it for today's post! In the next article we will generate the code for array assignments.

Next up on this series, in general, are:
  • Machine Code generation (MIPS Assembly)
  • Various Optimizations in the Compiler's Code

     Which are all topics for which we will need more than one article to complete them. Also, note that we might also get into AST Code Optimizations later on, or that we could even extend the Language by adding complex datatypes (structs and unions), more rules etc.

So, see ya next time!

GitHub Account:

https://github.com/drifter1

Keep on drifting! ;)

H2
H3
H4
3 columns
2 columns
1 column
6 Comments