34

From what I've read, the first FORTRAN compiler built a machine-code program entirely in memory; it was, in fact, designed to read the entire source code of the program, and then sequentially load pieces of the compiler that would process different parts of the source code into either machine code or other information that would be processed by later parts of the compiler.

Although the just-in-time compilers for most (all?) implementations Java and .NET directly produce machine code in memory, and although Borland's language products would produce machine code directly, it seems much more common to have compilers output assembly language instead.

While it is certainly useful to have a means of getting a human-readable dump of the compiler's output, having to feed the output of a compiler through a separate assembler program would seem like it would substantially increase build times. While targeting assembly language would make it possible for a compiler to produce output containing forward jumps, a compiler could produce output targeting a much simpler "fixup" program which would expect input of the form "output the following 56 bytes, output a two-byte fixup, output the next 127 more bytes, output another 2-byte fixup, patch the fixup 2 records back to the value 1137, then output the next 57 more bytes, etc." Processing such a fixup file would be much faster than processing an assembly-language source file, and for test builds that process could even be deferred until load time.

When did the now-ubiquitous approach of inserting an "assemble" step into code generation become commonplace, and why was it seen as worth the extra build time?

  • 4
    It's not ubiquitous. At least some compilers I used between the '90s and now compiled straight to machine code, but had an option to output instead and/or also to assembly if you wanted. I think this is actually more common these days but I'm interested in what the real experts have to say. – hippietrail May 26 at 2:24
  • 1
    @hippietrail: Perhaps ubiquitous wasn't quite the right term, but it seems a very common way of doing things. – supercat May 26 at 2:28
  • 2
    Around the time the first Java JITs appeared, I was working on a non-JIT system which compiled Java byte code to a virtual processor byte code, then to machine code, all at install time (not runtime). This is also before LLVM, but similar idea. We also had a macroised assembler for the virtual processor. javac was way, way slower than the assembler for programs with similar function (although of course the time to write the code wasn't the same). So, in some cases the answer is definitely, "what extra build time"? – Steve Jessop May 26 at 4:07
  • 3
    Of course, if you have to manually take off the tape for the compiler and thread the tape for the assembler between steps, then the runtime isn't what matters :-) – Steve Jessop May 26 at 4:09
  • 2
    GCC is the only notable compiler that compiles via assembly anymore. It not ubiquitous or even common today. – Ross Ridge May 26 at 15:07
37

why did high-level language compilers start targeting assembly language rather than machine code

Well, the answer is probably: to avoid developing a high level language to binary converter for each language.

Issuing assembler text is much easier than issuing binary directly for at least 3 reasons:

  • writing text is easier than writing binary. The compiler doesn't have to worry about the binary representation of the mnemonics or branch computation. That makes the interface of the compiler very clear: high-level language as input, low-level language text file as output.
  • the non-relocatable code is managed by the assembler, not the compiler. A binary file isn't always position independent, so there are relocation tables. Handling those relocation tables aren't trivial. Better let it be done by a single tool.
  • as you mentioned, if you suspect a compiler bug then it's better to have intermediary output with symbols than a disassembly (and disassembling a .o file usually fails on the relocated symbols, you need to disassemble the whole executable file for it to be correct)

The overhead exists, of course (must write the asm, then parse it back, in a different process), but converting assembly to binary is done in a very systematic way.

The costly bits are located in the compiler itself:

  • Optimizations (which cost a lot of CPU time when compiling) are done at source level, not at assembly level (well, optimizations are always possible at assembly level but those are micro/local optimizations, and not all assemblers do them).
  • Locating all include/header files and parsing them (when the produced assembly file is self-contained)

In terms of I/O, the assembly file is usually written on a temporary diskspace, so it can even remain in ram and never be written to disk (unless requested).

So it's a trade-off between efficiency and convenience. Once the assembler has been written, it can be used to assemble any file any compiler produces.

(Some Ada compilers like GNAT used to issue C code instead of assembly or binary file, also because it was easier)

Nowadays GNU compilers even add another stage: the compiler front-end produces an intermediary language output (known as GIMPLE) regardless of the language (Ada, C, C++, Fortran...), and the back-end produces the assembly from this GIMPLE file.

| improve this answer | |
  • 1
    If one is trying to keep the compiler output in a small temporary storage device, having it in a bloated text format would seem less useful than storing it as packed binary plus fixups. I could see a multi-phase build process with intermediate text output as perhaps being useful if one were using a direct-to-machine code assembler so combine assembly-code files (as opposed to a linker) but if there's going to be a linker step after the assembler, that would turn the assembly-code processing into a separate build step. – supercat May 26 at 2:25
  • 3
    A significant convenience of using an assembler as the target, if you're generating code directly, is that the assembler will resolve branch targets for you, thus all you need do in your code generator is have a scheme for generating unique labels. This can get tricky quite quickly — some architectures have variable length branch instructions, and others have limits on distances after which you'll have to replace the instruction with a sequence of instructions. – alastair May 26 at 9:24
  • 1
    yes, the compiler could generate branches without size, and assembler could find the best branch size (if available) or replace by an absolute jump. Apart from the jump/replacement instruction thing, this is a micro optimization. A good compiler should not transfer the risk of branch distance overflow to the assembler though. – Jean-François Fabre May 26 at 9:27
  • 4
    @another-dave "A compiler can equally easily emit 0x123456 as "OP REG,DEST""_ not necessarily true. OP reg,dest could have several different encodings depending on memory location etc., that the compiler doesn't have to worry about if the assembler takes care of it. Without an assembler it needs more intimate knowledge of the encoding, which means it needs to have similar internal code as an assembler. And if you need an assembler anyway... – Bruce Abbott May 26 at 16:49
  • 3
    @supercat I am not denying that direct compilation is faster, but that it needs more code (and more opportunity for bugs etc.), especially if different CPUs are targeted. I don't have much experience with 8086, but the 68000 assembler I use is ~20 times faster than the C compiler, so the time taken to parse the assembly source is insignificant compared to other stuff the compiler does. Quite important when coding on a retro machine where compilation may take minutes rather than seconds. – Bruce Abbott May 26 at 18:16
18

According to this answer gcc does this because of the proliferation of different object file formats: x86-64 processor alone uses ELF, PE/COFF, MachO64.

But other compilers (e.g. clang) go straight to object files without using an intermediate assemble step, so I would disagree that an assemble step is "now ubiquitous".

| improve this answer | |
  • 2
    Some compilers even emit C code (which can then be compiled to assembly code which can then be assembled....). The advantage of that of course is that you're also independent of the particular hardware architecture, and probably of the OS architecture too. – another-dave May 26 at 0:30
  • 1
    @another-dave: I know Cfront, Stroustrup's original implementation of C++, used to do that. Way back when I was into compilers I recall reading that some potential C++ optimizations were not possible via C (or much harder). I know small languages still like to target C as a "portable assembly language". When I moved from assembly to C way back when I really missed some types of instructions. One was the rotate instructions. Anyway a modest number of things are harder to do in C than asm. I'm not sure if any major languages/compilers still go via C. – hippietrail May 26 at 2:42
  • 1
    Comeau C++ compiler also targeted C, but it's abandonware now. – Steve Jessop May 26 at 3:52
  • 3
    @hippietrail: The new MJIT compiler in the YARV Ruby VM compiles to on-disk C source code and compiles it with bog standard GCC. No fancy in-memory streaming to libgcc or whatever. Literally the simplest and stupidest possible way to implement a JIT. And it is surprisingly fast. You'd think all the overhead of serializing C to disk and invoking compiler, assembler, linker, out-of-process would make it useless for JITting, but no. I'd argue that Ruby is at least somewhat major and YARV is the most popular implementation. – Jörg W Mittag May 26 at 7:47
  • 5
    @hippietrail Also keep in mind that currently we have way fewer processor architectures to deal with for general purpose computing, which makes native way easier compared to the 25+ years ago. C as a portable assembly language in many ways meant having GCC w/ ANSI C, and not the OS supplied K&R cc. And as a side note, GHC (defacto standard Haskell compiler) still can do C output, primarily to help new ports. – mpdonadio May 26 at 18:23
16

Early Unix C compilers were actually a pipeline, preprocessor | compiler | optimizer | assembler > abc.o. The optimizer was an assembly optimizer, doing things like fixing up things that the compiler took the easy way on, like subroutine entry and exit, and deciding between a short or a long jump (PDP-11s had short conditional branch instructions). Having used other OSs that required paper tape for intermediate stages, this was quite the revelation.

| improve this answer | |
  • 3
    Great profile picture. – Lars Brinkhoff May 26 at 5:55
  • 6
    The optimiser in that pipeline would these days be called a "peephole optimiser"; it's the bit that does local optimisations on the generated instructions (as if looking through a "peephole", since it can't see any significant amount of context). – alastair May 26 at 9:28
  • 4
    This may actually be a big reason why - the UNIX philosophy has always had an emphasis on combining separate programs that do their own tasks. – jpa May 26 at 11:36
  • 3
    gcc and clang is still a pipeline. Well, they can run also pipe-less, by creating temporary files. – peterh - Reinstate Monica May 26 at 20:31
8

I think that some of the existing answers are using the modern state of development ecosystems to address the state of things in the "retro" time. I don't recall using anything other than a.out format until the mid-90s, and the switch was driven by shared libraries (which I wouldn't call retro). You need to think in terms of not being able to download prebuilt binaries; if you were lucky you could download source but often times you may have had to request a QIC.

In my experience (which I will admit is skewed more toward specialized systems and less towards general computing), compilers used external assemblers and linkers because they already existed, plain and simple. Debugging was slow enough with dbx/gdb, so why risk needing to maintain your own when someone else had already done the work. It also means that working towards a fully bootstrapped compiler (ie, a compiler written in the target language), was easier since there was less to bootstrap.

From a practical standpoint, it also meant being able to work with buggy compilers (and optimizers), by being able to look at the intermediate asm and patching it. And in some cases, prototype code was worked out at a high language, asm generated, and then the asm was hand optimized for cases where you could work around language semantics or if the compiler didn't "get" what you were trying to accomplish. For example, some later gen processors with 32-bit ALUs would support 64-bit math for certain operations (maybe MC68040?) that the compiler would never output.

| improve this answer | |
  • 1
    good point, a friend of mine fixed Ada exceptions on an old compiler by patching the generated assembly with some sed script. – Jean-François Fabre May 26 at 16:59
5

Turbo Pascal was made famous specifically because it skipped the assembly step (as well as most of the linking step). In a single pass it created raw, absolute located binary code and saved a lot of time. This is one aspect that made Turbo particularly fast. Action! on the Atari was very similar.

The time was saved mostly by skipping the I/O, especially to the then glacially slow and low capacity floppy drives of the day.

Compiling to assembly removed a litany of issues from the compiler. The compiler could pretty much blindly emit opcodes and pseudo-opcodes. The assembler and linker were joined at the hip, having to work with the shared experience of managing an object file, which contained both binary code, symbols, and relocation information.

Since the assembler and linker are so closely entwined, the assembler acts as a level of abstraction between the compiler and linker. This also allows the assembler and linker to diverge and improve apart from the compiler. As object file formats evolved, the compilers had to at best make only minimal changes (to perhaps update the meta data as manifest by assembler pseudo ops). Whereas were the compilers writing object files directly, then now all of them have to be updated as the linkers et al improve.

Turbo Pascal was able to target the very simple system that is CP/M, with its absolute memory layout and not need many of problems that a linkage step solved. Turbos solution to code reuse was simply the include file (and they sold several Toolboxes of utility source code to incorporate directly in to you applications rather than precompiled binary code that could be linked).

It wasn't until Turbo Pascal 4 that Turbo actually started to involve a formal conventional link step in to the process (via the addition of Units).

Addenda for comment:

most practical programs would be small enough to be handled by a single-shot build.

Simply put "small enough" is solely dependent on the speed of the machine doing the build. Linking pre-compiled objects is faster than compiling source code. At some point, the time it takes to incrementally rebuild and link a final executable will be faster than recompiling everything, all the time. As machines got faster, the size of that program grew. But machines were not always fast.

Back in the day, Moria (a dungeon crawl "roguelike" game) was distributed on DECUS tapes in source and binary. The source was 22,000 lines of VAX Pascal. Our tiny VAX 11/730, on which we did a remarkable amount of daily work (with up to 10 users), simply could not compile that program before the universe achieved heat death (at least it felt that way). Were it built as a bunch of modules that were linked together, we might have had a chance to dabble with it. But on our machine, it wasn't practical.

However, on the authors machine, a VAX 8600 (far far bigger), it was, demonstrably, not an issue. Since it wasn't an issue, he never bothered to break the program up. If he had, then maybe (maybe) we'd have had a remote chance of being able to build and iterate and play with the source code.

You also have to consider other aspects. When doing development on a large program on a PDP-11/70, my friend and I would have 3 terminal sessions open. One to run the program, one to edit the program, and one to compile the program.

We did that simply because getting in and out of the editor was glacial due to the size of our file. When it started up, the editor (on our 1200 baud terminal...) even noted "Loading xxx.yyy slowly...", and it wasn't kidding. Even then we still had to manually page blocks in and out of active memory. It would have been awful if we had to weather reloading that editor every compile cycle. Compile time alone was bad enough if a simple typo slipped in.

I can't say whether we could have done multiple source files with incremental build and link for our program or not -- we were just college students bumbling our way through it. I don't even know if it was possible with that particular dev environment (probably, but we may not have got that far in to the back of the manual). But it just stands as an example that highlights how small the definition of "small enough" can truly be, and how fast one can outgrow the tools.

Oh, just how big WAS our program? 35K of source code.

All of these tools were built to facilitate productivity, and the domain of those tools was REALLY BAD hardware. It's amazing anything was accomplished at all in hindsight, but that's just looking backward with jaded eyes.

I ran the compile/assemble/link cycle on a C environment for the Atari 800 -- once. It was completely unusable it took so long.

I have a current Turbo Pascal project, it's around 1200 lines of code. It's in several include files. On a simulator, running a simulated 4Mhz CPU, this takes 1-2 minutes to build. But, while the CPU is simulated at 4MHz, the I/O is my "XXX Gbps" hardware, vs 2000 Bps (if we're lucky) floppy drive. It would be even slower on a "real machine", since it has to read all of the files and write the final .COM file each build, vs normal Turbo compiling a memory based program in to a memory based executable. 1-2 minutes isn't bad. Human scale, it's ok. But 10 lines per second? Nothing to brag about. But in the end I have no choice because of how TP is structured and it's feature set. This will not get any faster outside of porting to something else, and who knows at what point that would be.

It's not 20 minutes, thank heavens for that.

| improve this answer | |
  • Although the Turbo Pascal approach is limited to programs of a certain size, and using a separate linking step would make it possible to accommodate bigger programs than would otherwise be possible, most practical programs would be small enough to be handled by a single-shot build. My question is why the concept of single-shot builds had largely gone by the wayside by until Turbo Pascal came on the scene. – supercat May 26 at 18:49
  • I don't think the speed of the machine doing the build doesn't matter so much as the relative fraction of partial-build artifacts that would be usable, or the ability to hold in memory everything that's needed for each compilation pass. If your code could be partitioned into a couple of source files that don't call each other too extensively, and only one would change frequently, I think you could slash your build time by compiling one program to a CHN file with a fixed start address near the top of memory, and having the other program use BlockRead to fetch that into memory. – supercat May 27 at 15:48
  • Your CHN-file program would need to start with some inline-machine-code functions that would jump to the "real" functions, as well as some that would call back to the original. The "main" program would need to include a inline-machine-code function to patch the callbacks in the CHN file as well as to functions that would chain to those in the CHN file. A little bit of a pain to set up, and you'd have to rebuild everything if your guesses as to where things should go need to be adjusted, but otherwise you could avoid rebuilding the CHN file. – supercat May 27 at 15:52
  • The major reason for this being possible was that the editor+compiler+runtime was small enough to fit in memory with room to spare for the user. The trick with the runtime being reused from the compiler was probably the enabler for this. – Thorbjørn Ravn Andersen Jun 3 at 18:58
2

I don't know exactly when it started, but Wikipedia says:-

The first C compiler, written by Dennis Ritchie, used a recursive descent parser, incorporated specific knowledge about the PDP-11, and relied on an optional machine-specific optimizer to improve the assembly language code it generated. In contrast, Johnson's pccm was based on a yacc-generated parser and used a more general target machine model. Both compilers produced target-specific assembly language code which they then assembled to produce linkable object modules.

Most compilers are not capable of creating all the code required to produce a complete program from high level source only, so some assembly is required anyway. If you need an assembler for producing startup files and inline assembly code etc. anyway, why not use it? Or just use an existing assembler and save work on the compiler package. This becomes even more useful when the compiler needs to target different CPUs that may have similar assembly language but quite different machine codes.

Another reason for having a separate assembly phase is that it guards against the compiler producing invalid machine code. If the compiler produces the machine code directly then it is responsible for every detail of the encoding, which is easy to get wrong when nothing is checking it

I have seen some real clangers in directly compiled code for the Amiga - things like incorrect encoding that crashes later CPUs, jumps into the middle of instructions, instructions with blank register lists that are effectively no-ops, and 'junk' code that was apparently meant to be for alignment - all stuff that a good assembler would would have flagged (and much harder to fix when the machine code is produced by direct manipulation of bits by the compiler).

| improve this answer | |
  • I would expect Ritchie targeted assembly language because that's what compilers for other languages were already doing. Something like Turbo Pascal, however, doesn't need to include an assembler to use its runtime library, nor to allow user-code functions to include machine-code routines. I would guess that the evolution of object-file formats is responsible for the decision to output assembly language, rather than constantly-changing object-file formats, but that still leaves the question of why even small programs have to be processed that way. – supercat May 26 at 19:03
  • I would guess that the way mainframe computers worked made the 'pipeline' process more attractive than trying to squeeze everything into memory at the same time. Early 'desktop' computers had relatively large memory but limited storage and slow CPUs, so it made more sense to compile direct to memory. Turbo Pascal was a rather special case. It was written in assembler for 8080 and 8086 only, developed from a cassette tape based compiler for the Nascom (Z80 kit computer). – Bruce Abbott May 26 at 22:59
  • Many mainframes were tape based, and so I would think that on such systems minimizing the number of tape swaps would be desirable. If one has some jobs that support single-shot operation and some that require multiple passes, I would think the best use of computer time would be to process a tape of single-shot jobs while one transcribes card stacks for multi-pass jobs to tape, then process the multi-pass jobs tape, while transcribing single-pass jobs to tape, etc. Even if a compiler couldn't produce directly-executable code, it should be able to produce something... – supercat May 26 at 23:26
  • ...that would be easy enough to process that it could be loaded into memory and apply fix-ups to itself. If one assigns indices to all of the functions exported by a program, as well as all modules, and all functions imported within each module, it should even be practical to have a loader handle a concatenation of separately-built files. For large jobs, having to maintain indices, common sections, etc. would be a pain, but for many small jobs, the reduction in build times would be worth it. – supercat May 26 at 23:30
2

Could this be when the "middle-end" was created? ("Front-end" = lexing, parsing, analysis and "back-end" = compiling to machine code.) With the "middle-end" the idea was to have an Intermediate Representation of the code. That way you can break the process into escapulated steps, with the IR as a bridge between the two.

Then you can focus on turning your IR into platform specific code as a separate tasks, rather than something you need to think about from the beginning when examining the source code.

From "Crafting Interpreters" by Bob Nystrom

(Image from "Crafting Interpreters" by Bob Nystrom)

You can see where the IR sits in the process of going "up" and "down" the compiler mountain.

I'm no expert, this is just a guess that ASM is being used as the IR?

| improve this answer | |
0

Assembler output can help with debugging. The compiler can annotate the assembler with comments that help the programmer and the debugger relate instructions back to the higher level language statements. Some of it is simple quality-of-life stuff like giving numbers in both decimal and hexadecimal bases, right up to writing the actual high level statements in comments next to the assembly code that implements them.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.