Optimization Analysis¶
Copied from https://joldosh.blogspot.com/2019/12/optimized-msp430-assembly-in-mecrisp.html
A few years ago, I got interested in Forth due to its connection to RPN calculators but lost interest because of the huge hit to performance a stack-based system takes on an architecture like 6502. Recently, my interest was piqued again during a conversation in the #Forth IRC channel on FreeNode about Mecrisp-Across, which uses an ARM-based microcontroller board to produce optimized assembly for the MSP430. Because the compiler tries to keep values in registers instead of the stack, it has the potential to reclaim some of the performance lost in most Forths. Some of these optimizations might be useful for a 6502-based Forth, so I tried to understand how optimizations in Mecrisp work.
The first step was getting Mecrisp running on a PC. The author provides versions that are compiled for ARM with Linux system calls, so you can use QEMU for emulation under Linux. Getting this working on Windows was a real challenge. One Debian image I tried emulating with QEMU crashed the emulator outright. Another image booted into Linux but refused to install QEMU complaining about needing the Linux CD in the drive before it would install any packages. Getting Ubuntu working on VirtualBox under Windows 10 and installing QEMU on it wasn’t too tough, but the Mecrisp image wouldn’t run until I got the right type of QEMU (there are several). The right combination was VirtualBox, an Ubuntu image from OSboxes, and QEMU-user-static.
Mecrisp-Across has a host mode for compiling and other high level tasks and a target mode for defining Forth words for the MSP430. The documentation shows that you can only compile once after typing in your words and then you have to erase everything before compiling again. Maybe this is reasonable considering how little memory there is to work with. You can save some time by saving all your commands to a file then using cat and a pipe to direct the file contents to QEMU:
Code Analysis¶
cat test.txt | qemu-arm-static mecrisp-stellaris-linux-with-mecrisp-across
The file itself is pretty simple to set up, and you can generate a binary with just a few lines.
new
target
: main 2 2 + ; \ main program
host
$FFFE vector main
crosscompile
disimage
The last line shows a disassembly of the compiled program, which is the really interesting part. Here is the first program I tried:
Does the compiler folds constants and if so, if it does it between words?¶
: t1 3 + ;
: t0 5 * t1 ;
: main 7 t0 ;
This should calculate 7 * 5 + 3 and leave 38 on the stack.¶
Here is the generated assembly:
F800: 40B2 mov.w #5A80h, &120h
F802: 5A80
F804: 0120
F806: 4031 mov.w #280h, r1
F808: 0280
F80A: 4034 mov.w #260h, r4
F80C: 0260
F80E: 8324 sub.w #2h, r4
F810: 4684 mov.w r6, 0h(r4)
F812: 0000
F814: 4036 mov.w #26h, r6
F816: 0026
F818: 3FFF jmp F818
F800 to F80C disables the watchdog timer and sets up the two stacks. F80E - F812 saves r6 and the next line loads r6 with the calculated value 38, so it is folding constants even between words! One thing we can see is that mov.w #260h, r4 and sub.w #2h, r4 could be combined into mov.w #25Eh, r4, although it might not be optimized if the setup code is just boilerplate. Also, the line saving r6 to the stack could be eliminated since r6 is uninitialized at that point.
Does it also fold constants when an if statement is involved?¶
: t2 dup 38 = if 5 then ;
: t1 3 + t2 ;
: t0 5 * t1 ;
: main 7 t0 ;
(setup removed)
F80E: 8224 sub.w #4h, r4
F810: 40B4 mov.w #26h, 0h(r4)
F812: 0026
F814: 0000
F816: 4684 mov.w r6, 2h(r4)
F818: 0002
F81A: 4036 mov.w #5h, r6
F81C: 0005
F81E: 3FFF jmp F81E
This saves the calculated 38 to the stack and keeps 5 in TOS as expected.
Does constant folding also work in loops?¶
This code sums all the numbers from 1 to n, where here n is 7:
: sum 0 swap 1+ 1 do i + loop ;
: main 7 sum ;
(setup removed)
F80E: 4307 mov.w #0h, r7
F810: 4318 mov.w #1h, r8
F812: 4239 mov.w #8h, r9
F814: 480A mov.w r8, r10
F816: 570A add.w r7, r10
F818: 5318 add.w #1h, r8
F81A: 9908 cmp.w r9, r8
F81C: 4A07 mov.w r10, r7
F81E: 23FA jnz F814
F820: 8324 sub.w #2h, r4
F822: 4684 mov.w r6, 0h(r4)
F824: 0000
F826: 4706 mov.w r7, r6
F828: 3FFF jmp F828
Other than unnecessarily caching r6 on lines F820 - F824, this is close to the version you would write in assembly, which is impressive. It doesn’t use the stack at all. Unfortunately, it does not collapse constants in this case, even though there is enough information to calculate the answer at compile time.
How register allocations are handled in situations where the size of the stack cannot be determined at compile time.¶
: main 3 4 P1IN @ 5 = IF 6 THEN * ;
Here, stack starts with [3 4] and depending on the input of P1IN may become [3 4 6]. Therefore, the * instruction can’t predict whether it will multiply 3 and 4 or 4 and 6. Here is the assembly:
(setup removed)
F80E: 90B2 cmp.w #5h, &20h
F810: 0005
F812: 0020
F814: 4227 mov.w #4h, r7
F816: 4038 mov.w #3h, r8
F818: 0003
F81A: 2007 jnz F82A
F81C: 8324 sub.w #2h, r4
F81E: 4684 mov.w r6, 0h(r4)
F820: 0000
F822: 4806 mov.w r8, r6
F824: 4708 mov.w r7, r8
F826: 4037 mov.w #6h, r7
F828: 0006
F82A: 4309 mov.w #0h, r9
F82C: 1008 rrc.w r8
F82E: 2801 jnc F832
F830: 5709 add.w r7, r9
F832: 5707 add.w r7, r7
F834: 23FB jnz F82C
F836: 8324 sub.w #2h, r4
F838: 4684 mov.w r6, 0h(r4)
F83A: 0000
F83C: 4906 mov.w r9, r6
F83E: 3FFF jmp F83E
Lots of neat things are happening here.¶
P1IN @ 5 =
reduces down to just one instruction, which is really cool! The multiplication is done with the Russian peasant algorithm. The main thing I was wondering about is what happens to register assignments when the top of the stack is unpredictable. In this case, register assignments are shifted by one, accomplishing the same function as a stack push. This ends up being slower than the code you would write if you weren’t relying on the stack but a lot faster than relying on the stack directly like other Forths do.
Summary¶
I think the optimizations that Mecrisp does are very impressive, and it was interesting to see how some of them work. It gave me a lot of ideas for how I would try to do optimizing if I made a language like Forth for one of my calculators.
