COMP2012 PA2 Briefing
MAK Ching Hang (David)
chmakac@connect.ust.hk
PA2 Information
● Website: https://course.cse.ust.hk/comp2012/assignments/assignment2/
● Download Skeleton Code + Your Platform’s Library
○ Alternatively: Full Source Set
● Deadline: Apr 1st 23:59:00
PA2 Topic: Assembly Emulator
● Emulator: A program which simulates execution of another system
○ E.g.: Android/iOS Emulator - For developers to run their apps on their local machine
● Needs to replicate all parts of a processor (and more)
● You will need to implement parts of it
● Based (loosely) on ARMv7-A
● “Crash Course to COMP2611”
Your Objectives
1. Complete all implementations for InstructionAST.cpp
2. Write-up Abstract Base Class AST and ExprAST
Special Data Types
● Computer Hardware are Fixed-Size
● We want fixed-size data types to simulate hardware
○ short, int, long are not fixed-size
● Fixed-Size Data Types are provided for you
○ s8/s16/s32/s64: Signed integer (8/16/32/64-bit)
○ u8/u16/u32/u64: Unsigned integer (8/16/32/64-bit)
#include “Util.h”
Background
Assembly Language
● Low-level programming language
● Mapped one-to-one to instructions supported by the processor
● Differs from architecture-to-architecture
● Directly executed on your processor
● Most compiled languages “compile” to Assembly
C++ and (ARM) Assembly
int getInt();
int main() {
return getInt() + 1;
}
main:
push {r11, lr}
bl getInt()
add r0, r0, #1
pop {r11, lr}
b lr
Assembly
main:
push {r11, lr}
bl getInt()
add r0, r0, #1
pop {r11, lr}
b lr
● main
○ Label Name
○ Usually matches the function name
● push/pop {r11, lr}
○ (I will explain later)
● bl: “Branch with Link”
○ Jump to a label (but will come back later)
● b: “Branch”
○ Jump to a label (and won’t come back)
● r0, r11, #1, lr
Instruction Set Architecture (ISA)
● Definition of the internals of processors
○ List of supported instructions
○ Instruction variants and operands
○ Number and Size of Registers
○ …
● Common ISAs
○ x86 (and x86-64)
○ ARM (and AArch64)
○ MIPS (and MIPS64)
Abstract Syntax Tree (AST)
● A tree representing the syntax of a programming language
● Removes parsing ambiguity
● For example: a + b
operator+
|- variable a
|- variable b
a b
operator+
C++ AST
int main() {
int a = 1;
int b = 2;
return a + b;
}
FunctionDecl line:1:5 main 'int ()'
`-CompoundStmt
|-DeclStmt
| `-VarDecl used a 'int' cinit
| `-IntegerLiteral 'int' 1
|-DeclStmt
| `-VarDecl used b 'int' cinit
| `-IntegerLiteral 'int' 2
`-ReturnStmt
`-BinaryOperator 'int' '+'
|-ImplicitCastExpr 'int'
| `-DeclRefExpr 'int' lvalue Var 'a' 'int'
`-ImplicitCastExpr 'int'
`-DeclRefExpr 'int' lvalue Var 'b' 'int'
ASTs in PA2
● Each instruction/operand is one AST node
● The AST has been constructed for you
● You need to use these nodes to determine what to do for each instruction
● We will explain using AST classes from now onwards
https://course.cse.ust.hk/comp2012/assignments/assignment2/docs/classAST.html
Instructions
● Tells what the processor should do
● Composed of an opcode and operand(s)
○ Opcode: Name of the operation
○ Operands: What to operate on
● Example: add r1, r0, #1
○ The whole thing is the instruction
○ add is the opcode - The instruction perform addition
○ r1, r0, #1 are all operands - The addition is performed on these values
Instructions
● All instructions inherit from InstructionAST
● All derived classes have:
○ One constructor (accepting all required operands)
○ Destructor
○ void eval(Processor& processor)
○ Other accessors
○ Accessors for the instruction name and opcode
● One opcode may have multiple derived classes (if they have multiple forms)
○ E.g. AddInstructionAST
● Read the documentation for what each field should store
● We will come back to this later
Operands
● The “arguments” (formal parameters) of instructions
● Derived from OperandExprAST
● Contains:
○ Constructor
○ Destructor
○ Accessors for their contents and name
○ Helper functions?
Register Operands
● On-Processor fast memory
○ 100x faster than main memory
● RegisterOperandExprAST
● Either use getRegister or getRegisterIndex
○ getRegister returns Register
○ getRegisterIndex returns u8
● Register: Enum of all registers
Register List Operands
● A non-empty list of registers
● RegisterListOperandExprAST
● Functions
○ getListCount: The number of registers within this reglist operand
○ hasRegister: Whether the specified register exists in this reglist operand
Immediate Operands
● “Constant Value”
○ Embedded into the instruction
○ Prepended by #
● ImmOperandExprAST
● Functions
○ getUnsigned16: Returns the value as an unsigned 16-bit integer (may perform truncation)
○ getSigned16: Returns the value as a signed 16-bit integer (may perform truncation)
○ getUnsigned32: Returns the value as an unsigned 32-bit integer
○ getSigned32: Returns the value as a signed 32-bit integer
Indirect Operands
● “Dereferenced Pointer”
● Used mainly for memory locations
● Example: [r0]
○ “The value pointed to by the address in r0”
○ *r0
● Example: [r0, #4]
○ “The value pointed to by the address in (r0 + 4 bytes)”
○ *((char*) r0 + 4)
Indirect Operands
● IndirectOperandExprAST
● Functions
○ getRegisterTarget: The register operand storing the target address
○ getOffset: The immediate operand storing the relative memory offset
Detour: Stack Memory
● Memory for stack-allocated variables
● Grows from TOP to BOTTOM
○ Variables allocated first are stored at top-of-stack
○ Variables allocated last are stored at bottom-of-stack
● Hence: Last-In First-Out
● Implemented in MemStack.h
○ MemStack::store: Stores a given value into a specific location within the stack
○ MemStack::load: Loads a given value from a specific location within the stack
PA2 Details
Instructions: nop
● NopInstructionAST
● Does nothing
● Really, that’s it
Instructions: mov
● MovInstructionAST
● Copies the value of the source operand to the destination operand
○ Yes, COPY
● Two forms
○ RegMovInstructionAST: Register-to-Register mov
■ Source Operand is RegisterOperandExprAST
○ ImmMovInstructionAST: Immediate-to-Register mov
■ Source Operand is Imm32OperandExprAST
Instructions: str
● StrInstructionAST
● Stores the value of a register into the stack memory
○ Source: RegisterOperandExprAST
○ Destination: IndirectOperandExprAST
Instructions: ldr
● LdrInstructionAST
● “Reverse str”
● Loads the value of a register from the stack memory
○ Destination: RegisterOperandExprAST
○ Source: IndirectOperandExprAST
Instructions: add
● AddInstructionAST
● Adds the value of two source operands and saves the result to the destination
operand
● Two forms
○ RegAddInstructionAST: 3rd Operand is a Register
■ Source 2 Operand is RegisterOperandExprAST
○ ImmAddInstructionAST: 3rd Operand is an Immediate
■ Source 2 Operand is Imm32OperandExprAST
Instructions: sub
● SubInstructionAST
● Subtracts the value of the third operand from the second operand and saves
the result to the destination operand
● Two forms
○ RegSubInstructionAST: 3rd Operand is a Register
■ Source 2 Operand is RegisterOperandExprAST
○ ImmSubInstructionAST: 3rd Operand is an Immediate
■ Source 2 Operand is Imm32OperandExprAST
Instructions: push
● PushInstructionAST
● Decrements the stack pointer, and stores the contents of the register-list into
the stack
○ Stack pointer decrement depends on the how many registers are in the register-list
○ Each register = 4 bytes
○ Lower-number registers should be stored in lower memory addresses
○ “Multi-str”
Instructions: pop
● PopInstructionAST
● Loads the contents of the register-list from the stack, and increments the
stack pointer
○ Stack pointer increment depends on the how many registers are in the register-list
○ Each register = 4 bytes
○ Lower-number registers should be loaded in lower member addresses
○ “Multi-ldr”
Header Files
● Read the assignment description
○ It should be pretty clear
Other Information
Pointer Ownership
● All pointers passed into your constructor point to heap-allocated memory
● The caller of your constructor will NOT free the memory for you
● You need to be responsible for that memory
Unsigned Overflow
● Signed overflow is undefined behavior
○ Compiler may do anything
● You should use unsigned for add/sub
○ They always wraparound
○ 0 - 1 = maximum of the unsigned data type
○ Maximum of the unsigned data type + 1 = 0
● Unsigned addition/subtraction is equivalent to signed addition/subtraction
(bitwise)
○ 0b00 - 0b01 = 0b11 (Signed: 0 - 1 = -1)
○ 0b11 + 0b01 = 0b00 (Signed: -1 + 1 = 0)
Debugging
● Processor::dump
○ Outputs the state of the processor at a given point
○ Read the description for explanation of the output
● Processor::Processor(bool)
○ Setting the parameter to true enables Processor::dump on every instruction
● Valgrind
● Compiler warnings
● Read the description again?
Other Notes
● Documentation is available
● Do not do more than what is asked of you
○ I.e. Do not perform unnecessary operations!
● Write your own test cases based on the specifications
○ The given test case is very rudimentary
● You can test with your own programs
○ Go to https://godbolt.org/, change compiler to “armv7a-clang”, and write C++ on left-hand side
○ Not all programs are supported
● Piazza is always open for clarifications
● This assignment is easier than it looks
○ A lot of the description is for your information
Questions?