COOL compiler note

COOL_compiler_note.md

Backend

IR -> IR Optimization -> Code Generation(Register allocation/Instruction selection) Assembly

Code generation

1.top-of-stack caching (1-TOSCA)
2.init garbage collector

Object layout

1.similar to C++ inheritance
2.gc in COOL runtime
3.Class Tag, Object Size, Dispatch table pointer (similar to C++ vptr), Dispatch table (similar to C++ vtable)
4.register allocation is Graph coloring
(Linear-Scan Register Allocation is another way to allocate registers)

IR

1.Three-address code (it doesn't be implemented in this course)

Runtime

1.it contains a concurrent garbage collector
2.the management of application memory
3.how the program accesses variables, mechanisms for passing parameters between procedures
4.interfacing with the operating system
5.The compiler makes assumptions depending on the specific runtime system to generate correct code.

GC (cgen.cc)

gc is also part of the program

Questions

1.gc in runtime
2.how gc works
3.stack-based virtual machine -> register-based virtual machine (?
4.code generation
4-1. stack based machine
4-2. register based machine
-> register allocation and assignment
-> instruction selection/instruction scheduling
5. how to verify and test compiler?

mips vs arm (both are 32-bit)

MIPS code         ARM code                      Comment

la   $1,X         ADR r1,X       Load a pointer. Note use of pseudo instruction in both cases

la   $2,Y         ADR r2,Y  

la   $3,Z         ADR r3,Z  

1w   $1,0($1)     LDR r1,[r1]    Load the value of X

1w   $2,0($2)     LDR r2,[r2]  

1w   $3,0($3)     LDR r3,[r3]  

addu $2,$2,$1     ADD r2,r2,r1   Add X and Y

subu $2,$2,$3     SUB r2,r2,r3   Subtract Z

la   $4,P         ADR r4,P       Load pointer to P

sw   $2,0($4)     STR r2,[r4]  



 # data in $t1-$t5     ; data in r1-r5    Yes, even comments are handled differently

  mul   $t1,$t2,$t3     MUL r1,r2,r3       The MIPS multiplication is a pseudo instruction

  addiu $t1,$t1,1       ADD r1,r1,#1       Add 1 to register 1

  ori   $t1,$t1,$t4     AND r1,r1,r4       Do an AND

  ori   $t1,$1,0xFF     ADD r1,r1,#0xFF    Do a logical OR with a literal

  move  $t5,$t1         MOV r5,r1          Note that the MIPS move is a pseudo instruction

; mips                    arm
la   $t1,X                ADR r1,X ; Load a pointer. Note use of pseudoinstruction in both cases

1w   $t1,0($t1)        LDR r1,[r1]  ;Load the value of X
1w   $t2,4($t2)       LDR r2,[r2,#4]  
lw   $t3,8($t3)        LDR r3,[r3,#8] 
addu $t2,$2,$t1     ADD r2,r2,r1 ;Add X and Y
subu $t2,$t2,$t3    SUB r2,r2,r3 ;Subtract Z
sw   $t2,12($t4)      STR r2,[r4,#12] 


.data  
X: DCW 0x1234      X DCW 0x1234  ;Declare X and put 0x1234 in memory
Y: .word 0x5678      Y DCW 0x5678   
Z: .word 0xABCD    Z DCW 0xABCD  ;Declare P and reserve 4 bytes of memory
P: .space 4              P SPACE 4  ;Declare P and reserve 4 bytes of memory

---

MIPS Stack

stack frame layout

-------<- start of previous stack frame

------<- arguments for calling current stack, func(a0, a1, a2, a3...)
$a3
$a2
$a1
$a0
------<-sp + (4n) // start of current stack frame, which is also end of previous stack frame
ra
------<-sp + (4n)-4
fp (for non-leaf function if necessary)
------<-sp + 4n
saved_registers($s.., save before calling next function/restore after returning from next function)
------<-
local variable ($t..)
------<-
arguments for calling another function ($a..)
------<-sp // end of current stack frame

push/pop stack frame

.globl func_a
func_a:
sub $sp, $sp, 12
sw $ra, 8($sp)
sw $fp, 4($sp)
move $fp, $sp   # $fp = $sp
jal func_b
# sw $v0, 0($fp) # store v0 (func_b return result)

# ... 

# lw $v0, 0($fp) # load v0 (func_b return result)
move $sp, $fp   # $sp = $fp
lw $fp, 4($sp)
lw $ra, 8($sp)
addi $sp, $sp 12
jr $ra

Cool compiler (mips) on mac

Lexer

make -f Makefile.Mac lexer

Parser

make -f Makefile.Mac parser

Semant

make -f Makefile.Mac semant

Code generator

make -f Makefile.Mac cgen

Compile

../PA2/lexer ../../examples/hello_world.cl | ../PA3/parser | ../PA4/semant | ./cgen

output mips assembly file(.s)

../PA2/lexer ../../examples/hello_world.cl | ../PA3/parser | ../PA4/semant | ./cgen -o ./hello_world.s

pipe together

test_coolc

#!/bin/bash
./assignments/PA2/lexer $* | ./assignments/PA3/parser $* | ./assignments/PA4/semant $* | ./assignments/PA5/cgen $*

chmod +x ./test_coolc

spim

# install spim
brew install spim
# replace trap handler
cp trap.handler /usr/local/Cellar/spim/{spim-version}/share/exceptions.s 
# execute .s
spim -file [your_mips_file.s]

Reference

https://github.com/gboduljak/stanford-compilers-coursework

---

Cool compiler (aarch64)

Lexer

make -f Makefile.Mac lexer ARCH=aarch64

Parser

make -f Makefile.Mac parser ARCH=aarch64

Semant

make -f Makefile.Mac semant ARCH=aarch64

Code generator

make -f Makefile.Mac cgen ARCH=aarch64

aarch64 note

1. SP_EL0 is an alias for SP. Do not use SP as a general purpose register.
2. You can use the SPSel register to select which stack pointer to use in the exception level.

MSR SPSel, #0 ; switch to SP_EL0
MSR SPSel, #1 ; switch to SP_ELn

Source: https://developer.arm.com/documentation/dui0801/g/Overview-of-AArch64-state/Stack-Pointer-register

.space

The .skip and .zero directives are aliases for the .space directive.

label

target:
     .word 0x1 // target value is 0x1, target address is 0x12345678

adr   x0, target     //   x0 is 0x12345678
ldr    x0, target     //   x0 is 0x12345678
// what is the difference between adr and ldr ?

ldr    x0, [x0]  // now, x0 is 0x1 at addr `0x12345678`

REF: What is the difference between =label (equals sign) and [label] (brackets) in ARMv6 assembly?

ldr     x0, =0x7 // 0x7 is addr, so x0 is 0x7

// but
ldr x0, =label1 // x0 is label1 addr
// 等同於
ldr     x0, label1
label1:
   .word 0x7

it's not allowed to mov r0, 0x12345678 (Error: immediate cannot be moved by a single instruction)

system call

read (int) : 0x3f (63)
write (int): 0x40 (64)
write (str): 0x40 (64)
brk: 0xd6 (214)
exit: 0x5d (93)

exception handling

when an exception occurs:
 - SPSR_ELn updated 
 - PSTATE updated （EL stays the same OR gets higher）
 - Return address stared to ELR_ELn 
 - ESR_ELn updated with cause of exception 
 - Branches to the exception table
 
 To return from an exception execute ERET instruction
 - Restores PSTATE from SPSR_ELn 
 - Restores PC from ELR_ELn

mrs x0, NZCV // Read the NZCV flags into r0
and x0, xzr, x0 // Clear the flags
msr NZCV, x0 // Write the flags back
/*
NZCV: Condition Flags
DAIF: Interrupt Bits (A: SError interrupt mask; I: IRQ interrupt mask; F: FIQ interrupt mask)
CurrentEL: Current Exception Level
*/

eret (=rfe in mips): return from an exception
VBAR_EL1 (Vector Based Address Registers in EL1)

Exception types
The type of exception (SError, FIQ, IRQ, or Synchronous)

CurrentEL bits[3:2] (bit #3 - bit #2)
00 (EL0)
01 (EL1)
10 (EL2)
11 (EL3)

---

not

not a = ~a

e.g. not(0) = not(0x00000000) = 0x11111111 = -1

mov x1, #0
mvn x1, x1 // x1 = -1

---

ldrb

load a unsigned byte

  .data
fmt_ldrb_print: .string "0x%x\n"
ldrb_num: .word 0x56fe

  .text
ldr x0, =fmt_ldrb_print
ldr x2, =ldrb_num
ldrb w1, [x2, #0]
bl printf  // 0xfe

ldr x0, =fmt_ldrb_print
ldr x2, =ldrb_num
ldrb w1, [x2, #1]
bl printf // 0x56

Garbage Collection

Simple Generational Garbage Collection and Fast Allocation by Andrew W. Appel (which is used in COOL runtime)

Source: 作業系統設計與實作 @kaiiiz

More details: ESR_EL1

Holds syndrome information for an exception taken to EL1.

[63:32]	[31:26]	[25]	[24:0]
Reserved	EC	IL	ISS

• EC: Exception Class. Indicates the reason for the exception that this register holds information about.
• IL: Instruction Length for synchronous exceptions.
• ISS: Instruction Specific Syndrome.

When EC = 0b000000 (exception with an unknown reason), ISS is not valid

void sync_exc_router(unsigned long esr, unsigned long elr) {
    int ec = (esr >> 26) & 0b111111;
    int iss = esr & 0x1FFFFFF;
    if (ec == 0b010101) {  // system call
        switch (iss) {
            case 1:
                uart_printf("Exception return address 0x%x\n", elr);
                uart_printf("Exception class (EC) 0x%x\n", ec);
                uart_printf("Instruction specific syndrome (ISS) 0x%x\n", iss);
                break;
            case 2:
                arm_core_timer_enable();
                arm_local_timer_enable();
                break;
            case 3:
                arm_core_timer_disable();
                arm_local_timer_disable();
                break;
            case 4:
                asm volatile ("mrs %0, cntfrq_el0" : "=r" (cntfrq_el0)); // get current counter frequency
                asm volatile ("mrs %0, cntpct_el0" : "=r" (cntpct_el0)); // read current counter
                break;
        }
    }
    else {
        uart_printf("Exception return address 0x%x\n", elr);
        uart_printf("Exception class (EC) 0x%x\n", ec);
        uart_printf("Instruction specific syndrome (ISS) 0x%x\n", iss);
    }
}

學習實作小型作業系統 (筆記) @tina0405
QEMU: 使用 Decodetree 新增 RISC-V 指令
(wip) a simple OS for aarch64
軟體開發平台及語言筆記大全
使用KVM的API寫一個簡單的AArch64虛擬機器
10分鐘讀懂 linker scripts
Linker Script初探 - GNU Linker Ld手冊略讀

boot in qemu-system-aarch64

qemu-system-aarch64 -m 4096 -cpu cortex-a72 -smp 4 -M virt -nographic -bios QEMU_EFI.fd -drive if=none,file=ubuntu-20.04-arm64.img,id=hd0 -device virtio-blk-device,drive=hd0 -drive file=user-data.img,format=raw -device virtio-net-device,netdev=net0 -netdev user,hostfwd=tcp:127.0.0.1:2222-:22,id=net0

username: ubuntu
password: asdfqwer

REF:
ARM64 Linux on Win10
QEMU + Ubuntu ARM aarch64
ubuntu-18.04-server-cloudimg-arm64.sh
qemu-arm64.sh

ssh connect to qemu

ssh ubuntu@localhost -p 2222

Question:

1. E514: write error (file system full?)

ubuntu@ubuntu:~$ df -hl

Filesystem      Size  Used Avail Use% Mounted on
udev            1.9G     0  1.9G   0% /dev
tmpfs           393M   21M  372M   6% /run
/dev/vda1       2.0G  2.0G     0 100% /
tmpfs           2.0G     0  2.0G   0% /dev/shm
tmpfs           5.0M     0  5.0M   0% /run/lock
tmpfs           2.0G     0  2.0G   0% /sys/fs/cgroup
/dev/loop0       49M   49M     0 100% /snap/core18/2127
/dev/loop1       58M   58M     0 100% /snap/core20/1084
/dev/loop2       62M   62M     0 100% /snap/lxd/21032
/dev/loop3       61M   61M     0 100% /snap/lxd/21544
/dev/loop4       29M   29M     0 100% /snap/snapd/12886
/dev/vda15       98M  290K   98M   1% /boot/efi

How to fix :

Remember to ssh connect to qemu : "ssh ubuntu@localhost -p 2222"

Step1: resize the ubuntu image
qemu-img resize [your_image_name] +8G // add more 8G
e.g. qemu-img resize ubuntu-20.04-arm64_10G.img +8G

Step2: To avoid a No space left on the block device error
sudo mount -o size=10M,rw,nodev,nosuid -t tmpfs tmpfs /tmp

Step3: Run the growpart command to grow the size of the root partition or partition 1
sudo growpart /dev/vda 1

Step4: Expand the file system (e.g. EXT2/EXT3/EXT4 file system)
sudo resize2fs /dev/vda1

Step5: Unmount the tmpfs file system (/tmp which is done in Step2)
sudo umount /tmp

REF:
How do I increase the size of my EBS volume if I receive an error that there's no space left on my file system?
Error message "sudo: unable to resolve host (none)" (echo $(hostname -I | cut -d\ -f1) $(hostname) | sudo tee -a /etc/hosts)

2. fgets not waiting for user input
   scanf does not consume the '\n' that follows the number. The next fgets reads that 1 character '\n'.

---

transfer a file from host to guest in qemu

rsync -e 'ssh -p [ssh port]' [file_in_host] [user_name]@localhost:[guest dir] (from host to guest)
e.g.
rsync -e 'ssh -p 2222' ./main ubuntu@localhost:/home/ubuntu

ref: How to Transfer Files with Rsync over SSH

---

debug with gdb

gdb ./main2

Reading symbols from ./main2...
(gdb) run
Starting program: /home/ubuntu/main2 

Program received signal SIGILL, Illegal instruction.
main () at main2.c:6
6		__asm__ ("mrs x0, CurrentEL;" : : : "%x0");
(gdb) x/i $pc
=> 0xaaaaaaaaa774 <main+8>:	mrs	x0, currentel
(gdb) where
#0  main () at main2.c:6

---

Write a linux module to show the current exception level of aarch64 in qemu

Ref: 如何寫一個 Linux Kernel Module

hello.c

#include <linux/init.h>
#include <linux/module.h>

MODULE_DESCRIPTION("Hello_world");
MODULE_LICENSE("GPL");

static int hello_init(void) {
	register uint64_t x0 __asm__ ("x0");
	__asm__ ("mrs x0, CurrentEL;" : : : "%x0");
	printk(KERN_INFO "EL = %llu \n", x0 >> 2);
	return 0;
}
static void hello_exit(void) {
  	printk(KERN_INFO "Bye\n");
}

module_init(hello_init);
module_exit(hello_exit);

Makefile

PWD := $(shell pwd) 
KVERSION := $(shell uname -r)
KERNEL_DIR = /usr/src/linux-headers-$(KVERSION)/

MODULE_NAME = hello
obj-m := $(MODULE_NAME).o

all:
	 make -C $(KERNEL_DIR) M=$(PWD) modules
clean:
	 make -C $(KERNEL_DIR) M=$(PWD) clean

make // compile into kernel module hello.ko
sudo insmod hello.ko  // load module
sudo rmmod hello.ko // remove module
sudo lsmod | grep "hello" // find module hello.mo
dmesg // show kernal log "KERN_INFO"
tail -1 /var/log/kern.log // show the last one message in kernal log

QEMU "-bios" vs. "-kernel" vs. "-device loader,file=..."
qemu-system-aarch64 entering el1 when emulating a53 power up

How to generate an exception ??
How to implement a customized exception ??
How to print a message of exception ??

basic signal handler to simulate uncaught exception handler in mips

#include<stdio.h>
#include<signal.h>
#include<unistd.h>
#include<stdlib.h>


void sig_handler(int signum){

  //Return type of the handler function should be void
  printf("\nsignnum %d", signum);
  //printf("\nInside handler function\n");
  printf("\nUncaught Exception of Class ");
  printf("\nthrown. COOL program aborted.\n");
  //abort();
  //exit(0);
  exit(1);
}
void sig_handler2(int signum){
  //raise(SIGQUIT);
  //raise(SIGSEGV);
  //raise(SIGILL);
  raise(SIGSYS);
}

int main(){
  //signal(SIGINT,sig_handler); // Register signal handler
  //signal(SIGINT,SIG_IGN); // Register signal handler for ignoring the signal
  signal(SIGINT, sig_handler2);
  //signal(SIGQUIT, sig_handler);

  signal(SIGFPE, sig_handler);
  signal(SIGILL, sig_handler);
  signal(SIGSEGV, sig_handler);
  signal(SIGBUS, sig_handler);
  signal(SIGABRT, sig_handler);
  signal(SIGSYS, sig_handler);

  for(int i=1;;i++){    //Infinite loop
    printf("%d : Inside main function\n",i);
    
    // int i, j;
    // for(i = 0; i < 10; i++) 
    // {
    //     // Call signal handler for SIGFPE
    //     j = i / 0;
    // }
    sleep(1);  // Delay for 1 second
  }
  return 0;
}

Ref:
How to use signal handlers in C language?
24.2.1 Program Error Signals
How to set up a callback function when an Exception occurs?
Writing your own startup code for Cortex-M
arm64 vector table

as main.s -o main.o
ld main.o -o main -lc

as -g // add debug symbol for gdb

as hello_world.s -o hello_world.o
as trap_handler_aarch64.s -o trap_handler_aarch64.o
ld hello_world.o trap_handler_aarch64.o -o hello_world -lc
setarch `uname -m` -R ./hello_world // temporarily disable ASLR for a particular program

// ASLR = address space layout randomization 

---

(gdb) x/8xw $sp // examine sp, from sp to show next 8 words in hex format
(gdb) x $sp // examine $sp => 0xfffffffffab8: 0x00000004 , address is 0xfffffffffab8 and value is 0x00000004
(gdb) x $sp+4 // examine $sp+4 => 0xfffffffffabc: 0x004003a8 , address is 0xfffffffffabc and value is 0x004003a8
(gdb) set *((int*)$sp)=0x4 // save value0x4 at address of sp
(gdb) p *((int*)($sp)) // get value in decimal format at address of sp
(gdb) p/x *((int*)($sp+4)) // get value in hex format at address of sp+4
(gdb) watch *(address) // watch this address
(gdb) info address [yout_symbol] // check yout_symbol from address
(gdb) info symbol [your_addr] // check your_address from symbol

// decimal format: 10進位格式
// hex format: 16進位格式
NOTE:
ldr w9, [x9, #12] // ok
ldr w9, [w9, #12] // error

str w9, [x9, #12] // ok
str w9, [w9, #12] // error

ldr x2, =stdin // ok
ldr w2, =stdin // error, relocate problem

blr x12 // ok
blr w12 // error

adr x12 label // ok
adr w12 label // error

---

gdb in assembly

Show current assembly instruction in GDB
How to break on assembly instruction at a given address in gdb?
Jumping to the next "instruction" using gdb
Step out of current function with GDB
How do I jump to a breakpoint within GDB?
GDB: Change string in memory on stack
Can I have gdb break on read/write from an address? [duplicate]

step vs next
(程式碼專用)step (會進入子函數)
(程式碼專用)next (不會進入子函數)
(指令專用) stepi/si
(指令專用) nexti/ni

---

Ref : Porting to 64-bit ARM by Chris Shore, ARM

---

watch *0x413ffc == 0x33280041 // x7
because when calling "bl puts", value of "0x1" (stdout), which means $x1 was overwritten...

---

No segmentation fault if program running under gdb

Linux下關閉ALSR(地址空間隨機化)的方法

setarch `uname -m` -R ./yourProgram

---

gdb input file

(gdb) show debug-file-directory
The directory where separate debug symbols are searched for is "/usr/lib/debug".
(gdb) set debug-file-directory // set /home/ubuntu as debug directory
(gdb) r < g1.graph // input /home/ubuntu/g1.graph to graph executable

0< filename // Reads stdin from filename.
< filename // Reads stdin from filename.
1> filename // Writes stdout to filename.
> filename // Writes stdout to filename.
2> filename // Writes stderr to filename.
2>&1 // Writes stderr to the same place as stdout.
>& file //Writes both stdout and stderr to filename.
>> filename // Appends stdout to filename.
>>& filename // Appends both stdout and stderr to filename.

(gdb) x &stdin
0x4149b8 <stdin@@GLIBC_2.17>: 0xf7fc6898
(gdb) x 0xf7fc6898
0xf7fc6898: Cannot access memory at address 0xf7fc6898

// =stdin
x2, 403938 <_NoGC_Collect_ok+0x98>
ldr w2, 4038e8 <_NoGC_Collect_ok+0x48>

(gdb) x $x2
0xfffff7fc6898 <_IO_2_1_stdin_>: 0xfbad2088
(gdb) x &stdin
0x4111b0 <stdin@@GLIBC_2.17>: 0xf7fc6898
_IO_2_1_stdin_

Temp sol:
ldr x2, =0xfffff7fc6898 // stdin 0xfffff7fc6898 <IO_2_1_stdin>: 0xfbad2088
ldr x2, =0xfffff7fc7548 // stdout 0xfffff7fc7548 <IO_2_1_stdout>: 0xfbad2084

ubuntu@ubuntu:~$ readelf -r graph

Relocation section '.rela.dyn' at offset 0x3b0 contains 1 entry:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
0000004149b8  000a00000400 R_AARCH64_COPY    00000000004149b8 stdin@GLIBC_2.17 + 0

Relocation section '.rela.plt' at offset 0x3c8 contains 9 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000414000  000100000402 R_AARCH64_JUMP_SL 0000000000000000 strlen@GLIBC_2.17 + 0
000000414008  000200000402 R_AARCH64_JUMP_SL 0000000000000000 exit@GLIBC_2.17 + 0
000000414010  000300000402 R_AARCH64_JUMP_SL 0000000000000000 raise@GLIBC_2.17 + 0
000000414018  000400000402 R_AARCH64_JUMP_SL 0000000000000000 sbrk@GLIBC_2.17 + 0
000000414020  000500000402 R_AARCH64_JUMP_SL 0000000000000000 memset@GLIBC_2.17 + 0
000000414028  000600000402 R_AARCH64_JUMP_SL 0000000000000000 sscanf@GLIBC_2.17 + 0
000000414030  000700000402 R_AARCH64_JUMP_SL 0000000000000000 puts@GLIBC_2.17 + 0
000000414038  000800000402 R_AARCH64_JUMP_SL 0000000000000000 printf@GLIBC_2.17 + 0
000000414040  000900000402 R_AARCH64_JUMP_SL 0000000000000000 fgets@GLIBC_2.17 + 0

Using the Stack in AArch32 and AArch64
AArch64, sp must be 16-byte aligned whenever it is used to access memory.

// Broken AArch64 implementation of `push {x1}; push {x0};`.
 str   x1, [sp, #-8]!  // This works, but leaves `sp` with 8-byte alignment ...
 str   x0, [sp, #-8]!  // ... so the second `str` will fail.

// AArch64 implementation of `push {x0, x1}`.
 stp   x0, x1, [sp, #-16]!

---

assembly difference between .s and .S
source

.S (capital S) stands for assembly code that must still pass through a pre-processor. That means it can have #include and #define among other macros. It can also be seeing as extension .sx

.s (lower s) is pure assembly code that can be compiled into an object.

shell script

10.1. Manipulating Strings: Substring Removal
How do I parse command line arguments in Bash?

known issues

1. How to work under ASLR ? (fPIC?)
2. stdin/stdout is hardcoded. (Type: R_AARCH64_COPY)
3. fflush(stdin) before fgets (problem)
4. Under GC mode, Program received signal SIGSEGV, Segmentation fault. _GenGC_MajorC_stackloop () at trap_handler_aarch64.s

(gdb)x/xg is equivalent to x/2xw (g: 8-byte, w: 4-byte)

0xfffffffffad0: 0x0040128c
(gdb) x/4xw 0xfffffad0