13
$\begingroup$

Okay, we all know the standard compiler architecture: a batch program with multiple passes for parsing, optimizing, and generating code.

Suppose you wanted to go all Turbo Pascal and implement a compiler in one pass.

What are the pros and cons of doing that? Is that even feasible in this day and age?

Note: This is not a duplicate of the question about single-pass parsers for languages that require forward declarations. That one is about parsers only; this one is about architecting a compiler without multiple passes, even for optimization and code gen.

$\endgroup$
4
  • 5
    $\begingroup$ They're faster in general. $\endgroup$
    – CPlus
    Jul 2, 2023 at 20:40
  • $\begingroup$ You might want to use the <details> tag for the unnecessary background bit, because it does make the question a bit long $\endgroup$
    – user
    Jul 2, 2023 at 20:45
  • $\begingroup$ Oh, how do you do that? Does it hide the stuff by default? $\endgroup$ Jul 2, 2023 at 20:52
  • 2
    $\begingroup$ Might be a good idea to reference your other question langdev.stackexchange.com/questions/1905/… and explain the differences between them otherwise there will be a temptation to close one as a duplicate. $\endgroup$ Jul 3, 2023 at 12:46

3 Answers 3

29
$\begingroup$

I’m going to assume this question is about ahead-of-time compilers; JIT compilers are a different story altogether. With that in mind…

The performance benefits of single-pass compilers are overstated

For starters, there is essentially no longer any benefit to implementing a single-pass compiler: they are a relic of an era in which memory was extraordinarily scarce, and compilers simply could not afford to fit the entire program in memory; this has not been true for 30 years. This is really a crucial point: single-pass compilers were developed to save on memory, not time. Fundamentally, they do all the same work as an equally-simple multi-pass compiler (modulo some marginal translation costs), they just run the whole pipeline on one statement or definition at a time rather than on entire compilation units.

Perhaps you feel that memory usage is nothing to sneeze at. After all, compilers—and especially optimizing compilers—can use quite a lot of memory, and though memory may be much cheaper than it once was, it’s still not free. But this is something of a red herring: compilers that do things that need lots of memory cannot be implemented as single-pass compilers because…

Single-pass compilers just can’t do the job

Modern compilers have features and perform analyses that require considering much more context than a single definition at a time. At least some of these features are present in essentially all modern programming languages. Let’s consider some examples (though this list is not by any means exhaustive).

Forward references

Forward references without separate forward declarations are almost universally supported by modern programming languages. There is essentially no reason to statically forbid forward references in general.

Error reporting

Parse errors and typechecking failures can be made significantly more helpful if the compiler has access to the entire module when generating them. For example, suppose the user has written a correct definition, but given it the wrong type. A naïve compiler would trust the type declaration and report several type mismatches: one at the definition and another at every use site.

However, if the compiler has access to the use sites, it could note that all the uses reflect the actual type rather than the expected one. It can therefore include a suggestion in the error message that perhaps the type signature ought to be changed.

Type inference

Different languages perform differing amounts of type inference, but some languages, like Haskell, have type inference that is quite global. In Haskell, a definition’s type is determined by both its body and all of its uses, so computing the type of a top-level definition may require typechecking all other definitions in the module.

GHC (the Haskell compiler) does break up modules into declaration groups very early in the pipeline, immediately after resolving names, based on dependency analysis between declarations (which is very cheap). This allows the definition groups to be typechecked independently, so users don’t pay a cost for this feature if they don’t use it.

Inlining

Essentially all ahead-of-time compilers worth their salt perform some very basic optimizations, even if they don’t do enough to warrant the name “optimizing compiler”. For example, most compilers will do constant folding and constant propagation, reducing constant expressions like 5 * 2 to 10. And once any optimizations are at play, a crucial part of the process is inlining.

In order to inline a function, its body must be known to the compiler while optimizing its call site. This is naturally impossible if the compiler has already processed its code and promptly unloaded it from memory. So compilers generally want to keep the definitions of functions from the same module in memory, anyway, and many even perform cross-module inlining for sufficiently small functions, which requires keeping them in memory, too.

Interprocedural analysis

More sophisticated optimizing compilers also perform a battery of optimizations that are explicitly interprocedural, which is to say they cross function boundaries. For example, a compiler might notice that a program boxes some values and passes them to a function that immediately unboxes them, in which case it could remove the unnnecessary boxing. It might also keep track of what side-effects a function performs so that it can reorder calls to it if the compiler deems that will improve performance.

These sorts of optimizations fundamentally depend on considering much more than a single function at a time. In theory, some of them could be done by analyzing each function as it is compiled and saving the results of those analyses for downstream calls (and indeed this is how some cross-module interprocedural analysis works), but even where this is possible, it would miss out on some useful optimizations. This is because these optimizers are usually iterative: they perform an analysis, use it to make some improvements, then analyze the program again, since the previous step might have uncovered new opportunities for further optimization. This iterative process benefits greatly from larger compilation units where more information is available.

Common subexpression elimination

Optimizing compilers also perform common subexpression elimination (CSE), which essentially deduplicates code. Obviously, the more code the compiler is able to consider at once, the greater likelihood that it will find duplicate occurrences of the same thing.

Multi-pass compilers are much easier to write

As the above examples hopefully demonstrate, modern compilers do a lot of things. They must handle complex languages with lots of features, they must detect misuses and mistakes and report them to users in a comprehensible fashion, and they must somehow translate the language into another (usually much simpler) one while preserving its semantics. Ultimately, compilers are written by humans, so they must be organized in a way that allows them to flexibly grow and evolve.

For this reason, modern compilers of general-purpose programming languages near-universally translate the program into some intermediate representation that is easier to work with. Optimizing compilers use several intermediate representations, each progressively lower level than the last. These intermediate representations are much smaller and more uniform languages than the ones written by humans, which dramatically cuts down on the number of cases the compiler must consider.

In theory, this approach is not incompatible with processing a single definition at a time: a compiler could each single definition through the entire pipeline before moving onto the next one. But, as alluded to in the first paragraph of this answer, this would not save anything that wouldn’t also be saved by writing a simpler compiler! Sure, it would avoid needing to store the whole compilation unit in memory at once, but even an extraordinarily inefficient AST is not going to take up much more memory to store than the text file containing its source code. The real costs come from all the work the compiler is doing.

So unless you’re either writing a compiler for an exceptionally simple language or a compiler that must, for some reason, run on embedded systems, single-pass compilers are a relic of the past. Multi-pass compilers can do much more while remaining easier to understand, easier to maintain, easier to extend, and easier to debug. They’re a nearly universal compiler technique, and for good reason.

$\endgroup$
9
  • $\begingroup$ Unfortunately, I think you still misunderstand. My compiler does have all of those passes. What it doesn't do is parse the file, build up a list of all declarations, and parse it again, solely to prevent the need to forward declarations. $\endgroup$ Jul 2, 2023 at 21:20
  • $\begingroup$ @GavinD.Howard No real compiler works by running the parser twice on the input text. Perhaps you are referring to a multi-pass parser, not a multi-pass compiler? What you’ve written sounds like a multi-pass compiler to me. $\endgroup$
    – Alexis King
    Jul 2, 2023 at 21:32
  • $\begingroup$ I do know what a multi-pass compiler is, and yes, I'm implementing one, and yes, I mean a multi-pass parser. That's what the question text says. The question is about whether someone would implement a language like C with one parser pass. C is famously multi-pass (it requires a preprocessor pass, a parser pass and all the rest), but because it requires everything to be declared before use, it can run the parser and not do an extra resolution pass on the AST. That extra resolution pass, which may not actually use the file text is what I refer to as a second parser pass. $\endgroup$ Jul 2, 2023 at 21:38
  • 2
    $\begingroup$ @GavinD.Howard if you're talking about the quirks of C and C++ specifically, there's a way to parse such languages in just one go - GLR. See Elkhound, for example. Every time there's an ambiguity you just branch and parse all possible interpretations. $\endgroup$
    – SK-logic
    Jul 3, 2023 at 9:44
  • 1
    $\begingroup$ Since the comparison is Turbo Pascal--while it was one-pass I do not believe it wrote out the code for a method until it was done. I managed to break the compiler with a big method (configuration file parser--one massive case statement.) Some resource was certainly consumed over the course of a method. $\endgroup$ Jul 3, 2023 at 21:01
2
$\begingroup$

When we wrote a single pass compiler, and we wanted to add more language features, the code got super convoluted, and we had this logical "cycle" where we had to so something before AND after something else. This basically halted the development of the language and a rewrite had to be done.

Things like syntax desugaring, type information, optimizations, inlining. Some of the steps mutate the program globally, instead of locally, which is really the downside of single pass compilers.

Another major drawback is that it's hard reusing code for a language server, which does not care to pass the entire codebase on each keystroke.

Modern compilers use a query system. Here's a link: https://ollef.github.io/blog/posts/query-based-compilers.html

I take inspiration from C# (roselyn) and rist-analyzer.

$\endgroup$
1
  • $\begingroup$ Do you mean rust-analyzer? $\endgroup$
    – mousetail
    Jul 3, 2023 at 8:24
1
$\begingroup$

You can't just decide that you want a single pass compiler. A single pass compiler must be able to read a compilation unit line by line, and compile it using the information it has gathered so far, and nothing else. Pascal was a language that could easily be processed that way.

Now if you have a language like Swift, you have absolutely zero chance to compile that with a one pass compiler, so there are no pro's and con's to discuss at all. For example, you need to parse all files, especially the standard library files, for "operator" declarations to even know that + - * / are operators, and whether they are left or right associative or neither, and what their precedence is, and without that you cannot even compile 1 + 2 * 3 because you don't even know whether it is (1 + 2) * 3 or 1 + (2 * 3) or whether it is an error because there are no binary operators + or *.

Personally, I would use a multi-pass compiler even for a language like Pascal today, where you can calmly collect information from your source files, find out things about the program structure, find out more things, after some time figure out what code you want to produce, apply simplifications and optimisations to that code and so on, and finally generate code. Note that modern multi-pass compilers will also store information from the compilation process along with the source code, so if you change one of 50 functions in a source file, there is a good chance that 49 of the functions require very little work, and only the changed one actually requires the full work.

$\endgroup$
1
  • $\begingroup$ Since this site is "Programming Language Design and Implementation", should you not assume that "What are the pros and cons of single-pass compilers?" is asked in that context? So then, can we assume that if having a single-pass compiler is important, then the question asker will design (or inherit from) a language (like Pascal) that facilitates making a single-pass compiler? Especially for the "critical code" he wants to produce? $\endgroup$ Jul 16, 2023 at 2:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .