How did our code in "English" turn into 0s and 1s?

What happened in between?

What does it mean to compile?

In simple terms, a Compiler is a translater, that takes code written in a high-level language (return blablabla) and converts it into a low-level language that a computer can understand (01010101...)

This is a one-time process, and the output is a file that can be executed multiple times

But this isn't the only translator in the market

Enter the Interpreter

Instead of translating the entire code at once, an Interpreter translates the code line-by-line, executing it as it goes

with some trade-offs...

Compiler vs. Interpreter

Compiler	Interpreter
Compiles the whole code before execution	Executes code line-by-line
Faster execution	Slower execution
Displays all errors after compilation	Stops at the first error
No source code needed after compilation	Requires source code every time
Used in production (C, C++, C#)	Used in development (Python, Ruby, Perl)

Interpretation Flow

Lexing – Convert code into tokens.
Parsing – Generate AST.
Semantic Analysis – Check correctness.
Execution:
- Interpreter – Executes code line by line.
- Bytecode – Runs on VM (e.g., CPython, JVM).
- JIT – Converts hot code to machine code.

Compilers

Compiler converts the code into assembly language, which is then converted into machine code by the assembler
What does the assembly code for our C++ program look like? We can run the following command to get the assembly code

g++ -S -o hello.s hello.cpp

C++ Code

 int main() {
    return 57;
}

Assembly

 	.file	"hello.cpp"
	.text
	.globl	main
	.type	main, @function
main:
.LFB0:
	.cfi_startproc
	endbr64
	; and so on...

Compilation Flow

Lexing – Convert code into tokens.
Parsing – Generate AST.
Semantic Analysis – Check correctness.
IR Generation – Convert AST to IR.
Optimization – Improve performance.
Code Generation – Convert IR to assembly.
Assembly to Machine Code:
- Assembler – Assembly → Object code.
- Linker – Creates executable.
Execution – CPU runs machine code.

Symbol Table is a data structure used by compilers to store information about the variables, functions, and other identifiers in the program. This information is gathered during the analysis phase and used during the code generation phase.

During Lexing, entries for identifiers are added to the symbol table

During Parsing, information about the type of the identifier is added

During Semantic analysis, the symbol table is used to check for undeclared variables, type mismatches, etc.

During IR Generation, Symbol Table is used to generate intermediate representation of the code

During Optimization, the symbol table is used to track the usage of variables and functions

During Code Generation, the symbol table is used to generate assembly code using the addresses of the variables and functions

Lexing is the process of converting the code into tokens and removes comments and whitespaces (space, tab, newline etc.)

Types of Tokens in a Compiler

Keywords (e.g., if, else, while)
Identifiers (e.g., variableName, functionName)
Operators (e.g., +, -, *, /)
Literals (e.g., 42, "Hello", true)
Punctuation (e.g., ;, ,, {}, ())

Tokenization of C Code

Code


int main()
{
    int x, a=5, b=7;
    x = 4*a + b;
    printf("x is %d", x);
}

Keywords: int, int

Identifiers: main, x, a, b, x, a, b, printf, x

Operators: =, =, =, *, +

Literals: 5, 7, 4, "x is %d"

Punctuation: (, ), {, ,, ,, ;, ;, (, ,, ), ;, }

Parsing is the process of converting the tokens into a tree-like structure called the Abstract Syntax Tree (AST)

The AST is a representation of the code that is easier to work with

It is used to check the correctness of the code and generate the intermediate representation

This is done using the use of Context-Free Grammars

The grammar defines the syntax of the language

The grammar consists of Terminals and Non-terminals, Production Rules, and Start Symbol

Parse Tree, Code, and AST for `return(57);`

Code


return(57);

Parse Tree


         stmt
          │
   returnStmt
      ┌────┴────┐
   RETURN    expr
      │         │
   LPAREN     NUMBER
      │         │
      (         57
      │         
   RPAREN
      │
   SEMI

AST


  ReturnStmt
     │
    57

Parse Tree, Code, and AST for
`x = a + b * 7;`

Code


x = a + b * 7;

Parse Tree

         stmt
          │
    assignmentStmt
      ┌────┴────┐
      ID       expr
      │         │
      x       ┌─┴─┐
            expr  expr
             │     │
            ID  ┌──┴──┐
            │   expr  NUMBER
            a     │      │
                 ID      7
                 │
                 b

AST


  Assign(x)
      │
      +
     / \
    a   *
       / \
      b   7

Semantic Analysis is the process of checking the correctness of the code

It does type checking, scope checking, name resolution, control flow analysis and type inference

It uses the AST and the symbol table to perform these checks

Intermediate Representation (IR) is a representation of the code that is easier to work with than the AST and is used to perform optimizations

It allows for machine-independent optimizations

Three Address Code (TAC) is a form of IR that uses at most three operands per instruction, with only one operator

Code

x = (a + b) * c;

Three Address Code

t1 = a + b
t2 = t1 * c
x = t2

Each name has a pointer to an entry in the symbol table

Another Example

TAC greatly simplifies nested loops and if-while statements


While a < b
  If c < d Then
    x = (y + z) * w
  Else
    x = (y - z) * w
  End If
End While

L1:  IfFalse a < b goto L3
     IfFalse c < d goto L2
     t1 = y + z
     t2 = w * t1
     x = t2
     goto L1
L2:  t2 = y - z
     x = t2
     t1 = y - z
     t2 = w * t1
     x = t2
     goto L1
L3:  ...

Before conversion to machine code, the TAC might be partitioned into Basic Blocks

A basic block is a sequence of instructions with a single entry point and a single exit point and they are always executed together

This allows for better optimization

L1:  IfFalse a < b goto L3
     IfFalse c < d goto L2
     t1 = y + z
     t2 = w * t1
     x = t2
     goto L1
L2:  t2 = y - z
     x = t2
     t1 = y - z
     t2 = w * t1
     x = t2
     goto L1
L3:  ...

B1  IfFalse a < b goto B7
B2  IfFalse c < d goto B5
B3  t1 = y + z
    t2 = w * t1
    x = t2
B4  goto B1
B5  t2 = y - z
    x = t2
B6  t1 = y - z
    t2 = w * t1
    x = t2
B6  goto B1
B7  ...

Note that flow between different blocks is stored in a graph called the Control Flow Graph

Each node is a basic block and each edge is a possible flow of control

Instructions inside each node are stored in a linked list, order can thus be changed with just manipulation of pointers when we optimise this IR

Basic Block Optimisation

This involves removing redundant instructions, dead code, and constant folding

The observable behaviour of the program should not change after these optimizations

... and it needs to be quick

Common Subexpression Elimination involves eliminates redundant calculations

This is done by using a directed acyclic graph (DAG) to store the results of the calculations

 t1 = a + b
t2 = a + b
# becomes 
t1 = a + b
t2 = t1 t1 = a + b
t2 = a + b
# becomes 
t1 = a + b
t2 = t1

Look at if a new expression points to the a pre-existing node with the same children and operator

If it does, then that part of the tree can be reused and we can copy the value of the pre-existing node


a = b + c
b = a - d
d = a - d

#becomes

a = b + c
b = a - d
d = b

Copy Propagation and Constant Folding involves replacing variables with their values and evaluating constant expressions

 p = 5               p = 5
q = p + 3           q = 8
r = q + 2           r = 10
p = q * r           p = 80 p = 5               p = 5
q = p + 3           q = 8
r = q + 2           r = 10
p = q * r           p = 80 p = 5               p = 5
q = p + 3           q = 8
r = q + 2           r = 10
p = q * r           p = 80 p = 5               p = 5
q = p + 3           q = 8
r = q + 2           r = 10
p = q * r           p = 80 p = 5               p = 5
q = p + 3           q = 8
r = q + 2           r = 10
p = q * r           p = 80

Dead Code Elimination involves removing code that doesn't affect the program's output

This is done by checking if the value of a variable is used after it is assigned

 int foo(void) {
  int a = 24;
  int b = 25; /* Assignment to dead variable */
  int c;
  c = a * 4;
  return c;
  b = 24; /* Unreachable code */
  return 0;
} int foo(void) {
  int a = 24;
  int b = 25; /* Assignment to dead variable */
  int c;
  c = a * 4;
  return c;
  b = 24; /* Unreachable code */
  return 0;
}

Removing dead code can make the program smaller and faster

Algebraic Transformations involves simplifying expressions using algebraic rules

 a = b + 0           a = b
b = c * 1           b = c
c = d - 0           c = d
t = x**2            t = x * x
t = x * 2           t = x + x
t = x * 8           t = x << 3 a = b + 0           a = b
b = c * 1           b = c
c = d - 0           c = d
t = x**2            t = x * x
t = x * 2           t = x + x
t = x * 8           t = x << 3 a = b + 0           a = b
b = c * 1           b = c
c = d - 0           c = d
t = x**2            t = x * x
t = x * 2           t = x + x
t = x * 8           t = x << 3 a = b + 0           a = b
b = c * 1           b = c
c = d - 0           c = d
t = x**2            t = x * x
t = x * 2           t = x + x
t = x * 8           t = x << 3 a = b + 0           a = b
b = c * 1           b = c
c = d - 0           c = d
t = x**2            t = x * x
t = x * 2           t = x + x
t = x * 8           t = x << 3 a = b + 0           a = b
b = c * 1           b = c
c = d - 0           c = d
t = x**2            t = x * x
t = x * 2           t = x + x
t = x * 8           t = x << 3 a = b + 0           a = b
b = c * 1           b = c
c = d - 0           c = d
t = x**2            t = x * x
t = x * 2           t = x + x
t = x * 8           t = x << 3 a = b + 0           a = b
b = c * 1           b = c
c = d - 0           c = d
t = x**2            t = x * x
t = x * 2           t = x + x
t = x * 8           t = x << 3

Object Code Generation

This is the process of conversion of IR to assembly code, it involves :

Mapping machine code instructions to IR instructions
Register Allocation and assignment
Machine Specific Optimizations to take advantage of the target architecture

Mappings for each instruction can be direct or complex depending on the architecture and data types (int, float, double ...)

Basic arithmetic and bitwise operations are usually direct (provided the registers are loaded properly)

For example, the IR instruction t1 = a + b can be mapped to ADD a, b, t1 in x86-64

Complex operations like division are split into multiple instructions (as we will soon see...)

Register Allocation is the process of assigning variables to registers

Registers are faster than memory, so the goal is to keep as many variables in registers as possible

If there are more variables than registers, some variables will be stored in memory, this is called spilling

Division v/s GCC

Division is a very computationally expensive operation

So, GCC does black magic (math) to convert division into multiplication and bit shifts

A simple function which divides by 2006 looks something like this

 divideby2006(unsigned int):
        mov     eax, edi
        imul    rax, rax, 1096222959
        shr     rax, 41
        ret

n/2006 = ( n * 1096222959 ) >> 41 (How?)

	$ g++ -o hello hello.cpp
	$ ./hello
	$ echo $? # shows return value of last command
	57

	$ g++ -o hello hello.cpp
	$ ./hello
	$ echo $? # shows return value of last command
	57

	global _start
	_start:
	mov rax, 60
	mov rdi, 57
	syscall

	global _start
	_start:
	mov rax, 60
	mov rdi, 57
	syscall

	global _start
	_start:
	mov rax, 60
	mov rdi, 57
	syscall

Interpreting Compilers and Compiling Interpreters

Compiler vs. Interpreter

Interpretation Flow

Compilers

C++ Code

Assembly

A brief look at assembly

Compilation Flow

Tokenization of C Code

Parse Tree, Code, and AST for `return(57);`

Parse Tree, Code, and AST for
`x = a + b * 7;`

Basic Block Optimisation

Object Code Generation

Division v/s GCC

	.file "hello.cpp"
	.text
	.globl main
	.type main, @function
	main:
	.LFB0:
	.cfi_startproc
	endbr64
	; and so on...

	int foo(void) {
	int a = 24;
	int b = 25; /* Assignment to dead variable */
	int c;
	c = a * 4;
	return c;
	b = 24; /* Unreachable code */
	return 0;
	}

	a = b + 0 a = b
	b = c * 1 b = c
	c = d - 0 c = d
	t = x*2 t = x x
	t = x * 2 t = x + x
	t = x * 8 t = x << 3

	mov eax, [mem] ; Load from memory
	add eax, 1 ; Add 1
	sub ebx, 6 ; Subtract 6
	mov [mem], eax ; Store to memory

	mov eax, [mem] ; Load from memory
	sub ebx, 6 ; Subtract 6, perform this while eax loads
	add eax, 1 ; Add 1
	mov [mem], eax ; Store to memory

	mov eax, [arr1] ; Load from memory
	mov ebx, [arr2] ; Load from memory
	add eax, ebx ; Add
	mov [arr3], eax ; Store to memory

	movdqu xmm0, [arr1] ; Load 4 packed integers from arr1
	movdqu xmm1, [arr2] ; Load 4 packed integers from arr2
	paddd xmm0, xmm1 ; Add packed 32-bit integers
	movdqu [arr3], xmm0 ; Store result to arr3

	divideby2006(unsigned int):
	mov eax, edi
	imul rax, rax, 1096222959
	shr rax, 41
	ret