[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) <ul> <li>BLE $rs, $rt, Label - GP-register operands</li> <li>BLE $rs, imm, Label - GP-register and constant (when the first operand is a constant, we have to write the opposite (BGT)</li> <li>C.LE.D $f1, $f2 and BC1T Label (FP-constant will be stored in $f30)</li> </ul> </li> </ul> <br>     In the FP-operations we will of course have to convert the integers to floating-point numbers, storing them inside of $f28.<br><br> 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

  • Introduction
  • A simple C Language
  • Lexical Analysis using Flex
  • Symbol Table (basic structure)
  • Using Symbol Table in the Lexer

  Syntax Analysis

  • Syntax Analysis Theory
  • Bison basics
  • Creating a grammar for our Language
  • Combine Flex and Bison
  • Passing information from Lexer to Parser
  • Finishing Off The Grammar/Parser: [part 1] [part 2]

  Semantic Analysis (1)

  • Semantic Analysis Theory
  • Semantics Examples
  • Scope Resolution using the Symbol Table
  • Type Declaration and Checking
  • Function Semantics: [part 1] [part 2]

  Intermediate Code Generation (AST)

  • Abstract Syntax Tree Principle
  • Abstract Syntax Tree Structure
  • Abstract Syntax Tree Management
  • Action Rules for Declarations and Initializations
  • Action Rules for Expressions
  • Action Rules for Assignments and Simple Statements
  • Action Rules for If-Else Statements
  • Action Rules for Loop Statements and some Fixes
  • Action Rules for Function Declarations: [part 1][part 2]
  • Action Rules for Function Calls

  Semantic Analysis (2)

  • Datatype attribute for Expressions
  • Type Checking for Assignments
  • Revisit Queue and Parameter Checking: [part 1][part 2][part 3][part 4]
  • Revisit Queue and Assignment Checking : [part 1][part 2][part 3]

  Machine Code Generation

  • Machine Code Generation Principles
  • MIPS Instruction Set
  • Simple Examples in MIPS Assembly
  • full_example.c in MIPS Assembly: [part 1][part 2]
  • Generating Code for Declarations and Initializations
  • Generating Code for Array Initializations and String Messages
  • Register Allocation & Assignment Theory
  • Implementing Register Allocation: [part 1][part 2][part 3][part 4]
  • Generating Code for Expressions: [part 1][part 2]

  ---

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