# Bachelor thesis logbook Camil Staps ### 2016-09-18 Made a Vim plugin for ABC code highlighting (camilstaps/vim-abc). ARM/Thumb-2 mode switches are expensive, and since a Clean program continuously switches between the RTS and the program itself, it is not viable to have the RTS run in ARM mode and the code generator generate Thumb-2 code. Hence, I started to rewrite the RTS for Thumb-2. Mostly minor, trivial changes: - Invisible registers for some instructions (auxiliary register needed) Started to make changes to the code generator: - Added `.thumb`, `.syntax unified` to the top of each generated file - Added `.thumb_func` before each code label - Fix for the `str pc,[sp,#-4]!` and similar instructions, since `pc` cannot be the `Rd` operand in a `str` instruction: copy to scratch register first. **Question**: Is there an interface to get an auxiliary register in the code generator? For example, to swap to registers a third is necessary (or the stack, but then the PC and SP cannot be modified). In `w_as_jsr_instruction`, the PC is stored on the stack, but PC cannot be `Rd` for `str`. Therefore we need an auxiliary register (`8c91384` does this for some cases). *Answer on 09-19*. ### 2016-09-19 Talked to John: - (*Answer to question from 09-18*) Registers R14 (LR) and probably also R12 are scratch registers and can be used at any time. - When the program counter is stored on the stack in ARM (`str pc,[sp,#-4]!`), the value pushed is actually the PC + 8, which gives space for a call after storing the PC. On Thumb-2 this is different, so this should be checked. To solve the latter problem, we need to add an offset to the stored PC. Old ARM code was: ```armasm str pc,[sp,#-4]! @ Actually pushed PC+8, to after the branch. ``` First solution, since `PC` cannot be `Rd` for `str`: ```armasm mov r12,pc @ Stores PC+4 (see A5.1.2 of the ARMv7-A manual) (this is a 16-bit instruction) str r12,[sp,#-4]! @ Pushes stored value (address of THIS register) ``` New solution, with a proper offset: ```armasm add r12,pc,#9 @ Stores PC+12+1 (this is a 32-bit instruction) @ +1; bit 0 is the execution state and should be Thumb-2 str r12,[sp,#-4]! @ This is a 32-bit instruction, as is the branch below ``` After this, this program crashes only when it wants to print time information (specifically, `time_string_4`, `thumb2startup.s:929`): ```clean Start = 10 ``` The last crash has to do with alignment in `exit_clean` (`thumb2startup.s`). This indicates that `add r12,pc,#9` is not right in some cases. The second bullet point in A5.1.2 applies: > Read the word-aligned PC value, that is, the address of the current > instruction + 4, with bits [1:0] forced to zero. Hence, in some cases (when the address of the `add` instruction is 2 mod 4), we should add 11 instead of 9. A quick fix is to use `.align`, which inserts a `nop` if needed. It would be more convenient if there would be preprocessor directives like `.align` where you could yourself decide what is added depending on the current alignment (see http://stackoverflow.com/q/39582517/1544337 for this). ### 2016-09-27 See also https://community.arm.com/thread/2341 about the PC offset when reading. Started working on the actual text: wrote about - Approach: why no ARM/Thumb-2 interworking - Difficulties with storing the program counter ### 2016-10-01 **Note**: in ABC code: - `.d 1 0`: *demands* 1 argument on A-stack, 0 on B-stack - `.o 0 1 i`: *offers* 0 arguments on A-stack, 1 on B-stack with type `Int` **Problem**: instructions like `ldr pc,[sp],#4`. On the stack, program memory addresses. We need to jump to an address like that *+1* to stay in Thumb mode. Assuming every address that is stores somewhere is used like this, it is most efficient to fix this when storing the address rather than when loading it (since an address stored once may be loaded multiple times). The code generator should be adapted in `w_as_descriptor` to add 1, however, the same function is used to load pointers to data. ### 2016-10-02 **Problem**: the problem with storing the program counter was not properly fixed. In fact, it looks like the only reason it worked was some old binaries hanging around on the disk. The issue probably (**Question** for John) stems from the fact that the LSB of addresses are used by the garbage collector . Hence, storing an address with offset `#9` modifies the garbage collector information, giving incorrect results when using an up-to-date `_system.o`. **Solution**: the new solution is to store addresses with an offset of `#8`, and when jumping to an address making sure that the LSB is set (to force Thumb state). Hence, where we first had: ```armasm ldr pc,[sp],#4 ``` We now have: ```armasm ldr lr,[sp],#4 @ use lr as auxiliary register orr lr,lr,#1 @ pc cannot be left operand of orr, so orr pc,lr,#1 is not possible mov pc,lr ``` Hence, not only storing addresses is slowed down by two instructions, now also loading addresses is slowed down by two instructions. **Question** for Rinus: the solution for this problem was influenced by the fact that the Clean code generator uses the lowest two bits already. If this weren't the case, it would be more efficient to store a `#9` offset and not modify addresses when jumping. What solution should be given in the thesis? Both? **Current commits**: cg `5effb5b`, rts `0f7f68d`, tests `f7f261f`. ### 2016-10-03 Another **problem**: the Start rule `twice twice ((+) 1) 0` gives a segmentation fault. At some point it switches to ARM mode. This is probably something that should be tackled later on. **Yet another problem**: the Start rule `[]` segfaults. The issue turns out to be that for this rule, the node entry point `n1` is accidentally halfword-aligned. Hence, its bit 1 is set. This bit is used to store if a node has been reduced to (r)nf yet (not sure if rnf or nf). Therefore, it is not evaluated to `[]` properly before printing it. The **solution** to this issue is to `.align` node entry points (cg: `d9c2a69`). **New problem**: conditional instructions don't have a preceding `IT` instruction. A minimal example (borrowing some functions from StdEnv) is `Start = 1 < 2`. It seems to be resolved quite easily by adding an `IT` block (cg `9496e96`). **Question**: it is unclear to me how the instructions for `IFSGE` and `IFSLT` work. They branch, rather than move (`cgarmwas.c`): ```c case IFSGE: w_as_set_float_condition_instruction (instruction,"bpl","bmi"); ``` The generated code would then be something like: ```armasm bpl rx,#1 bmi rx,#0 ``` but what the constants are for (and if this is valid syntax) is unclear to me. **Problem**: there is no `Heap full` message. This can be verified with: ```clean fromto :: !Int !Int -> [Int] fromto a b | a > b = [] | otherwise = [a:fromto (a+1) b] Start = fromto 1 25 ``` and running with `-h 1k`. The program segfaults rather than displaying a `Heap full` message. ### 2016-10-09 The above problem (no heap full message) only occurs with the copy/compacting garbage collector (`-gcc`), not with the marking/compacting garbage collector (`gcm`). The problem seems to be that when `collect_1` returns the value in `r6` is different than before. **Question**: It seems there are whole areas of the generated binaries that are all zero (like `file_table`, where you can expect that, but also e.g. `small_integers`, should this be zero as well?) ### 2016-10-13 The problem that the copying collector segfaults has to do with `thumb2copy.s` (rts). About this file: * `continue_after_selector_2`: checks with bit 1 if the node is in rnf and jumps to `in_hnf_2` (`1`) or `not_in_hnf_2` (`0`) accordingly. * `not_in_hnf_2`: checks with bit 0 if the node has been copied to the other semispace already. If so (`1`), it jumps to `already_copied_2`. The issue above arises due to the fact that `r6`, which holds the node address, has the lowest bit set. Hence, it isn't copied. John pointed at a new **problem** that arises with a standard `append` program: ```clean append [] ys = ys append [x:xs] ys = [x:append xs ys] Start = append (fromto 1 15) (fromto 30 40) ``` This uses `fromto` from above and segfaults with `-h 1k -gcc`. In `thumb2copy.s`, `not_in_hnf_2`, the address right above the node entry point is loaded. Here, the arity is stored. This should be 2, but the generated assembly looks like: ```objdump 10f8e: 00000000 andeq r0, r0, r0 10f92: 00000002 andeq r0, r0, r2 10f96: f8dfbf00 ; 00010f98 : 10f98: f8df c030 ldr.w ip, [pc, #48] @ etc. ``` Hence, the instruction `ldr r4,[r6,#-4]` with `r6=0x10f98` reads `0xbf000000`. Note that `bf00` is `nop`. ### 2016-10-15 As suggested by John on the 13th, this is temporarily fixed by settings the lowest bit to 0 manually (rts `887b38e`). Should be fixed properly. **Idea**: if the start of a function would look like ```armasm .align .thumb_func n7: nop @ etc. ``` Then both `=n7` and `=n7+2` are good addresses to `n7`. Hence, bit 1 is free for use. On second thought, this is not necessary: when bit 1 is set, the node is in HNF, so we don't jump to it any more. ### 2016-10-16 In the branch rts:gc-flipped and cg:gc-flipped, I'm trying to not `orr lr,lr,#1` every time you want to jump to a label (to make sure you stay in Thumb mode). It seems the LSB is used only *internally* by the copying collector (see above: LSB is set iff the node is a redirection to the other semispace = iff it has been copied already). In these branches, the meaning is flipped: LSB is cleared under that condition. For nodes being used it would then be set, so we don't need to `orr`. In general the copying collector seems much more difficult than the marking collector. Consider e.g. the following programs: ```clean Start = fromto 1 100 Start = take 200 [x \\ x <- fromto 1 100000 | isEven x] Start = append (fromto 1 15) (fromto 30 40) ``` Only the first works in the gc-flipped branches with `-gcc -h 1k`, but all work with `-gcm -h 1k`. ### 2016-10-19 We're now working with node entry addresses *plus one*. There is some information stored right before the node entry, such as arity, which is used in the garbage collector (among other places?). This was previously fetched with `[r6,#-4]` for example, and should now be fetched with `[r6,#-5]` to accommodate for this. This is done in cg:gc-flipped `56d30f5` and rts:gc-flipped `9f522d3`. ### 2016-11-06 Talked to John some weeks ago about the idea to flip the meaning of bit 1 in the copying collector; this is possible, but not all cases where bit 1 should/need to be modified. Hence, the commits on gc-flipped were partially incorrect. They have (hopefully) been fixed in rts:gc-flipped `b36ae1f`. In general, cases where is dealt with records do not need to be modified. Also, we do not need to use things like `INT+3` but can simply use `INT+2` (like before), because these nodes are in hnf, and bit 1 only has a meaning for those nodes that are not in hnf. After these changes, all three programs above work fine with `-gcc -h 1k`: ```clean Start = fromto 1 100 Start = take 200 [x \\ x <- fromto 1 100000 | isEven x] Start = append (fromto 1 15) (fromto 30 40) ``` There is a **problem** with higher-order functions though. The following program segfaults. The problem may be somewhere in `_system.abc` (`e_system_nAP` or around), or may be related to there. ```clean Start = map toReal (fromto 1 100) ``` ### 2016-11-07 **Flashtalk**. **Problem** in `thumb2divmod.s`, which was edited quickly without looking what it actually did: there's something going on with dynamically calculating an offset and jumping to it, e.g. (from `divide`): ```armasm clz r1,r4 clz r2,r3 rsb r1,r1,#31-5-11 add r1,r1,r2 mov r2,#0 cmp r1,#32-5-11 bhs divide_large_result add r1,r1,r1,lsl #1 .align add r14,pc,#8 @ Here add r14,r14,r1,lsl #2 mov pc,r14 nop ``` This offset is incorrect, since some of the following instructions are narrow. Should check with John if this can be done intelligently, or that we should simply force all instructions to be wide. The offsets are fixed now. Then there was an issue with the modulo function, which returns different results than on x64 (see mail to John from this day). This affects ARM as well. I presume it has been fixed (see follow-up mail and rts `08f4cf8`). **Current status**: the only known problem is with higher order functions and AP. I still need to look at records, unboxed lists, uniqueness, and possibly other things. Apart from that, all small examples in the Clean distribution seem to work. ### 2016-11-08 Tackled several problems: - cg `6ad63a4` fixes an issue where the offset added to `pc` was incorrect in `_system.s`, `e_60` (caused issues with hof). - cg `59e9272` ensures that code addresses stored in data sections have the LSB set for Thumb mode, which solves an issue with hof. For example (`twice.s`): ```armasm .long dTwice_P1+2 dTwice_P1: .hword 0 .hword 16 .long yet_args_needed_0+1 @ here .hword 1 .hword 8 .long lTwice_P1+1 @ here .hword 2 .hword 0 .hword 0 .hword 2 .long m__twice+1 @ here ``` - cg `f64b035` ensures that the jump to the `ea*` label right before the `l*` entry is in fact exactly 8 bytes before that label, as is assumed in `thumb2ap.s`(?). Example affected code (`twice.s`): ```armasm b.w eaTwice_P1 @ The .w ensures a wide instruction nop.w lTwice_P1: ldr r7,[r7,#4] eaTwice_P1: ldr r12,[r7] ``` - Cleaned up `thumb2{ap,divmod,startup}.s` in rts (`3e5b585`, `70a575a`): don't `orr lr,lr,#1` before `mov lr,pc` and `ldr pc,[sp],#4` directly instead of through `lr`. This caused alignment issues in `thumb2divmod.s` that are fixed now, but it should be **noted** that this file is very sensitive to alignment. - Fixed an issue with the `pascal.icl` example program, where the argument to `toString` was not strict, causing problems with its instance for `Int` (i.e., no changes for cg or rts) (tests `00310d6`). All in all, some higher order functions now work: ```clean Start = map toReal (fromto 1 10) Start = app plus 1 2 where app f a b = f a b plus a b = a + b ``` However, `twice.icl` and `stwice.icl` still segfault. **Status** of the example programs: - `copyfile.icl`: not looked into yet. - `reverse.icl`, `revtwice.icl`, `sieve.icl`: require `StdEnum` for `..` notation, which is hard to test in my current setup. - `stwice.icl`, `twice.icl`: broken (segfault). - All others work fine. ### 2016-11-10 Updated `reverse.icl`, `revtwice.icl`, `sieve.icl` and `copyfile.icl` to compile (i.e. use `fromto` instead of `..` and copy library functions in). `sieve`, `reverse` and `copyfile` work straightaway. Got `twice.icl` and `stwice.icl` to work by fixing `thumb2ap.s` (rts `4f0223b`). The issue was that the PC was stored with offset 9 instead of seven, while a narrow `blx` instruction followed. There is an issue with `revtwice.icl`; at some point in the garbage collector `$r6 == 0x1d1`. This is because the address of `__cycle__in__spine` or `__reverse` >> 8 equals `0x1d1`. So somewhere there is an off-by-one error. Fixed an issue where empty labels like `_cycle_in_spine` in `_system.abc` got a `nop`, which failed because then `__reserve` didn't have a `.long 0` right before it (cg `f64b035`). ### 2016-11-16 The compacting collector has a **problem**, for example with `./twice -h 1k -gc -st`. It is difficult to find programs that have this problem, since the compacting collector is only used when the copying collector is deemed inefficient (when we would have to copy too much, copying is inefficient). ### 2016-11-17 Did some tests with garbage collecting, records and HOF together, e.g.: ```clean :: Rec = { x :: Int, y :: String, z :: Real } toRec x = { x = x, y = toString x, z = toReal (x + x) / 3.0 } Start = append (fromto toRec 1 100) (fromto toRec 500 1000) ``` Seems to work fine so far.