Writing a simple Compiler on my own - Generating Code for Expressions (part 3)

in #utopian-io5 years ago

[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 the remaining Expressions (Boolean, Relational and Equality).

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

Boolean Operations

    The operands of Boolean operations can only be integers. Integers can occur inside of GP-registers or as constants that are translated into immediate operands. So, the various combinations of operands are limited. Using similar code to the arithmetic operations, we basically check which of the operands of the AND and OR operations (NOT is applied to a register and also a pseudo-instruction) is a constant. If no operand is a constant then the const_op flag will be 0. For immediate operations we use ORI and ANDI. For "simple" operations we use OR, AND and NOT.

The final function is:
void generate_bool(FILE *fp, AST_Node_Bool *node){
int const_op = 0;
/* GP: 0, Constant: 1 */ int Operand1 = 0; int Operand2 = 0;
AST_Node_Const *temp_const;
if(node->op != NOT){ if(node->left->type == CONST_NODE){ const_op = 1; Operand1 = 1; } else if(node->right->type == CONST_NODE){ const_op = 1; Operand2 = 1; } }
/* operation */ switch(node->op){ case OR: if (const_op == 1){ if(Operand1 == 1){ temp_const = (AST_Node_Const*) node->left; fprintf(fp,"ORI %s, %s, %d\n", GetRegisterName(node->g_index, 0), GetRegisterName(getGraphIndex(node->right), 0), temp_const->val); } else{ temp_const = (AST_Node_Const*) node->right; fprintf(fp,"ORI %s, %s, %d\n", GetRegisterName(node->g_index ,0), GetRegisterName(getGraphIndex(node->left),0), temp_const->val); } } else{ fprintf(fp,"OR %s, %s, %s\n", GetRegisterName(node->g_index ,0), GetRegisterName(getGraphIndex(node->left),0), GetRegisterName(getGraphIndex(node->right),0)); } break; case AND: if (const_op == 1){ if(Operand1 == 1){ temp_const = (AST_Node_Const*) node->left; fprintf(fp,"ANDI %s, %s, %d\n", GetRegisterName(node->g_index ,0), GetRegisterName(getGraphIndex(node->right),0), temp_const->val); } else{ temp_const = (AST_Node_Const*) node->right; fprintf(fp,"ANDI %s, %s, %d\n", GetRegisterName(node->g_index ,0), GetRegisterName(getGraphIndex(node->left),0), temp_const->val); } } else{ fprintf(fp,"AND %s, %s, %s\n", GetRegisterName(node->g_index ,0), GetRegisterName(getGraphIndex(node->left),0), ' GetRegisterName(getGraphIndex(node->right),0)); } break; case NOT: fprintf(fp, "NOT %s, %s", GetRegisterName(node->g_index ,0), GetRegisterName(getGraphIndex(node->left),0)); break; default: fprintf(stderr, "Error in OP selection!\n"); exit(1); } }

    As I said in the first part, Boolean operations will mostly be used as "information" and don't occur that often as actual operations, but still writing the Code was necessary.

Relational Operations

    In relational operations, we again end up having most of the combinations that are available in arithmetic operations. The operands can be GP and FP registers, and integer or floating-point constants. Thus, we first have to check the operands setting the various flag variables. For relational operations we will also give two more parameters:
  • invLogic - that tell us if the logic is inverted (> is <= etc.) - mostly 1
  • Label - to which the branch jumps to when the condition is true

Getting operand information

    The code for getting the needed information from the operands is:
int const_op = 0;
int float_op = 0;
/* GP: 0, FP: 1, Constant: 2, FP Constant: 3 */ int Operand1 = 0; int Operand2 = 0;
/* check left operand */ if (expression_data_type(node->left) == REAL_TYPE){ float_op = 1; if(node->left->type == CONST_NODE){ const_op = 1; Operand1 = 3; } else{ Operand1 = 1; } } else{ if(node->left->type == CONST_NODE){ const_op = 1; Operand1 = 2; } else{ Operand1 = 0; } }
/* check right operand */ if(expression_data_type(node->right) == REAL_TYPE){ float_op = 1; if(node->right->type == CONST_NODE){ const_op = 1; Operand2 = 3; } else{ Operand2 = 1; } } else{ if(node->right->type == CONST_NODE){ const_op = 1; Operand2 = 2; } else{ Operand2 = 0; } }

Inverted Logic

    To invert the logic, we will include a small switch-case that stores the "correct"operand inside of a temporary "op" variable, to be used in the later switch-case that manages the actual "printing". When invLogic equals 1, we basically write the inverted logic into op.

The Code looks like this:
* inverted logic */
int op;
if(invLogic == 1){
    switch(node->op){
        case GREATER:
            op = LESS_EQUAL;
            break;
        case LESS:
            op = GREATER_EQUAL;
            break;
        case GREATER_EQUAL:
            op = LESS;
            break;
        case LESS_EQUAL:
            op = GREATER;
            break;
        default:
            fprintf(stderr, "Error in OP selection!\n");
            exit(1);
    }
}
else{
    op = node->op;
}

Printing out the Branch Instructions

    As we showed in the first part, the various relational operations correspond to the following branch instructions:
  • ">" (GREATER)
    • BGT $rs, $rt, Label - GP-register operands
    • BGT $rs, imm, Label - GP-register and constant (when the first operand is a constant, we have to write the opposite (BLE)
    • C.LE.D $f1, $f2 and BC1F Label (FP-constant will be stored in $f30)
  • "<" (LESS)
    • BLT $rs, $rt, Label - GP-register operands
    • BLT $rs, imm, Label - GP-register and constant (when the first operand is a constant, we have to write the opposite (BGE)
    • C.LT.D $f1, $f2 and BC1T Label (FP-constant will be stored in $f30)
  • ">=" (GREATER_EQUAL)
    • BGE $rs, $rt, Label - GP-register operands
    • BGE $rs, imm, Label - GP-register and constant (when the first operand is a constant, we have to write the opposite (BLT)
    • C.LT.D $f1, $f2 and BC1F Label (FP-constant will be stored in $f30)
  • "<=" (LESS_EQUAL)
    • BLE $rs, $rt, Label - GP-register operands
    • BLE $rs, imm, Label - GP-register and constant (when the first operand is a constant, we have to write the opposite (BGT)
    • C.LE.D $f1, $f2 and BC1T Label (FP-constant will be stored in $f30)

    In the FP-operations we will of course have to convert the integers to floating-point numbers, storing them inside of $f28.

For the "GREATER"-operation, the Code is:
if(float_op == 1){
    if(const_op == 1){
        if(Operand1 == 2 || Operand1 == 3){
            temp_const = (AST_Node_Const *) node->left;
         }
        else{
            temp_const = (AST_Node_Const *) node->right;
        }
        if(temp_const->const_type == REAL_TYPE){
            fprintf(fp, "LI.D $f28, %.2f\n", temp_const->val);
        }
        else{
            fprintf(fp, "LI.D $f28, %d.0\n", temp_const->val);
        }		
    }
if(Operand1 == 0){ fprintf(fp, "MTC1.D %s, $f30\n", GetRegisterName(getGraphIndex(node->left) , 0)); fprintf(fp, "CVT.D.W $f30, $f30\n"); } else if(Operand2 == 0){ fprintf(fp, "MTC1.D %s, $f30\n", GetRegisterName(getGraphIndex(node->right) , 0)); fprintf(fp, "CVT.D.W $f30, $f30\n"); }
fprintf(fp, "C.LE.D ");
switch(Operand1){ case 0: fprintf(fp, "$f30 "); break; case 1: fprintf(fp, "%s ", GetRegisterName(getGraphIndex(node->left) , 1)); break; case 2: case 3: fprintf(fp, "$f28 "); }
switch(Operand2){ case 0: fprintf(fp, "$f30 "); break; case 1: fprintf(fp, "%s ", GetRegisterName(getGraphIndex(node->right) , 1)); break; case 2: case 3: fprintf(fp, "$f28 "); } fprintf(fp, "\n");
fprintf(fp, "BC1F %s\n", Label);
} else if(const_op == 1){ if(Operand1 != 0){ temp_const = (AST_Node_Const *) node->left; fprintf(fp, "BLE %s, %d, %s\n", GetRegisterName(getGraphIndex(node->right), 0), temp_const->val, Label); } else if(Operand2 != 0){ temp_const = (AST_Node_Const *) node->right; fprintf(fp, "BGT %s, %d, %s\n", GetRegisterName(getGraphIndex(node->left), 0), temp_const->val, Label); } } else{ fprintf(fp, "BGT %s, %s, %s\n", GetRegisterName(getGraphIndex(node->left), 0), GetRegisterName(getGraphIndex(node->right), 0), Label); }

The code for the other 3-cases is similar and just changes at the OP-Codes.

Equality Operations

    The equality operations are handled similar to Relational Operations. The Equality-operators correspond to branch-instructions in the following way:
  • "==" (EQUAL)
    • BEQ $rs, $rt, Label - GP-register operands
    • BEQ $rs, imm, Label - GP-register and constant
    • C.EQ.D $f1, $f2 and BC1T Label (FP-constant will be stored in $f30)
  • "!=" (NOT_EQUAL)
    • BNE $rs, $rt, Label - GP-register operands
    • BNE $rs, imm, Label - GP-register and constant (when the first operand is a constant, we have to write the opposite (BGE)
    • C.EQ.D $f1, $f2 and BC1F Label (FP-constant will be stored in $f30)

After the operand-checking, we have an inverse-logic block:
int op;
if(invLogic == 1){
    /* EQUAL <-> NOT_EQUAL */
    if(node->op == EQUAL){
        op = NOT_EQUAL;
    }
    else{
        op = EQUAL;
    }
}
else{
    op = node->op;
}

    Lastly, we have a switch-case for the operator, where the EQUAL and NOT_EQUAL have similar code to the GREATER-case of the relational operators. Just go to GitHub to see the whole Code. The code_generation.c file is about 2100 liens of code right now!

Output for Examples

Let's run our compiler again for the examples to see the new output files!

There are no changes for the first simple Example!

Simple Example 2

    Running the compiler for the second example, we basically get most of the main function's code right:
.data
# variables
i: .word 0
val: .double 2.500000
res: .space 80
# messages
.text main: LW $s0, i($0) BGE $s0, 10, Temp_Label L.D $f2, val LW $s0, i($0) LI.D $f6, 0.0 LW $s2, res($0) LW $s2, res($0)

As you can see the for-loop is mostly setup!

Full Example

    Running for full_example.c most if-statements and loops are basically mostly "structured" by now.

The output file is:
.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) LW $s0, i($0) BGE $s0, 10, Temp_Label LW $s0, i($0) BGT $s0, 5, Temp_Label LW $s0, i($0) BNE $s0, 5, Temp_Label LW $s0, i($0) MULI $s5, $s0, 2 LI $s6, 0 L.D $f4, val LW $s0, i($0) LI.D $f14, 0.0 LW $s3, res($0) L.D $f4, val LW $s0, i($0) LI.D $f16, 0.0 LW $s3, res($0) LW $s3, res($0) LW $s4, p($0) ADDI $t1, $s4, 1 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 LW $s0, i($0) BGE $s0, 12, Temp_Label LW $s0, i($0) LW $s1, c($0)

I guess someone can distinguish the various parts of the main's code...

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 of simple statements (break, continue, increment/decrement).

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! ;)
Sort:  

Thank you for your contribution.
As always, your compiler tutorials are well-written. Glad to see you're still innovating on the topic.

REPLACE WITH FEEDBACK

Your contribution has been evaluated according to Utopian policies and guidelines, as well as a predefined set of questions pertaining to the category.

To view those questions and the relevant answers related to your post, click here.


Need help? Chat with us on Discord.

[utopian-moderator]

Thank you for your review, @mcfarhat! Keep up the good work!

Hi @drifter1!

Your post was upvoted by @steem-ua, new Steem dApp, using UserAuthority for algorithmic post curation!
Your post is eligible for our upvote, thanks to our collaboration with @utopian-io!
Feel free to join our @steem-ua Discord server

Hey, @drifter1!

Thanks for contributing on Utopian.
We’re already looking forward to your next contribution!

Get higher incentives and support Utopian.io!
Simply set @utopian.pay as a 5% (or higher) payout beneficiary on your contribution post (via SteemPlus or Steeditor).

Want to chat? Join us on Discord https://discord.gg/h52nFrV.

Vote for Utopian Witness!

Congratulations @drifter1! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You distributed more than 30000 upvotes. Your next target is to reach 31000 upvotes.

You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

You can upvote this notification to help all Steem users. Learn how here!

Coin Marketplace

STEEM 0.35
TRX 0.12
JST 0.040
BTC 70638.80
ETH 3565.34
USDT 1.00
SBD 4.73