Another section of this website tells about forming program structures in assembly by using macros, and has source code for the assembler to do it. The purpose of this page here is to further explain the stack operations required for the assembler to know where to make the branches go and where to fill in branch distances or addresses when they become known. Although we're talking about assembly language here, the same things would apply to compilers.
All of the extra burden is on the assembler, and in most cases the machine code it produces is exactly the same as you would get without the macros, except that it came from source code that's more legible and maintainable; so it presents absolutely zero penalty to in run speed or memory taken. I keep repeating this because it's often hard for people to grasp. There's an extended piece of example source code, heavily commented, near the end of the page on simple multitasking methods.
Start with a simple single IF...END_IF:
| | resulting
with the macros: | w/o macros | machine code
----------------------------+------------------------+---------------
INC COUNT | INC COUNT | E6 F0
IF_ZERO | BNE label | D0 02
INC COUNT+1 | INC COUNT+1 | E6 F1
END_IF | label: <continue> |
----------------------------+------------------------+---------------
The resulting machine code won't tell you which source code it came from, because it's the same six bytes either way. In the example,
two-byte variable COUNT is in ZP, at address $F0.
When the assembler reaches the "IF_ZERO", it does not know yet where the forward branch will need to go to. It assembles a BNE instruction with garbage in the operand, and puts the operand's address on a stack in the assembler for the assembler to come back and fill in later when the END_IF macro is reached and it can calculate the offset. (Later we'll see that ELSE_ can also fill in the branch instruction's operand.)
Now consider an IF...END_IF nested three deep:
CMP #14
IF_EQ ; BNE to ??#1
<actions>
<actions>
IF_NEG ; BPL to ??#2
<actions>
<actions>
IF_EQ ; BNE to ??#3
<actions>
<actions>
END_IF ; Fill in operand for BNE 3 lines up.
END_IF ; Fill in operand for BPL 7 lines up.
<actions>
<actions>
END_IF ; Fill in operand for BNE 13 lines up.
Since a stack is a last-on-first-off memory, each END_IF encountered fills in the operand for the last
unresolved IF___ above it.
So how do you have such a stack in the assembler itself, when most assemblers don't provide for stacks? A stack is normally done with
indexing into the stack array, and the pointer is incremented or decremented by 1 cell size every time a cell is added or removed. If your
assembler allows assembler array variables and indexing into them, that would undoubtedly be best. Microchip's MPASM assembler for its PIC
microcontrollers has the #v(x) feature which allows concatenating a number ("x",
converted to text) onto the end of a label name; so in essence it is like indexing into an array whose name is the initial part of the label
name. I did not realize this possibility when I did my PIC structure macros, so I did them much the way I had to do them for the C32
assembler I use for 65c02/816, with a series of variables called STK_LVL_1, STK_LVL_2, etc. (for "stack level x"),
then I copied them one to the next as I added or deleted stack cells, like the following, illustrated to five stack levels. (In reality
you'll want more levels.) Here's how you would add a cell to the stack:
STK_LVL_5: SETL STK_LVL_4 ; SETL stands for "SET Label value" in the C32
STK_LVL_4: SETL STK_LVL_3 ; assembler, and you can do it as many times as
STK_LVL_3: SETL STK_LVL_2 ; you want for any given assembler variable,
STK_LVL_2: SETL STK_LVL_1 ; unlike EQU which only allows defining one time.
<now assign the desired value to STK_LVL_1 as the top-of-stack>
and to pop a level off the stack, do:
STK_LVL_1: SETL STK_LVL_2 ; STK_LVL_1 is always the top of the stack, regardless of depth.
STK_LVL_2: SETL STK_LVL_3
STK_LVL_3: SETL STK_LVL_4
STK_LVL_4: SETL STK_LVL_5
(I also had macros for pushing or pulling two or three at a time, and for swapping the top two cells.) The above does not tell how deep
the stack is, something you may need for certain things as we'll discuss in a minute. To maintain a record of the depth with the
above, you can add to the macro something like:
STK_DEPTH: SETL STK_DEPTH + 1
for the first one, where we add an item to the stack, or:
STK_DEPTH: SETL STK_DEPTH - 1
for the second one, where we remove an item from the stack. (Make it ±2 or 3 if adding or removing two or three items at
once.) Don't forget to initialize it at the beginning of the source code with:
STK_DEPTH: SETL 0
It might be good to add a check for overflow or underflow, and warn if either of these conditions occur.
So now go back to the example at the top of this page, about the double-byte increment of a variable
called COUNT. The first line increments the low byte. No mystery there. Next is
the IF_ZERO, because if incrementing the low byte made it go from $FF to 00, we need to do the indented section and
increment the high byte too. (The assembler doesn't care if you indent that portion or not, but it's good programming practice for making
the structures more obvious.) The IF_ZERO macro lays down a BNE instruction to
branch around the next section of code "if not equal" (ie, "if not zero," since the INCrement instruction
has an automatic, implied "compare-to-zero" instruction built in). The problem is that it doesn't have any way to know yet what the branch
distance is; so it just puts a dummy byte in the operand, and puts the operand's address on the assembler's stack used for making the program
structures.
The next line lays down the instruction to increment the high byte. Again, no secrets there. Then we get to the END_IF. This doesn't assemble any new code; but now the assembler knows where the corresponding relative-branch instruction (the BNE above) needs to branch to. The END_IF records the current address in assembler variable CUR_ADR (for "current address") using something like CUR_ADR: SETL $. ("SETL" in the C32 assembler stands for "SET Label value," like EQU except that you can change it over and over.) We'll do this for two reasons. We're going to temporarily change the address at which the assembler lays down bytes, and later we'll need to be able to get back to where we left off so we can resume the assembly process there. Using ORG (for "ORiGin"), we'll change the address to the one given by the number in the cell at the top of the stack (and remove it from the stack), calculate the offset using that address and what we stored in CUR_ADR, store the offset as BNE's operand, then use ORG CUR_ADR to get back to where we need to resume assembly. Source code for the structure macros the way I did them is in this file.
Let's look at what's on the assembler's stack at each line of the second listing near the top of this page:
line# ; What's on the assembler stack:
1 CMP #14 ; ^ empty
2 IF_EQ ; ^ BNE_operand_addr
3 <actions> ; These other lines can also use the stack, but their net effect
4 <actions> ; on it must be zero when the corresponding END_IF is encountered.
5 IF_NEG ; ^ line-2's_operand addr, BPL_operand_addr
6 <actions>
7 <actions>
8 IF_EQ ; ^ line-2's_operand addr, line_5's_operand_addr, BNE_operand_addr
9 <actions>
10 <actions>
11 END_IF ; ^ line-2's_operand addr, line_5's_operand_addr
12 END_IF ; ^ line-2's_operand addr
13 <actions>
14 <actions>
15 END_IF ; ^ empty
Note that a second assembler pass is not necessary to resolve all the branch distances.
You can nest other structure types without interfering with the IF...END_IF's, for example:
IF_<condition>
<do_stuff>
<do_stuff>
BEGIN
<actions>
<actions>
UNTIL_<condition>
<do_more_stuff>
END_IF
The other structures like this BEGIN...UNTIL are discussed on the
main page of the structure macros section of this website, and the
source code is in the STRUCMAC.ASM file; so those won't be
repeated here.
Let's look at the next step though, which is to put an ELSE_ in the IF...END_IF
structure:
CMP #14
IF_EQ ; BNE to ??
<actions>
<actions>
ELSE_ ; BRA to ??, then fill in operand for BNE 3 lines up.
<actions>
<actions>
END_IF ; Fill in operand for BRA 3 lines up.
(The underscore is put at the end of the ELSE so the assembler can differentiate it from the
ELSE which is the assembler's own conditional-assembly directive. END_IF is also made to prevent
clashing with the assembler's ENDIF or ENDI.) If you're on an NMOS 6502 without the
branch-relative-always (BRA) instruction, you'll have to use JMP. (There's a list
of the improvements of the 65c02 over the 6502 here. What the above is
to assemble is:
line# ; machine-language output of relevant lines:
1 CMP #14 ; C9 0E
2 IF_EQ ; D0 __ (BNE to line 6)
3 <actions>
4 <actions>
5 ELSE_ ; 80 __ (BRA to line 8, then fill in line 2's operand.)
6 <actions>
7 <actions>
8 END_IF ; (This line only fills in line 5's operand.)
Uh-oh, now we have a conflict at line 5. It adds the BRA instruction and puts its operand address on the stack,
then needs what's under it on the stack to fill in the operand for the BNE above it. No problem of course, with
a SWAP macro. Mine is simply:
STK_SWAP_TEMP: SETL STK_LVL_1
STK_LVL_1: SETL STK_LVL_2
STK_LVL_2: SETL STK_SWAP_TEMP
and is used by the ELSE_ macro.
The BEGIN...AGAIN, BEGIN...UNTIL, BEGIN...WHILE...REPEAT, and FOR...NEXT
structures, described in the structure macros section of this
website, are ones that branch from the end of the loop up to the top of the loop. For most of these, the earlier macro lays down no machine
code at all, only puts an address on the stack for a later branch instruction to branch up to. So take the
BEGIN...UNTIL structure for example, which loops until the specified condition is met:
BEGIN ; This line assembles nothing. Only puts the address on the stack.
<do_stuff>
<do_stuff>
UNTIL_EQ ; Assemble BNE to top, getting the addr from the assembler's stack.
And again, since it's a stack, you can nest it with other BEGIN...UNTIL's, or any other structure, like this for
example:
line#
1 BEGIN ; Only put addr on assembler stack.
2 <do_stuff>
3 <do_stuff>
4 FOR_Y 8, DOWN_TO, 0 ; LDY #8, then put addr, dir to count, & lim on assembler stack.
5 <bla bla bla>
6 <bla bla bla>
7 NEXT_Y ; DEY, BNE to line 5. Pops three cells off assembler stack.
8 <actions>
9 <actions>
10 UNTIL_BIT VIA3PA, 6, IS_LOW ; BIT VIA3PA, BVS to line 2. Pop a cell off assembler stack.
Here I sprang a couple of new ones, but I'm sure the idea is sinking in by now. UNTIL_BIT is a long macro
(which you can see in STRUCMAC.ASM), and
NEXT_Y is even longer, to check for all the various options; but here they only lay down two machine-language instructions each.
In my own programming, it has been highly unusual that a structure was so big that the relative branches would not reach. Andrew Jacobs' As65 assembler has program-structure capability built in, and it intelligently uses JMP instructions if a distance is too far for a relative branch. Even without that though, remember that having the macros does not obligate you to use them. It's not an all-or-nothing proposition. If you wish, you can still mix some more-conventional assembly in, using labels. My structure macros all use relative branches except the CASE statement which uses JMP instructions for the END_OF's to reach past lots of cases' code to get to the END_CASE.
My CASE structure is one of only two that I did not make nestable. (The other one is the 16-bit FOR...NEXT.) You can nest it with other structures, but one CASE structure cannot be nested inside another CASE structure. The reason was to prevent needing an absolutely huge stack. I may revisit this, because after I did it, I had an occasion where it would have been nice to nest them.
Compilers would make the structures in the same way. In fact, I took the idea for the assembly
structure macros from how Forth does it, and in fact I re-used most of the same names.
Forth uses "compiler security" (something I did not implement in my assembly-language structure macros) to make
sure you don't accidentally do something like:
BEGIN
...
FOR ; (Note that the "NEXT" is missing, or at least
... ; is not inside the BEGIN...UNTIL structure.)
UNTIL
or end a definition without finishing a structure—things which won't have a good outcome. You're not as likely to make this mistake in
assembly though, as it normally allows only one instruction, directive, or macro invocation per line, and good indentation practice will
automatically and immediately expose most errors of this kind. You should use appropriate vertical-alignment practices and white space in
higher-level languages too, especially since having lots of instructions on a line makes it easier to make a nesting mistake or forget to close a
structure, and there may be more than one good way to arrange code for readability.
To implement the "compiler security" (for lack of a better term, although we're mostly talking about assembly language in this stacks treatise, not compiled languages), you will make the structure-beginning macro put an additional number on the stack, and later parts check for it, and the last word of the structure remove it. So for example an IF puts a 1 on the stack after putting the address for the ELSE_ or END_IF to fill in, ELSE_ checks to make sure there's the right security number at the top of the stack (1 in this case) but does not remove it, and END_IF checks it too but removes it. BEGIN puts a 2 on the stack after putting the address for the UNTIL or AGAIN or REPEAT to branch to, FOR_X puts a 3 on, etc.. The numbers are not critical, and you can make up your own if you like. Since the right number could be there from something else by coincidence, it's not totally foolproof, but close enough.
Here's the idea, using a simple IF...END_IF:
IF_ZERO ; The assembler lays down the BNE, then puts operand addr on its own stack, followed by a 1 (or
<do_stuff> ; other chosen "compiler-security" number for IF).
<do_stuff> ; The code inside the program structure can include additional structures of any and all kinds.
END_IF ; Assembler pops TOS and gives Err msg if it's not a 1. If it is a 1, use the current addr and
; the BNE operand addr from the stack to calc the offset. Save the current address in CUR_ADR
; to come back to, then pop the above addr off the stack and go to it (with ORG), and lay down the
; offset. Finally, get back to the current addr with ORG CUR_ADR, and resume assembly from here.
If there's a mismatch, or if the stack is empty, conditional assembly encounters a line in the macro definition that issues an error
message. How user-defined error messages are issued may differ from one assembler to another. If the assembler does not
offer the option, you could set an EQUate, something like:
IF STK_DEPTH == 0 ; If there's nothing on the stack,
ZZZErr001: ; issue the error message as a label that will show in the .lst file.
ELSE ; If there is something on the stack,
IF <condition> ; see if it's the right "compiler-security" number. If it's not,
ZZZErr001: ; issue the same error message as above, indicating the problem.
ENDI
ENDI
and then in the .lst (list) file, at the end (because of the initial Z's), you can quickly see the errors, along with the addresses (assuming it
doesn't allow using the line number). The labels need to be unique. If the assembler allows labels to start after the first column
(which I wish they all would), you can indent appropriately:
IF STK_DEPTH == 0 ; If there's nothing on the stack,
ZZZErr001: ; issue the error message as a label that will show in the .lst file.
ELSE ; If there is something on the stack,
IF <condition> ; see if it's the right "compiler-security" number. If it's not,
ZZZErr001: ; issue the same error message as above, indicating the problem.
ENDI
ENDI
This would be part of any structure macro that does not start a structure, like ELSE, END_IF, UNTIL, etc..
Now, stepping up the complexity, consider the CASE structure (called switch in C),
with multiple occurrences of CASE_OF...END_OF between CASE and
END_CASE. The description and example usage is shown on the
structure-macros page; but here I'll do the insides differently
from how the source code in the structure macros section
of this website does it, in order to show the use of the assembler stack and nesting of even CASE
structures. We'll look at it without "compiler security." This is from the structure macros website section, but
you can mouse over the underlined source code parts below to get the explanation of the assembler's operation on the
particular line. "Stack" here refers to the assembler's stack, not the 6502's stack.
CASE ACCUM ; Test the accumulator against the following cases.
CASE_OF $0A ; If it has the linefeed character,
<actions> ; execute these instructions,
<actions>
END_OF ; then branch to the first instruction after END_CASE.
CASE_OF $0D ; If it has the carriage-return character,
<actions> ; execute these instructions,
<actions>
END_OF ; then branch to the first instruction after END_CASE.
CASE_OF $08 ; If it has the backspace character,
<actions> ; execute these instructions,
<actions>
END_OF ; then branch to the first instruction after END_CASE.
<actions> ; If the character is anything else, do these actions
<actions> ; to feed it to the display as display data.
END_CASE
There's more than one way to skin a cat of course. Instead of using a null terminator in the list of addresses the
END_CASE fills in, what I did in my 6502 Forth was to start an initial count of 0 in CASE on the stack, and
increment the count at every CASE_OF, then END_CASE loops, decrementing the count each
time, using and then discarding each address, until the count is 0. The count is then discarded too of course. (It also does compiler
security, which is not shown in the example above.)
related links:
"ANN: HXA0.190" teamtempest's (Anton Treuenfels') 6502.org
forum topic on program structures in his HXA 65c02/816 assembler. It was an honor that he copied my structures from my
structure macros section of this website and implemented them
in the assembler he wrote.
As65 assembler written by Andrew Jacobs (BitWise on the 6502.org
forum) has structure capabilities without the user adding macros. His even automatically chooses branch versus jump instructions to get
the code compact in most cases but still able to make the jump when the distances exceed 127 bytes.
"A sensible macro engine" (6502.org forum topic) enso proposes
and explores the idea of a macro pre-processor that could then be used with various assemblers including ones with no macro capability.
"assembler macros!" (6502.org forum topic)
"desirable assembler features" (6502.org forum topic)
"Passing a variable as an argument to a macro" (6502.org forum
topic)
16. enough stack space? <--Previous |
(Next--> 18. stack potpourri)
last updated Aug 14, 2017