G. Compiler

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.

Input programs

Problem format

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.

Example input

2 3
0 12
1 5
halt - + call 2 3 call 2 4 call 2 5
* get 1 get 1

Meaning:

List of possible expressions in the input

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.
  1. Evaluate expr
  2. If result is > 0, evaluate and return expr_t (true branch)
  3. If result is <= 0, evaluate and return expr_f (false branch)
Example: > + 8 -5 * 2 2 * 3 3 is 4 (if 8-5 > 0 then 2*2 else 3*3) 		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.)

Target platform

Special registers:

General purpose registers:

Memory layout

Instruction set

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

Assembler

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.

Example output, a solution to the example input

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

Scoring

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.