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

Groups > comp.compilers > #1097 > unrolled thread

Best tools for writing an assembler?

Back to article view | Back to comp.compilers

Contents

  Best tools for writing an assembler? tpphysik@gmail.com - 2014-02-18 16:04 -0800
    Re: Best tools for writing an assembler? "C. Bergström" <cbergstrom@pathscale.com> - 2014-02-19 11:14 +0700
    Re: Best tools for writing an assembler? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-02-19 04:25 +0000
    Re: Best tools for writing an assembler? Ivan Godard <ivan@ootbcomp.com> - 2014-02-18 23:23 -0800
      Re: Best tools for writing an assembler? Robert A Duff <bobduff@TheWorld.com> - 2014-02-19 18:20 -0500
        Re: Best tools for writing an assembler? Sébastien Fricker <sebastien.fricker@gmail.com> - 2014-02-21 12:00 +0100
        Re: Best tools for writing an assembler? "BartC" <bc@freeuk.com> - 2014-02-22 00:28 +0000
        Re: Best tools for writing an assembler? noitalmost <noitalmost@cox.net> - 2014-02-23 11:22 -0500
          Re: Best tools for writing an assembler? Sébastien Fricker <sebastien.fricker@gmail.com> - 2014-02-24 07:32 +0100
            Re: Best tools for writing an assembler? Louis Krupp <lkrupp@pssw.com> - 2014-02-24 15:39 -0700
            Re: Best tools for writing an assembler? Ivan Godard <ivan@ootbcomp.com> - 2014-02-24 15:04 -0800
              Re: Best tools for writing an assembler? rpw3@rpw3.org (Rob Warnock) - 2014-02-25 13:00 +0000
            Re: Best tools for writing an assembler? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-02-25 04:09 +0100
          Re: Best tools for writing an assembler? "James Harris" <james.harris.1@gmail.com> - 2014-02-24 23:18 +0000
          Re: Best tools for writing an assembler? noitalmost <noitalmost@cox.net> - 2014-02-27 18:11 -0500
            Re: Best tools for writing an assembler? George Neuner <gneuner2@comcast.net> - 2014-03-01 13:09 -0500
              Re: Best tools for writing an assembler? federation2005@netzero.com - 2014-03-26 17:57 -0700
                Re: Best tools for writing an assembler? federation2005@netzero.com - 2014-04-13 12:24 -0700
    Re: Best tools for writing an assembler? Sébastien Fricker <sebastien.fricker@gmail.com> - 2014-02-19 09:59 +0100
      Re: Best tools for writing an assembler? Robert A Duff <bobduff@shell01.TheWorld.com> - 2014-02-19 18:27 -0500
    Re: Best tools for writing an assembler? Patrik Túri <tpphysik@gmail.com> - 2014-02-20 17:15 -0800
      Re: Best tools for writing an assembler? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-02-21 12:09 +0100
        Re: Best tools for writing an assembler? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-02-24 20:42 +0000
          Re: Best tools for writing an assembler? Ivan Godard <ivan@ootbcomp.com> - 2014-02-24 15:13 -0800
          Re: Best tools for writing an assembler? hu47121@usenet.kitty.sub.org (Hannah) - 2014-02-25 00:43 +0000
            Re: Best tools for writing an assembler? Walter Banks <walter@bytecraft.com> - 2014-02-27 14:14 -0500
          Re: Best tools for writing an assembler? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-02-25 04:23 +0100
      Re: Best tools for writing an assembler? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-02-24 20:35 +0000

Page 2 of 2 — ← Prev page 1 [2]

#1104

Thank you all.
About using an existing assembler -- it's like writing Machine Description
files for GCC right? Well my problem is that those stuff seemed quite complex
and would take a while to understand all syntax and options, and then define
all 'generalized' instructions.
Any good "Getting Started" guide on that with any assembler or compiler which
would make it easier to learn?
[Adapting an assembler is much easier than retargeting a compiler.
The assembler doesn't know anything about the semantics of
instructions, just what field goes where. -John]

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

#1106

Patrik Tzri schrieb:
> Thank you all.
> About using an existing assembler -- it's like writing Machine Description
> files for GCC right? Well my problem is that those stuff seemed quite complex
> and would take a while to understand all syntax and options, and then define
> all 'generalized' instructions.

Depending on your instruction set and addressing modes, it may be
simpler and more instructive to write your own assembler. During this
discussion I remembered that I wrote my first assemblers (and
disassemblers) in Forth, for all the microprocessor development
systems I had built for the then available 8 bit microprocessors. At
least Forth uses an interesting and amazingly simple approach to
generate machine code. Plus it comes with a full development system,
includes macro capabilities off the shelf, and many more goodies.

Unfortunately Forth writes the generated code directly into RAM, which
is nice for immediate debugging of the source code, or for an JIT
assembler/compiler, but nowadays assembler output most probably should
go into object files. In so far I'd suggest to use some existing
assembler, capable of writing the required object file format, and add
your instruction set to it as just another front-end. Essentially the
same as John suggests:

> Any good "Getting Started" guide on that with any assembler or compiler which
> would make it easier to learn?
> [Adapting an assembler is much easier than retargeting a compiler.
> The assembler doesn't know anything about the semantics of
> instructions, just what field goes where. -John]

This said, I cannot resist to add some more comments on the items
popping up during this discussion.

IMO the choice of the implementation language of an assembler is
unrestricted, OO capabilities are not required (but nice to have, of
course).

IMO an automated parser is overkill for an assembly language, it may
take more time to develop and debug the parser than writing one by hand.
Here it matters whether compatibility with an existing assembly language
is required, in this case a parser generator may be helpful. But when
one is free in the construction of the language, it may be a good idea
to cast your own language, easy to write/read/understand, and easy to
parse. In detail for CISC (Intel) processors I preferred to use the
Motorola assembler notation, with an operand size (.b,.w ...) appended
to the opcode, and prefixes for hex/octal/binary numbers. When you
compare the 32 bit x86 (Intel) and 64 bit (AMD?) x64 assembler
languages, you better know what I mean.

Instead it's essential to understand the philosophy behind the target
machine architecture, in order to create a table of instruction
mnemonics, opcodes and allowed operands and addressing modes. Assembling
one instruction then boils down to:
1) which instruction to encode?
2) get the operands
3) determine the best opcode for that combination, if there is a choice
4) merge the bits for these parts, checking for invalid combinations

Also the object file format deserves some studies, in detail the
possible fixups for external symbols. Every use of an external symbol
restricts the encoding of that operand, to a form that the linker or
program loader can process later. Also the debugger should be
considered, so that the symbol tables for the debugger can be generated.

Last not least an assembler should allow for kind of macros, for target
specific items like calling conventions, register preservation, and
other subroutine entry/exit code.

DoDi

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

#1112

Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:

(snip)

> Depending on your instruction set and addressing modes, it may be
> simpler and more instructive to write your own assembler. During this
> discussion I remembered that I wrote my first assemblers (and
> disassemblers) in Forth,

(snip)

> Unfortunately Forth writes the generated code directly into RAM, which

The traditional assembler makes (at least) two passes through the
program, the first to assign addresses to all the labels, and later to
generate the code using those addresses. But that was when memories
were smaller. If you just generate into memory, you can easily fixup
the addresses once they are defined. Then, at the end, write the whole
thing out to a file.

Both those cases work will if all instructions (and constants) have a
known length, even when the actual addresses aren't yet known.

There are some interesting cases where the instruction choice (and
length) depends on the size of an address, which (in the case of a
forward reference) depends on the instruction length.  If you can
avoid that, it is pretty easy.

-- glen
[Variable length instructions aren't that hard.  You start by assuming
everything will be the long form, then iterate over the code a few
times shrinking what you can.  That isn't always perfectly optimal
(which is known to be NP complete), but it's pretty close. -John]

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

#1115

On 2/24/2014 12:42 PM, glen herrmannsfeldt wrote:

<snip>


> -- glen [Variable length instructions aren't that hard.  You start by
> assuming everything will be the long form, then iterate over the code
> a few times shrinking what you can.  That isn't always perfectly
> optimal (which is known to be NP complete), but it's pretty close.
> -John]
>

Shrink is not NP, it is exact using a relaxation algorithm: track pairs
of addresses, one the smallest address assuming all unresolved are
resolved short, and one largest assuming all unresolved address are
long. Resolve long all those spreads whose shortest is longer than the
longest short; resolve short all those spreads whose longest is shorter
than than the longest short. Iterate resolution until you do a pass in
which no more were resolved. Set any remaining unresolved to short.

In practice, three iterations are always sufficient, including the final
one that resolves nothing.
[With some assumptions about chaining variable length jumps,
it really is NP-complete.  See this 1978 CACM article
http://dx.doi.org/10.1145/359460.359474 -John]

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

#1117

Hi!

glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:

Actually, our moderator wrote:

>-- glen
>[Variable length instructions aren't that hard.  You start by assuming
>everything will be the long form, then iterate over the code a few
>times shrinking what you can.  That isn't always perfectly optimal
>(which is known to be NP complete), but it's pretty close. -John]

Can't one also go the other way round: Start in the short(est) form and
lengthen as long as needed?

Hannah.
[Shrinking long versions has the advantage that the code is always valid,
even if you miss a few. -John]

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

#1121

Hannah wrote:

> Hi!
>
> glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:
>
> Actually, our moderator wrote:
>
> >[Variable length instructions aren't that hard.  You start by assuming
> >everything will be the long form, then iterate over the code a few
> >times shrinking what you can.  That isn't always perfectly optimal
> >(which is known to be NP complete), but it's pretty close. -John]
>
> Can't one also go the other way round: Start in the short(est) form and
> lengthen as long as needed?
>
> Hannah.
> [Shrinking long versions has the advantage that the code is always valid,
> even if you miss a few. -John]

One processor that we did a few years ago had three branch types
4 bit signed offset, jump within 256 byte page and unlimited jump.
(National COP8) Coded as 1,2,3 byte instructions. The page jump
caused all kinds of havoc as the code moved around as the branches
were being optimized.

It was the first processor I saw that that starting long and shrinking
the code wouldn't work cleanly.

Walter Banks
[The PDP-8 had short references to the current page or page 0,
and long indirect references.  Back in that era, we juggled code
into pages by hand. -John]

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

#1119

glen herrmannsfeldt schrieb:

> There are some interesting cases where the instruction choice (and
> length) depends on the size of an address, which (in the case of a
> forward reference) depends on the instruction length.  If you can
> avoid that, it is pretty easy.
>
> -- glen
> [Variable length instructions aren't that hard.  You start by assuming
> everything will be the long form, then iterate over the code a few
> times shrinking what you can.  That isn't always perfectly optimal
> (which is known to be NP complete), but it's pretty close. -John]

Hmm, I'd start with the *shortest* encoding, and extend whatever doesn't
fit afterwards. This avoids "deadlocks", resulting from kind of circular
references. Indeed harder is reordering parts of the code, in order to
reduce the number of long references - kind of "travelling salesman"
problem?

DoDi

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

#1111

Patrik Tzri <tpphysik@gmail.com> wrote:

> About using an existing assembler -- it's like writing Machine Description
> files for GCC right? Well my problem is that those stuff seemed quite complex
> and would take a while to understand all syntax and options, and then define
> all 'generalized' instructions.
> Any good "Getting Started" guide on that with any assembler or compiler which
> would make it easier to learn?
> [Adapting an assembler is much easier than retargeting a compiler.
> The assembler doesn't know anything about the semantics of
> instructions, just what field goes where. -John]

Some years ago, I used a system to assemble 8080, 6800, or 6809 code
using the OS/360 assembler. Each instruction is a macro, though many
call other macros to generate the appropriate addressing mode.  Once
you get the addressing modes right, the rest are very easy to write,
mostly putting in the appropriate opcode and calling the one to do the
right address mode.

In addition, there was a program to generate motorola hex files from
OS/360 object files, and another to fix up the lising file.  The usual
OS/360 assembler listing file has the generated code to the left of
each instruction. For a macro, you only see that if you have the macro
expansion shown. The fix-up program moves it up such that it is to the
left of the macro call, and then doesn't show the macro expansion (all
DC instructions).

It uses assembler arithmetic to generate little endian addresses on a
big endian system, using one byte (AL1) address constants.

Some of the assembler contentions remain, though, such as constants
still being in OS/360 format (X'1234') instead of the more traditional
intel form (01234H).  I do remember taking some existing source and,
with just a little editing, getting it to assemble. Also, the comment
and label conventions will be those for the OS/360 assembler, but that
wasn't much of a problem. (As I remember, the intel assembler uses a
colon after a label, and the OS/360 assembler doesn't want one there.)

It is very convenient in that the host assembler does all the
keeping track of forward references.

-- glen
[This is a classic and very useful hack.  The assembler for at least
one of IBM's minis, maybe the System 7, worked that way. -John]

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.compilers

csiph-web