Re: High Level Assemblers vs. High Level Language Compilers

>> since C is really just a very very high level macro assembler.


I totally agree with Alfred. C is a terrible macro assembler simply
because it's macro facilities are so weak. C (and derivatives) would
be a much better language if CPP were beefed up considerably (think
Dylan rather than GCC). However, the current trend is to avoid using
macros entirely in HLLs because of "semantic issues" (i.e., macros
don't behave like functions) that tend to confuse weaker programmers.
This is a real shame because, as I noted, you could do tremendous
things (like DSELs) if C (/C++) had a much better macro processor.


Of course, anyone who thinks that C is a low-level language doesn't
really understand low-level access to the machine architectural
features. This is not a complaint about C. You can't have
portability and access to the low-level features simultaneously (e.g.,
accessing the carry flag on those processors that support it) because
low-level features aren't consistent across architectures. That's why
there will always be a need for assembly language code; sometimes you
really do need the low-level access to accomplish the job.


>From: Ketil Z Malde (ketil@ii.uib.no)
>>...yet people complain about C being hard to optimize for modern CPUs,
>>which are superscalar and do OOO scheduling and whatnot.
>>
>>Which makes me curious, what would a "very high level macro assembler"
>>for modern processors look like? Could you design a language that
>>would make a difference - i.e. be faster and more/as portable than/as
>>C?


Let me inject my example here:
HLA (the High Level Assembler) a high level assembler for the x86.
Check it out at http://webster.cs.ucr.edu.
This is a high level assembler for the x86 running under Windows and Linux.
Not portable between different CPU architectures, but it is possible to
write *pure* assembly language programs that run under Windows and
Linux with nothing more than a recompile. There is no reason this
trick won't work on other 32-bit OSes (e.g., BSD, BeOS). Since
HLA runs under Linux, porting to these other *NIX OSes shouldn't
take too long (probably a day for the compiler, written in FLEX/Bison,
and about two weeks to port the HLA Standard Library to the new OS).


>I try to answer that below. The CAS-8051 assembler (now rereleased
>at www.csd.uwm.edu/~whopkins/8051/index.html) was intended to be
>the first phase in a much more encompassing high-level assembler
>suitable for all processors. Nonetheless, it's functioned beautifully
>even in that regard ... at least for the projects I've carried out.


I will have to check this out (sorry, haven't done it yet). I've had
several requests for the past couple of years for a microcontroller
version of HLA (which is x86 only) from Webster visitors who like HLA
but need an 8051 or 68xx assembler. What you've written sounds
interesting.


>Partly on account of it, I've been able to maintain a high level
>programming language style even for assembly and the code looks
>so much like C that for 2 products I developed it was a matter of
>a week apiece of very straightforward line-by-line recoding to get
>them into C, ported to a standalone environment to a PC-based
>environment.


This has been my experience with HLA, as well. I've written hundreds
of programs ranging from a few lines to tens of thousands of lines in
HLA. The readability and maintainability of the HLA code is much
greater than the MASM code I used to write (and I was proud of how
well written my MASM code was, too).


>There were two major problems which were unresolved which blocked
>that line of development: (1) a comprehensive scheme for properly
>handling the weirdness associated with the way assemblers allow for
>references to yet-to-be-defined addresses but yet allows them to
>be used in assembler directives and expressions (a VERY nasty
>recursion issue lurks beneath this),


This problem doesn't get resolved via multi-phase assembly? Maybe I
don't understand the exact nature of the problem you are describing.


HLA v1.x is very weak in this regard. HLA is a symbolic compiler,
emitting MASM, Gas, or TASM assembly code for further processing into
object code. Certain forward references it simply will not allow.
Others it requires a "forward declaration" much like Pascal or C to
keep things on track. HLA v2.x is currently under development and
(among other things) will resolve many of these issues. However,
having said that, I would point out that there are still some forward
references that can never be resolved properly (that is, without
generating an error). Perhaps in the limited 8051 environment you
don't come across these problems, but in a multi-segmented (or
section) environment, you can't always allow the programmer to mix and
match variables in address expressions. Taking the difference of two
addresses in different segments, for example, doesn't make sense
logically. Maybe this is what you were alluding to, I don't know.
Certainly there are other issues (like optimizing displacement sizes)
that absolutely require multi-phase operation (NP-Complete in the
general case, though the degenerate situation only occurs in synthetic
examples).


> (2) a sensible macro language
>that works by pattern-matching (the problem being: "matching what?")
>and is so powerful that you can define the target processor's
>assembly language, itself, ENTIRELY through it (if you were
>so inclined).


HLA's macro facilities are quite comprehensive. I've used HLA's
macros to create several DSELs (domain specific embedded languages).
While I'm not entirely happy with HLA macro facilities yet, HLA has
one of the more powerful macro facilities around (in any language, not
just assemblers). In theory, you could write a complete compiler
using HLA's macro and compile-time language facilities (e.g., I've
written a simple expression compiler inside HLA that compiles simple
arithmetic expressions to assembly code), though the current
implementation leaves a bit to be desired with respect to performance.


For example, HLA does not support a SWITCH/CASE statement, but I've
written a macro to provide this capability (though, for performance
reasons, I will probably add the statement to HLA in v2.x). On
Webster (http://webster.cs.ucr.edu) I provide examples of macros that
implement lots of other specialized HLL-like control structures as
well, including macros for all the standard control structures (HLA,
btw, already incorporates a set of HLL-like control statements; I
provide the macros just as an example of HLA's macro facilities).


>C is not a high level macro assembler. The compiler is performing
>language translation which (among other things) means having its
>own abstract run-time model ingrained into the code (the run-time
>system) and a code-to-code mapping of control flow structures.


More importantly, you don't get to define new statements in C and you
don't have access to the low-level features of the underlying
architecture without dropping down into real assembly. OTOH, C+HLA
makes a great combination. Too bad C's macro processor isn't any
better, but don't get me started again...


>A high-level assembler, in contrast, would be more like a macro
>language whose control flow constructs direct the generation of
>binary, rather than translate INTO the binary.
>
>if (X < 16) {
> setb B; nop; nop;
>} else {
> jc Addr;
>}
>
>controls which statement is assembled, whereas a high-level
>sequence
>
>if (X < 16) Z++; else U = U->Next;
>
>IS the statement!
>
>The analogue to the "high-level" part of the assembler in C would be
>its macro preprocessor, if it had also included #while, #for,
>#switch directives in addition to #if, #else and #endif.
>
>These are two VERY DIFFERENT things! One high-level assembler
>generates code, the high level language IS the code.


If I understand you correctly (and I may not), you're suggesting that
the high level features should exist at assemble/compile time rather
than at run-time. That is, the high-level features should be an
extension of the conditional assembly directives normally provided by
an assembler? Allow me to work under that assumption.


In HLA, I differentiate these two *VERY DIFFERENT things* by referring
to them as the "compile-time language" and the "run-time language".


The compile-time language in HLA is a set of simple statements that
control the compilation of other statements in the code. This
includes statements like #if, #elseif, #else, #endif, #while,
#endwhile, #print, #error, etc. (sorry, no #for in v1.x, but it's easy
enough to synthesize with #while; I will add a #foreach compile-time
statement to HLA v2.x). Macros can be thought of as "compile-time
procedures" in the compile-time language.


The run-time language is, of course, the x86 machine instructions that
HLA emits and you run at a later time.


Knowing, of course, how to deal with the compile-time and run-time
languages in HLA raises the general issue of "compile-time" vs.
"run-time" that seems to plague so many compiler course students.


>Assemblers are code generators, whereas compilers are translators.
>
>Now to the matter at hand: what's an ideal high-level assembler?
>I'll answer that by answering what CAS was intended to look like.
>
>CAS is supposed to be a macro language which directs the generation
>of "db" statements: db generates individual byte-sized pieces of code
>into the memory image. Everything is either a "db" statement or a
>directive built out of macros or macros supplied with the particular
>port of the assembler.
>
[lots snipped]


Our definitions of a "high level assembler" definitely diverge at this
point. You're after a "reconfigurable assembler" (i.e., you want to
provide a parser generator as part of the package).


The good news is, everything you've described can be done with HLA
(admittedly, with a bit of work).


However, I'm not a member of the "semantics is everything, syntax is
nothing" crowd. Being able to specify the syntax of the instructions
is real important.


>Mnemonics may be overloaded. So, macros need to be resolved
>by pattern-matching. Another macro might look like this:
>
>define move(accum + @ (reg R), #D) { ... }
>
>which matches (for instance) to "move A + @R3, #35.


Overloaded macros is something HLA doesn't directly support, though
overloading is not necessary to do what you're trying here. HLA
supports a full set of pattern matching functions (ala SNOBOL4 or
Icon) that allow you to manipulate macro parameters, so you could
easily achieve what you're trying here. Also, take a look at the
macro facilities in Dylan; they make specifying syntax (like this)
quite easy (another feature for HLA v2.x).


>Both of these imply the need to be able to (re)name registers in the
>language and to even define the underlying register-segment
>model used by the processor. This can get hairy. For
>instance, two major register segments for the x86 could be
>defined as:
>
>_Xseg (including the registers named AX, CX, DX, BX)
>_LHseg (including the registers amed AL, CL, DL, BL, AH, CH, DH, BH)
>
>which the x86 actually treats as 2 separate address spaces with
>respect to its instruction binary coding, but whose mapping to
>the internal logical (register) address space overlaps.


OTOH, you could provide more sophisticated macro processing facilities
and use the equivalent of a compile-time SWITCH statement to select
the appropriate output.


>For the 8051, you have the "rseg" area which has 8 addresses that
>have the built-in names R0 through R7.
>
>Both of these examples illustrate that there is an extra layer of
>distinction over and above the "logical address" layer. Example:
>rseg's mapping to the logical address space is run-time defined and
>so isn't even known at assemble-time.


This is exactly the multi-segment problem I mentioned earlier.


>Or, consider the example:
>
>define jump(cseg C) {
>1:
> if (C - 1b < -0x7f || C - 1b >= 0x80) db 0x80, (C - 1b)
> else if ((C&0xf800) == (1b&0xf800)) db 0x01 | (C&0x700) >> 7, (C&0xff);
> else { db 0x02; dw C; }
>}
>
>where the anonymous label "1" is referred to by "1b".
>
>This one is particularly nasty because it shows the entanglement
>involved in calculating code addresses. The address following this
>instruction depends on which branch is used by the assembler. But the
>branch used by the assembler depends on what C and 1: are -- and C,
>itself, may be an address which follows the application of a "jump"
>instruction so that its address is only known once the size of the
>"jump" instruction is known.


You realize, of course, that you cannot statically generate optimal
displacement sizes (indeed, the general problem is NP-Complete). I'd
have to think long and hard about how you could do this, efficiently,
using only a compile-time language (i.e., without any support in the
assembler itself to optimize the displacements). Of course, you could
"brute-force" it in the compile-time language (CTL), but the CTL is
usually interpreted and this would run rather slowly in some special
cases.


>The high level assembler has to be able to find solutions to circular
>systems such as this. It need not find the OPTIMAL solution, but
>there has to be some kind of comprehensive system set up within it
>that allows assembly-time conditionals to be deferred until AFTER the
>linker resolves addresses.


Okay, I should have read ahead :-) You are pushing work off on some
other system (linker, rather than lower levels of the compiler in this
case). I'm not sure I agree with your solution. This requires a
specially written linker to process the conditionals embedded in the
object code. This works fine if you're supplying all the tools (e.g.,
in an embedded 8051 environment). In environments where others are
linking in C, Pascal, Kylix/Delphi, and other code, you're at the
mercy of the linkers that they support. So you can't always count on
this capability from the linker.


>Linking, however, is the stage that FOLLOWS assembly.
>
>There may be symbolic algebraic computation involved that the
>assembler has to do to resolve these kinds of statements. The
>underlying problem is known in the computer science as "constraint
>satisfaction".


But this need not take place at link time. An assembler can support
multi-phase operation and resolve as much of this information as
possible during assembly. Again, if you control all the tools, then
you can push some of the work down into the linker (which really is
the right place to put much of this). But, alas, most assembler
writers don't have this control over the end-users' tool sets. So we
have to live with the lowest-common denominator (typically COFF).


>Most assemblers take the easy way out of these kinds of quandries --
>at the expense of the extra documentation telling you where and when
>and how the statements are resolved in the ways they are; and when
>they can't be resolved; and also at the expense of the inclusion of
>extraneous concepts such as "first pass" and "second pass".


Those are older assemblers. Many modern assemblers outside of the
embedded space make as many passes over the source (or the parse tree
some pass generates) as necessary to completely resolve everything.


You've described a nifty scheme for an "assembler-generator" that lets
one specify the instruction set, syntax, and object code generation
all within the same source file as the actual assembler program. I'll
let John Levine pipe in with comments about meta-languages where you
define the language's syntax on the fly. However, I have a completely
different idea about what a High Level Assembler should be; I've even
written a short white paper on the subject (see
http://webster.cs.ucr.edu/Page_hla/WhatIsHLA.html) David Solomon, in
his text "Asssemblers and Loaders" also has a lot to say about "high
level assemblers." (for an abstract, see the HLA documentation at
http://webster.cs.ucr.edu/Page_hla/HLARef.html#pgfId-1035157)


Indeed, our esteemed moderator once graced these pages
with the following (excuse the paraphrase if I haven't got the
quote exact):


1999/07/11 19:36:51, the moderator wrote:


"There's no reason that assemblers have to have awful syntax. About
30 years ago I used Niklaus Wirth's PL360, which was basically a S/360
assembler with Algol syntax and a a little syntactic sugar like while
loops that turned into the obvious branches. It really was an
assembler, e.g., you had to write out your expressions with explicit
assignments of values to registers, but it was nice. Wirth used it to
write Algol W, a small fast Algol subset, which was a predecessor to
Pascal. ... -John"


I'd been working on HLA for a couple of years when this post appeared
(indeed, HLA v1.0 was released around September, just two months
later), but John concisely sums up the reason I designed and
implemented HLA in the first place. Standard x86 assembly uses a
horrible syntax, and it's quite possible to write an x86 assembler
that lets you do anything you can do with a traditional assembler
(like MASM), but do so in a readable and maintainable fashion. Of
course, I also wanted an assembler that would allow me to teach
assembly language to University students in a much more efficient
manner. Although I stopped teaching two quarters after I released HLA
v1.0, my experiences using HLA during those two quarters suggests that
HLA is a very good tool for teaching assembly language to those who
already know a HLL like C/C++, Java, or Pascal, since they can
leverage their HLL knowledge when learning assembly. Students in my
courses using HLA got much farther along in 10 weeks than the students
who used MASM in previous quarters.


Randy Hyde
[FYI, branch optimization is NP complete, but you can get close enough for
all practical purposes by making a table of branches in the first pass,
then between the first and second passes start by assuming all branches
are long form then, iteratively looking for one that can be shortened,
adjust symbols as needed, repeat until you don't find any more. Unix
assemblers have always done that. Re C's lousy macros, I agree, but if
you need better macros, use a separate prepass like m4 or a preprocessor
written in perl. Done that, too. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.