Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1614 > unrolled thread

8-bit processor specific techniques

Back to article view | Back to comp.compilers

Contents

  8-bit processor specific techniques "lucretia9@lycos.co.uk" <laguest9000@googlemail.com> - 2015-09-27 07:30 -0700
    Re: 8-bit processor specific techniques for Ada Luke A. Guest <laguest@archeia.com> - 2015-09-27 23:04 +0100
    Re: 8-bit processor specific techniques BGB <cr88192@hotmail.com> - 2015-09-27 17:34 -0500
    Re: 8-bit processor specific techniques Walter Banks <walter@bytecraft.com> - 2015-09-28 11:04 -0400
      Re: 8-bit processor specific techniques "lucretia9@lycos.co.uk" <laguest9000@googlemail.com> - 2015-09-29 10:55 -0700
        Re: 8-bit processor specific techniques BGB <cr88192@hotmail.com> - 2015-09-29 20:06 -0500

#1614 — 8-bit processor specific techniques

Hi,

I've been looking around for anything related to compiler development for
8-bit processors. I'm looking at a couple of projects and one is a z80 based
project and one is a compiler. I am wanting to target multiple platforms with
the compiler, but I would like to generate z80 as well as 32-64-other-bit
platforms.

Is there any particular research out there that I cannot seem to find that you
know of? Is there anything specific I need to know? Should I just generate
from an SSA form, or is it just ad-hoc stuff?

Thanks,
Luke.
[There are plenty of compilers for 8 bit machines, particulary at
retrocomputing sites, but I don't recall a lot of interesting code
generation stuff.  They tend to have so few registers and be so
irregular that little of the optimization stuff intended for code
generation applies. -John]

[toc] | [next] | [standalone]

#1616 — Re: 8-bit processor specific techniques for Ada

lucretia9@lycos.co.uk <laguest9000@googlemail.com> wrote:

> [There are plenty of compilers for 8 bit machines, particulary at
> retrocomputing sites, but I don't recall a lot of interesting code
> generation stuff.  They tend to have so few registers and be so
> irregular that little of the optimization stuff intended for code
> generation applies. -John]

What I've seen seems to be ad hoc stuff with code gen going done in a pass
or two. This is fine for simple languages like pascal and c, but I'm doing
Ada, so it really needs to be fairly aggressive.

Luke
[I'd think the aggressive stuff would be largely machine independent,
figuring out what's a constant so it can do stuff at compile time
rather than in the code.  Once you've done that, adding two numbers
together or deferencing a pointer is pretty much the same in any
language. -John]

[toc] | [prev] | [next] | [standalone]

#1617

On 9/27/2015 9:30 AM, lucretia9@lycos.co.uk wrote:
> I've been looking around for anything related to compiler development for
> 8-bit processors.

...

> [There are plenty of compilers for 8 bit machines, particulary at
> retrocomputing sites, but I don't recall a lot of interesting code
> generation stuff.  They tend to have so few registers and be so
> irregular that little of the optimization stuff intended for code
> generation applies. -John]

I am not sure what the best approach is, but yeah, I have doubts how
well SSA would apply to this use-case.

a lot probably depends on the specific ISA, for example, what makes
sense for Z80 or 6502 may be rather different than for MSP430 or AVR8.


if I were to make a guess, it might make more sense for a lot of targets
to represent the code initially more as a sort of stack machine
potentially with a lot of compound operations, and then try to run a
variation of LZW over this (to build a dictionary of repeating
patterns). the dictionary would retain any sequences longer than a
certain minimum length (to offset the call/return overhead).

the assumption would be to try to make the stack-machine sufficiently
context independent that the same sequence of instructions will have the
same behavior independent of caller. this means that if stack-relative
addressing is used, the offsets of variables would be resolved in the
stack IR (so that they are also constant in the output code).

likely, a fairly minimalist register allocator would be used (if one is
used at all), and would be mostly for caching the top stack items and
maybe a few variables.

likely, the main goal is mostly to minimize code size, as IME this tends
to be a bigger factor than the execution time when it comes to small
(8/16 bit) targets. in a way, this makes it closer to a data-compression
problem than a traditional optimization problem.

typically there is also a need for handling operations via internal
function calls, as things like a hardware multiplication and multi-bit
shifts tend to be absent. for example, one may see trickery like
implementing multi-bit shifts via computed jumps into a sequence of
single-bit shifts (the ISA in question could use PC as a GPR, and
arithmetic on PC was done rather often), ...

but, granted, I haven't done much personally in this area as of yet, and
haven't really looked that much into how the existing compilers do it
(at least much beyond their ability to somehow fit around 500 lines of C
code into a 2kB ROM).

[toc] | [prev] | [next] | [standalone]

#1618

On 27/09/2015 10:30 AM, lucretia9@lycos.co.uk wrote:
> I've been looking around for anything related to compiler development for
> 8-bit processors. ...

> [There are plenty of compilers for 8 bit machines, particulary at
> retrocomputing sites, but I don't recall a lot of interesting code
> generation stuff.  They tend to have so few registers and be so
> irregular that little of the optimization stuff intended for code
> generation applies. -John]

John, you actually have identified the source for a lot of code
generation technology used in 8 bit compilers. There is a wealth of
material in some of the compilers that is used to map processors with
unusual instruction sets on to C.

Unfortunately most of this material has never been published and
hasn't been the focus of research projects. The techniques used mostly
show up in application specific ISA's. This is the type of processor
whose applications tend not to be hosted and are small enough that
compilers can be exhaustive and often have tight execution
requirements.

A couple starting places for this type of compiler. Once parsed
implement a strategy pass to map out application implementation
approachs this time. Seriously consider dispensing with linkers for
this type of compiler, their original purpose was to allow separately
compiled modules and combine them later, in this type of compiler
cross compiling a whole application is both possible and appropriate.

w..
[Agreed about the linker bit.  These days, in the tool sets for
embedded processors the object files that the compilers create are
really just an intermediate code, and the linker does a global
optimization pass over the whole program and only then generates
the machine code. -John]

[toc] | [prev] | [next] | [standalone]

#1622

On Monday, 28 September 2015 20:26:51 UTC+1, Walter Banks  wrote:

> > [There are plenty of compilers for 8 bit machines, particulary at
> > retrocomputing sites, but I don't recall a lot of interesting code
> > generation stuff.  They tend to have so few registers and be so
> > irregular that little of the optimization stuff intended for code
> > generation applies. -John]
>
> John, you actually have identified the source for a lot of code
> generation technology used in 8 bit compilers. There is a wealth of
> material in some of the compilers that is used to map processors with
> unusual instruction sets on to C.

I'll have to take a look at these compilers.

> Unfortunately most of this material has never been published and
> hasn't been the focus of research projects. The techniques used mostly
> show up in application specific ISA's. This is the type of processor
> whose applications tend not to be hosted and are small enough that
> compilers can be exhaustive and often have tight execution
> requirements.

All the documented stuff is targetting 32+ bit arches.

> A couple starting places for this type of compiler. Once parsed
> implement a strategy pass to map out application implementation
> approachs this time. Seriously consider dispensing with linkers for
> this type of compiler, their original purpose was to allow separately
> compiled modules and combine them later, in this type of compiler
> cross compiling a whole application is both possible and appropriate.
>
> w..
> [Agreed about the linker bit.  These days, in the tool sets for
> embedded processors the object files that the compilers create are
> really just an intermediate code, and the linker does a global
> optimization pass over the whole program and only then generates
> the machine code. -John]

I intend for the project to have multiple back-ends, using LLVM as one (to
start and for access to Apple OSes) and a full Ada one. I'm not sure about
just producing a final binary for 8-bit targets as there will be a system rts
library for each target and that needs to be linked. Yes, it could be just
built straight in memory. I'd have to look at it.
[Re linker, the library is just a library of intermediate code.  Pull in
the parts you need, optimize and generate the code for the whole program.
A little googlage suggests that there is or was an 8-bit back end for
Gnu GNAT, although it's hard to tell in what state it is. -John]

[toc] | [prev] | [next] | [standalone]

#1625

On 9/29/2015 12:55 PM, lucretia9@lycos.co.uk wrote:
> On Monday, 28 September 2015 20:26:51 UTC+1, Walter Banks  wrote:

>> Unfortunately most of this material has never been published and
>> hasn't been the focus of research projects. The techniques used mostly
>> show up in application specific ISA's. This is the type of processor
>> whose applications tend not to be hosted and are small enough that
>> compilers can be exhaustive and often have tight execution
>> requirements.
>
> All the documented stuff is targetting 32+ bit arches.

if you mean things like LLVM, yes.

in terms of basic techniques, these shouldn't really care all that much
what the CPU word size is.

likewise, not all 8/16-bit targets are equivalent.

older architectures (6502 or Z80 or similar) have tended towards being
rather idiosyncratic with a small number of specialized registers.

newer ones, such as MSP430 or AVR8, tend to have a more regular
instruction set and a larger number of registers (mostly GPRs with a few
special purpose registers).

for example, TAC/SSA would likely be more applicable to an MSP430 or AVR
than it would to something like a Z80 or 6502, but I could be wrong on
this front.


generally, a stack machine model can either mapped fairly directly to a
native instruction set, or internally partially or fully mapped to the
use of registers or temporaries, being able to utilize which registers
exist, and need not map to memory (the value stack could exist entirely
in CPU registers).

where TAC+SSA has an advantage is if you have more machine registers
available than intermediate values in an expression, so it might be
useful to keep things around temporarily (being able to detect and reuse
previously computed values, ...).

TAC (without SSA) is generally better suited for code-generation though
(handled naively, SSA form could risk increasing register pressure and
MOV operations with little or no gain over plain TAC).

TAC has an advantage over RPN in terms of allowing more efficient code
to be generated on common targets with a simplistic code-generator, due
to mapping a little more directly to CPU registers and making it easier
to share patterns.

though, one possibility is a model where operations are performed
between a stack and variables, ex, rather than operations like:
"$z=$x+$y;" or "$x; $y; +; =z;" we have, say, "$x; +y; =z".


RPN could be better though for irregular CISC style targets, or for
recognizing patterns.

TAC or SSA could potentially risk more "noise" which would hinder
finding repeating patterns, as an otherwise equivalent sequence of
instructions may operate on a different set of temporaries. however,
TAC+SSA could still be useful after these patterns are found.


> I intend for the project to have multiple back-ends, using LLVM as one (to
> start and for access to Apple OSes) and a full Ada one. I'm not sure about
> just producing a final binary for 8-bit targets as there will be a system rts
> library for each target and that needs to be linked. Yes, it could be just
> built straight in memory. I'd have to look at it.

I have little idea about LLVM and 8/16 targets, as personally I still
haven't really made much use of LLVM (it hasn't really tended to align
all that well with what I am doing).

I have some stuff that runs on ARM chips, but thus far it is using a
threaded-code interpreter, rather than generating native code.


> [Re linker, the library is just a library of intermediate code.  Pull in
> the parts you need, optimize and generate the code for the whole program.

yes.

conventional object-file based linking isn't really recommended for
small targets, since linking object files will try to pull in code or
data that isn't needed in the final image (C runtime libraries have
often tried to minimize this by putting each function in its own object
file), and space is at a premium on an 8/16 target. ideally, the
inclusion should be a bit more fine-grained than this.

better is only pulling in individual functions, and then try to omit any
code which is unreachable within those functions or data that isn't used
by the reachable code.


as noted before, it probably makes sense to try to eliminate repeating
patterns, in addition to avoiding any code which isn't used (such as
branches into code which wont actually be executed).

this is partly where LZ would come in. to some extent, it could be
possible to first break things into basic-blocks and potentially use
constant-propagation or similar to detect branches which would never
execute.

LZ compression could help detect patterns between functions for which it
may make sense to try to eliminate them, but this may require care in
the design of the IR (to make patterns easier to detect and utilize).

aggressive inlining and constant propagation could potentially also
increase the number of such patterns enough to outweigh the cost such
inlining would otherwise incur (though it could potentially also
backfire and make the output larger).


granted, I could be wrong on all this, as this is outside of areas for
which my existing experience applies.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web