One-pass Compiler • Hacker News Board

Re: One-pass Compiler

#11

Post by wlib » Sat, May 23, 2020, 2:45 PM UTC

bogomipz wrote: post #6

The author states: >"An optimizing compiler would constant-fold our expression into a single number ahead of time." Could someone say what is meant by constant-folding here?

Say you have a simple expression within your code: 4+3*2. Rather than computing the result at run time, you can reduce (fold) that expression into 10, because it's a simple constant that only needs to be computed once.

Re: One-pass Compiler

#12

Post by azhenley » Sat, May 23, 2020, 2:49 PM UTC

I'm currently working on a 3-part blog series on writing a one-pass compiler in Python that emits C. It is quite a bit longer though because we make the lexer and parser from scratch. I started it because my students were having trouble with other tutorials because of all the jargon, theory, and libraries required.

http://web.eecs.utk.edu/~azh/blog/teenytinycompiler1.html

Re: One-pass Compiler

#13

Post by eatonphil » Sat, May 23, 2020, 2:57 PM UTC

azhenley wrote: post #12

I'm currently working on a 3-part blog series on writing a one-pass compiler in Python that emits C. It is quite a bit longer though because we make the lexer and parser from scratch. I started it because my students were having trouble with other tutorials because of all the jargon, theory, and libraries required. http://web.eecs.utk.edu/~azh/blog/teenytinycompiler1.html

I've done the same thing for the same reason but in JavaScript and compiling a lisp dialect.

https://notes.eatonphil.com/compiler-basics-lisp-to-assembly...

Re: One-pass Compiler

#14

Post by eatonphil » Sat, May 23, 2020, 2:59 PM UTC

Cool stuff! Register management is a pain to do. It's nice to be able to leave that to LLVM or treat x86 as a stack machine.

I wrote a compiler series exploring all three of these variations for a lisp dialect compiled by JavaScript.

https://notes.eatonphil.com/compiler-basics-an-x86-upgrade.h...

Re: One-pass Compiler

#15

Post by klyrs » Sat, May 23, 2020, 3:07 PM UTC

tom_mellior wrote: post #8

klyrs wrote: post #5

Earlier quoted context omitted.

> Interestingly, this restriction does not apply to goto labels, which you can use first and define later: The compiler can just emit the label as written into the assembly code and let the assembler worry about patching up the jump target. A one-pass compiler can manage this by maintaining a mapping of undefined labels to a list of goto statements that refer to them. Once the definition is located, unwind the list a…

There is no way to "fill in the jump values" if you have already emitted the goto to a place you can't modify later. Like the featured article does, emitting its code with printf. I agree that you could emit code to an intermediate buffer, fix it up later, and still call this (a slightly more relaxed version of) one-pass compilation.

Fair point... kinda feels like passing the buck, but not having that memory overhead is nice

Re: One-pass Compiler

#16

Post by AlexeyBrin » Sat, May 23, 2020, 3:14 PM UTC

Tangential - in your work in progress compiler book https://keleshev.com/compiling-to-assembly-from-scratch-the-... are you going to write yourself the lexer and parser or use Flex and Bison like in the article ?

Re: One-pass Compiler

#17

Post by ufo » Sat, May 23, 2020, 3:29 PM UTC

Lua is an example of a programming language that still uses an one-pass compiler. It keeps the implementation small, which is useful in embedded contexts. Additionally, not constructing an AST helps when parsing very large files. Lua files are sometimes used to store data, sort of like JSON.

Re: One-pass Compiler

#18

Post by stevekemp » Sat, May 23, 2020, 4:01 PM UTC

I wrote something very similar recently, also a single-pass, but with a trivial internal representation:

https://github.com/skx/math-compiler

The real difference between the compiler in the example, and mine, is that I handle floating-point operations and also explicitly use printf to show the output. (Because otherwise your return value is limited to an 8bit number.)

Re: One-pass Compiler

#19

Post by stevekemp » Sat, May 23, 2020, 4:07 PM UTC

bogomipz wrote: post #6

The author states: >"An optimizing compiler would constant-fold our expression into a single number ahead of time." Could someone say what is meant by constant-folding here?

As a concrete example I wrote a simple interpreter a while back, in golang. Operations would be compiled to a simple bytecode which would be executed at runtime. So:

     3 + 4

Would get "compiled" to:

     PUSH_INT 3
     PUSH_INT 4
     OP_PLUS

As you can imagine this was a virtual stack-machine. After a while I started folding these operations:

* If there was a "push int"

* And another "push int"

* And a maths operation.

* Then replace.

So in my case I'd first generate the naive version, then have a separate "optimise" pass which would rewrite the program:

     PUSH_INT 7
     NOP
     NOP
     NOP
     NOP

A later optimization pass would remove consecutive NOP operations. I made a brief blog-post here:

https://blog.steve.fi/adventures_optimizing_a_bytecode_based...

There were a couple of bugs found along the way, but the actual implementation of this optimization pass was pretty simple:

https://github.com/skx/evalfilter/pull/66/files

The biggest issue I had to face was that "1 + 3 => 4" is trivial, but my virtual machine only supports loading integers. So I couldn't collapse "2 * 3.3" into the constant "6.6".

Re: One-pass Compiler

#20

Post by nonsince » Sat, May 23, 2020, 5:06 PM UTC

I’ve been writing a one-pass optimising compiler for Wasm. It’s not perfect, but the code it outputs currently outperforms Cranelift's by a factor of 2-10x for many of the files in the Wasm specification testsuite.