5 ms·

As another extreme, Turbo Pascal's earlier implementations had only one pass. Just straight from Pascal to binary code with some optimizations too. I wonder wha

by mojuba 7y ago

As another extreme, Turbo Pascal's earlier implementations had only one pass. Just straight from Pascal to binary code with some optimizations too. I wonder what the minimum number of passes could be by today's optimization standards. Two? Three?

ThinkBeat 7y ago
and the code it produced was fast as well. IDE, Compiler and code all really fast (back then)
soegaard 7y ago
Apropos, a web-site/book dedicated to compiler internals: http://turbopascal.org/ http://turbopascal.org/
sansnomme 7y ago
Go, V etc. all have straightforward compiler systems that produce reasonably fast code without calling into LLVM. The fact that a lot of modern day compilers don't have a built-in assemblers etc. are probably more due to laziness.
- dorfsmay 7y ago
  Laziness? Or time constraints and specialization? I see the last stage of compiling as a special skills which requires a lot of time, especially if you want to support multiple platforms. If you're thing is to create a great programming language, then your time is better spent on that rather than create a bad or ok backend supporting very few platforms.
- mojuba 7y ago
  Probably more to do with cross-CPU portability than laziness
- rickbutton 7y ago
  No one that maintains a production grade compiler is lazy. I would say that no one that maintains a compiler of any quality is lazy. Let's replace "laziness" with "carefully considered trade-offs" in this context. i.e. "The fact that a lot of modern day compilers don't have built in assemblers etc. are probably more due to carefully considered trade-offs".
Wohlf 7y ago
I have to imagine that was possible because everything was just simpler back then. Simpler hardware, simpler operating systems, lower overhead, lower expectations (i.e. security). I feel like it may have been possible to know the full spec of everything you were working on.
- codr7 7y ago
  More importantly, a simpler language. It's still perfectly possible to design languages [0] for efficient single pass compilation, but they won't look like C#, Swift or Rust. https://github.com/codr7/cidk https://github.com/codr7/cidk
  - cpeterso 7y ago
    What syntactic changes would be necessary for C++, C#, or Java style language to allow one-pass compilation?
    - skybrian 7y ago
      Usually declarations need to come before usages. (Like happens with C headers.) Or else, you need to be able to generate the output for a usage without seeing the declaration.
lboasso 7y ago
I wrote a self-hosted one pass compiler exactly to showcase Niklaus Wirth's approach to writing compilers: https://github.com/lboasso/oberonc https://github.com/lboasso/oberonc We often forget this alternative way (with its pros and cons).
- AnimalMuppet 7y ago
  I think that you need Wirth's approach to writing languages, not just compilers. I'm not sure that a one-pass C++ compiler would be easy. But Pascal (and Oberon?) were designed with that in mind. ("No forward references" is one place this shows.)
  - mntmoss 7y ago
    Another one-pass data point is Action![0] for the Atari 8-bit computers. The compiler is extremely efficient for its day and a source code release was made just a few years ago. [1] But good luck making sense of it -- besides being all 6502 assembler, the source code is tremendously complicated by the amount of codesize optimization taking place, and discussion in the AtariAge forums from the folks who got it released indicates that writing this compiler pushed the author to his very limits. It probably could have benefited from a compiler-compiler! [0] http://wiki.c2.com/?ActionLanguage http://wiki.c2.com/?ActionLanguage [1] https://sourceforge.net/projects/atari-action/ https://sourceforge.net/projects/atari-action/
phaedrus 7y ago
It seems to me that if a logic programming language with nondeterministic search and residuation were used to implement a compiler, the question of how many "passes" it has could be as moot and unimportant as counting the "number of stack frames" used in an imperative program. That is, I do not see why things could not be organized so that all the (pieces of) transformations are like actors in an actor model, and either act immediately or wait on data. In turn, whether their output is processed in another batch (layer) or immediately is just an optimization choice of the compiler compiler optimizer.
- tom_mellior 7y ago
  Can you explain what you mean by residuation here? But anyway, what you describe is maybe not entirely unlike equality saturation: https://www.cs.cornell.edu/~ross/publications/eqsat/ https://www.cs.cornell.edu/~ross/publications/eqsat/ The idea is to apply a whole bunch of optimizations in parallel, but in a non-destructive fashion. So instead of changing "x * 5" to "x << 2 + x" or whatever, you just note that both are equivalent ways of expressing the same. Then you go on applying optimizations to both variants. At some point you stop and end up with a soup that contains many many different computations that all do the same thing. Then you apply a solver once to pick out an optimal variant. The trick is to make this scale.
tom_mellior 7y ago
Depends on what you mean by optimization standards, I guess. But a bare minimum for any compiler that wants to call itself optimizing is register allocation on whole functions. For that you need to build a representation of a whole function, do liveness analysis on it, then do the actual register assignment and spill code generation. That's at least three passes.

by mojuba 7y ago

ThinkBeat 7y ago

and the code it produced was fast as well. IDE, Compiler and code all really fast (back then)

soegaard 7y ago

Apropos, a web-site/book dedicated to compiler internals: http://turbopascal.org/ http://turbopascal.org/

sansnomme 7y ago

Go, V etc. all have straightforward compiler systems that produce reasonably fast code without calling into LLVM. The fact that a lot of modern day compilers don't have a built-in assemblers etc. are probably more due to laziness.

dorfsmay 7y ago
Laziness? Or time constraints and specialization? I see the last stage of compiling as a special skills which requires a lot of time, especially if you want to support multiple platforms. If you're thing is to create a great programming language, then your time is better spent on that rather than create a bad or ok backend supporting very few platforms.
mojuba 7y ago
Probably more to do with cross-CPU portability than laziness
rickbutton 7y ago
No one that maintains a production grade compiler is lazy. I would say that no one that maintains a compiler of any quality is lazy. Let's replace "laziness" with "carefully considered trade-offs" in this context. i.e. "The fact that a lot of modern day compilers don't have built in assemblers etc. are probably more due to carefully considered trade-offs".

Wohlf 7y ago

I have to imagine that was possible because everything was just simpler back then. Simpler hardware, simpler operating systems, lower overhead, lower expectations (i.e. security). I feel like it may have been possible to know the full spec of everything you were working on.

codr7 7y ago
More importantly, a simpler language. It's still perfectly possible to design languages [0] for efficient single pass compilation, but they won't look like C#, Swift or Rust. https://github.com/codr7/cidk https://github.com/codr7/cidk
- cpeterso 7y ago
  What syntactic changes would be necessary for C++, C#, or Java style language to allow one-pass compilation?
  - skybrian 7y ago
    Usually declarations need to come before usages. (Like happens with C headers.) Or else, you need to be able to generate the output for a usage without seeing the declaration.

lboasso 7y ago

I wrote a self-hosted one pass compiler exactly to showcase Niklaus Wirth's approach to writing compilers: https://github.com/lboasso/oberonc https://github.com/lboasso/oberonc We often forget this alternative way (with its pros and cons).

AnimalMuppet 7y ago
I think that you need Wirth's approach to writing languages, not just compilers. I'm not sure that a one-pass C++ compiler would be easy. But Pascal (and Oberon?) were designed with that in mind. ("No forward references" is one place this shows.)
- mntmoss 7y ago
  Another one-pass data point is Action![0] for the Atari 8-bit computers. The compiler is extremely efficient for its day and a source code release was made just a few years ago. [1] But good luck making sense of it -- besides being all 6502 assembler, the source code is tremendously complicated by the amount of codesize optimization taking place, and discussion in the AtariAge forums from the folks who got it released indicates that writing this compiler pushed the author to his very limits. It probably could have benefited from a compiler-compiler! [0] http://wiki.c2.com/?ActionLanguage http://wiki.c2.com/?ActionLanguage [1] https://sourceforge.net/projects/atari-action/ https://sourceforge.net/projects/atari-action/

phaedrus 7y ago

It seems to me that if a logic programming language with nondeterministic search and residuation were used to implement a compiler, the question of how many "passes" it has could be as moot and unimportant as counting the "number of stack frames" used in an imperative program. That is, I do not see why things could not be organized so that all the (pieces of) transformations are like actors in an actor model, and either act immediately or wait on data. In turn, whether their output is processed in another batch (layer) or immediately is just an optimization choice of the compiler compiler optimizer.

tom_mellior 7y ago
Can you explain what you mean by residuation here? But anyway, what you describe is maybe not entirely unlike equality saturation: https://www.cs.cornell.edu/~ross/publications/eqsat/ https://www.cs.cornell.edu/~ross/publications/eqsat/ The idea is to apply a whole bunch of optimizations in parallel, but in a non-destructive fashion. So instead of changing "x * 5" to "x << 2 + x" or whatever, you just note that both are equivalent ways of expressing the same. Then you go on applying optimizations to both variants. At some point you stop and end up with a soup that contains many many different computations that all do the same thing. Then you apply a solver once to pick out an optimal variant. The trick is to make this scale.

tom_mellior 7y ago

Depends on what you mean by optimization standards, I guess. But a bare minimum for any compiler that wants to call itself optimizing is register allocation on whole functions. For that you need to build a representation of a whole function, do liveness analysis on it, then do the actual register assignment and spill code generation. That's at least three passes.