This version is of historical interest only. See updated version.

Adding Structured Control-flow to any* Assembler (part 2)

[* Well almost any. Unfortunately this method cannot be used with the GNU Assembler because it does not allow the assembly location to be moved backwards. For the GNU Assembler, an attempt to .org backwards is an error.]

In part 1 I showed how to set up the control-flow stack and how to use it to implement the structured conditionals _IF _ENDIF and _IF _ELSE _ENDIF, and the structured loops _BEGIN _UNTIL and _BEGIN _WHILE _ENDW. In this part we look at short-circuit-AND and OR conditionals, switch/case statements and counted loops. These can all be implemented using the 5 basic control-flow elements defined in part 1: _IF, _ENDIF, _BEGIN, _UNTIL and _CS_SWAP (which swaps the top two elements of the control-flow stack).

Short-Circuit Conditionals (using overlapping structures)

A short-circuit conditional is a conditional involving multiple tests where we don’t bother doing the later tests if the result of an earlier test makes this unnecessary. For example, in the AND case, if the first test returns FALSE the overall result must be false. Higher-level languages usually distinguish logical AND and OR from bitwise AND and OR and treat the former in a short-circuiting manner. For example, C has && and || as short-circuiting Boolean operators.

In assembly language, we don’t usually explicitly AND or OR the results of multiple tests together. The logical relationship is implicit in the control-flow. For example, in the AND case, if the first test fails we simply jump past the remaining tests, which is of course what the corresponding short-circuit C-code would compile to.

In the case of a short-circuit-AND with no ELSE clause, this is easy to do using our existing structured control-flow macros. We can simply nest multiple _IF _ENDIFs.

Instead of                                                 we can write

 tst R8 tst R8
 jnz label _IF _Z
 tst R9 tst R9
 jn label  _IF _NN
 mov R9,R8 mov R9,R8
label: _ENDIF
 _ENDIF

Unfortunately, short-circuit-OR, and any short-circuit with an ELSE clause, is more difficult to do in a strictly structured manner. By “strictly structured” I mean not only using matching sets of keywords that represent one entry and one exit, but also using them in a strictly nested manner (like parentheses [or brackets]). But we can do them in a manner that avoids the need for labels, by allowing overlapping structures (like these strange parentheses [and) brackets].

For short-circuit-OR with no ELSE clause:

Instead of                                                 we would like to write

 tst R8 tst R8
 jz label1 _IF _NZ
 tst R9 tst R9
 jn label2 _IF _NN
label1:  _ENDIF
 mov R9,R8 mov R9,R8
label2: _ENDIF

But we can’t do that because the assembler ignores our indenting and takes the first _ENDIF as terminating the immediately preceding _IF _C when we want it to terminate the prior _IF _NZ. The trick is to define a word _END_PRIOR_IF as follows.

; Resolve a forward jump due to the _IF, _ELSE or _WHILE
; that came _before_ the most recent unresolved _IF, _ELSE or _WHILE.
 
_END_PRIOR_IF MACRO
 _CS_SWAP ; Get the prior _IF address back on top
 _ENDIF ; Back-fill the jump instruction for the prior _IF
 ENDM
 

Then for short-circuit-OR, instead of                        we can write

 tst R8 tst R8
 jz label1 _IF _NZ
 tst R9 tst R9
 jn  label2 _IF _NN
label1: _END_PRIOR_IF
 mov R9,R8 mov R9,R8
label2: _ENDIF

It turns out that _END_PRIOR_IF is all we need, to do short-circuited structures with any number of ANDed or ORed conditions, and with ELSE clauses. The equivalent of the C-like OR conditional

_IF _CC1 || _CC2 || _CC3 ... _ELSE ... _ENDIF

is written as

 ...
 _IF _CC1_inverse
  ...
 _IF _CC2_inverse
 ...
 _IF _CC3
 _END_PRIOR_IF
 _END_PRIOR_IF
 ...
 _ELSE
 ...
 _ENDIF

Note the inversion of all but the last condition in the short-circuit OR.

The equivalent of the C-like AND conditional

_IF _CC1 && _CC2 && _CC3 ... _ELSE ... _ENDIF

is written as

 ...
 _IF _CC1
 ...
 _IF _CC2
 ...
 _IF _CC3
 ...
  _ELSE
 _END_PRIOR_IF
 _END_PRIOR_IF
 ...
 _ENDIF

Notice how the _END_PRIOR_IFs come after the _ELSE in the short-circuit AND, whereas they come after the _IF in the short-circuit OR.

The implementation of all the other control-flow words in these articles is derived from their implementation in the language Forth. The evil idea of _END_PRIOR_IF, and using overlapping control-flow structures to implement label-free short-circuit conditionals, is mine.

Short-Circuit Conditionals (without overlapping structures)

The above overlapping control-flow structures can be difficult to read, so I now show how to define a more readable set of non-overlapping words for doing short-circuit conditionals. They ultimately resolve to exactly the same macro calls, but those nasty _END_PRIOR_IFs are hidden away. The names of these assembly-language macros are inspired by some extensions to standard Forth, written by Wil Baden. Note that the definitions of _ELSES, _END_IFS and _OR_IFS require a macro loop.

The equivalent of the C-like AND conditional

_IF _CC1 && _CC2 && _CC3 ... _ELSE ... _ENDIF

is written as

_COND

...

_AND_IF _CC1

...

_AND_IF _CC2

...

_AND_IF _CC3

...

_ELSES

...

_ENDIF ; Use _ENDIFS if there is no ELSES clause

The equivalent of the C-like OR conditional

_IF _CC1 || _CC2 || _CC3 ... _ELSE ... _ENDIF

is written as

_COND

...

_OR_ELSE _CC1

...

_OR_ELSE _CC2

...

_OR_IFS _CC3

...

_ELSE

...

_ENDIF

They are defined as follows.

_COND MACRO ; Begin a short-circuit conditional of either type

_CS_PUSH 0 ; Push an _IF-count of zero onto the control flow stack

ENDM

_AND_IF MACRO cond ; Short circuit AND condition

_count SET _CS_TOP+1 ; Copy and increment the _IF-count

_CS_DROP ; and take it off the stack for now

_IF cond

_CS_PUSH _count ; Put the _IF-count back on the stack

ENDM

_ELSES MACRO ; Used in place of ELSE for short circuit AND

_count SET _CS_TOP-1 ; Copy and decrement the _IF-count

_CS_DROP ; and take it off the stack permanently

_ELSE

REPT _count ; Repeat _IF-count - 1 times

_END_PRIOR_IF ; Resolve a forward jump

ENDR

ENDM

_ENDIFS MACRO ; Used in place of ENDIF for short-circuit AND, but only when there is no ELSES clause

_count SET _CS_TOP ; Copy the _IF-count

_CS_DROP ; and take it off the stack permanently

REPT _count ; Repeat _IF-count times

_ENDIF ; Resolve a forward jump

ENDR

ENDM

_OR_ELSE MACRO cond ; Short circuit OR condition, except last

; Calculate the inverse condition. This will be different for different processors

_inverse_cond SET ((cond&1)==0)*(cond+1) + ((cond&1)!=0)*(cond-1) ; Example only

_count SET _CS_TOP+1 ; Copy and increment the _IF-count

_CS_DROP ; and take it off the stack for now

_IF _inverse_cond

_CS_PUSH _count ; Put the _IF-count back on the stack

ENDM

_OR_IFS MACRO cond ; Last short-circuit OR condition

_count SET _CS_TOP ; Copy the _IF-count

_CS_DROP ; and take it off the stack for good

_IF cond

REPT _count ; Repeat _IF-count times

_END_PRIOR_IF ; Resolve an unconditional forward jump

ENDR

ENDM

CASE statement

Here are the macros needed to implement a simple CASE (or switch) statement for the IAR assembler and MSP430 instruction set. You should be able to easily adapt them to your own assembler and target. Note that the definition of _END_CASE requires a macro loop. These macros generate code equivalent to a series of IF ELSE ENDIFs. They do not use a jump table or anything more sophisticated.

; Typical use:

; _CASE

; _OF #1,R8 ; OF uses CMP (word comparison)

; ...

; _ENDOF

; _OF_B ’B’,R8 ; OF_B uses CMP.B (byte comparison)

; ...

; _ENDOF

; ... ; default case

; _ENDCASE

_CASE MACRO

_CS_PUSH 0 ; Push an _OF-count of zero onto the control flow stack

ENDM

_OF MACRO src,dest ; src is usually #N, dest can be Rn, X(Rn), &ADDR, ADDR

_count SET _CS_TOP+1 ; Increment the _OF-count

_CS_DROP ; and take it off the stack for now

CMP src,dest ; Assemble the word comparison

_IF _EQ ; Mark where a conditional jump will be backfilled later

_CS_PUSH _count ; Put the _OF-count back on the stack

ENDM

_OF_B MACRO src,dest ; src is usually #N, dest can be Rn, X(Rn), &ADDR, ADDR

_count SET _CS_TOP+1 ; Increment the _OF-count

_CS_DROP ; and take it off the stack for now

CMP.B src,dest ; Assemble the byte comparison

_IF _EQ ; Mark where a conditional jump will be backfilled later

_CS_PUSH _count ; Put the _OF-count back on the stack

ENDM

_ENDOF MACRO

_count SET _CS_TOP ; Take the _OF-count off the stack for now

_CS_DROP

_ELSE ; Resolve the previous unconditional jump

; and mark where an unconditional jump will be backfilled later

_CS_PUSH _count ; Put the _OF-count back on the stack

ENDM

_ENDCASE MACRO

_count SET _CS_TOP ; Take the _OF-count off the stack for good

_CS_DROP

REPT _count ; Repeat _OF-count times

_ENDIF ; Resolve an unconditional forward jump

ENDR

ENDM

Counted Loops

Here we have the macro definitions for counted loops. You might prefer “FOR” and “NEXT” instead of Forth’s “DO” and “LOOP”.

; Post-tested counted loops (fastest)

; Typical use:

; _DO #5,R8

; ... ; Will be done 5 times. _DO #0 would do 65536 times.

; _LOOP R8 ; Must have same destination as matching _DO

; _DO #10,R9

; ... ; Will be done 5 times.

; _MLOOP #2,R9 ; Minus 2 each time, so R9 takes on only even values.

_DO MACRO src,dest ; src is usually #N, dest can be Rn, X(Rn), &ADDR, ADDR

MOV src,dest ; Assemble a move instruction

 _BEGIN ; Mark the start of a loop

ENDM

_LOOP MACRO dest

DEC dest ; Assemble a decrement instruction

 _UNTIL _Z ; The conditional end of a post-tested loop

ENDM

_MLOOP MACRO src,dest ; “M” for minus

SUB src,dest ; Assemble a subtract instruction

 _UNTIL _Z ; The conditional end of a post-tested loop

ENDM

; Pre-tested counted loops

; Typical use:

; _QDO #7,R8 ; “Q” for question

; ... ; Will be done 7 times. _QDO #0 would do 0 times

; _QLOOP R8 ; Must have same destination as matching _QDO

; _QDO #21,R9

; ... ; Will be done 7 times

; _QMLOOP #3,R9 ; Minus 3 each time, so R9 takes on only multiples of 3

_QDO MACRO src,dest

MOV src,dest ; Assemble a move instruction

 _BEGIN ; Mark the start of a loop

TST dest ; Assemble a test instruction

 _WHILE _NZ ; Assemble the conditional exit of a pre-tested loop

ENDM

_QLOOP MACRO dest

DEC dest ; Assemble a decrement instruction

_ENDW ; Assemble the end of a pretested loop

ENDM

_QMLOOP MACRO src,dest

SUB src,dest ; Assemble a subtract instruction

_ENDW ; Assemble end of a pretested loop

ENDM

I wish you all the best with your own implementation. Don’t hesitate to contact me if you spot any errors or omissions above, have any questions, or just to tell me if this was useful.

-- Dave Keenan, 2014-May-26 (last updated 2015-Oct-05)