Operator & with negative offset

[sromero-uma]

The operator & is used, in sugar expression of instructions, to refer to a stack location. For example &0 is the position in memory of the last pushed word before the instruction containing such sugar expression.

Sometimes, it is useful to duplicate an element in the stack after loading it. We have tested that &-1 refer to the position in memory of the first element in stack pushed by the sugar expression. The example instruction:
push! (* (load4 (load8 &0)) (load4 &-1)) makes and indirect load of a variable (x) whose address is at TOS (top of stack), replicates its value and then multiply them, leaving the result (x * x) on the stack (just below the address of x). If there are intermediate pushes, adjusting the negative offset is required. Instructions below should be equivalent for (x * x + 1):
push! (+ (* (load4 (load8 &0)) (load4 &-1)) 1)
push! (+ 1 (* (load4 (load8 &0)) (load4 &-2)))
but the first one give a more compact and faster binary.

In the code below, this situation changes because the assembler reorganized the pushes, placing PC (get_pc) before the first load4 (perhaps because of the label, being a PC relative address). The assembler then changes &0 from (load8 &0: get_sp+load8) to (load8 &1: get_sp+push 8+add+load8), but it does NOT change &-1 to &-2.

_start:
	push! .index
.watch:
	push!	(load8 (+ (* (+ (| (load4 (load8 &0)) (* (& (load8 &-1) 0x80000000) -1)) -1) 8) .label))
	exit

.label:
	data8 [ 0  1 2 3 4 5 6 7 8 9 ]
.index:
	data4 [ 7 ]

Executing the above code with ivm as-run -t, the duplicated word is not the number 7, but the value pushed by get_pc, which is not the intended.

If the label (get_pc+push1+add) is the last pushed (just before add+load8 as the expression suggests) the reference &-1 (to the location of the previously pushed word) will be correct and the binary will be better (more compact and faster). But, leaving get_pc as the first instruction (after .watch) of the binary we have to use &-2 which is not coherent with the written expression, and also extra 'push' and 'add' instructions appear.

Can we trust operator & with negative offset in expressions including labels?

[ivar-rummelhoff]

Hello Sergio,

I find this a bit hard myself, but I'm afraid the short answer is "no", you cannot trust (load8 &-1) etc. inside expressions. As you have seen, the main reason for this is that there is some reordering of operations. I suspect it might also interfere with the implementation of some pseudo-instructions.

Currently, there is no way to safely duplicate elements on the stack inside an expression. If you want to do this for efficiency, you should use statements instead. There are ways to solve this in the assembler, but it is not much time left in the project for such adjustments. If this is important to you, you should escalate the issue (to the Oscar and Bjarte or to Ole).

[sromero-uma]

Thank you for you answers both the short and the long ones. :-D

The reason why it is labeled as a 'question' is because: first, it is not important itself (we can handle it by emitting statements as you propose) and, second, I had no idea if negative offset were "updated" as well as positive offset, as these later ones are in fact updated regardless there are any reordering of operations or not.

We use extensively the negative offset in operator '&' in instruction set_sp &-N to make room for N local variables in C functions, you may inspect the resulting assembly of the C compiler if you wish. If this fact becomes a problem, as we are trusting in negative offsets, you should warn us as soon as possible as well as propose an alternative way (apart of several push0).

I my experiment (where this issue comes from) there are no pseudo-instructions involved, only labels. I treat labels as if they fit in a word as each label were a constant or the result of a plus over to words: set_pc+const.

This is what I thought:
push! (load8 (+ (* (+ (| (load4 (load8 &0)) (* (& (load8 &-1) 0x80000000) -1)) -1) 8)(+ (get_pc) constant)))
being constant the gap between the .label and the current position of the get_pc instruction where it must/should (?) be placed.

I am aware that there is not much time, that is why I was a bit surprised by the last modifications of the IVM native instruction set.

[ivar-rummelhoff]

1. It has been the plan all along to ensure that we have found a good trade-off between efficiency and the complexity of the instruction set. Last week we tested adding primitives for signed division and modulo/reminder, but again we concluded the improvement was not worth the additional complexity. On the other hand, removing the SIGXn instructions had almost no noticeable effect. Maybe we should have started this process sooner, but we had to wait for a compiler emitting reasonably efficient assembly code.

2. Using the addresses &-n in expressions is completely safe. It is the contents of these addresses (i.e. the unallocated stack) you should not trust. As soon as you move the SP, the situation changes.

3. I agree that it could make sense to allow loadN &-n in expressions in order to optimize repeated subexpressions etc. However, it would require some work. Simply removing the reordering of statements is not an option, as we use this to compute the distance between two labels at assembly time etc.

[sromero-uma]

Hello Ivar,

I would like to thank you for your work with the ivm assembly language. The syntactic sugar you designed allowed us to choose the aspect of the C compiler production, and now with our delivery of the Yet Another IVM64 C Compiler, you can also choose the final aspect of your assembly, object and asm-executable output files as all of them are assembly.

Regarding this already unclosed issue (I think we should close it soon), I share with you the above snapshot with the result of the compilation of a very simple C program (left) and the compiled output in two flavours: natural (centre) and sugar (right). As you can see, in natural flavour (and also light flavour, statement based with or without pseudo instructions) it is easy to duplicate the common expression once it is computed at the top of the stack (just load8! &0 -> set_sp load8). In the sugar flavour, the common expression appears twice, this is why we wonder if we could use the new top of the stack or, in general, new stack elements, using the negative offset:
store4!! (* (+ (load4 &1) (load4 &2)) (load8 &-1)) &1
instead of:
store4!! (* (+ (load4 &1) (load4 &2)) (+ (load4 &1) (load4 &2))) &1

In either case, the result is correct (both without the negative offset), a few steps more or less when executed. And perhaps the readability is worse with negative offsets.

I agree with you that this seen more or less affordable when only load and native arithmetic instructions appear in the expression, and it becomes harder if other pseudo instructions (requiring to be expanded) are also involved.

Perhaps in the future, some one decides if this way deserves to be walked.

Again, thank you Ivar, and thank all the immortal machine project people.

[ivar-rummelhoff]

Thanks for the update, Sergio (and sorry about the late reply). I think we should leave this question/suggestion open for now since it makes a lot of sense. If someone decides to continue the development (e.g. Piql), then they can decide if it is something they would like to prioritize.