CSE302 Lab 3-Control Structures and x64 Assembly Solution

1 INTRODUCTION
In this lab you will extend our source language BX with support for boolean values, boolean expressions, and control structures. You will also extend our intermediate language, TAC, with support for labels and jumps. Finally, in this lab you will build your first complete compiler, targeting x64 assembly. You will be required to be able to assemble and link your assembly output into executables.
It is recommended that you work in groups of size 2. Your submission must contain a file called GROUP.txt that contains the names of the group members.
2 STRUCTURE OF THE LAB
Checkpoint deliverables The checkpoint will consist of a backend instruction selection pass that will produce x64 assembly from TAC (extended with labels and jumps). You will need to design a pass that goes from a TAC file example.tac.json to an x64 assembly file example.s, which can then be compiled into example.exe using gcc and the BX runtime. This task is explained in more detail in section 3.
[Continued…]
3 ASMGEN: FROM TAC TO X64 (WEEK 1 – CHECKPOINT)
3.1 Labels and Jumps in TAC
The TAC intermediate language you have seen in previous labs is now extended with new features:
• Local labels, which are of the form %.L followed by a sequence of alphanumeric characters.
• Label (pseudo)instructions, which are part of the instruction sequence and serve to point to the next instruction in the sequence. Label instructions are represented in JSON with the instruction opcode "label", a single argument (which is the label tself), and no result temporaries.
• A collection of jump instructions that consist of:
– Unconditional jumps that look like: jmp %.L42;
– Conditional jumps that look like: jcc %1, %.L42; where jcc ∈ {jz,jnz,jl,jnl,jle,jnle} and the instruction jumps to the label %.L42 if the
first argument %1 satisfies certain conditions.
jcc condition jcc condition
jz %1 == 0 jnz %1 != 0
jl %1 < 0 jnl %1 >= 0
jle %1 <= 0 jnle %1 > 0
3.2 Mapping TAC Temporaries to x64
Registers and Stack Slots x64 has only 14 general purpose registers (GPRs) available for computation. Of these GPRs, a further 5 are callee-save registers, and are therefore inadvisable to use at present, since you will not yet have a lot of sophistication in managing the stack. Therefore, the recommendation is to use only the remaining 9 registers: RAX, RCX, RDX, RSI, RDI, R8, R9, R10, and R11.
TAC, on the other hand, can use an arbitrary number of temporaries. Therefore, to compile TAC to x64, you will have to keep these temporaries in main memory, specifically the stack. For now, it is useful to think of the stack as being built of stack slots. Each temporary that is used in the TAC program should have a dedicated stack slot, which we can identify with a number ∈ {1,2,...,n} where n is the total number of temporaries. You need to create and manage this mapping in your code.
The Stack Figure 1 contains a schematic diagram of the stack, highlighting a single stack frame. For the purposes of this project, we will only focus our attention on the yellow portion of the figure. (We will explore the rest of the elements of the stack frame in the next lab.)
When the program begins, the RSP register points to the top of the stack, which (by convention) is the lowest allocated memory location in the stack area of the program. The stack grows downwards from high memory to low memory, so to allocate new stack slots it suffices to decrement RSP by the number of slots desired, multiplied by 8 since each stack slot is 8 bytes (64 bits) wide. Therefore, to allocate 42 stack slots, you would need to decrement RSP by 42 × 8 = 336. Be aware that in x64 the stack size needs to be a multiple of 16 so if you only have an odd number of temporaries you should add an extra unused slot.
The Frame Pointer, RBP At the end of the program, you need to restore the stack pointer, RSP, to its initial value; if you don’t, your program will most likely crash on exit. To achieve this, a common technique is to use the RBP register, known as the base pointer or more commonly the frame pointer, to store the old value of RSP. However, RBP itself is a callee-save register, so it too must be restored on exit from a

Figure 1: A schematic diagram of a stack frame
Accessing the Contents of the Stack Since we are not using any callee-save registers, the pink region for callee-saves will be limited to just the saved RBP; i.e., for us m = 0. Therefore, the first slot for temporaries will be at offset RBP - 8, and the nth temporary will be located at RBP - 8n. Note that memory locations grow upwards, so the first temporary (e.g.) will be laid out in the bytes between RBP - 8 and RBP. Stack slots are always referenced by the location of their first byte.
To get/store the contents of the n slot, we will need to dereference the memory address RBP - 8n. In x64, this is written conveniently as -8n(%rbp); that is, the various slot contents are -8(%rbp), -16(%rbp),
-24(%rbp), -32(%rbp), …
Setup To put this together, here is a template you can reuse to build your assembly file for a BX program. The template assumes that it is allocating 8 stack slots for 8 temporaries; you will have to modify this in your compiler
.globl main
.text main:
pushq %rbp # store old RBP at top of the stack movq %rsp, %rbp # make RBP point to just after stack slots
# At that point, we are 16-byte aligned
# - return address (8 bytes) + copy of old RBP (8 bytes)
# Now we allocate stack slots in units of 8 bytes (= 64 bits)
# E.g., for 8 slots, i.e., 8 * 8 = 64 bytes
# -- MODIFY AS NEEDED --
subq $64, %rsp
#
# -- The rest of the compiled code from TAC goes here. --
#
movq %rbp, %rsp # restore old RSP popq %rbp # restore old RBP movq $0, %rax # set return code to 0
retq # exit
3.3 Instruction Selection
We recommend that you limit yourself to the following simple subset of the x64 assembly language. This will minimize complications when trying to convert TAC to x64. Later, once you have a functional assembly generator, you can experiment with other instructions outside this set. Whenever you try such experiments, make sure to pre-write a regression test case that triggers the modification, and then always check that your experiment yields the same results before and after the modification.
Operand Specifiers In x64, instructions can take operands of several different forms, and each form has a unique operand specifier. For now we will only use the following specifiers.
kind example description
Immedi-
ate $42 The value can be in decimal or hexadecimal (using the prefix 0x). Don’t forget the $ – without it, it will be interpreted as a raw absolute memory address, not an immediate value.
Register %rax Registers are named with % followed by the name of the register in lowercase.
Dereference (%rax) Gets or sets the value stored at the memory location contained in the given register.
Derefer- 42(%rax) Adds the offset to the register value to get the locaence w/ tion being dereferenced. Note that the offset can be
Offset negative.
In all of the following, the page references are to the document “AMD64 Architecture Programmer’s Manual (vol 3): General Purpose and System Instructions”, where these instructions are described in the Intel syntax that puts the destination operand first instead of last. We will use the AT&T/GNU syntax that places the destination operand last.
Data Transfer Instructions
instruction description page
movq Src, Dst Move Src value to Dst. 231
pushq Src Decrement RSP by 8 and put Src into where it points to afterwards 285
popq Dst Load the value pointed to by RSP into Dst, then 273 increment RSP by 8
In these and all subsequent instructions, both Src and Dst cannot be dereferences simultaneously.
Arithmetic Instructions
instruction description page
addq Src, Dst Increment Dst by the value of Src 83
subq Src, Dst Decrement Dst by the value of Src 342
imulq Src, Dst Multiply Dst by the value of Src 178
andq Src, Dst Bitwise-and Dst with the value of Src 87
orq Src, Dst Bitwise-or Dst with the value of Src 262
xorq Src, Dst Bitwise-xor Dst with the value of Src 359
instruction description page
notq Dst Bitwise-not Dst (i.e., flip all its bits) 261
negq Dst Negate Dst 258
Arithmetic Instructions with Fixed Operands
instruction description page
sarq Src, Dst Arithmetic right-shift Dst by the amount Src. Src cannot be a dereference. If Src is a register, it must be %cl. 314
salq Src, Dst Arithmetic left-shift Dst by the amount Src. Src cannot be a dereference. If Src is a register, it must be %cl. 311
idivq Src Signed divide RDX:RAX by Src, storing quotient in RAX and remainder in RDX 176
cqto Sign-extend RAX into a 128-bit value RDX:RAX 140
/* This should be in a file such as: bx_runtime.c */
#include <stdio.h>
#include <stdint.h>
/* Note: TAC int == C int64_t
This is because C int is usually only 32 bits. */
void bx_print_int(int64_t x)
{ printf("%ld ", x);
}
Figure 2: The BX “runtime”
Conditions and Jumps
instruction description page
cmpq Src1, Src2 Set the flags register based on the result of computing Src2 - Src1. Carefully note the order of the operands of the subtraction! 155
jmp Lbl Unconditionally jump to local label Lbl 199
jcc Lbl Conditional jump to local label Lbl. Here, jcc 194
is one of the opcodes in the table below, with the interpreted condition with reference to cmpq above
jcc condition

je, jz Src2 == Src1
jne, jnz Src2 != Src1
jl, jnge Src2 < Src1
jle, jng Src2 <= Src1
jg, jnle Src2 > Src1
jge, jnl Src2 >= Src1
3.4 Dealing with print
The print statement of TAC will be compiled by making a function call from x64 to the BX runtime function bx_print_int(). For this lab, the runtime is just the file bx_runtime.c shown in figure 2. You have to link it to create the final executable, as explained in section 3.5.
pushq %rdi # if you're currently using RDI for anything else
pushq %rax # if you're currently using RAX for anything else
movq -56(%rbp), %rdi # load stack slot 7 (note: 7 * 8 == 56)
callq bx_print_int # you *must* be 16-byte aligned here!
popq %rax # if you pushed RAX
popq %rdi # if you pushed RDI
The saves (pushqs) of RDI and RAX, and their subsequent restores (popqs), are optional. They are only needed if you are storing values in these registers that you will need access to after the print. These are caller-save registers, so callees such as bx_print_int() are allowed to modify them as needed.
3.5 Building and Debugging Executables
Once you have produced an assembly file, say example.s, you should use gcc to link it together with your runtime in one shot. Use the following invocation:

3.6 What You Should Submit for the Checkpoint
Your main program should be called tac2x64.py (or tac2x64.exe if you’re not using Python). It should at the very least accept a single TAC (JSON) file in the command line, e.g., prog.tac.json, and it should produce a corresponding x64 assembly file (here, prog.s). You don’t need to produce prog.exe by running gcc (but you can if you wish).

4 THE BX LANGUAGE
The additions to BX in this lab are as follows:
• A new type, bool, of booleans. Note that BX does not (yet) have any variables of bool type; indeed, all BX variables continue to be int variables.
• A number of new operators that produce values of bool type. This includes the comparison operators (==, !=, <, <=, >, and >=) for comparing two int expressions, and the boolean connectives &&, ||, and !. There are also two new constants of bool type: true and false.
• Conditional if ... else ... statements.
• Looping while ... statements.
• The two structured jumping statements, break and continue.
The lexical structure and grammar of the current BX fragment is shown in figure 3. The extended operator precedence table is shown in figure 4. As usuall, the overall BX program is represented by the nonterminal

Figure 3: The lexical structure and grammar of the current fragment of BX.
operator description arity associativity precedence
|| boolean disjunction (or) binary left 3
&& boolean conjunction (and) binary left 6
| bitwise or binary left 10
^ bitwise xor binary left 20
& bitwise and binary left 30
==, != (dis-)equality binary nonassoc 33
<,<=, >, >= inequalities binary nonassoc 36
<<, >> bitwise shifts binary left 40
+,- addition, subtraction binary left 50
*, /, % multiplication, division, modulus binary left 60
- , ! integer/boolean negation unary – 70
~ bitwise complement unary – 80
Figure 4: BX operator arities and precedence values. A higher precedence value binds tighter.
if (cond1) {
// body1
} else if (cond2) {
// body2
} else if (cond3) {
// body3
}
...
// optional:
else {
// code that runs if none of the condi is true
}
Figure 5: General form of the BX conditional.
hprogrami and consists of a single function named @main. In the rest of this section we will specify the semantics of the new features of BX.
Boolean Relations The six new binary relational operators, {==,!=,<,<=,>,>=}, are used to compare the values of signed 64-bit integers. These operators are non-associative, meaning that there is no particular meaning ascribed to expressions such as x == y == z or x <= y < z. Such expressions would be considered to be parse errors.
Note that the == and != operators are used to compare ints alone.
Boolean Connectives and Short-Circuiting The two binary boolean connectives && and || and the unary boolean negation ! have the following truth tables.
b1 b2 b1 && b2 b1 || b2 !b1
true true true true false
true false false true false
false true false true true
false false false false true
The binary operators && and || are also short-circuiting. To compute the value of the expression b1 && b2, first b1 is evaluated; if it is false, then the value of b1 && b2 is taken to be false and b2 is not evaluated. Likewise, the value of b1 || b2 is taken to be true if b1 evaluates to true without evaluating b2.
Conditionals The general form of the if ... else ... statement is shown in figure 5. This form in BX is inspired by C. Immediately after the condition, there is a block (delimited by {}) that is executed if the condition evaluates to true. If the condition evaluates to false instead, the control moves to the optional remainder of the expression that is separated by means of the else keyword. The remainder could contain further conditions to check, or it could be a final fallback for when none of the conditions is true. Note that the conditions are evaluated top-to-bottom, and the first conditional that evaluates to true causes its corresponding body to be evaluated.
Loops BX has only a single kind of loop, the while ... loop. Its syntax is inspired by C and consists of a single condition hexpri that is evaluated for every iteration of the loop. If the condition evaluates to true, then the body is evaluated, and and control subsequently returns to the start of the while ... loop. If the condition evaluates to false, the entire loop is skipped and control moves to the next instruction.
Structured Jumps The two structured jump statements, break and continue, are allowed to occur in the scope of a while ... loop. They are inspired by the identically named constructs from C.
• The break statement exits the innermost loop in which the statement occurs. In other words, control jumps to the statement after the innermost while ... statement, as if the condition of the statement had evaluated to false.
• The continue statement immediately jumps to the start of the innermost while ... loop. (It turns out that continue is not that useful in BX, but it will be a handy control structure when we add ranged for-loops to BX.)
It is a semantic error for these statements to occur outside the body of a loop.
5 IRGEN: FROM BX TO TAC (WEEK 2)
Type Information To begin with, build an abstract syntax tree (AST) structure for BX with support for type information. Use the features of your chosen programming language to achieve this. In lecture 4 you have seen how to do it in Python using a hierarchy of classes, with each expression subclass having a read-only .ty attribute that can be used to access the type of the expression. Place your AST classes in a separate module, say bxast.py.
Typed Maximal Munch It is your choice whether to use the untyped maximal munch (lecture 1) or typed maximal munch (lecture 4) to handle boolean expressions, but it should be obvious at a glance that the typed variant is shorter and considerably easier to understand. Therefore, it is recommended that you use the typed variant for handling conditions in if ... else ... and while ... statements.
Standalone Front-End Start by ignoring the back-end of the compiler (TAC onwards) and write a standalone BX to TAC converter. Call it bx2tac.py. Its behavior will be similar to the bx2tac.py program you wrote for lab 2: it will take a single .bx file as input and convert it to a corresponding .tac.json file.
Final Deliverable: bxcc.py To put things together, write an overall wrapper program called bxcc.py
(bxcc.exe if you are not usng Python) that will chain the phases corresponding to bx2tac and tac2x64 together to go from a .bx file to a .s file.

Grading Criteria For an A in the lab, just implement a correct compiler to x64. For an A+, you must implement typed maximal munch and produce reasonably good—i.e., must display a relevant line number at least—error messages for syntax errors and type errors.

Figure 6: An example gdb session