One of the problem when coding for the 6502 is to choose whenever your variables should to go Zero Page (ZP) or to "normal" RAM (which I'll call non-ZP).

It's of course pretty simple to do it manually, but there is no guarantee that the choice made by the programmer will be optimal. What I personally typically do is that I have all my "straight" variables in ZP, and all arrays non-ZP. The only exception is array of pointers which can be more efficient if they're in ZP as I can use the ($xx,X) addressing mode but this is extremely rare.

One way to guarantee optimal allocation would be to do the following :

First note that the ZP-only instructions are :


Non-ZP only instuctions are :


The procedure for optimisation would be the following :

1) Variables declared by the user as "ZP" are always allocated to zero page. If any instruction using non-ZP only addressing is used, the instruction is used with the high byte of address set to $00
2) Variable declared by the user as "non-ZP" are never allocated to zero page. If any instruction using ZP only addressing is used with this variable, an assembling error is emmited.
3) Variables declared as automatic are automatically allocated.
On a fist pass, the assembler counts the size of the code it will emit without actually emitting anything. Every time an ambiguous instruction is used (for example "STA variable"), as the instruction takes 2 bytes if ZP and 3 if non-ZP, the difference between both possibilities is 1 byte, so 1 is added to an internal counter relative to the variable.

For the simpler version of the optimizer, if any ZP-only addressing is ever used with a automatic variable, it is immediately changed into a ZP variable, and the byte count for the non-ZP route is discarded.

The the total byte count is something like this :
#bytes = integer_constant + 3*variable_1 + 152*variable_2 + [...]

As long as there is room for variables in ZP, variables with the highest count are asigned to ZP, and once ZP is full, remaining variables are assigned to non-ZP.
Then, during a second pass, the assembler actually assemble the code, this time knowing exactly what is ZP and what is non-ZP without ambiguity.

Does any assembler does anything like this ?

The only problem I see is that this is not taking into account the branch overflow problem, as it's impossible to predict whenever a branch will overflow or not on the 1st pass.

I haven't seen one that does that, but note that you're only talking about space-optimal, not speed-optimal. An assembler like this wouldn't know that a piece of code might run millions of times more than others, but rather as it just sees it literally referenced a few times it might leave it in absolute addressing space.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

Absolutely.
Doing it speed optimal would be much much harder as it would need some kind of simulator, and eventually it'd depend on the I/O so simulating speed would not be possible.

The user is free to declare ZP variables explicitly for speed critical parts. Also, I find myself more often than not concerned about ROM space than speed, but I think it really depends on the project you're doing.

Perhaps you are imagining that assembler languages are high-level languages. They are not. They allow full control of the machine - or whatever the OS will let them have access to - but in exchange demand that the programmer pay attention to details normally ignored when using high-level languages.

That said, most assemblers for 6502 and related processors "naturally" provide (1) and (2), if by "declare" you mean something like:



Once they've been assigned addresses, those symbols will behave as (1) and (2) require without any further fuss. Plus, if they're defined this way before they're used, the assembler won't have to guess at their sizes.

You can get something like automatic variable space allocation using a macro assembler that also allows symbol re-definition. Using the peculiar syntax of an assembler I'm familiar with:



...and probably two other sets, one for word-sized allocations and one for arbitrary-size allocations taking two arguments, name and space required (or the arbitrary size set could be the base set and byte- and word-sized set just use them to do their work).

This doesn't provide everything asked for - in particular it makes no judgement about whether zero page or absolute memory is a better choice for any particular variable. But it is one way to allow any variable to be "declared" near the point where it is first used, rather than in a block of other variables far from the code that uses it.

You have a point, assembly is not high level and should never be so.

I edited out my "more complex example" because it made no sense in the 1st place.

However, I maintain that allow the user to automatically assign addresses is an interesting idea. First of all - the user is free to never use this features. Second if he uses it there is always the choice to not use it, typically to make sure the most critical variables are in ZP.

The user has still total control of what instructions are being used. He just (potentially) lacks control on whenever they'll use their ZP or non-ZP addressing variant.
If he uses any ZP-only mode, then it silently guarantees that the variables becomes assigned to ZP. It's similar to assemblers that allows to declare variables in the first place, where they are automatically assigned to addresses and you get no direct control of the addresses.

I've seen assemblers for ARM silently replace instructions by other equivalent instructions (*), so it's not worse than this. As far I know the handling of ZP/non-ZP has never been standardized between 6502 assemblers, and most of them ressort to weird tricks to do the difference. WLA-6502 which is the one I use the most requires ".w" after any non-ZP label in order to clearly state that it's not ZP. I don't remember how the other assemblers handle this.
(*)
For a simple example mov r0, #-1 will become mvn r0, #0

The two 6502 assemblers I've used (C32 and 2500AD) let you tell it where to start any given section, then for variables, you are in essence just putting down a list of labels with each line telling how much to advance the pointer. In 2500AD the directive was BLKB (assign a BLocK of Bytes, the number of bytes given in the operand); and in C32, it's DFS (DeFine Storage, working the same way). The next variable just goes down at the next available address in line. The assembler then chooses which addressing mode to use for an instruction based on where the variable label is, whether ZP or absolute. If you move a variable from ZP to say address $9800, the source code referencing it does not need to change. It will work fine, assuming you didn't want an indirect or something that's not available outside of ZP. There are tons of assemblers out there and I have not tried the others, but I expect this is pretty common. I choose which things to put in ZP based on addressing mode restrictions and on planned frequency of use, and all the rest go elsewhere.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

There is also the issue of aliasing symbol names, as perhaps by equating more than one name to the same memory address. A programmer can see that some block of memory can be re-used because of non-simultaneous use by two or more routines. So every routine that uses that block can divvy it up however it likes using names convenient for it.

It's hard to see how an assembler could recognize this possibility just by a static analysis of names in the source code.

High level languages typically don't recognize this situation directly either, but block stacked ones re-use memory all the time by expanding and contracting a run time stack frame.

Short answer: This is a variant of the halting problem.

Long answer: Imagine you have a program that handles conditions A and B based n external input. Imagine the code that handles A and B are both long and use many variables. Does the compiler allocate zero page memory to A or B or both? If the compiler allocates most of the zero page to A and B occurs 99% of the time, then zero page is wasted, and vice versa. If the compiler allocates zero page evenly to A and B, and one case occurs more frequently than the other, then ZP is wasted.

In order to do this properly, you probably need:

1) Branch hinting - so the assembler knows which code will be more frequently executed.

2) Full program variable lifetime analysis so the assembler knows which variables may be in-use at the same time so they aren't allocated to the same memory location.

3) Fairly sophisticated pointer alias analysis to disambiguate memory references.

Toshi

It's really a variant of the register allocation problem, and compiler writers have been tackling that one for years. It may need heuristics, it may not be optimal, it might have poor worst-case behaviour - but it still might be worth doing!

Cheers
Ed

Which is also part of larger compilers, not assemblers. Assemblers generally only focus on encoding individual machine instructions independently, not making broad encoding decisions about bulk instruction use across the program.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

IMHO this is not a variant of the register allocation problem. It is a separate problem.

A register allocator manages registers. This ZP allocator manages memory.
Registers differ from memory because registers do not alias, but memory can alias.

Let's say you have a register r1. If you write to any of the other registers, the contents of register r1 will not change. If you write to any location in memory, the contents of r1 will not change. The register r1 is not aliased by any other register or memory location.

If you have a pointer FOO and a memory location BAR, then FOO may alias BAR. This means that a write through the pointer FOO may change the contents of BAR even though BAR was not directly addressed.

So if you try to manage memory by using a register allocator, it violates one of the fundamental assumptions made by a register allocator, and it will generate incorrect code in some circumstances.

Another reason why a this is not a register allocation problem is: a register allocator is primarily concerned about managing the location of values, and shuffling them back and forth between registers and memory as needed.

In this case, the symbols are statically allocated in ZP (otherwise taking the address of a symbol does not work) and they are not being shuffled back and forth between memory and ZP. So this is a different problem IMHO.

Toshi

Fair point about aliasing! I still don't see that there's nothing worth tackling, although I agree of course that it's rarely if ever tackled by assemblers today, and indeed that it's a non-trivial problem.
Cheers
Ed

Hum hum...
What I was suggesting was to optimize code space, not speed.

This is considerably simpler, no simulation on assembled code, no high level stuff.

The user is free to manually assign variables to ZP for speed critical sections.

Also in 6502 system it's typical there is only 32k of ROM, so space is very much an issue, typically moreso than speed. You can have more by having funky memory mappings and/or bankswitching, but that's another topic.

Upon what do you base that generalization?

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

The Pasta assembler here on GitHub attempts to solve this problem using register colouring tricks. No idea how well it works but might be worth a look. And it's written entirely in OCaml, which is an interesting and unusual choice.