Your task is to write a compiler for a simple programming language. The result should be assembly code that we can compile for our old and forgotten 16-bit minicomputer. The programs of the teams compete against each other (this is a scaled problem). Submission scoring is based on the number of cycles your program takes to execute. Faster programs score better. To ensure validity of submissions, programs have a return value, and operate on an I/O memory (the contents of which are known only to your program at runtime). Programs that produce invalid output will not be accepted. |
![]() |
To make your task slightly easier, we allow you to run programs in debugging mode. You can enable this by making your submission to problem "X" instead of problem "G", and enabling the "detailed log" checkbox. In this case, you will receive a trace of execution. Note however, that you will not get a score for these submissions. Also, the contents of the I/O memory may be different from the real submissions. Please note that by submitting to problem "X" instead of problem "G", you ensure that you will get no trace penalty (however, you can ask for a such trace only once every 5 minutes).
If your submitted program runs much longer than it reasonably should, we might kill it before it HALTs. These runs will be considered a failure.
Line 1 contains two integers:
number of functions number of general purpose registers
From line 2, a line for each function, with two integers:
number of arguments length of definition in words
Then a line for each function with the function definition.
Function definitions are given in prefix notation.
2 3 0 12 1 5 halt - + call 2 3 call 2 4 call 2 5 * get 1 get 1
Meaning:
Expression | Value / Meaning | Relevant machine instruction |
---|---|---|
+ expr1 expr2 | expr1 + expr2 | ADD |
- expr1 expr2 | expr1 - expr2 | SUB |
* expr1 expr2 | expr1 * expr2 (lower 16 bits) | MULT |
/ expr1 expr2 | expr1 / expr2 | DIV |
% expr1 expr2 | expr1 % expr2 | DIV |
halt expr | Call HALT with expr | HALT |
get argument_number | Value of argument, numbered from 1 | BPGET, others |
set argument_number expr | Set value of argument numbered from 1 to expr, returned value is expr | BPSET, others |
call function_number arg1 ... | Call function, numbered from 1, with given arguments | CALL, others |
in expr1 | Read memory at address expr1+32000 | LOADAT |
out expr1 expr2 | Write memory at address expr1+32000, using value expr2; returned value is expr2 | STOREAT |
> expr expr_t expr_f | Conditional.
| SGT |
Note that all expressions have a return value, and thus any expression can stand as an argument to another expression. (halt is an exception, because its return value will never be used.)
Special registers:
General purpose registers:
Memory layout
Instruction | Action | Used cycles | Size (words) | Memory & General |
---|---|---|---|
LOAD reg const | Load into register from constant address. | 2 | 2 |
LOADAT reg1 reg2 | Load into reg1 from address in reg2. | 3 | 1 |
STORE reg const | Store value in reg1 at constant address. | 2 | 2 |
STOREAT reg1 reg2 | Store value in reg1 at address in reg2. | 3 | 1 |
DATA reg const | Load constant into register. | 1 | 2 |
MOV reg1 reg2 | Copy value in reg1 into reg2. | 1 | 1 |
BPGET reg const | Load into register from address BP+const. | 3 | 2 |
BPSET reg const | Store value in register at address BP+const. | 3 | 2 | Arithmetic |
NEG reg | Negation: reg := (0 - reg) | 1 | 1 |
ADD reg1 reg2 | Addition: reg1 := reg1 + reg2 | 1 | 1 |
SUB reg1 reg2 | Subtraction: reg1 := reg1 - reg2 | 1 | 1 |
MULT reg1 reg2 | Multiplication: reg1 := (reg1 * reg2) & 0xffff, reg2 := (reg1 * reg2) >> 16 The case when reg1 is the same as reg2 is undefined. | 1 | 1 |
DIV reg1 reg2 | Division: reg1 := reg1 / reg2, reg2 := reg1 % reg2 The case when reg1 is the same as reg2 is undefined. | 1 | 1 | Flow control |
JMP const | Jump to constant address. | 1 | 2 |
JMPI reg | Jump to address in register. | 2 | 1 |
SGT reg | If value in register > 0, skip following instruction. | 1 | 1 |
HALT reg | Halt execution, final result is value in register. | 0 | 1 | Stack |
PUSH reg | Store register at address in SP, then decrease SP by 1. | 3 | 1 |
POP reg | Increase SP by 1, then load value at new address in SP into the register. | 3 | 1 |
CALL const | Push offset of instruction after CALL, then jump to constant address. | 3 | 2 |
CALLI reg | Push offset of instruction after CALLI, then jump to address in register. | 3 | 1 |
RET | Pop, jump to resulting address. | 3 | 1 |
Jump labels may be defined like this (on their own line):
labelname:
Jump labels must be unique. The names of jump labels can be used anywhere as the value of a constant; the address of the instruction directly following the definition of the label will be substituted.
function1: data r0 3 ; 3*3 call function2 push r0 data r0 4 ; 4*4 call function2 pop r1 ; result of 3*3 add r0 r1 ; add to result of 4*4, save push r0 data r0 5 ; 5*5 call function2 pop r1 ; (3*3+4*4) - 5*5 sub r1 r0 halt r1 ; halt(result) function2: mov r0 r1 ; mult r0 r0 is undefined mult r0 r1 ret
The exact formula that determines your final score is:
finalscore = 20 + 80(5-value/min)/4
Where min is the score received by the best submission so far, and value is the score received by your submission.