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

Question

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?

Answer 1

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. LLVM compilers do the same, emitting IR (intermediate representation), that the back-end uses to produce assembly.

Answer 2

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".

Answer 3

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.

Answer 4

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.

Answer 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 its 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.

Answer 6

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).

Answer 7

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.

(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?

Answer 8

For the record: IBM's first Fortran compiler did not necessarily produce machine code output (it depends on how you look at it). Most of the compilation process is spent building up symbolic instructions (i.e., lines of assembly) in a table called CIT (Compiled Instruction Table). Parts of the program depend on the symbolic format; for instance, section four detects basic blocks by the presence of an operation mnemonic beginning with “T”, since such instructions designated transfers. The CIT goes through many phases of refinement during compilation.

After the CIT has been fully constructed, and all the code has been compiled, an assembler built in to the compiler is run to assemble the code. (I believe that it was possible to run the assembler on its own, separately from Fortran.)

Source: “Systems manual for 704 Fortran and 709 Fortran”, via http://www.softwarepreservation.org/projects/FORTRAN.

Answer 9

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.

Answer 10

In my case it's been the other way around - multiple executables were the way I started and then moved to direct binary generation later. I started university in 1981, and in introductory computing was taught a locally-developed version of Pascal, run interactively on an IBM Series 1 (IIRC). This was after doing porta-punch Fortran mailed to the university with a 1-2 week turnaround in secondary school (NZ terminology). So I wanted to use Pascal when employed at the university from 1985. IBM PCs were just a thing but only had 2 floppies. The MS Pascal compiler was (IIRC again) a multi-disk job, and took forever to run the various passes, using files on disk as intermediaries. I wrote a lot of utilities in assembler back then. As mentioned in an earlier answer, Turbo Pascal (3.x) was a godsend for floppy-based development.

The 8051 development environment was also a chain of individual executables. I don't remember the brand, but you could buy two different versions of the linker, the more expensive of which could generate overlays for a bank-switched ROM environment with the correct linkages back and forth. There may have been an $$$ optional optimiser pass. I think we had issues even then running out of memory when building from source and had to partition the source further.

I always understood that the separate pre-process (for C), compile, assemble, link executables were to reduce the memory footprint of both executable and working set for small memory machines. Turbo Pascal for CP/M on the MS Z80 Softcard for the Apple II made development there a lot easier, although you had less RAM than the PC could support.

I am still using an ancient version of the Renesas M32C toolchain, which has explicit executables for each step. At least we know the bugs. And when your corporate-IT-inflicted anti-virus scans each toolchain executable and build product, every time one of the hundreds of source files is compiled, it takes hours!

Answer 11

To add to other answers: Iʼve met once a statement that GCC was designed to make assembly output because of licensing problems with linking on proprietary Unix flavors (like SunOS, HP-UX, etc.) It was possible to make a free software implementation of C compiler, but then object file formats and linking algorithms were closed by OS vendors. OTOH, vendors could not close the way to use assembly sources because of wide use of assembly for highly-optimized subroutines where even their compiler optimization coped much worse, and for own goals like targeted kernel compilation. So, the way selected for GCC was to always produce assembly output and rely on local "binutils" package, whatever it was called in the target system.

Iʼll update this answer if find again the source of this statement.

Compared to GCC, most compilers avoid this approach by default but typically allow to request such output in a form suitable to feed into separate assembler. (This wasnʼt always true; for example, MS Fortran compilers Iʼve met at MS-DOS were producing a listing form which could not be fed to their assembler.) Or, LLVM has one more intermediate form - its IR... this is another story.