Branching (label, jump, jumpz, if)

[JOT85]

We need to decide upon how we intend to allow jumping and conditional jumping/branching.

For reference, this document contains the instructions available on ARM: https://static.docs.arm.com/100898/0100/the_a64_Instruction_set_100898_0100.pdf
And this on x86: https://en.wikipedia.org/wiki/X86_instruction_listings

We obviously need a way to refer to somewhere to jump to; I think a label directive is an effective way to do this. It does't add syntax, and could just have the form:

label example
add something something_else
...
jump example

Here, jump example would jump to the add instruction.

We also need conditional branching. There are A LOT of conditions that these instruction sets support. With jump if 0, we can effectively implement everything else I think? Jump if equal is sub then jump if 0; jump if positive can be done with a bit mask then jump if 0; not equal would just jump over a jump if they are equal, etc. Then overflow checking can be done my comparing the operands before hand. Obviously none of these are as efficient as using the instructions, however it is an easy place to start and get things working - then we can add the different type of conditional jumps later.
So I propose that we just implement:

jumpz x example

which would jump to example if x is 0 for now.

Labels should be scoped, as otherwise you'd have to track which label names you've used which would get really messy.
Perhaps having an if directive could make writing code a lot nicer.
Consider the example where you want do thing_x if the condition is met, or thing_y if not.
You might have to write:

... something so that result will be 0 iff the condition is met.
jumpz result true
thing_y
jump aftercond
label true
thing_x
label aftercond

For this, the labels true and aftercond have to be used, which means that if this pattern becomes common, the programmer will have to be careful not to reuse labels in the same block - which is just messy!
To solve this, we could have some if ... else ... directive which has the form of this pattern. The syntax for this could be:

if result {
    thing_y
} else {
    thing_x
}

The above is also much more readable.

[sharnoff]

With jump if 0, we can effectively implement everything else I think?

Yes, that seems to be the case.

which would jump to example if x is 0 for now.

I assume you mean something more like "If the value sitting in the memory address we've assigned to x is zero", right?

For this, the labels true and aftercond have to be used, which means that if this pattern becomes common, the programmer will have to be careful not to reuse labels in the same block - which is just messy!

I definitely agree that it would become messy. I don't believe that many things here will need to be used multiple times - if you're writing an if rule for your language, you should hopefully only have to do that once. I'd suggest that we don't implement any compiler directive for runtime if yet, and perhaps add it in if it really is an issue.

---

Other thoughts

In the interest of wrapping multiple features into one (i.e. making each feature of the language powerful, instead of having many smaller features), perhaps we add local variables to label statements to mimic the arguments of functions.

For example:

jump main

label fn x
add x 1 -> y
set x y
jump return

label main
const 4 -> z
jump fn z
label return

Obviously we'd want "jump back to a place in code known at compile time" to actually implement functions, but this would be a decent start for the syntax. The obvious downside is that it would add a bunch of syntax to the label directive.

---

Lastly: A "compile-if" statement seems out of the scope of this issue, but it may be something good to think about.

[JOT85]

which would jump to example if x is 0 for now.

I assume you mean something more like "If the value sitting in the memory address we've assigned to x is zero", right?

Yes

For this, the labels true and aftercond have to be used, which means that if this pattern becomes common, the programmer will have to be careful not to reuse labels in the same block - which is just messy!

I definitely agree that it would become messy. I don't believe that many things here will need to be used multiple times - if you're writing an if rule for your language, you should hopefully only have to do that once. I'd suggest that we don't implement any compiler directive for runtime if yet, and perhaps add it in if it really is an issue.

That makes sense... But... (Read the last point...)

Other thoughts

In the interest of wrapping multiple features into one (i.e. making each feature of the language powerful, instead of having many smaller features), perhaps we add local variables to label statements to mimic the arguments of functions.

For example:

jump main

label fn x
add x 1 -> y
set x y
jump return

label main
const 4 -> z
jump fn z
label return

Obviously we'd want "jump back to a place in code known at compile time" to actually implement functions, but this would be a decent start for the syntax. The obvious downside is that it would add a bunch of syntax to the label directive.

Hmm... I think I agree, but I need to think more about it before I'm 100% on board.

Whilst we're on the subject of returning, we also need to have a way to set a return point and then jump back to it. We could do this with call and return directives - which would work differently depending on the architecture, or we could allow some way to get the memory address of the instruction for the next directive and store that to a compiler variable, pass that with jump to the function, and then have that jump to the thing pointed to by that compiler variable. In fact, I think we have to do the later (to allow for different call stacks to be implemented), however the first would allow us to use the call and return CPU instructions (when they exist) which is something that must be done for optimal performance - if we don't have specialized directives, then we would have to inspect the code to guess which jumps are calls and which are returns; that could get messy and won't be 100% accurate.

Lastly: A "compile-if" statement seems out of the scope of this issue, but it may be something good to think about.

What if we don't have a compile-time if, but just have an if which runs at compile time iff the variable it's checking is known at compile-time, or at run-time if it's not? We would be doing this (to an extent) at compile time for optimisations, and if you are yielding constant size/type data, then it allows that to be compared at compile time without the need for those type of things to be yielded specially.

In addition, if the if directive has blocks which are only run by the if directive, then the compiler can trivially eliminate them if they are never going to be run, whereas if it's a jump, it has to check if somewhere else jumps to it - which requires knowledge of the rest of the program, which means that the rest of the program has to be compiled before this can be done (which could cause compilation to be slower), but also leads to other complexities in determining if a section of code can actually be jumped to (for example if there are other jumps to it, but they can only happen if a string of jumps happen which can only happen if the section is run). We will have to deal with those complexities at some point, but that might not be 100% optimal whereas a block which you know can be eliminated would be.

[sharnoff]

In fact, I think we have to do the latter

Yeah, that's exactly what I was thinking of.

If we don't have specialized directives, then we would have to inspect the code to guess which jumps are calls and which are returns; that could get messy and won't be 100% accurate

The accuracy issues seem like they'd only occur in cases where we can't correctly identify that it is a call/return, not the other way around, so it shouldn't be a breaking issue, but I agree that it is a difficult problem. Thankfully though, I would imagine that most instances of jumping back to addresses specified by "label" should be defined by a couple rules at most - and because we can analyze the rules looking only at the definition, we should hopefully be able to identify nearly all of these cases.

What if we don't have a compile-time if, but just have an if which runs at compile time iff the variable it's checking is known at compile-time, or at run-time if it's not?

I'm not too keen on this idea, but perhaps I'm misunderstanding. I think that we primarily need "compile-if" to allow conditional compilation - be it from feature flags or from different architectures (as much as we'd like compatibility to not be an issue, there are unavoidable cases: windows OS strings are utf-16, whereas everyone else's are utf-8, for example). This "compile-if" wouldn't necessarily evaluate compiler variables to determine whether it should produce the code, but perhaps some additional configuration options (think #[cfg(not(unix))] from Rust). Otherwise, I would imagine that - because we can do everything with "jump if" - it would be better to leave anything else out unless the program analysis becomes too difficult. Let me know what you think about this.

---

Lastly: If we do go the route of allowing "jump" statements to pass locations in code, we'd need some way of distinguishing between "normal" compiler variables and pointers to places in the executable (or maybe elsewhere, if the there's a function created on the heap, for example)