Arithmetic
Compiler Implementation
COP-3402
Arithmetic
Goal
Map SimpleIR operations
x := a + b
To assembly, e.g.,
add %rbx %rax
Challenges
- Handling variables
- Handling integer constants
- Handling assignment
SimpleIR operations
operation:
NAME ':=' operand1=(NAME | NUM)
operator=('+' | '-' | '*' | '/' | '%')
operand2=(NAME | NUM);
Intuition
x := a + b
- NAME for the assignment, e.g.,
x - Operands, e.g.,
aandb - An operator, e.g.,
+
Variations
Operands can be integers
x := a + 1
- Five operators available:
+-*/%- Add, subtract, multiply, divide, modulo
Accessing operands
Variable operands
How do we access variables?
mov -8(%rbp), %rax
Use the local variable storage scheme in the stack frame.
Integer constants
How do we represent integer constants?
mov $1, %rbx
Use a move immediate.
How do we save the result?
mov %rax, -24(%rbp)
Use the local variable storage scheme to save the data to the corresponding local variable's stack frame entry.
Performing arithmetic
Addition
add %rbx, %rax
is equivalent to
rax = rax + rbx
Left operand and the destination operand are the same register and are the second argument to the assembly instruction.
Remember, the destination is always the second argument to the att assembly instruction.
Subtraction
sub %rbx, %rax
Behaves the same as addition operation, except subtraction happens
Getting the operands mixed up
What are the results of these additions?
%rax first:
mov $9, %rax mov $5, %rbx add %rax, %rbx
%rax second:
mov $9, %rax mov $5, %rbx add %rbx, %rax
Mixing up subtraction operands
What are the results of these additions?
%rax first:
mov $9, %rax mov $5, %rbx sub %rax, %rbx
%rax second:
mov $9, %rax mov $5, %rbx sub %rbx, %rax
Remember that that left operand and the destination are the same register and are the last argument to the assembly instruction
There are two consequences to getting the arguments swapped. The register you don't expect will end up storing the result. Additionally, for subtraction, you will get an unexpected result.
Integer Multiplication
imul %rbx, %rax
Translating SimpleIR to assembly
function main localvars x a b a := 9 b := 5 x := a + b return x
What are the base pointer offsets of x, a, and b?
Local variable offsets
| Variable | Offset |
|---|---|
| x | -8 |
| a | -16 |
| b | -24 |
Three pieces to the operation
- Load variable data to registers (a and b)
- Perform arithmetic (a + b)
- Store resulting variable data (x)
Assembly code
# load a and b
mov -16(%rbp), %rax
mov -24(%rbp), %rbx
# perform addition, i.e., rax = rax + rbx
add %rbx, %rax
# store result in x
mov %rax, -8(%rbp)
Handling integer constants
function main localvars x a b b := 5 x := 7 + b return x
One or both of the operands can be an integer constant
Assembly code
# immediate 7
mov -$7, %rax
# load b
mov -24(%rbp), %rbx
# perform addition, i.e., rax = rax + rbx
add %rbx, %rax
# store result in x
mov %rax, -8(%rbp)
There are many ways to generate this code. This is a straightforward way to handle it when writing the compiler. Everything is the same except for how the register is originally given a value.
Division
- Division and remainder happen together
- Only specific registers can be used
Why might a process architecture design division this way?
Performing integer division
mov $9, %rax mov $5, %rbx # %rax holds the numerator cdq # now %rdx:%rax holds the sign-extended numerator idiv %rbx # divide %rdx:%rax by %rbx # quotient (result) now in %rax # remainder now in %rdx
Notes
- Use
idivfor division and modulo - Setup predefined registers first (%rax and %rdx)
- Retrieve results from predefined registers (%rax and %rdx)
Example
function main localvars x a b a := 9 b := 5 x := a / b return x
Assembly code
# setup operands (%rax must hold numerator)
mov -16(%rbp), %rax
mov -24(%rbp), %rbx
# perform division
cdq
idiv %rbx # %rbx is the demoninator
# store the result in x
mov %rax, -8(%rbp)
Modulo
How would the assembly code change for modulo?
# original: store the quotient (%rax) in x
mov %rax, -8(%rbp)
# new: store the remainder (%rdx) in x
mov %rdx, -8(%rbp)