path: root/log.md

# 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			; <UNDEFINED>

00010f98 <n3>:
   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.

### 2016-11-26

Some updates, log is outdated...

- I had mixed the `heap_size` and `heap_size_multiple` variables in `cgopts.s`
  in September, and setting them correctly breaks some programs (one example is
  `lqueen.icl`). It most likely indicates a problem that was already there but
  somehow did not occur before.

- Adapted the RTS to use aliases for register names, so that optimisation can
  be done easily. **TODO**: there is an optimisation possibility with
  registers, as some narrow thumb instructions can only use r0-r7; the
  most-used registers should be there.

- A number of programs that this log claimed were working seems broken now,
  perhaps I didn't check with small heap sizes before?

- The compacting compiler is broken.

---

There is an issue in `ccall`s; they attempt to do `and sp,sp,#-8` which is not
allowed (see 3.7 of the Thumb-2 supplement). The quick solution is to `mov` to
the scratch register, do the operation there, and then move back (implemented
in cg `4290310`).

Tried compiling the Clean compiler with a hacked clm. Had to `strip cocl`
manually, then achieved a size of 5.1M (5325412 bytes) compared to 5.3M
(5475152) for ARM. Segfaults, of course, when tried to use.

### 2016-11-28

Hardcoded registers in `cgthumb2was.c` (not in the `register_name` array):

- `r12`, r. 601, 606, 613, 619 (`w_as_*scratch_register*`) (removed `a24f0e1`)
- `sp`, r. 1186 (`dyadic_instruction_allowed`, goes through `register_name`),
  2396 (`rts`), 2412 (`rtsi`)
- `pc`, r. 1425, 1431 (`jmp`), 1541, 1544, 1555, 1561, 1566 (`jsr`), 2396
  (`rts`), 2412 (`rtsi`)
- `lr`, r. 1541, 1544, 1555, 1561, 1566 (`jsr`) (removed `a24f0e1`)
- `r5`, r. 2750, 2762 (`garbage_collect_test`) (removed `a24f0e1`)

The below table lists some options that can be looked at for the register
allocation optimisations. The first column, ARM, is the allocation as is used
in the ARM RTS/CG, the other columns are possible changes.

| Option           | ARM   | +Aux, -B | +Aux, -A | +Aux, +A | Aux/B, -A | Aux/B, -Scratch | Aux/B, -Link | Aux/B, -Heap |
|------------------|:-----:|:--------:|:--------:|:--------:|:---------:|:---------------:|:------------:|:------------:|
| **B-stack**      | **4** | **4**    | **4**    |   8      | **4**     | **4**           | **4**        | **4**        |
|                  | **3** |  14      | **3**    |  14      | **3**     | **3**           | **3**        | **3**        |
|                  | **2** |  12      | **2**    |  12      |  12       |  14             |  12          |  14          |
|                  | **1** |  10      |  10      |  10      |  10       |  10             |  10          |  12          |
|                  | **0** |   9      |   9      |   9      |  14       |   9             |   9          |   9          |
| **A-stack**      | **6** | **6**    |  14      | **6**    | **6**     | **6**           | **6**        | **6**        |
|                  | **7** | **7**    |  12      | **7**    | **7**     | **7**           | **7**        | **7**        |
|                  |   8   |   8      |   8      | **4**    |   8       |   8             |   8          |   8          |
|                  |  11   |  11      |  11      |  11      |  11       |  11             |  11          |  11          |
| **Free heap**    | **5** | **5**    | **5**    | **5**    | **5**     | **5**           | **5**        | **5**        |
| **A ptr**        |   9   | **0**    | **0**    | **0**    |   9       | **0**           | **0**        | **0**        |
| **Heap ptr**     |  10   | **1**    | **1**    | **1**    | **1**     | **1**           | **1**        |  10          |
| **Scratch**      |  12   | **2**    | **7**    | **2**    | **2**     |  12             | **2**        | **1**        |
| **B ptr**        |  13   |  13      |  13      |  13      |  13       |  13             |  13          |  13          |
| **Link/Scratch** |  14   | **3**    | **6**    | **3**    | **0**     | **2**           |  14          | **2**        |

However, before this can be tried out, there is an **issue** in the code
generator which makes that `frontend/predef.icl` in the cocl cannot be
compiled: in the long array updates there are many negative offset addresses,
and in Thumb these can be at most 255.

Made some changes to the garbage collector:

- In the copying collector, modified `copy_arity_0_node2_` to hopefully store
  the right LSB (rts `5a329af`)
- In the compacting/marking collector, there was still an issue with an address
  being loaded from an address off-by-one (e.g. `0xcc000002f6` instead of
  `0x2f60e`); fixed this temporarily in rts `b8710c5` but should talk to John
  about this. Also, the compacting compiler still breaks on the following with
  `-h 1k`:

  ```clean
  Start = (length xs, hd xs) where xs = fromto 1 100
  ```

### 2016-12-01

About the negative offsets: this was finally fixed in cg `2245229` (the commits
before that attempted to fix it as well). It is done by checking the minimum
(largest negative) offset to the A-stack pointer, and subtracting this at the
start of a basic block if it is lower than -255.

Then there was an issue with indirect addressing with `[rn],#x` and `[rn,#x]!`,
where `x` can only be 8 bits in ARM. These offsets are generated at the end of
a basic block, when the A-stack pointer will be updated, to combine the last
load with the add/subtract of that update. We can now only make this
optimisation if the offset is reasonably large.

Concretely, the following offsets can be used (this only applies to not-SP
registers):

| `[rn,#x]`                                                  | `[rn],#x`            | `[rn,#x]!`           |
|:----------------------------------------------------------:|:--------------------:|:--------------------:|
| -255 &le; x &le; 4095 (32-bit); 0 &le; x &le; 124 (16-bit) | -255 &le; x &le; 255 | -255 &le; x &le; 255 |

Then there is a new **problem**, relating to constants: instructions like
`cmp r4,#2147483647` (generated for `frontend/analtypes`) are not allowed
because `2147483647=0x7fffffff` cannot be captured in one of the (relatively
many) different immediate constant encodings for Thumb-2 (A5.3.2 of ARMv7-M).
This is **fixed** quite easily in cg `a355a7a`, by checking if the constant can
be immediate or not.

And then there was a **problem** in `backend/backend`, where the instruction
`add sp,r8,#4` is generated. This is not allowed due to special treatment of
`sp` (A5.1.3 of ARMv7-M). The **solution** is to store the result temporarily
in the scratch register (cg `7c22910`).

Now there is an **issue** with long jumps; see
http://stackoverflow.com/q/40916440/1544337. In the cocl, branches to
`selector__m__error` (in the RTS) are too long and cannot be conditional.
Ideally, we would just rewrite these bits from

```armasm
	cmp	r12,r14
	bne	selector__m__error
```

to

```armasm
	cmp	r12,r14
	beq	a_bit_further
	b	selector__m__error @ not conditional, so no problem
a_bit_further:
```

Should check with John about this. For now, the generated code is (cg
`306d8d6`):

```armasm
	cmp	r12,r14
	mov	r12,=selector__m__error
	it	ne
	bxne	selector__m__error
```

After all this, the compiler uses 9979032 bytes, or 5026236 after `strip
--strip-all`.  For ARM, this is 5345608 (after `strip --strip-all`). Now we
need to look at register optimisations.

# Todo

- C calls
- Branch optimisation?